资源预览内容
第1页 / 共28页
第2页 / 共28页
第3页 / 共28页
第4页 / 共28页
第5页 / 共28页
第6页 / 共28页
第7页 / 共28页
第8页 / 共28页
第9页 / 共28页
第10页 / 共28页
亲,该文档总共28页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第三讲非线性规划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(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)+入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)二 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维向量,则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,证毕.注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线性无关得卩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 jp* 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解变为 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.注: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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号