《运筹学》课程教学资源（PPT课件讲稿）第8章 非线性规划——约束极值问题

第8章约束极值问题 第1节最优性条件 第2节二次规划 第3节可行方向法 ■第4节制约函数法 清华大学出版社

第8章 约束极值问题 ◼第1节 最优性条件 ◼第2节 二次规划 ◼第3节 可行方向法 ◼第4节 制约函数法 清华大学出版社

第1节最优性条件 大多数极值问题其变量的取值都会受到一定限制,这种限制由约束 条件来体现。带有约束条件的极值问题称为约束极值问题。非线性 规划的一般形式为 min f(X h(X)=0,i=1,2…,m 00(7-1) g,(X)≥0,j=1,2,…,l 或 f(X) 8(X)≥0,j=1,2, 0(7-2) 问题(7-2)也常写成 minf(X),X∈RcEn 1R={x(x)≥0j=12… 0(7-3) 清华大学出版社

第1节 最优性条件 min ( ) ( ) 0, 1,2, , ( ) 0, 1,2, , i j f X h X i m g X j l    = =   =  min ( ) ( ) 0, 1,2, , j f X g X j l    =    min ( ), ( ) 0, 1,2, , j f X X R En R X g X j l      =  =  大多数极值问题其变量的取值都会受到一定限制，这种限制由约束 条件来体现。带有约束条件的极值问题称为约束极值问题。非线性 规划的一般形式为 或 问题(7-2)也常写成 (7-1) (7-2) (7-3) 清华大学出版社

第1节最优性条件 11起作用约束和可行下降方向的概念 现考虑上述一般非线性规划,假定(1、h(X和(X)1=12…m,/=12,… 具有一阶连续偏导数。 设ⅹ媞非线性规划的一个可行解。现考虑某一不等式约束条件 g/(X)≥0 x满足它有两种可能:其一为8(X)>0这时,点xo 不是处于由这一约束条件形成的可行域边界上,因而这一约束对x 点的微小摄动不起限制作用,从而称这个约束条件是X 点的不起作用约束或无效约束);其二是8(X)=0,这时Xo 点处于该约束条件形成的可行域边界上,它对x0 的摄动起到了某种限制作用,故称这个约束是X0) 点的起作用约束(有效约束) 显而易见,等式约束对所有可行点来说都是起作用约束。 清华大学出版社

第1节 最优性条件 ( )( 1,2, , ; 1,2, , ) j g X i m j l = = (0) X ( ) 0 j g X  (0) X ( ) 0 j g X  (0) X (0) X (0) X (0) g Xj ( ) 0 = (0) X (0) X (0) X 1.1 起作用约束和可行下降方向的概念 现考虑上述一般非线性规划，假定f(X)、hi (X)和 具有一阶连续偏导数。 设 是非线性规划的一个可行解。现考虑某一不等式约束条件 满足它有两种可能：其一为 ，这时，点 不是处于由这一约束条件形成的可行域边界上，因而这一约束对 点的微小摄动不起限制作用，从而称这个约束条件是 点的不起作用约束(或无效约束)；其二是 ，这时 点处于该约束条件形成的可行域边界上，它对 的摄动起到了某种限制作用，故称这个约束是 点的起作用约束(有效约束)。 显而易见，等式约束对所有可行点来说都是起作用约束。 清华大学出版社

第1节最优性条件 假定0是非线性规划(7-3)式的一个可行点,现考虑此点的 某一方向D,若存在实数A0>0,使对任意∈[0]均有 X0)+D∈R 就称方向D是X0点的一个可行方向。 清华大学出版社

第1节 最优性条件 0 λ  0 λ0,λ0  (0) X D R +  λ 假定X (0)是非线性规划(7-3)式的一个可行点，现考虑此点的 某一方向D，若存在实数 ，使对任意 均有 就称方向D是X (0)点的一个可行方向。 清华大学出版社

第1节最优性条件 若D是可行点X处的任一可行方向,则对该点的所有起作用约束 8(X)≥0 ⑩(7-5) 均有 g1(X)=0 g(X0)D≥0,j∈J vg2(Xo) 其中/为这个点所有起作用约束下标的集合。 R 另一方面,由泰勒公式 g(X0+D)=g,(X0)+g,(X0)D+0(0) Vg, (Xo) 对所有起作用约束,当心>0足够小时,只要 g(X0)D>0,j∈J⑩(7-6)g2(x)=0 就有8(X+AD)≥0,j∈J 图7-1 此外,对XO)点的不起作用约束,由约束函数的连续性,当入>0足够小时亦有 上式成立。从而,只要方向D满足(7-6)式,即可保证它是X0点的可行方向。 清华大学出版社

第1节 最优性条件 ( ) 0 j g X  (0) T ( ) 0, j    g X D j J (0) (0) (0) T ( λ ) ( ) λ ( ) (λ) j j j g X D g X g X D o + = + + (0) T ( ) 0, j    g X D j J (0) ( λ ) 0, j g X D j J +   若D是可行点X(0)处的任一可行方向，则对该点的所有起作用约束 均有 其中J为这个点所有起作用约束下标的集合。 另一方面，由泰勒公式 对所有起作用约束，当λ>0足够小时，只要 就有 此外，对X(0)点的不起作用约束，由约束函数的连续性，当λ>0足够小时亦有 上式成立。从而，只要方向D满足(7-6)式，即可保证它是X(0)点的可行方向。 图7-1 （7-5） （7-6） 清华大学出版社

