非线性规划的理论与算法

1、第五章非线性规划：理论和算法5.5约束优化我们现在继续讨论更一般的有约束的线性优化问题。特别的，我们考虑一个具有非线性目标函数和(或者)非线性约束的优化问题。我们可以将这种问题表示为下面的一般形式：minxf(x)gi(x)0,i(5.10)gi(x)0,i在本节的末尾，我们假设f和gi,i全部是连续可微的。拉格朗日函数是研究有约束的优化问题的一个重要工具。为了定义这个函数，我们结合每个约束的乘子i称作拉格朗日乘子。对于问题(5.10)拉格朗日函数如下定义：L(x,):f(x)igi(x)(5.11)本质上，我们考虑的是目标函数违反了可行约束时的惩罚函数。选择合适的i,最小化无约束函数Lx,等

2、价于求解约束问题(5.10)。这就是我们对拉格朗日函数感兴趣的最根本的原因。与这个问题相关的最重要问题之一是求解最优问题的充要条件。总之，这些条件称为最优性条件，也是本节的目的。在给出问题(5.10)最优性条件之前，我们先讨论一个叫做正则性的条件，由下面的定义给出：定义5.1：设向量x满足gi(x)0,i和gi(x)0,i。设J是使得gi(x)0等号成立的指标集。x是问题(5.10)约束条件的正则点，如果梯度向量gi(x)(iJ)相互线性无关。在上述定义中与J对应的约束，即满足gMx)0的约束称为在x点处的有效约束。我们讨论第一章提到的两个优化的概念，局部和全局。回顾(5.10)的全局最优解向

3、量x,它是可行的而且满足f(x)f(x)对于所有的x都成立。相比之下，局部最优解x*是可行的而且满足f(x*)f(x)对于x:|xx*|(0)成立。因此局部解一定是它邻域的可行点中最优的。下面我们考虑的最优性条件仅仅判别局部解，则可能是全局最优解，也可能不是。幸运的是，这里存在一类局部最优解和全局解一致的问题一一凸优化问题。附录A中讨论的就是基于凸集的凸优化问题。定理5.1(一阶必要条件)设x是问题(5.10)的局部最小值，假设x是这个问题的约束的正则点。则存在i,i使得：f(x)igi(x)0(5.12)i0,i(5.13)，*、Cigi(x)0,i(5.14)注意，(5.12)左边表达的意

4、思是拉格朗日函数Lx,对每个变量x的梯度。一阶条件在局部最小值，局部最大值及鞍点处满足。当目标函数和约束函数是二次连续可微的时候，可以用函数的曲率排除最大值和鞍点。根据定理5.1,我们考虑拉格朗日函数Lx,和这个函数对每个变量x的海森矩阵，来计算目标函数和约束函数在当前点处的曲率。定理5.2(二阶必要条件)假设函数f和gi(i)都是二次连续可微的。假设*.一、一.一一.x是问题(5.10)局部取小值而且是这个问题的约束正则点。则存在i,i满足(5.12)(5.14)及下面的条件：2-*、2,*、f(x)igi(x)(5.15)在x处有效约束的切线子空间处是半正定的。、.、一.*定理后半部分可以

5、改写为含有效约束的雅阁比矩阵的形式。设A(x)表示x处有效约束的雅阁比矩阵，设N(x)表示基于A(x)的零空间。则定理的最后一个条件等价于下面的条件：T*9_*9*N(x)f(x)igi(x)N(x)(5.16)是半正定的。二阶必要条件并非常常保证给出的解的局部最优性。局部最优性的充分条件更加严格和复杂，因为要考虑到退化的可能性。定理5.3(二阶充分条件)假设函数f和gi都是连续二次可微的。同时假、1*设x是问题(5.10)可行点而且是这个问题的约束正则点。设A(x)表示x处有效约束的雅阁比矩阵，设N(x)表示基于A(x)的零空间。如果存在i,i满足(5.12)一(5.14)及下面的条件:，*

