什么是K-T点

第 1 页 共 25 页 第三讲 非线性规划

§4约束极值问题(1)

问题 min(),{|()0,1,}jfXRXgXjl <1>

思路:有约束无约束; 非线性线性; 复杂简;

一、最优性条件

1. 可行下降方向(有用约束,可行方向,下降方向)

(1) 有用(效)约束

设<1>式的(),()jfXgX有一阶连续偏导

设(0)X是一个可行解, 下一步考察时，要讨论约束. 第 2 页 共 25 页 分析: 应有(0)(0)(0)()0()0()0jjjgXgXgX

若(0)()0jgX,

则在(0)()UX内,

有()0jgX,

此时各个方向均可选.

若(0)()0jgX,

则(0)X()0jgX形成的边界, 影响下一步选向. 1x2x{()0}RXgX()fX()0jgX(0)X第 3 页 共 25 页 故称()0jgX是(0)X点的有效约束.

(2) 可行方向(对可行域来说)

设(0)X为可行点, P为某方向,

若存在00, 使得(0)0,[0,]XPR

则称P是(0)X点的一个可行方向.

(a) 可行方向P与有效约束(0)()0jgX的梯度(0)()jgX关系是:

(0)()0TjgXP.

记有效约束下标集 第 4 页 共 25 页 (0){|()0,1}jJjgXjl

若P为(0)X的可行方向, 则

存在00, 使得当0[0,],有

(0)(0)()()0,jjgXPgXjJ

从而

(0)(0)0d()()0,djTjgXPgXPjJ

见下图.

第 5 页 共 25 页

(b)反之,

若(0)()0TjgXP, 则P必为可行方向.

(0)(0)(0)()()()()TjjjgXPgXgXPo<1>对有效约束(0)()0jgX,只要充分小,得(0)1()0gX(0)2()0gX(0)2()gX(0)1()gXP(0)X第 6 页 共 25 页 (0)()0jgXP, 所以P是可行方向;

<2>对无效约束(0)()0jgX,同样只要充分小,

就有(0)()0jgXP,故P也是可行方向;

事实上, 对无效(0)()0jgX,P都是可行方向.

(3) 下降方向(对目标函数来说)

设(0)XR, 对某P方向, 若在00[0,],0内, 有

(0)(0)()()fXPfX 第 7 页 共 25 页 则称P是一个下降方向.

下降方向判定:

若(0)()0TfXP,则P是(0)X的一个下降方向.

因为(0)()()fXfXP

(0)(0)()()()TfXfXPo,

只要充分小, 都有(0)()()fXfX.

(4) 可行下降方向

若(0)XR的某方向P是 可行方向+下降方向,

则称P是(0)X的可行下降方向. 第 8 页 共 25 页 即 存在00,当0[0,]时,有

(0)()0jgXP且(0)(0)()()fXPfX,

是继续寻优方向.

讨论: (0)X非极小值点存在可行下降方向P;

(0)X极小值点  无可行下降方向P;

(可行但不下降,或下降不可行)

第 9 页 共 25 页 定理(局部极(最)小必要条件)

设X是min(),{()0}ifXXgX局部极小点,

(),(),jfXgXjJ(有效约束下标集)在X处可微, (),jgXjJ在X处连续,

则在X处无可行下降方向P,即不存在P, 使

**()0,,()0,TjTgXPjJfXP (**)

证 否则由(**)及前面的分析, 可找出可行下降点

X非局部极小值点矛盾. 第 10 页 共 25 页 如图

所示

问题:min(),{|()0,1,}jfXRXgXjl <1>

2. 库恩—塔克条件(局部最小的必要条件)

是非线性规划中最重要成果之一

(1) Gordan引理(不加证明)

设12,,...,lAAA是l个n维向量, 则 1x2x()fX()fX1()gX第 11 页 共 25 页 P,使0,1,2,...,TjAPjl

0j,不全为零, 使10ljjjA.

