《约束条件极值1》由会员分享，可在线阅读，更多相关《约束条件极值1（28页珍藏版）》请在金锄头文库上搜索。
1、第三讲非线性规划4约束极值问题(1)问题Jmin f (X),tR =X 1 gj(X)、0,j思路:有约束T无约束；非线性T线性；复杂T简；一、最优性条件1.可行下降方向(有用约束，可行方向，下降方向)(1)有用(效)约束设1式的f (X),g .(X)有一阶连续偏导j设X (0)是一个可行解，下一步考察时，要讨论约束分析：应有 g ( X (0) 0 Tgj ( X ) 0 jI g (X(0)二 0若 g (X(0)0,j则在U(X(0) 内,有 g(X)0,此时各个方向均可选.若 g (X(0) = 0,则X(0)g g (X)二0形成的边界，影响下一步选向.j故称g (X)二0是X(
2、0)点的有效约束.可行方向(对可行域来说)设X(o)为可行点，P为某方向，若存在0,使得X(0)+九PeR,Xe 0,九0 0则称P是X(0)点的一个可行方向.(a)可行方向P与有效约束g (X(0) = 0的梯度jVg (X(0)关系是：jVg (X(0)tP0.记有效约束下标集J=j I g (X(0)=0,1 j 0,使得当九w 0,九，有0 0g (X(0)+XP) g (X(0) = 0, j e Jj j从而dg (X(0) + 九 P)j- =Vg (X (0)tP 0, j e Jd九jX=0见下图.（b）反之，若Vg （X（o）tP 0,则P必为可行方向.jg （X（0）+入
3、P） = g （X（0） + XVg （X（0）tP + o（九）对有效约束g （X（o） = 0,只要九充分小,得jg (X (O) +x P) 0,所以P是可行方向；j对无效约束g (X(o) 0,同样只要九充分小, j就有g (X(O) +xP) 0,故P也是可行方向；j事实上，对无效g (X(0) 0, VP都是可行方向.j(3)下降方向(对目标函数来说)设X(0) g R ,对某P方向，若在九w 0,九,九 00 0内,有f (X (0) + 九 P) f (X (0)则称P是一个下降方向.下降方向判定：若Vf (X (0)tP 0,则P是X (O)的一个下降方向. 因为 f (X)
4、二 f (X(0) +九 P)二 f (X(0) + XVf (X(0) )tP + 0(九), 只要九充分小，都有f (X) 0,当九0,九时，有0 0g （X（0）+X P） 0 且 f （X（0）+ 九 P） 0局部极小点,if (X), g .(X), j e J (有效约束下标集)在X *处可 j微，g .( X),总 在X*处连续，j则在X*处无可行下降方向P，即不存在P ,使Jvg (X*)TP 0, j e J,Vf (x*)tP 0, j = 1,1 j2.库恩一塔克条件（局部最小的必要条件） 是非线性规划中最重要成果之一Gordan引理（不加证明）设A , A，,A是l个n
5、维向量，则12l3P，使 AtP 0,不全为零，使丈卩A = 0.jj jj=i（不指向同侧的向量，正组合为零）（如l=3,n=2）若同侧，则有P（图a）,否则无P（图b）,但可正组为0.(2) Fritz John 定理设X*是1极小值点，f (X)和g .(X)有一阶连 j续偏导数，则存在不全为零的卩，卩,.,卩,使01lr vf（x*）Vg（x*）= 0 0j jj=1卩 g （X*） = 0, j = 1,2,., l、卩 0, j = 1,2,., lj证明因X*是问题v1的解，故由定理4,不存在 可行下降方向P,使Vf (X * )tP 0 -Vg (X * )tP 0j=1, 2
6、,证毕.注1：类似于条件极值的必要条件.注2若卩=0,则有效约束的Vg (X*)正线性相关 ojT同侧T有可行下降方向T X*非极值点.故一般设Vg (X*)线性无关T卩0.j0以上条件称为Fritz John条件，X *称为Fritz John占八、(3)必要条件(库恩-塔克条件)设X *是极小值点,f (X)和g .(X)有一阶连 j续偏导，且有效约束梯度线性无关，则3*，,卩*,使 iiVf(X*)*Vg (X*) = 0j jA1”*g (X*) = 0, j = 1,2,., l j j、* 0, j = 1,2,., lj证明由Fritz John引理，Vg (X*) j w J线
7、性无关得卩0,作卩* =卩/卩 0,即得V2.0j o o式=库恩-塔克条件.相应点=库恩-塔克点.简称K-T条件,K-T点.对一般非线性规划min f (X), o, j = 17J j它的K-T条件如下设X *是极小值点,min f (X),h (X) 0, 0, i = 0 g(X) 0, j = 口且有效约束的Vh (X*)和Vg (X*), j e J线性无关，则 3r* = (丫*,y*Y* )t 和M* = (|i*p*)t , 12m1l使Vf (X*) y *Vh (X*) p*Vg (X*) = 0i ij ji=1j=1p*g (X*) = 0, j = 1,2,lj j
8、p* 0, j = 1,2,., lj其中y*,y*，,y* , p*，p*称为广义Lagrange乘子.12m 1l注1对凸规划,K-T条件也是充分的.设Xk为某可行解,若Xk是极小点，且g(Xk) = 0,1和 g (Xk) = 0,2则Vf (X(k)必与,Vg2( Xk)Vg1(Xk k)g (Xk) = 0-二Vf (xk叫Xk )和Vg2(Xk )同侧，否则有可行下降方向.由Vg (Xk)和 Vg (Xk)线性无关1 2Vf (X*)二吓g (Xk)+RVg (Xk)11 2 2Vf (X *) -Vg (Xk) pVg (Xk)二 0min f (x) = - (x - 4)2解
9、变为 0,ig (x) = 6 一 x 0l 2vf (x) = -2(x - 4), Vg (x) = 1, Vg (x) = -1,1 2引入广义拉格朗日乘子卩:，巴，则有2( x* 4) p* + p* =1 2所以具体分析如下.p* (x* 1) = 0 0V 1 2若附0,附0,引出矛盾，无解；12若卩* 0,附二 0：x* 二 1，点；f (x*)二9(附二6)121若 p* = 0,p* = 0:x* 二 4, f (x*) = 0 ；12若 p* = 0, p* 0: x* = 6, f (x*) = 4( p* = 4)122所以最大值点x* =1,最大值f (x*) = 9
10、.注：f (x) = -(x-4)2非凸函数，在1, 6上有两个局部最小值点. 还有一个”驻点”附加例题(略)用K-T条件解非线性规划min f (x)二(x 3)20 x 5Jmin f (x) = (x 3)2,解 0,(是凸规划)g (x) = 5 x 01 2Vf (x)二 2(x 3), Vg (x)二 1, Vg (x) = -1,1 22(x* 3) y* + y* 二 01 2y*x* 二 0所以 1,具体分析如下.y* (5 x*)二 02y*, y* 0，1 2若yv 0, yv 0,引出矛盾，无解；1 2若 y* 丰 0, y* 二 0,解得 x* 二 0, y* = 6，非 K-T 点；121若 y* 二 0, y* 丰 0,解得 x* 二 5, y* = 4,非 K-T 点;121若 y* = 0,y* = 0,解得x* = 3,f(x*)二0全局最小.12习题4.1已知非线性规划max f (X) = xi 0J 12的极大点为(1,0),试(1)转化目标函数后，写出其K-T条件;求出K-T点.4.2试用K-T条件求解问题min f (X) = (x - 4)21 x 6