6、、八一Cgi(x)0,1暗本i0(5.17)和T*2*2*N(x)f(x)igi(x)N(x)(5.18)是正定的，则x是问题(5.10)的局部最小值。定理5.1、5.2和5.3中列出的条件称作Karush-Kuhn-Tucker(KKT)条件，以它们的发明者命名的。一些求解约束优化问题的方法表达成一系列简单的可以用一般迭代步骤求出解的简单优化问题。这些“简单”的问题可以是无约束的，此时可以应用我们前面章节介绍的方法求解。我们在5.5.1中考虑这些策略。在其他情况下，这些简单的问题是二次规划且可以应用第七章中的方法求解。这个策略的典型例子是5.5.2中讨论的连续二次规划问题。5.5.1广义简约

7、梯度法在本节中，我们介绍一种求解有约束的非线性规划的方法。这种方法建立在前文讨论的无约束优化法之最速下降法的基础上的。这种方法的思想是利用约束减少变量的个数，然后用最速下降法去求解简化的无约束的问题。线性等式约束首先我们讨论一个约束是线性方程组的例子。minf(x)x；x2x；x4g1(x)x1x24x34x440g2(x)x1x22x32x420在其他变量给定情况下，很容易求解只有两个变量的约束方程。给定Xi,4，令为3*8刈8和x3Xi3应3。把这些变量代入目标函数，然后得到下面简化的形式：22minf(x1,x4)x13为8x48x13x43x4这个简化形式是无约束的，因此可以利用5.4

