- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
--11
0
-1 0 11
x
y
2、一般约束非线性规划的最优性条件
（1）两个不等式约束的情形：（以三元函数为例）
min f ( x1, x2 , x3 ) s.t. g1( x1, x2 , x3 ) 0
g2 ( x1 , x2 , x3 ) 0
其中 f, g1, g2 均为可微函数。
g1(x)=0 x*
结合 2* 0 ，可统一写作
i* 0, i 1, 2.
(3)
总之，两个不等式约束的非线性规划问题
min f ( x1, x2 , x3 ) s.t. g1( x1, x2 , x3 ) 0
g2 ( x1 , x2 , x3 ) 0 的最优解应满足的条件为
f ( x* ) 1* g1( x* ) 2* g2 ( x* ) 0
(1)
i* gi ( x1* , x2* , x3* ) 0, i 1, 2.
(2)
i* 0, i 1, 2.
(3)
gi ( x1* , x2* , x3* ) 0, i 1, 2.
(4)
（2）一般的约束非线性规划问题
min f ( x) s.t. hj ( x) 0, j 1, 2, , l,
2 y1 )
0
L y1
2(
y1
y2 )
1(2 x1
6 y1 )
0
L z1
2( z1
z2 )
41
0,
L x2
2( x1
x2 )
2
0,
L y2
2( y1 y2 ) 2 0,
L z2
2(z1 z2 ) 42 0,
L x2
1 21 x2
2
0,
2( x1 x2 1) 0,
1 0,
x12 x22 9 0,
2 0,
x1 x2 1 0.
解的可能情形：
(1) 1 0, 2 0; (2) 1 0, x1 x2 1 0;
h2( x1, y1, z1, x2 , y2 , z2 ) x2 y2 4z2 1 0
续解： ②利用最优性条件求解
L( x1, y1, z1, x2 , y2 , z2 , 1, 2 ) f 1h1 2h2
L x1
2( x1
x2 )
1(6 x1
* j
hj
(
x*
)
0
j1
hj ( x) 0, j 1, 2, , l
例4.1 求曲面 4z 3x2 2xy 3 y2 到平面 x y 4z 1 的 最短距离。
解：①建立数学模型 设点 A( x1, y1, z1 ) 在曲面上变化，点 B( x2 , y2 , z2 ) 在平面 上变化，A、B间的距离为S，则
g2 ( x) x1 x2 1 0 解：构造Lagrange函数
L( x1, x2 , 1, 2 ) x12 x2 1( x12 x22 9) 2( x1 x2 1)
令
L x1
2 x1
21 x1
2
0,
1( x12 x22 9) 0,
若f, h1, h2, …, hl 均可微，且h1( x* ), h2( x* ), , hl ( x* ) 线性无关，则 x* 是最优解的必要条件为：存在 Lagrange乘子 (1* , 2* , , l* )T , 使得
l
x L( x* , * ) f ( x* )
s.t. x1 x2 1 0, 1 x1 0, 1 x2 0.
最优解x*为 ( 1 , 1 )T ,
22
最优值为
1 .
2
x2
1
S
x*
O
1
x1
x12 x12xx2212x22 12x221 2
• 单纯形法? 最优解不一定在顶点。
• 无约束问题的迭代法？ * 最速下降方向：
(1)
另外， g1( x1* , x2* , x3* ) 0 和 2* 0 也可统一写为
i* gi ( x1* , x2* , x3* ) 0, i 1, 2.
(2)
f ( x* ) 1*g1( x* )
f ( x* ) 和g1( x* ) 共线
由于x*是目标函数的最小点，故p是 使 f(x)增加的方向；又p指向 g1(x) 的
多元函数 求条件极值
“拉格朗日乘数法”
Lagrange乘数法：
构造Lagrange函数
def
L( x, ) f ( x) h( x)
其中μ称为Lagrange乘子。
f(x)的极值点必满足
x
L
f
(
x)
h(
x)
0
L
h(
x)
0
（2）多个等式的约束问题
其中 I( x* ) {i | gi ( x* ) 0约} 不束称要条为忘件x记哟* ！的有效约束指标集。 满足K-T条件的可行点称为K-hTj (点x) 。 0, j 1, 2, , l,
gi ( x) 0, i 1, 2, , m,
例4.2 求以下非线性规划的K-T点。
min f ( x) x12 x2 s.t. g1( x) x12 x22 9 0
2
s.t. Ax b,
x 0,
其中 H 是 n 阶对称半正定矩阵，c 是 n 维列向量， A 是 m×n 矩阵，b 是 m 维列向量。
不失一般性地，本节讨论第 (3) 种形式的求解。
最优解的必要条件为：存在拉格朗日乘子 *和 *，使得
m
l
x L( x* , * , * ) f ( x* )
i* gi ( x* )
* j
hj
(
x
*
)
0,
i 1
j1
i* gi ( x*) 0, i 1, 2, , m,
i* 0, i 1, 2, , m,
S ( x1 x2 )2 ( y1 y2 )2 (z1 z2 )2
目标函数简化后的数学模型为 min S 2 f ( x1, y1, z1, x2 , y2 , z2 ) ( x1 x2 )2 ( y1 y2 )2 (z1 z2 )2 s.t. h1( x1, y1, z1, x2 , y2 , z2 ) 3x12 2x1 y1 3 y12 4z1 0
(0)
(0)
d (1)
O
1 x1
求解约束非线性规划问题的一般思路： • 用线性函数近似非线性函数 • 构造具有下降 可行 方向的迭代算法 • 将问题转化为无约束 非线性规划问题
§4.1 最优性条件
1、等式约束极小的最优性条件 （1）仅有一个约束方程的情形：
min f ( x) s.t. h( x) 0 其中 f, h 均为可微函数。
g1(x)=0 p x*
内部，故p也是使 g1(x) 增加的方向。
g1(x) 增加的方向必为 f(x) 增加的方向。 g2(x)=0
又f ( x* ) 和 g1( x* ) 都分别指向函数值 f(x) 和 g1(x) 增 加的方向，因此，f ( x* ) 和g1( x* ) 不仅共线而且共向。 故有 1* 0.
min f ( x)
s.t. hj ( x) 0, j 1, 2, , l
其中f, hj均可微，构造Lagrange函数
def
l
L( x, ) f ( x) T h( x) f ( x) jhj ( x)
j1
(1 , 2 , , l )T为Lagrange乘子，
g2 ( x) x1 x2 1 0
x2
x12 x22 9
3
注意：实际应用中，很 难验证所得的点是否为 所求问题的最优解，若 能验证是K-T点，就把KT点作为最优点。
作业
x12 x2 a
O (0, a) x*
3 x1 P101: 1(2), 4(2)
x1 x2 1
gi ( x) 0, i 1, 2, , m, x n
构造Lagrange函数：
def
m
l
L( x, , ) f ( x) i gi ( x) jhj ( x)
i 1
j1
定理4.2 （Kuhn-Tucher条件，K-T条件）
对于一般的约束非线性规划问题，若f, gi, hj 均可微， 且 gi (x*), i I(x*),hj (x*), j 1, , l 线性无关，则x*是
min f ( x) x12 x22 s.t. x1 x2 1 0,
1 x1 0, 1 x2 0.
x2 1
d (k) f ( x(k) ) (2 x1(k) , 2 x2(k) )T
在 x(1) 处无可行方向 * 步长
S
x d x x * (1)
h( x) (h1( x), h2 ( x), , hl ( x))T , x n .
f (x)的极值点必满足
x
L
பைடு நூலகம்
f
(