(不指向同侧的向量, 正组合为零)(如l=3,n=2)

若同侧, 则有P(图a), 否则无P(图b),但可正组为0.

3A1A2APH()a3A1A2APH()b第 12 页 共 25 页 (2) Fritz John 定理

设X是<1>极小值点, ()fX和()jgX有一阶连续偏导数, 则存在不全为零的01,,...,l, 使

01()()0()0,1,2,...,0,1,2,...,ljjjjjjfXgXgXjljl

证明 因X是问题<1>的解, 故由定理4, 不存在

可行下降方向P, 使 第 13 页 共 25 页 ()0()0,TTjfXPgXPjJ

由Gordan引理,存在不全为零非负数0,,jjJ使

0()()0jjjJfXgX

对无效约束jJ, 令0j, 则()0jjgX

从而有(对所有l) 第 14 页 共 25 页 01()()0ljjjfXgX

且有 ()0,0,1,2,.jjjgXjl, 证毕.

注1: 类似于条件极值的必要条件.

注2 若00,则有效约束的()jgX正线性相关

同侧有可行下降方向X非极值点.

故一般设()jgX线性无关00.

以上条件称为 Fritz John条件, *X称为Fritz John点. 第 15 页 共 25 页 (3) 必要条件 (库恩-塔克条件)

设X是<1>极小值点, ()fX和()jgX有一阶连续偏导,且有效约束梯度线性无关,则1,...,l, 使

1()()0()0,1,2,...,0,1,2,...,ljjjjjjfXgXgXjljl<2>

证明 由Fritz John引理, ()jgXjJ线性无关 第 16 页 共 25 页 得00, 作00/0j, 即得<2>.

式<2>=库恩-塔克条件. 相应点=库恩-塔克点.

简称K-T条件, K-T点.

对一般非线性规划

min(),()0,1,()0,1,ijfXhXimgXjl min(),()0,()0,1,()0,1,iijfXhXhXimgXjl<3>

它的K-T条件如下

设X是<3>极小值点, 相应函数有一阶连续偏导,第 17 页 共 25 页 且有效约束的()ihX和(),jgXjJ线性无关,则12(,,...,)Tm和1(,...,)TlM,

使

11()()()0()0,1,2,...,0,1,2,...,mliijjijjjjfXhXgXgXjljl<4>

其中12,,...,m,1,...,l称为广义Lagrange乘子.

注1 对凸规划, K-T条件也是充分的. 第 18 页 共 25 页 设kX为某可行解,

若kX是极小点,

且1()0kgX,

和2()0kgX,

则()()kfX必与,

1()kgX和2()kgX同侧, 否则有可行下降方向.

由1()kgX和2()kgX线性无关

1122()()()kkfXgXgX

即 1x2x()kfX()fX1()0kgX2()0kgX2()kgX1()kgX第 19 页 共 25 页 1122()()()0kkfXgXgX

例10 用库恩-塔克条件解非线性规划

2max()(4)16fxxx. 1()gX()kX()()kfX86()1()0kgX()2()0kgX2()gXR164第 20 页 共 25 页 解 变为 212min()(4)()10()60fxxgxxgxx,

12()2(4),()1,()1fxxgxgx,

引入广义拉格朗日乘子12,, 则有

所以1212122(4)0(1)0(6)0,0xxx, 具体分析如下. 第 21 页 共 25 页 若120,0,引出矛盾, 无解;

若120,0:1x,点; ()9fx(16)

若120,0:4x,()0fx;

若120,0:6x,()4fx(24)

所以最大值点1x, 最大值()9fx.

注: 2()(4)fxx非凸函数,

在[1,6]上有两个局部最小值点.

还有一个”驻点” 164第 22 页 共 25 页 附加例题(略)用K-T条件解非线性规划

2min()(3)05fxxx.

解 212min()(3),()0,()50fxxgxxgxx,(是凸规划)

12()2(3),()1,()1fxxgxgx,