第1节最优性条件 考虑非线性规划的某一可行点X0),对该点的任一方向D来说,若存在实数 ′>0使对任意∈[0,]均有 f(X+λD)<f(X0 就称方向D为X0)点的一个下降方向。 将目标函数八X)在点X处作一阶泰勒展开,可知满足条件 Vf(rO))D<O 的方向D必为X0)点的下降方向 如果方向D既是X0点的可行方向,又是这个点的下降方向,就称它 是该点的可行下降方向。假如X0点不是极小点,继续寻优时的搜索方向 就应从该点的可行下降方向中去找。显然,若某点存在可行下降方向, 它就不会是极小点。另一方面,若某点为极小点,则在该点不存在可行 下降方向。 清华大学出版社

第1节 最优性条件 λ'  0 λ[0, λ'] (0) (0) f X D f X ( +  λ ) ( ) (0) T   f X D ( ) 0 考虑非线性规划的某一可行点X(0)，对该点的任一方向D来说，若存在实数 ，使对任意 均有 就称方向D为X(0)点的一个下降方向。 将目标函数f(X)在点X(0)处作一阶泰勒展开，可知满足条件 的方向D必为X(0)点的下降方向。 如果方向D既是X(0)点的可行方向，又是这个点的下降方向，就称它 是该点的可行下降方向。假如X(0)点不是极小点，继续寻优时的搜索方向 就应从该点的可行下降方向中去找。显然，若某点存在可行下降方向， 它就不会是极小点。另一方面，若某点为极小点，则在该点不存在可行 下降方向。 清华大学出版社

第1节最优性条件 定理1设X*是非线性规划(7-3)式的一个局部极小点,目标函数f(X)在 X*处可微,而且 g(X)在X*处可微,当j∈J g,(X)在X*处连续,当了 则在X*不存在可行下降方向,从而不存在向量D同时满足: Vf(X)D0.j∈J 清华大学出版社

第1节 最优性条件 ( ) j g X j J  ( ) j g X j J  * T * T ( ) 0 ( ) 0, j f X D g X D j J        定理1 设X*是非线性规划(7-3)式的一个局部极小点，目标函数f(X)在 X*处可微，而且 在X*处可微，当 在X*处连续，当 则在X*不存在可行下降方向，从而不存在向量D同时满足： 清华大学出版社

第1节最优性条件 12库恩一塔克条件 假定X*是非线性规划(7-3)式的极小点,该点可能位于可行域的内部,也 可能处于可行域的边界上。若为前者,这事实上是个无约束问题,X*必 满足条件 f(X)=0 若为后者,情况就复杂得多了 下面讨论当极小点位于可行域边界的情形。 清华大学出版社

第1节 最优性条件 * f X( ) 0 = 1.2 库恩－塔克条件 假定X*是非线性规划(7-3)式的极小点，该点可能位于可行域的内部，也 可能处于可行域的边界上。若为前者，这事实上是个无约束问题，X*必 满足条件 若为后者，情况就复杂得多了。 下面讨论当极小点位于可行域边界的情形。 清华大学出版社

第1节最优性条件 不失一般性,设X*位于第一个约束条件形成的可行域边界上,即第 个约束条件是X点的起作用约束(8(Xx’)=0)。若X*是极小点,则 V(X)=0必与V/(x)在一条直线上且方向相反。 否则,在该点就一定存在可行下降方向(图7-2中的X*点为极小点;X点不满 足上述要求,它不是极小点,角度β表示了该点可行下降方向的范围)。 上面的论述说明,在上述条件下,存在实数x1≥0,使 Vf(X)-%g1(X)=0 清华大学出版社

第1节 最优性条件 * 1 g X( ) 0 = * 1  = g X( ) 0 * −f X( ) 1   0 * * 1 1  − = f X g X ( ) ( ) 0  不失一般性，设X*位于第一个约束条件形成的可行域边界上，即第 一个约束条件是X*点的起作用约束( )。若X*是极小点，则 必与 在一条直线上且方向相反。 否则，在该点就一定存在可行下降方向(图7-2中的X*点为极小点；X点不满 足上述要求，它不是极小点，角度β表示了该点可行下降方向的范围)。 上面的论述说明，在上述条件下，存在实数 ，使 清华大学出版社

第1节最优性条件 若X*点有两个起作用约束,例如说有 81(Xx')=0g2(X)=0 在这种情况下,Vf(X)必处于Vg(X)和Vg2(X)的夹角之内。 如若不然,在点必有可行下降方向,它就不会是极小点(图7-3)。由此可 见,如果是极小点,而且X点的起作用约束条件的梯度Vg(x) 和Vg:(X)线性无关,则可将V/(X)表示成v(x)和vgx) 的非负线性组合。也就是说,在这种情况下存在实数1≥0和n20,使 Vf(X)-nVg(X)-12Vg2(X)=0 清华大学出版社

第1节 最优性条件 * 1 g X( ) 0 = * 2 g X( ) 0 = * f X( ) * 1 g X( ) * 2 g X( ) * 1 g X( ) * 2 g X( ) * f X( ) * 1 g X( ) * 2 g X( ) 1   0 2   0 * * * 1 1 2 2  −  −  = f X g X g X ( ) ( ) ( ) 0   若X*点有两个起作用约束，例如说有 在这种情况下， 必处于 和 的夹角之内。 和 线性无关，则可将 表示成 和 的非负线性组合。也就是说，在这种情况下存在实数 和 ，使 如若不然，在X*点必有可行下降方向，它就不会是极小点(图7-3)。由此可 见，如果X*是极小点，而且X*点的起作用约束条件的梯度 清华大学出版社