《高级运筹学》约束非线性规划

1、.约束非线性规划高级运筹学高级运筹学教学课件教学课件2015-10.本章内容本章内容 第一节 最优性条件 第二节 可行方向法 第三节 惩罚函数法 第四节 复形法.本章讨论如下的约束非线性规划问题本章讨论如下的约束非线性规划问题min( ). .( )01,2,.,( )01,2,.,jinf xsth xjlg ximxR其中 f, gi,hj均为实值连续函数，且一般具有二阶连续偏导数。求解一般约束非线性规划问题，比无约束问题和线性规划问题都要复杂得多。.*1 1,2 2Tx22121212min( ). .101010f xxxstxxxx x2x*o11可行域是一个三角形及其内部，目标函数

2、等值线是以原点为圆心的同心圆。最优解：最优值*1()2f x考虑问题x1. 线性规划的最优解总可以在可行域的顶点中找到，而顶点个数有限。 约束非线性规划问题的困难性：约束非线性规划问题的困难性： 最优解不一定在顶点上；最优解不一定在顶点上；1. 求解无约束问题的迭代法不能直接搬过来用。求解无约束问题的迭代法不能直接搬过来用。例如：对于上面的问题，如果不存在约束，从任意初始点例如：对于上面的问题，如果不存在约束，从任意初始点x (0) 出发，沿出发，沿f(x)的负梯度方向进行一维搜索，便求得极小的负梯度方向进行一维搜索，便求得极小点点(0,0)T。有了约束，在进行一维搜索时，为了使求得的点是一个

3、可有了约束，在进行一维搜索时，为了使求得的点是一个可行点，就必须对步长加以限制，这样，最远只能跑到边界行点，就必须对步长加以限制，这样，最远只能跑到边界上的一个点。上的一个点。.当所取的x (0)不在直线x1-x2=0上时，x (1)点就不会是最优解x*,因此还必须继续迭代下去找一个新的可行点，使目标函数取更小的值。x2x*o11x1x(1)x(0)可是，沿f(x)在x (1)处的负梯度方向已经找不到可行点，因而梯度迭代已经不能继续进行，尽管离最优解还可能很远。为了使迭代能继续下去，不仅要求搜索方向具有使目标函数下降的性质，而且要求在这个方向上有可行点。例如有一小段整个包含在可行域内，这样的方

4、向称为可行方向。.设计求解约束非线性规划的迭代法，关键是在每个迭代点处构造一个下降可行方向。求解约束非线性规划的另一个途径是：在某个近似解处，以已有较好解法的较为简单的问题近似代替原问题，用其最优解作为原来问题的新的近似解。如将目标函数及约束条件中的非线性函数分别以它们的一阶泰勒多项式或二阶泰勒多项式近似代替，或以一无约束非线性规划近似代替。如何判断约束非线性规划的一个可行解是否为最优解？.第一节 最优性条件123123min( ,). .( ,)0f x x xsth x x x一、等式约束极小化问题的最优性条件考虑下面的约束优化问题其中f, h 均为可微函数。以上问题的几何意义：在曲面12