8、.1节的最速下降法求解。例1：用最速下降法求minf(x)=f=(?-2)2+(y-4)2Matlab程序：M文件:functionR,n=steel(x0,y0,eps)symsx;symsy;f=(x-2)A4+exp(x-2)+(x-2*y)A2;v=x,y;j=jacobian(f,v);T=subs(j(1),x,x0),subs(j(2),y,y0);temp=sqrt(T(1)A2+(T(2)A2);x1=x0;y1=y0;n=0;symskk;while(temp>eps)d=-T;f1=x1+kk*d(1);f2=y1+kk*d(2);fT=subs(j(1),x,f1

9、),subs(j(2),y,f2);fun=sqrt(fT(1)A2+(fT(2)A2);Mini=Gold(fun,0,1,0.00001);x0=x1+Mini*d(1);y0=y1+Mini*d(2);T=subs(j(1),x,x0),subs(j(2),y,y0);temp=sqrt(T(1)A2+(T(2)A2);x1=x0;y1=y0;n=n+1;endR=x0,y0调用黄金分割法：M文件：functionMini=Gold(f,a0,b0,eps)symsx;formatlong;symskk;u=a0+0.382*(b0-a0);v=a0+0.618*(b0-a0);k=0;

10、a=a0;b=b0;array(k+1,1)=a;array(k+1,2)=b;while(b-a)/(b0-a0)>=eps)Fu=subs(f,kk,u);Fv=subs(f,kk,v);if(Fu<=Fv)b=v;v=u;u=a+0.382*(b-a);k=k+1;elseif(Fu>Fv)a=u;u=v;v=a+0.618*(b-a);k=k+1;endarray(k+1,1)=a;array(k+1,2)=b;endMini=(a+b)/2;输入：R,n=steel(0,1,0.0001)R=1.999994136676423.99999120501463n=1非线

11、性等式约束现在考虑用一个线性方程去逼近一个拥有非线性约束问题的可能性，而线性问题就可以像上面的例子那样解决。要了解如何工作的，考虑下面的例子，它和前面提到的例子类似，但是它的约束是非线性的。.一、22minf(x)x1x2x3x42g1(x)x1x24x34x4402g2(x)Xix22x32x420在当前点X我们用Taylor级数逼近约束方程：g(x)g(x)g(x)xx于是：xixi_x2x2gi(x)(xix24x34x44)(2xi,1,4,4)_x3x3x4x4八一，一22xixix24x34x4(xi4)0和g2(x)xiX22x3又4乂4(x：2)0广义简约梯度法(GRG)的思想

12、是求解一系列子问题，每个子问题可以利用约束的线性逼近。在算法的每一步迭代中，利用先前获得的点重新计算线性化约束的点。一般来说，即线性化的一个性质是在使约束是线性逼近的，但每一步迭代获得值也是逐步逼近最优点的。最优点，线性化的问题和原问题有相同的解。使用GRG的第一步是选择一个初值。假设我们开始设x00,8,3,0,而这个值恰好逼近公式，我们构造的首个逼近问题如下：minf(x)x2x2x2x4gi(x)x24x34x440g2(x)kx22&20程序思路与例i相似，具体参考例i程序。5.5约束优化现在我们这个逼近问题的等式约束，用其他变量表示其中的两个变量。不妨选择x2和x3,即得:I

13、-x22x14x48和x3-2x432把这些表达式代入目标函数，获得简化的问题：22Iminf(xi,x4)%(2xi4x48)xi2x43x42求解这个无约束的最小化问题，得到xi0.375x40.96875W代入上面表达式,得：x24.875x3i.25。因此GRG方法的第一步迭代产生了一个新点1X1(0.375,4.875,1.25,0.96875)继续这个求解过程，在新点上我们重新线性化约束函数，利用获得的线性方程组，把其中两个变量用其他变量表示，然后代入目标函数，就可以得到新的简化问题，求解这个新的简化问题得到新的点X2,依此类推。利用停止准则|xk1Xk|T其中T=0.0025。我

14、们得到结果如下表5.7.k(班丁点由EW-F0(0.000,-8,000,3.000.0.000)L0003.7291(-0.375,-4.875,1,250,0.069)-2,2030.5722(-0.423,*5.131,1,619,0,620)-L7110.3533(-0.458,-4.792.L537t0,609)-LG100.0224i-0.478,-4.802,1,534,0,610)-L6110.0155(-0.488,-4.013.l,534t0X10)4,612(1.0086(-0.494,-4,018,1,534,0,610)-1,6120.004f(4),497,-4,8

15、21.L534,(LC10)-L612(1,0028(-0,498,4网L534,0.610)-1,612一*,一一、把这个结果同最优解x(0.500,4.825,1.534,0.610)匕较，其目标值是1.612。k观察表5.7,注意到当k1或k2时，函数f(x)的值有时比最小值小，这是怎么回事呢？原因是通过GRG方法计算获得的点xk通常不满足约束条件。它们只对这些约束条件的线性逼近可行。现在我们讨论如何在一个不可行的点使用GRG方法：第一阶段问题是构建一个满足约束条件的点。第一阶段的目标函数是违反约束的绝对值总和。而第一阶段问题的约束都是不违反约束的。假设我们在点x01,1,0,1开始计算

16、，这个点不满足第一个约束，但满足第二个约束，所以第一阶段问题是：2min为x24x34x442x1x22x32x420一旦通过解决第一阶段问题获得一个适宜的解，那么上面阐述的方法就可以用来求最优解。线性不等式约束最后，我们讨论GRG是怎样像解决等式问题那样解决有不等式约束的问题。在每次迭代中，只有严格满足不等式约束的量才能进入线性方程组，以消除变量(这些不等式约束通常被认为是有效的)。这个过程是复杂的，由于为了得到好的结果，在当前点的每一个不等式约束都有被舍弃的可能。我们在下面的例子中说明了这一点。1252minf(Xi,X2)(Xi)(X2-)22Xx20x10x20x22图5.5广义简约梯

17、度算法的过程这个问题的可行集合显示在图5.5中。图中的可行箭头表示由每个约束指向的可行的超平面。假设我们从x°(1,0)开始。这一点满足所有约束条件。从图5.5可以看出：xix20,为0,x22三个约束条件是无效的，而约束x20是有效的。我们必须决定x2是否应该留在它的下界还是允许它离开边界。f(x°)2xi01,2x051,5。这表明如果我们沿方向d0f(x°)1,5移动，f减少的最多，即减少x1增大x2因为这个方向朝向可行区域内部，我们决定从边界释放x2。新的点变成x1x00d0o其中00。这个约束引入了0的一个上限，也就是00.8333。接下来我们通过线性搜

18、索来确定0在这个范围之内的最优值。结果是00.8333,从而x10.8333,0.8333;参见图5.5。现在，我们重复这个过程：约束x1x20开始起作用，其他约束失效。因为活动约束不是一个简单的上下限约束，我们引入一个剩余变量x3,然后将其中之一用其余变量表示。代入x1x2x3,我们得到如下化简的优化问题minfx2,x315X2一220x22X30在(X2,X3)10.8333,0简约梯度为f(x2,x3)2x22x312x25,2x22x312.667,0.667因此f在2.667,0.667方向降幅最大，也就是要增大x2并减小x3。但是x3已经到达其下界，我们无法再减小它。因此我们保持

19、x3在它的下界处，即我们沿方向d12.667,0到达新的点(x2,x3)2(x2,x3)11d1。沿这个方向的线性搜索给出10.25,(x2,x3)21.5,0。接下来仍然是该约束有效，所以我们仍然在X2和X3的空间中。在(x2,x3)21.5,0处的梯度f(x2,x3)0,2与当前解X2的边界线垂直，且指向可行区域的外部，因而f不可能进一步减小。于是我们找到了最优解。对应于最初的变量空间，这个最优解就是为1.5和x21.5。这就是一些广泛使用的非线性规划求解方法，例如Excel的SOLVER,GINO,CONOPT,GRG2以及一些其他的方法用来求解非线性规划问题的方法。具体求解时只需附加一

20、些额外细节，例如线性搜索时的Newton-Raphson方向等。同线性规划相比，能够在一个合理的计算时间内解决的问题通常规模比较小，并且求得的结果也可能不是特别精确。另外，可行集合或目标函数潜在的非凸性会导致求解结果是局部最优的而远非全局解。因此在解释非线性规划的结果时需要更加小心。5.5.2序列二次规划考虑一般的非线性最优化问题(5.20)minxf(x)gi(x)0,igi(x)Qi为了解决这个问题，有人试图利用可得到的较好的算法解决更有条理、更简单的二次规、k划(参见第七章)。这是连续二次方程背后的思想。在当前可行点x,问题(5.20)是由一个二次规划来近似的：拉格朗日函数的近似二次方程

21、可以像近似的线性约束一样计算。可以得到如下的二次方程规划问题：其中BkkTminf(x)x_/k、Tgi(x)xkTgi(x)x:L(xk,k),是拉格朗日函数1k-xx2k、gi(x)k、gi(x)(5.11)TBkxxk0,i0,i(5.21)的海森矩阵，k为当前估计的拉格朗日乘数。例如我们在第七章讨论的这个问题可以用解决二次方程规划问题的一种特殊算法来解,内点方法。二次规划的最优解是用来确定搜索方向。那么线性搜索或信赖域程序是为了确定下一个迭代。也许思考序列二次规划的最好方式是将其作为求解有约束条件问题的牛顿法的优化版的扩展。回想一下，牛顿方法的优化版使用目标函数的二次逼近，定义这个逼近

22、的最小值作为下一次迭代值，这很像我们描述的SQP方法。的确，对于一个无约束问题，二次规划与牛顿法是相同的。对于约束问题，在解决SQP时的二次规划问题的最优性条件相当于在当前迭代下牛顿法直接指向的原来问题的最优化条件。序列二次规划迭代直到该问题收敛。就像牛顿法一样，二次规划方法是非常强大，尤其是当运用线性搜索或信赖域方法来处理非线性和非凸性。我们推荐读者翻阅BoggsandTolle14和NocedalandWright55来进一步了解二次规划方法。5.6非光滑优化：次梯度方法在这一部分，我们考虑无约束非线性规划的形式minfx当x>,x2,xn并且f是一个不可微的凸函数。由于在此情况下没有定义梯度，所以无法获得基于梯度的最优条件。然而，梯度的概念可被推广如下。f在x*点的次梯度是向量s*s*,s2,sn使*一s(xx)f(x)f(x)对任意x都成立。当函数f是可微的，次梯度和梯度是相同的；当函数f在x点处不可微，通常在x处有