理论部分约束最优性条件等式约束问题
1m in nRxxf?
lEixcst i?,2,10,
一阶必要条件定理 1:若 (1)*x 是等式约束问题的局部最优解;
(2)xf 与lixc i?,2,1? 在 *x 的某邻域内连续可微;
(3)lixc i?,2,1 线性无关;
则存在一组不全为零的实数 **
2*1,,l
使得:
0*
1
**
xcxf
l
i
ii?
二阶充分条件定理 2:对等式约束问题,若:
(1)xf 与lixc i1 是二阶连续 可微函数;
(2) nRx * 与 lR?*? 使, ;0,**xL
(3) nRs 且,0?s 且 lixcs
iT?,2,1,0*
均有 0,**2 sxLs
xxT?
则 *x 是等式约束问题的严格局部极小点.
不等式约束问题
2m in nRxxf?
mixcst i?,2,10,
定义 1:有效约束,若 (2)中的一个可行点 x 使得某个不等式约束 0?xc
j
变成等式,即,0?xc
j
则 0?xc
j
称为关于 x 的有效约束.
非有效约束,若对,0?xc k 则 0?xc k 称为关于 x 的非有效约束.
有效集,0 xcixII
i
定义 2:锥,nR 的子集,如果它关于正的数乘运算是封闭的,如果锥也是凸集,则称为 凸锥,
凸锥 关于加法和正的数乘运算是封闭的.
定理 3:在 (2)中,假设:
(1) *x 为 (2)的局部最优解且
;mixciI i 1,0**
(2)xf 与*Iixc
i?
在 *x 点可微;
(3)*\ IIixc
i? 在 *x 点连续;
则0* dxfRdS Tn
与**,0 IidxcRdG T
i
n
交为空.
例 1,确定:

0,
01223
042.
26m in
21
21
21
2
2
2
1



xx
xx
xxts
xxxf
在点Tx 3,2? 处的可行下降方向,
解,Tx 3,22,1?xI





2
3
2
1
21 xcxc






2
8
42
122
2
1 xf
x
xxf
设Tddd
21,?
01 xcd T 02 21 dd
02 xcd T 023 21 dd
0 xfd T 028 21 dd
一阶必要条件定理 4:(Fritz-John一阶必要条件 )(1948)
设 *x 为问题 (2)的局部最优解且xcxf i,
mi1 在 *x 点可微,则存在非零向量
**1*0*,,,m 使得:
0
1
****
0
m
i
ii xcxf
mixc ii,,2,10**
mii,,2,1,00*
例 2,验证是否满足 Fritz-John条件:


0,
0,.
,m in
2212
2
3
1211
121


xxxc
xxxxcts
xxxf
验证Tx 0,0*? 处 Fritz-John条件是否成立?
解,2,1*?ITxf 0,1*
Txc 1,0*1Txc 1,0*2
取 00 *
2*1*0
总有 0*
2*2*1*1**0 xcxcxf
成立一阶必要条件定理 5:(Kuhn-Tucker一阶必要条件 )(1951)
设 *x 为问题 (2)的局部最优解,;0** xciI
i
xcxf i,mi1 在 *x 点可微,对于 *Ii?
的*xc
i?
线性无关,则存在非零向量
**1*,,m 使得:
0
1
***
m
i
ii xcxf?
mixc ii,,2,10**
mii,,2,10*
例 3,验证是否满足 Kuhn-Tucker条件:


0,
0,.
,m in
2212
2
3
1211
121


xxxc
xxxxcts
xxxf
验证Tx 0,0*? 处 kuhn-Tucker条件是否成立?
解,对T
21,
01
21
*
22
*
11
*?




xcxcxf
所以Tx 0,0*? 不是 KT点.
原因是*2*1,xcxc 线性相关.
一般约束问题
3m in nRxxf?
lEixcst i?,2,10,
mlIixc i,,10
一阶必要条件定理 6:(Kuhn-Tucker一阶必要条件 )
设 *x 为问题 (3)的局部最优解, ;,0** IixciI
i
xcxf i,mi1 在 *x 点可微,对于 *IEi
的*xc
i?
线性无关,则存在非零向量
**1*,,m 使得:
0
1
***
m
i
ii xcxf?
0**?xc ii?
0*?i?
Ii?
例 4,验证是否满足 Kuhn-Tucker条件:





0
0
0
0
03.
23m in
35
24
13
212
2
3
2
2
2
11
2
3
2
2
2
1






xxc
xxc
xxc
xxxc
xxxxcts
xxxxf
试验证最优点Tx 1,1,1*? 为 KT点.
013xxc
解,2,1*?ITxf 4,2,6*
Txc 2,2,2*1Txc 0,1,1*2


0
0
0
0
1
1
2
2
2
4
2
6
21
所以 2,2 21
即,*2*1* 22 xcxcxf
0*22?xc? 02
所以,*x 是 KT点.
二阶必要条件定理 7:设 *x 是 (3)的最优解且函数xf 与
mixc i1 是二阶连续 可微函数,又设约束规范条件在点 *x 成立,从而存在 *? 使
KT条件成立,如果严格互补松弛条件在 *x
成立,则, 0,**2 sxLs
xxT?
对一切满足**,,2,1,0 xIimixcs
iT
的方向 s 均成立.
二阶充分条件定理 8:设 (3)的函数xf 与mixc i1
是二阶连续 可微函数,又设 约束规范条件在点
*x 成立,若存在 *? 使 KT条件成立.
如果严格互补松弛条件在 *x 成立,且对所有满足**,,2,1,0 xIimixcs iT
的非零向量 s 有:
0,**2 sxLs xxT?
则 *x 是问题 (3)的一个严格局部最优解.