5、3123( ,)| ( ,)0 x x xh x x x上寻找函数 f(x1,x2,x3) 的最小值。（1）.设以上问题的最优解为*123*(,)Txx x x在曲面上任作一条通过点x*的光滑曲线112233:( ),( ),( )l xx t xx t xx t则必有123*112233( ( ),( ),( )0( ),( ),( )h x t x t x txx txx txx t显然，限于曲线 l 上 x* 亦是使f(x1,x2,x3)取极小值的点，即t*是一元函数F(t)=f(x1(t),x2(t),x3(t)的极小点.因此必有*123123( )()()()( )( )( )0dF

6、 tf xf xf xx tx tx tdtxxx即梯度f(x*)垂直于曲线l在点x*处的切线，由l的任意性知， f(x*)必垂直于在x*处的切平面方向。由上面的分析知f(x*) 和h(x*)必在同一直线方向上，即存在数*, 满足*()()f xh x.可以证明，对于一般等式约束问题min( ). .( )0,1,2,.,nx Rjjf xst h xjlf h其中 均可微在最优解x*处，必存在数值 (1*, 2*, l*),使*1()()ljjjf xh x为便于记忆，引进拉格朗日函数1( , )( )( )( )( )lTjjjL xf xh xf xh x12(,.,)Tl 其中称为拉格

7、朗日乘子*(,)0 xL x简单表示为（2）.定理定理1 1（等式约束问题最优解的一阶必要条件）（等式约束问题最优解的一阶必要条件）1*1*1,1,2,.,(),.,()(,.,) ,jlTlf hCjlh xh xx对于等式约束问题，若且线性无关，则 是最优解的必要条件为：存在相应的拉格朗日乘子使得*1(,)()()0lxjjjL xf xh x min( ). .( )0,1,2,.,nx Rjjf xst h xjlf h其中 均可微.22143-2341zxxyyxyz例求曲面到平面的最短距离解 （1）建立数学模型 取点A(x1,y1,z1), B(x2,y2,z2)，限制A在曲面上变

8、化，B在平面上变化，则A、B 间距离S的最小值为解。问题的数学模型为：222111222121212221111222111112111222222min(,)()()(). .(,)32340(,)410f x y z xyzxxyyzzsth x y z xyzxx yyzh x y z xyzxyz 其中已把距离S最小等价地替换成S2 最小，以简化目标函数。 .（2）利用最优性条件求解1112221 122( ,)L x y z xyzfhh1211112()(62)0Lxxxyx1211112()( 26)0Lyyxyy12112()40Lzzz12222()0Lxxx 12222()

9、0Lyyy 12222()40Lzzz .再加约束条件221111132340 xx yyz222410 xyz由上述方程组解得1112221175,4162448xyzxyz 相应目标函数值为28由问题的几何意义知最优解肯定存在，又据必要条件仅此一个解，故以上所求即为最优解和最优值。.二、一般非线性规划的最优性条件考虑问题12311232123min(,). .(,)0(,)0f x xxstg x xxgx xx其中f, g1, g2均可微。（3）设 为（3）的最优解，且设*123(,)xxxx*11232123(,)0,(,)0,g xxxgxxx由于x*为区域(x1,x2,x3)|g2

10、(x1,x2,x3)0的内点，所以，对于x*而言，约束g2(x1,x2,x3)0 实际并没有起作用。称约束g1(x1,x2,x3)0为点x*处的有效约束。.于是x*实际上也是问题1231123min(,). .(,)0f x xxstg x xx（4）的最优解，由定理1知，必有1*，使*11( *)( *)0f xgx为使形式整齐起见，引进2*=0，统一写成*1122( *)( *)( *)0f xgxgx把*1123(,)0g xxx和2*=0，统一写成*123(,)0,1,2iig xxxi（5）（7）（6）.从几何上看，(5)式的f(x*)和 g1(x*)都通过x*且应共线。实际上，由于

11、x*是(4)的最优解，所以，当动点x由x*出发沿着g1(x)=0上的各个方向移动时，目标函数值f(x)均增加，不仅如此，而且 x由x*出发往g1(x)0的内部移动时（即下图所示箭头方向），f(x)也应增加。1( )0g x 2( )0gx x*.由于梯度指向函数值的增加方向，因此，f(x*)和g1(x*)不仅共线，而且应该是同方向的。即（6）中的*120,0总之，(4)的最优解x*应满足条件 (6)(7)(8)（8）1( )0g x 2( )0gx x*g1(x*)f (x*)*1122( *)( *)( *)0f xgxgx*123(,)0,1,2iig xxxi*120,0.( ). .(

12、 )01,.,minnx Rifxstg xim考虑一般不等式约束问题.g2(x)=0 x*g1(x)=0g1(x*)=0, g1为有效约束.*xx D( *)f x ( )f x *2()gx *1()g x 2( )gx 3( )gx 不等式约束问题的不等式约束问题的K-T点的点的几何意义几何意义.对于一般约束非线性规划问题min( ). .( )01,.,( )01,.,nx Rijf xstg ximh xjl（9）构造拉格朗日函数11( , , )( )( )( )mliijjijL xf xg xh x （10）.定理2 （Kuhn-Tucher必要条件，简称K-T条件）对于非线性

13、规划（9），若f, gi,hj 均可微且gi(x*),iI(x*), hj(x*), j=1,l线性无关，则x*为（9）的最优解的必要条件为：存在相应的拉格朗日乘子*和*使*11(,)()()()0mlxiijjijL xf xg xh x *0,1,2,.,0iiigim*() |()0iI xi g xx其中为 的有效约束指标集（9）min( ). .( )01,.,( )01,.,nx Rijf xstg ximh xjl.是多元函数取得约束极值的是多元函数取得约束极值的,可以用来可以用来作为约束极值的判断条件。作为约束极值的判断条件。这种情况这种情况K-T条件即为多条件即为多元函数取得

14、约束极值的充分必要条件。元函数取得约束极值的充分必要条件。.满足满足K-T条件的可行点称为条件的可行点称为K-T点，最优性条件指在梯度线点，最优性条件指在梯度线性无关的条件下，最优点必定是性无关的条件下，最优点必定是K-T点。点。在实际应用中，很难验证所得的点是否为非线性规划的在实际应用中，很难验证所得的点是否为非线性规划的最优解，若能验证其是最优解，若能验证其是K-T点，就已经满足了。有时构点，就已经满足了。有时构造算法也是以得到造算法也是以得到K-T点为目标的。点为目标的。.例例2 求以下非线性规划的求以下非线性规划的K-T点点21222112212min( ). .( )90( )10f

15、 xxxstg xxxgxxx 解：非线性规划的解：非线性规划的K-T条件为条件为1112222102110 xxx 22112(9)0 xx212(1)0 xx120,0再加上约束221290 xx1210 xx （11）（12）（13）（14）（15）（16）.11122222211211221221222102110(9)0090(1)0010 xxxxxxxxxxx 12(1)0.矛盾矛盾122(2)0,01. 得得矛矛盾盾12111TT12222121(3)0,0(1)0011203*(0, 3)*( ,0)6196xxxxxxx 得得，.1112222221121122122122

16、2102110(9)0090(1)0010 xxxxxxxxxxx 1222112122(4)0,01179211172.xxxxxx 得得两两种种情情况况均均可可推推出出矛矛盾盾.22121222121212min(,)(3)(2). .5024000f xxxxs txxxxxx x1f(x1)x1x2.解解：122(3)( )2(2)xf xx 1122( )2xg xx 21( )2gx 31( )0g x 40( )1gx 22121222121212min(,)(3)(2). .5024000f xxxxs txxxxxx .在x1=(2,1)T 点，I=1,2122(3)( )2

17、(2)xf xx 1122( )2xg xx 21( )2gx 31( )0g x 40( )1gx 12()2f x 114()2g x 121()2gx 且，g1(x1), g2(x1)线性无关。为使1224102220 成立，只要取1212,33即可。所以，x1是K-T点。.在x2=(0,0)T 点，I=3,4122(3)( )2(2)xf xx 1122( )2xg xx 21( )2gx 31( )0g x 40( )1gx 26()4f x 231()0gx 240()1g x 且，g3(x2), g4(x2)线性无关。为使3461004010 成立，只有取346,4 由于30,

18、40，使对任意，使对任意t (0, )均有均有x+td D,则称则称d为从为从x点出发的可行方向。点出发的可行方向。d 为可行方向为可行方向d1不是可行方向不是可行方向xdd1D.第二节第二节 可行方向法可行方向法基本思想基本思想： 在每一个迭代点处，寻找一个下降可行方向，在每一个迭代点处，寻找一个下降可行方向，沿下降可行方向进行一维搜索。沿下降可行方向进行一维搜索。如何寻找可行方向？如何寻找可行方向？可行方向：设可行域DRn是非空集，xD.若对于某非零向量，d Rn,存在0，使对任意t (0, )均有x+td D,则称d为从点x出发的可行方向。.1234123412342342347(1)2

19、325(2)32(3)421(4)0,1,2,3,4ixxxxxxxxxxxxxxxxi例例7 在由约束在由约束所确定的可行域内，任求一个在点x=(0,1,2,3)T处的可行方向。.解解：首先检查在点x处哪些约束为有效约束，经检查，约束（1）（2）（3）和x10为有效约束。设所求可行方向为1234(,)Tdd d d d根据可行方向的定义，应存在，使对任意 t(0,)有1234(0,1,2,3)Txtdtdtdtdtd也能满足所有有效约束，即12341234123412()(1)3(2)4(3)72()3(1)(2)2(3)53(1)(2)(3)20tdtdtdtdtdtdtdtdtdtdtd

20、tdtd.整理得整理得123412341234123402320300ddddddddddddd满足上述不等式的 均为可行方向。1234(,)Tdd d d d现只求一个可行方向，可令不等号改为等号，求解1234123412342340232030dddddddddddd得得132342,0dd dd d 为使d10，可取d3=1得一可行方向(2, 1,1,0)Td .利用可行方向的概念，典型的策略是：由可行点x (k)出发，找一下降可行方向d (k)作搜索方向，然后确定沿此方向移动的步长，得下一迭代点x (k+1).这类方法称可行方向法。搜索方向的选择方式不同就形成不同的可行方向法。.Zou

21、tendijk可行方向法考虑min( ). .f xst AxbGxc(1)上述问题的约束是线性的，仅目标函数是非线性的，在迭代点x (k)附近，可以用f(x)的一阶泰勒展开式近似代替f(x).假设x (k)满足( )( )( )11221122,kkkAxb A xb GxcAbAbAb其中.( )( )( )11221122,kkkAxb A xb GxcAbAbAb其中( )( )( ), ( )()()kkkTxxd f xf xf xd令于是得到线性规划( )( )min()()kkTf xf xd ( )11( )22( ). .()()()kkkstA xdbA xdbG xdc

22、( )( )11(),kkf xA xb由由于于为为常常数数所所以以上上述述线线性性规规划划等等价价于于( )min()kTf xd2. .00stA dGd(2) .注意到d=0为上述线性规划(2)的可行点，其对应的目标函数值为0， 所以若d*为问题(2)的最优解，则( )min()kTf xd2. .00stA dGd( )*()0kTf xd( )*()0kTf xd若则d* 为问题(1)在x (k)处的下降可行方向； ( )*()0kTf xd若则x (k)为问题(1)的K-T点。(证明略)min( ). .f xst AxbGxc(2)(1).Zoutendijk可行方向法的具体步骤

23、可行方向法的具体步骤 任选可行点x (0)作初始点，令k=0; 2. 根据x (k)的有效约束把A分解为A1，A2， 相应地把b分解为b1,b2,使( )( )1122,kkAxb A xb3. 求解线性规划( )2. .0011,1,2,.(,min)kiTstA dGddxinfd 设其最优解为d (k) 。.( )( )( )4.|()|,5;kTkkf xdx若若则则即即为为所所求求的的最最优优解解 结结束束 否否则则转转( )( )( )(1)( )( )15.A0,min(),12;6;kkkkkkkdf xtdxxt dkk若若则则由由线线搜搜索索得得令令转转否否则则转转( )(

24、 )111( )( )(1)( )( )06.,min0min(),12.kkiiikkkkkkt tuA xb vAdutvvf xtdxxt dkk 设设计计算算由由确确定定令令转转.8例例用用Z Zo ou ut te en nd di ij jk k可可行行方方向向法法求求解解2212121212min( )4. .115101200f xxxstxxxxxx解：取x (0) =(0,2)T,注意1115101001A在x (0)点，有效约束仅x10一个，故A2=(1,0), b2=0.111111510 ,12010Ab(0)()(0,16)Tf x12( )(2 ,8)Tf xxx

25、.设所求的下降可行方向d (0) =(d1,d2)T,其相应的线性规划为2112min16. .01111dstddd 求得最优解 d (0) =(0,-1)T . 因(0)(0)()160Tf xd 还需继续迭代。求搜索区间。计算(0)11(0)1(1,8,2)( 1, 10, 1)TTuA xbvA d 312123441,255uuutvvv 从从中中选选出出最最小小者者111111510 ,12010Ab(0)(0,2)Tx.在t0,4/5中求(0)(0)2min()4(2)f xtdt4,50 0得得t =t =于于是是(1)(0)(0)060,5Txxt d作第二次迭代关于x (1

26、)的有效约束为1211510120 xxx和和，所所以以1122111151012A,A010100，bb (1)(1)1248()0,(,) ,5TTf xdd d设设相相应应线线性性规规划划为为.21211248min5. . 1510001111dstddddd 求得最优解 d (1) =(2/3,-1)T . 因(1)(1)48()05Tf xd 还需继续迭代。(1)11(1)11 6( , )5 51(, 1)3TTuA xbvAd 11111A010b ，(1)60,5Tx1212363,555uutvv 从从中中选选出出最最小小者者.在t0,3/5中求(1)(1)24048144

27、min()9525f xtdtt13,5得得t =t =于于是是(2)(1)(1)12 3,5 5Txxt d作第三次迭代关于x (2)的有效约束为12121151012xxxx和和，所所以以1122100111A,A010151012，bb (2)(2)124 24(),(,) ,55设设相相应应线线性性规规划划为为TTf xdd d.(2)(2)()40Tf xd 还需继续迭代。(1)11(1)12 3( , )5 5(1, 1)TTuA xbvAd12121212424min55. .0151001111ddstdddddd 求得最优解 d (2) =(1,-1)T . 因11100A0

28、10b ，(2)2 3,5 5Tx223355 由由于于，故故utv.(2)(2)28min()545f xtdtt22,5得得t t = =于于是是(3)(2)(2)24 1,5 5Txxt d在t0,3/5中求.作第四次迭代关于x (3)的有效约束为121xx ，所所以以 1122151012A100 ,A1 11010，bb(3)(3)128 8(),(,) ,5 5设设相相应应线线性性规规划划为为TTf xdd d12121288min55. .01111ddstdddd .求解得(3)(0,0)Td(3)(3)()0Tf xd即得本题的最优解为4 1,5 5T由于.用Zoutendi

29、jk可行方向法解下列问题22121212121212min( )22246. .25500f xxxx xxxs txxxxxx （1）取初始点 x (1) =(0,0)T（2）221221212min25. .200,0 xxxs txxxx取初始点 x (1) =(2,0)T.2211212min(4)(3). .30202xxs txxxx（3）取初始点 x (1) =(1,2)T.第三节第三节 惩罚函数法惩罚函数法 基本思想基本思想：通过构造罚函数把约束优化问题转：通过构造罚函数把约束优化问题转化为化为一系列无约束最优化问题一系列无约束最优化问题，进而用无约束最优，进而用无约束最优化方

30、法去求解。化方法去求解。 又称为序列无约束最小化方法。又称为序列无约束最小化方法。.考虑一般约束非线性规划问题考虑一般约束非线性规划问题min( ),. .( )01,2,( )01,2,nijfRst gimhjlxxxx根据约束的特点，构造某种根据约束的特点，构造某种“惩罚惩罚”项，然后把它加到项，然后把它加到目标函数中去，使得约束问题的求解，转化成一系列无目标函数中去，使得约束问题的求解，转化成一系列无约束问题的求解。约束问题的求解。“惩罚惩罚”策略：对于无约束问题求解过程中企图违反约策略：对于无约束问题求解过程中企图违反约束的那些迭代点，给以很大的目标函数值，迫使这一系束的那些迭代点，

31、给以很大的目标函数值，迫使这一系列无约束问题的极小点或者不断的向可行域靠近，或者列无约束问题的极小点或者不断的向可行域靠近，或者一直保持在可行域内部移动，直到收敛于原约束问题的一直保持在可行域内部移动，直到收敛于原约束问题的极小点。极小点。.常用的惩罚函数法有三种：一、外部惩罚函数法（外点法）一、外部惩罚函数法（外点法） 对违反约束的点在目标函数中加入相应的对违反约束的点在目标函数中加入相应的“惩罚惩罚”，而对可行点不予惩罚。此法的迭代点一般在可行域外部移而对可行点不予惩罚。此法的迭代点一般在可行域外部移动。动。二、内部惩罚函数法（内点法）二、内部惩罚函数法（内点法） 对企图从内部穿越可行域边

32、界的点在目标函数中加入对企图从内部穿越可行域边界的点在目标函数中加入相应的相应的“障碍障碍”，距边界越近，障碍越大，在边界上给以，距边界越近，障碍越大，在边界上给以无穷大的障碍，从而保障迭代一直在可行域内部移动。无穷大的障碍，从而保障迭代一直在可行域内部移动。三、乘子法三、乘子法 在拉格朗日函数中加入相应的惩罚。在拉格朗日函数中加入相应的惩罚。.一、外点法基本原理：外点法是从可行域的外部构造一个基本原理：外点法是从可行域的外部构造一个极小点序列极小点序列去去逼近逼近原约束问题的原约束问题的最优解最优解。对于等式约束问题：对于等式约束问题：min( ). .( )0,1,2,.,jf xsth

33、xjl定义辅助函数211( ,)( )( )ljjF xf xhx参数是很大的正数。.min( ). .( )0,1,2,.,jf xsth xjl211( ,)( )( )ljjF xf xhx（1）（2）当求解无约束问题当求解无约束问题1min( ,)xF x（3）得到的最优解得到的最优解x*，满足，满足 hj(x*)=0, j=1,2,l 时，显然时，显然x*就是原问题就是原问题(1)的最优解。的最优解。在求解问题在求解问题(3)的过程中，若的过程中，若x (k)不满足不满足 hj(x (k)=0,则则(2)中中第二项将是很大的正数，限制它成为极小点，以迫使无第二项将是很大的正数，限制它

34、成为极小点，以迫使无约束问题约束问题(3)的最优解满足（或接近满足）的最优解满足（或接近满足） hj(x)=0 (j=1,2,l).可见，求解问题可见，求解问题(3)能够得到问题能够得到问题(1)的近似解。的近似解。.对于不等式约束问题对于不等式约束问题min( ). .( )0,1,2,.,if xstg xim构造辅助函数221( ,)( )max0,( )miiF xf xg x这样可以将问题（4）转化为无约束问题（4）（5）2min( ,)F x（6）.对于一般约束问题对于一般约束问题可以定义辅助函数( ,)( )( )F xf xP x这样约束问题（7）转化为无约束问题（7）（8）m

35、in( ,)( )( )F xf xP x（9）min( ),. .( )01,2,( )01,2,nijfRst gimhjlxxxx11( )max0,( )|( )|mlijijP xg xh x其中，1，通常取 =2（10）.（9）11( )max0,( )|( )|mlijijP xg xh xmin( ,)( )( )F xf xP x（10）min( ),. .( )01,2,( )01,2,nijfRst gimhjlxxxx（7）当当x为问题为问题(7)的可行点时，的可行点时，P(x)=0， 从而从而F(x, )=f(x); 当当x 不是问题不是问题(7)的可行点时，的可行点

36、时， P(x)是很大的正数，可视为是很大的正数，可视为对对x脱离可行域的一种惩罚，其作用是在极小化问题脱离可行域的一种惩罚，其作用是在极小化问题(10)的的过程中迫使迭代点靠近问题过程中迫使迭代点靠近问题(7)的可行域。因此，求解问题的可行域。因此，求解问题(10)能得到问题能得到问题(7)的近似解，而且的近似解，而且 越大，近似程度越好。越大，近似程度越好。通常将通常将 P(x)称为惩罚项，称为惩罚项， 称为惩罚因子，称为惩罚因子， F(x, )称为惩称为惩罚函数。罚函数。.例例9 求解非线性规划问题求解非线性规划问题22122min( )(1). .( )10f xxxstg xx 解：定

37、义罚函数222122221222221222( ,)(1)max0, (1)(1),1(1)(1) ,1F xxxxxxxxxxx当当当当用解析法求解minF(x,)，有112222222(1),2,122 (1),1FxxxxFxxxx当当当当.112222222(1),2,122 (1),1FxxxxFxxxx当当当当120,0FFxx令令1*211xxx得得到到*11xx 当当时时，x*恰为所求非线性规划问题的最优解用此法求得的无约束问题最优解往往是不满足约束条件的，它是从可行域外部，随着的增大而趋于x*的，故称此法为外点法。.惩罚因子 的选择策略：选取一个趋于无穷大的严格递增正数列k，

38、逐个求解min( )( )kf xP x而得到一个极小点序列xk*，在适当条件下，这个序列将收敛于约束问题的最优解。通过一系列无约束问题来获得约束问题最优解的方法称为序列无约束极小化方法，简称SUMT方法(Sequential Unconstrained Minimization Techniques ).外点法的计算步骤 给定初始点x (0)，初始惩罚因子1，放大系数c1, 允许误差 0；2. 以x (k-1)为初始点，求解无约束问题min( )( )kf xP x设其极小点为x (k)； 若kP(x (k)0，初始参数r10,缩小系数 (0,1),k=1。2. 以x (k-1)为初始点，求

39、解问题min( )( ). .intkf xr B xstxD设求得极小点为x (k)；3. 若rkB(x (k) )，则停，得近似解x (k)；否则，令rk+1=rk, k=k+1,回2。.例例12 用内点法求解用内点法求解22121min( )s.t.( )10fxxgx xx解：首先构造内点罚函数（障碍函数）解：首先构造内点罚函数（障碍函数）22121( , )ln(1)kkGrxxrxx1112220120kGrxxxGxx用解析法求解用解析法求解intmin( ,)kxDG x r根据极值存在的必要条件得.1112220120kGrxxxGxx求解得12112( )2( )0kkkr

40、x rx r考虑约束 x1-10, 1112( )2kkrx r应舍去。.无约束问题的极值点为*1*2112( )2( )0kkkrxrxr1114,( )20,(, )4Trx rG x r2221.2,( )1.4220,(,)2.022Trx rG x r取r1=4, =0.3 得3330.36,( )1.1560,(,)1.336TrxrG xr0,( )10,(,)1Tkkkrx rG x rk时时.1( )10g xx x (r1)x (r2)123( )20( )1.4220( )1.1560TTTx rx rx r10Tx.最优点图解最优点图解.例例13 用内点法求解用内点法求

41、解312121min(1)12. .100 xxstxx 定义障碍函数定义障碍函数31212111( ,)(1)()121kkG x rxxrxx用解析法求解用解析法求解intmin( ,)kxDG x r令212112221(1)04(1)10kkrGxxxrGxx .解得212112221(1)04(1)10kkrGxxxrGxx *12( ,)( 12,)kTTrkkxx xrr*0(1,0) ,kTkrrxxx当当时时， 确确为为最最优优解解。.内点法注意事项：内点法注意事项：1. 初始点选取：尽量选择离约束边界较远的可行点初始点选取：尽量选择离约束边界较远的可行点 可以采用随机生成的

42、方法产生可以采用随机生成的方法产生2. 惩罚因子惩罚因子r初值的选取：初值的选取： 过大：迭代次数多过大：迭代次数多 太小：惩罚函数形态恶劣太小：惩罚函数形态恶劣 通常选取初始惩罚因子为通常选取初始惩罚因子为150 之间的数之间的数3. 缩小系数缩小系数 通常选取：通常选取：0.10.7 之间的数之间的数.例例14 用内点法求解用内点法求解12211221min( ). .( )0( )0f xxxstg xxxgxx 解：构造障碍函数212121( , )ln()ln( )kkkGrxxrxxrxx121121221221010kkkGr xrxxxxGrxxx 用解析法求解intmin(

43、,)kxDG x r根据极值存在的必要条件得.解得12211184kkrxxrx111 84krx 舍舍去去*T0(0,0)kkrrxx当当时时， .内点法和外点法的简单比较内点法和外点法的简单比较 内点法的特点：内点法的特点： （1 1）初始点必须为严格内点）初始点必须为严格内点 （2 2）不适于具有等式约束的优化问题）不适于具有等式约束的优化问题 （3 3）迭代过程中各个点均为可行解）迭代过程中各个点均为可行解 （4 4）初始罚因子要选择得当）初始罚因子要选择得当 （5 5）罚因子递减）罚因子递减(0)(0)，递减率，递减率 有有00 111 .外点法和内点法使用序列无约束极小化技巧，方法

44、简单，外点法和内点法使用序列无约束极小化技巧，方法简单，使用方便，并且能用来求解目标函数和约束函数导数不存使用方便，并且能用来求解目标函数和约束函数导数不存在的问题，因此，这种算法得到了广泛的应用。在的问题，因此，这种算法得到了广泛的应用。固有缺点：随着惩罚因子趋向其极限，惩罚函数的固有缺点：随着惩罚因子趋向其极限，惩罚函数的Hessen矩阵的条件数无限增大，因而越来越变得病态。惩罚函数矩阵的条件数无限增大，因而越来越变得病态。惩罚函数的这种性态给无约束极小化带来很大的困难。的这种性态给无约束极小化带来很大的困难。为了克服这个困难，为了克服这个困难，Hestenes和和Powell于于1969

45、年年各自独立各自独立地提出了乘子法。地提出了乘子法。.练习：练习： 用内点法求解下列问题用内点法求解下列问题122122221221(1)min( )2. .00(2)min( ). .2010f xxxstxxxf xxxstxx .三、乘子法三、乘子法1. 等式约束的情形等式约束的情形考虑问题考虑问题min( ). .( )0,1,2,.,jf xsth xjl其中f, hj (j=1,2,l)为二次连续可微函数，xRn运用乘子法，需要定义增广拉格朗日函数（乘子惩罚函数）211( , ,)( )( )( )2( )( )( )( )2lljjjjjTTxf xh xhxf xh xh xh

46、 x 1212(,.,) , ( )( ),( ),.,( ) ,0TTllh xh x hxh x 其中.211( , ,)( )( )( )2( )( )( )( )2lljjjjjTTxf xh xhxf xh xh xh x 乘子惩罚函数(x, ,) 与拉格朗日函数的区别在于增加了惩罚项( )( )2Th xh x与惩罚函数的区别在于增加了乘子项( )Th x这种区别使得增广拉格朗日函数与拉格朗日函数及惩罚函数具有不同的性态。对于(x, ,) ，只要取足够大 的惩罚因子，不必趋向无穷大，就可以通过极小化(x, ,) 求得原问题的局部最优解。.min( ). .( )0,1,2,.,jf

47、 xsth xjl（1）若x*是问题(1)的局部最优解，*是相应的最优拉格朗日乘子，且对每个满足dThj(x*)=0 (j=1,2,l)的非零向量d，均有二阶充分条件成立，即2*(,)0TxdL xd则存在00, 使得对所有 0, x*是(x,*,)的严格局部极小点。( )0,1,2,., ,( ,)1jxh xjlxxx 反反之之，若若存存在在 ，满满足足且且对对某某个个， 为为的的无无约约束束极极小小点点，又又满满足足极极小小点点的的二二阶阶充充分分条条件件，则则 即即问问题题( ( ) )的的严严格格局局部部极极小小点点。.根据上述结论，如果知道最优乘子*，那么只要取充分大的惩罚因子，不

48、需趋向无穷大，就能通过极小化(x,*,)求出问题（1）的解。问题：如何确定最优乘子*？ 方法:先给定充分大的和拉格朗日乘子的初始估计，然后在迭代过程中修正，力图使趋向*。修正的迭代公式：(1)( )( )()1,2,.,kkkjjjh xjl如果 (k) 不收敛，或者收敛太慢，则增大参数，再进行迭代。收敛快慢的衡量标准( )(1)()()kkh xh x.乘子法的计算步骤(0)(1)1.,01,0 1 ,1;xk给给定定初初始始点点，乘乘子子向向量量的的初初始始估估计计参参数数 ，允允许许误误差差，常常数数( ( ， ) )(1)2.kx以以为为初初始始点点，解解无无约约束束问问题题( )mi

49、n ( ,)kx( );kx得得解解( )( )3.(),;4kkh xx若若则则停停，得得近近似似解解否否则则转转 。( )(1)()4.,5()kkh xh x若若令令，转转 ；(1)( )( )5.()1,2,.,1,2kkkjjjh xjlkk计计算算回回 。.例例15用乘子法求解用乘子法求解22121212min22. .( )10 xxx xst h xxx 解：构造广义拉格朗日函数（乘子惩罚函数）解：构造广义拉格朗日函数（乘子惩罚函数）22212121212( , ,)22(1)(1)2xxxx xxxxx (1)21,min( ,1,2)x取取，用用解解析析法法求求解解，得得极

50、极小小点点为为(1)(1)1(1)21234xxx .修正，得(2)(1)(1)11()1 242h x 再解22212121212112min ( ,2)22(1)(1)222xxxx xxxxx得(2)(2)1(2)251258xxx.如此继续，一般地，在第k次迭代时，(x, (k) , 2)的极小点为( )( )( )1( )( )21(2)61(2)4kkkkkxxx(1)( )( )( )11()63kkkkh x(1)( )(1)(1)111 111().636 633111111(.)6336361211656kkkkkkk将的递推公式展开得.( )( )223555Tkkkx

51、当当时时，非线性规划问题的最优乘子和最优解分别为*223555Tx，.2. 不等式约束的情形对于只有不等式约束的问题min( ). .( )0,1,2,.,if xstg xim利用等式约束的结果，引入变量yi, 把(2)化为等式约束问题（2）2min( ). .( )0,1,2,.,iif xstg xyim定义增广拉格朗日函数22211( , , ,)( )( )( )2mmiiiiiiix yf xg xyg xy .从而把问题（2）转化为求解min( ). .( )0,1,2,.,if xstg xim（2）min( , , ,)x y 为此，将22211( , , ,)( )( )(

52、 )2mmiiiiiiix yf xg xyg xy 变形得22211222122222221222( , , ,)( )( )( )2( )( )( )22( )( )( )2( )( )22mmiiiiiiimiiiiiimiiiiiiiiiiiix yf xg xyg xyf xyg xyg xf xyg xyg xf xyg x 1mi.22211( , , ,)( )( )22miiiiix yf xyg x 2iy 为为了了使使 取取极极小小， 的的取取值值必必定定是是2( )1max0,1max0,( )iiiiig xg xy 2( )( )00( )01iiiiiiiyg x

53、g xg x .将 代入 22211( , , ,)( )( )22miiiiix yf xyg x 可以消去yi ，因此定义增广拉格朗日函数2( )( )00( )01iiiiiiiyg xg xg x min ( , ,)x 2212211( , ,)( )max(0,( )221( )max(0,( )2miiiimiiiixf xg xf xg x 从而将问题（2）转化为无约束问题 .对于既含不等式又含等式约束的问题min( ). .( )0,1,2,.,( )0,1,2,.,ijf xstg ximh xjl定义增广拉格朗日函数2212111( , , ,)( )max(0,( )2

54、( )( )2miiiilljjjjjxf xg xh xhx 以充分大的参数，并通过下列公式对迭代过程中的乘子进行修正。 (1)()(1)()()max(0,( ),1,2,.,()1,2,.kkiiikkkjjjg ximh xjl 计算步骤与等式约束相同。.例例16 问题问题22121211min26. .1xxst xx的最优解为x*=(0.25,0.75)T,分别用惩罚函数法和乘子法求它的迭代点列。解：解：1. 惩罚函数法，对于 222121211min( ,)(1)262kkxF xxxxx可求得最优解为( )3,1414Tkkkkkx.2. 乘子法，对于( )22( )21212

55、1211min ( ,)(1)(1)262kkkkxxxxxxxx可求得最优解为( )( )( )3(),1414Tkkkkkkkx.( )3,1414Tkkkkkx( )( )( )3(),1414Tkkkkkkkx(0)(1)( )( )( )120.1 2 ,0,(1),1kkkkkkkxxk取取所得迭代点列见下表.kx (k)(惩罚函数法)x(k)（乘子法）0(0.0714,0.2142)(0.0714,0.2142)1(0.1111,0.3333)(0.1507,0.4523)2(0.1538,0.4615)(0.2118,0.6355)3(0.1904,0.5714)(0.2409

56、,0.7227)4(0.2162,0.6486)(0.2487,0.7463)5(0.2318,0.6956)(0.2499,0.7497)6(0.2406,0.7218)(0.2499,0.7499)7(0.2452,0.7356)8(0.2475,0.7427)9(0.2487,0.7463)10(0.2492,0.7481)11(0.2496,0.7490)12(0.2498,0.7495)13(0.2499,0.7497)14(0.2499,0.7498)15(0.2499,0.7499).由上表可见，用乘子法迭代6次就达到惩罚函数法迭代15次的效果。惩罚因子在惩罚函数法中要增大到15

57、=3276.8, 而在乘子法中只要增大到6=6.4. 因此乘子法不需过分增大惩罚因子，因此，乘子法比惩罚函数法有效。.第四节第四节 复形法复形法无论是无约束最优化还是约束最优化问题，前面介绍的方法无论是无约束最优化还是约束最优化问题，前面介绍的方法均是利用梯度作为工具的。在实际应用中还有一类方法，它均是利用梯度作为工具的。在实际应用中还有一类方法，它在迭代时仅仅涉及目标函数及约束函数的函数值计算。在迭代时仅仅涉及目标函数及约束函数的函数值计算。复形法是求解约束非线性最优化问题的一种重要的直接方法。复形法是求解约束非线性最优化问题的一种重要的直接方法。复形法既可以用于无约束最优化问题，也可以用于

58、约束最优复形法既可以用于无约束最优化问题，也可以用于约束最优化问题。化问题。.引例引例 求解求解22121 21211223142512min ( )10460.( )0( )10( )60( )80( )110f xxxx xxxstg xxg xxg xxg xxg xxx . .在可行域内随机选取在可行域内随机选取k k个点构成初始复形。个点构成初始复形。找出坏点找出坏点x (l)。.求求x (l)关于关于x (0)的的 倍反射倍反射点点x( )= x(0)+ (x(0)-x(l)x( )为反射点，为反射点， 。 计算除最坏点以外的其余点的中点为计算除最坏点以外的其余点的中点为x (0)

59、。.在迭代过程中，在迭代过程中，若反射点不满足若反射点不满足可行性和适用性可行性和适用性，将反射系数减，将反射系数减小，小， 重新求重新求x( )， 使它满足可行使它满足可行性和适用性。性和适用性。.复形的顶点复形的顶点k通常取通常取n+1k2n个。个。方法方法1 1：设计者确定；：设计者确定；方法方法2 2：随机产生：随机产生：1、产生产生k个随机点个随机点 xi= ai +i (bi - ai) i=1,2,.,ni i为为(0，1)区间内产生的均匀分布的随机数，需要区间内产生的均匀分布的随机数，需要n个随机数产个随机数产生一个点生一个点 x (1)。同样，产生其它的随机点。同样，产生其它

60、的随机点x (2)、x (3) 、x (K)。初始复形的构成初始复形的构成.2、将非可行点调入可行域、将非可行点调入可行域判断产生的判断产生的k个随机点是否在可行域内，并重新排列，将个随机点是否在可行域内，并重新排列，将可行点依次排在前面，如有可行点依次排在前面，如有q个顶点个顶点x (1)、x (2)、 x (q)是是可行点，其它可行点，其它k-q个为非可行点。对个为非可行点。对x (q+1)，将其调入可行，将其调入可行域的步骤是：域的步骤是：（1）计算）计算q个点集的中心个点集的中心x (s)；（2）将第）将第q+1点朝着点点朝着点x (s)的方向的方向移动，按下式产生新的移动，按下式产生