- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
h( x) x1 x2 6 0.
f
解:
(
x
)
(2
x1,1)T ,g1(
2x1 1
x) (1,0)T
21 x2 1
, g2 0,
(
x
)
(
2
x1
,2
x2
)T
,
h1
(
x
)
(1,1)
;
K T条件为
1 22 x2 1 0,
x* （1，0）T 是 最 优 点 ， 起 作 用 约 束I ( x*) {1,3}，f ( x*) (1,0)T
g1( x*) (0,1)T , g3 ( x*) (0,1)T , 显 然 找 不 到1 , 3 0, 使 f ( x*) 1g1( x*) 5g3 ( x*)成 立 。
F(x0)= f (x0) + g (x0)=0.
若 F ( x0 , h) hT 2F ( x0 )h 0, h 0
gi ( x0; h) 0, i 1,2,, m
则x0是局部极小点。 二，具不等式约束的问题
1，下降方向和可行方向
考虑一般非线性约束优化问题：
满足：
f
(
x
)
m
i 1
1 ,m T ;
p
i gi ( x ) jhj ( x
j1
1 )
,,
0
ቤተ መጻሕፍቲ ባይዱ
p
T
i gi ( x ) 0, i 0, i 1,, m
称上式为K－T条件，满足上式的点称K－T点。
40
5
3), x~* (3 13,2)T , ~* 0, ~* 13 , ~*g( x~* ) 0, I( x~* ) .
26
例2:
g1
(
x
)
x1
min f 1 0,
(x) g2( x)
x12 x2 , x12
x
2 2
26
0,
L( x, , ) f ( x) T g( x) T h( x) 的鞍点。
定理5 ：若 ( x, , ) 是鞍点，则 x 是原问题的整体最优解，
但逆一般不成立。
例
考虑非线性规划问题：min
f (x)
x12
x
2 2
h( x) x2 0.
3 x2 ,
结论2：(Lagrange乘子规则)设(x0,y0)是局部极小点，且g (x0,y0)
0，则存在常数 ，对函数F (x0,y0)= f (x0,y0)+ g (x0,y0)，满足 F(x0,y0)= f (x0,y0) + g (x0,y0)=0.
结论3（充分条件）：设点x0满足必要条件：
相应的广义Lagrange函数为：
m
p
L( x,, ) f ( x) i gi ( x) jhj ( x)
i 1
j 1
例1：验证以下问题在最优解处K-T条件成立。
min f ( x) x1 g( x) 16 ( x1 4)2 x22 0
极小点为x*=(2,2)T，极小值为8，令
L( x1 x2 , )
x12
x
2 2
( x1
x2
4)
( ) min{x12 x22 ( x1 x2 4), x1 , x2 0}
min{ x1 0
x12
x1 }
m x2
in{
0
x
2 2
x2 }
4
因此
( )
2 4 ,当
2
4 ,当 0.
0,
对偶问题：max { 0
2
2
4 }
最优点*= 4，最大值 (*)=8。
1）对偶定理
定理1（弱对偶定理）若x 是原问题（1）的可行解， 而（，）是对偶问题（2）的可行解，则
第四章 约束非线性优化的理论与方法
一，等式约束问题
1，切向量与正规性
定义1 设x0 是由方程组gi(x)=0， i=1,2, …,m，确定的曲面 S上的一点，若在S上存在曲线x(t)，x(0)= x0，x’(0)=h，
则称向量是曲面S上点x0处的切向量。 定义2：如果关于h 的线性方程组：
系数矩阵
gi ( x0 , h)
h( x) ( x1 3)2 ( x2 2)2 13 0
解: 1),
x*
(0,0)T
, *
1
,*
0, * g( x* )
0,
I ( x* )
1;
8
2), x* (6.4,3.2)T , * 3 , * 1 , *g( x* ) 0, I( x* ) 1;
j
gi ( x0 x j
) h
j
0, i
1,2,, m
g1 ( x0 ) gm ( x0 )
x1
x1
g1 ( x0 ),gm ( x0 )
g1 ( x0 )
xn
gm ( x0 )
xn
满秩，则称x0为曲面S上的一个正规点。 注1 g1 ( x0 ),, gm ( x0 ) 是x0处法空间的一组基。 注2 方程组 gi ( x0 , h) 0, i 1,2,, m 的一组线
min f ( x)
S x gi ( x) 0, hj ( x) 0, i 1,, m; j 1,, p
例：求解 S
min f ( x) x12 x22 x x1 x2 1 0,1 x1 0,1 x2 0
1) 下降方向的选择
1( x1 1) 0, 2 (26 x12 x22 ) 0,
12
2.2 0.1或
1 0 2 3 8
1 0 1 11 4
x* (1,5)T f ( x*) 4
1 0, 2 0.
定理3 设x*是一个可行点，若存在使K-T条件成立，并且对应
(1)
min f (x) x h(x) 0, g(x) 0
题对偶问(2)
(
,
)
max (, ) min L( x,,
x
),
0
例 考虑问题
min
f ( x)
x12
x
2 2
,
h( x ) x1 x2 4 0, x1 , x2 0.
0
结论1：若 x0 S 所有方向P都是可行的。
结论2：若 x0 S 当 PTgi (x0) 0,i I(x0) {i gi (x0) 0} 时
则P为可行方向。
记 G0 {P T gi ( x0 ) P 0, i I ( x0 )} 为可行方
向集。
注：对等式约束而言，所有约束都是起作用约束。
i 1
( k 1) max{0, ( k ) L( x ( k ) , ( k ) )}
其中为某个取定的步长，迭代过程中逐步缩小，每次迭代需
计算两迭代点之间的距离，如距离减小 被接受，否则缩小，
最后当两点距离充分小时，迭代终止。
4，对偶问题
原问题：x S
i 1
的一个可行点,并且前t个约束为起作用约束,则x*为最
优解的一个必要条件是下式成立:
t
f ( x*)
iai , i 0
i 1
例:考虑问题
g1
(
x
)
min f （1
(x) x1）3
x1 , x2
0,
g2( x) x1 0, g3 ( x) x2 0
注 可验证x*=(0,0)T是问题的极小点(在x*是处，取* =－3，则
K-T条件成立)。
下证其Lagrange函数 L( x, , ) x12 x22 3 x2 x2
没有鞍点。
反证法 ，假设鞍点 ( x, ) 存在，由定理5知， x 必为问题的
最优解，故 x x* (0,0)T , 由鞍点定义，对所有的x与， 有
定理4： 凸规划问题的可行K-T点必为最优解。
3，Lagrange函数的鞍点
定义1：如果对 x Rn , ( 0) Rm , R p
有 L( x, , ) L( x, , ) L( x, , )
则称点 ( x, , ) 是Lagrange函数：
从上例看出，满足定理1还需增加一些约束规范，如梯度向量
线性无关等，上例有 g1 ( x*) g3 ( x*)
更一般的有：
定理2（Kuhn－Tucker）最优性必要条件：
在最优点x*处，设 gi ( x ),i I( x );hj ( x ), j 1,, p
线性无关，则存在
2，最优性条件
定义1：若对xC和0，有 xC ，则称C为锥，如果C是
凸的，则称其为凸锥。
定义2：设是约束集，称 D {P P 0, x0 P S, 0,
