非线性规划的理论与算法

第五章非线性规划：理论和算法5.5约束优化我们现在继续讨论更一般的有约束的线性优化问题。特别的,我们考虑一个具有非线性目标函数和（或者）非线性约束的优化问题。我们可以将这种问题表示为下面的一般形式：ixgixgxfiix,0)(,0)()(min(5.10)在本节的末尾，我们假设f和ig，i全部是连续可微的。拉格朗日函数是研究有约束的优化问题的一个重要工具。为了定义这个函数，我们结合每个约束的乘子i——称作拉格朗日乘子。对于问题（5.10）拉格朗日函数如下定义：iiixgxfxL)()(:),(（5.11）本质上，我们考虑的是目标函数违反了可行约束时的惩罚函数。选择合适的i，最小化无约束函数,Lx等价于求解约束问题（5.10）。这就是我们对拉格朗日函数感兴趣的最根本的原因。与这个问题相关的最重要问题之一是求解最优问题的充要条件。总之，这些条件称为最优性条件，也是本节的目的。在给出问题（5.10）最优性条件之前，我们先讨论一个叫做正则性的条件，由下面的定义给出：定义5.1：设向量x满足ixgi,0)(和ixgi,0)(。设J是使得0)(xgi等号成立的指标集。x是问题（5.10）约束条件的正则点，如果梯度向量)(xgi（iJ）相互线性无关。在上述定义中与J对应的约束，即满足0)(xgi的约束称为在x点处的有效约束。我们讨论第一章提到的两个优化的概念，局部和全局。回顾（5.10）的全局最优解向量*x，它是可行的而且满足)()(*xfxf对于所有的x都成立。相比之下，局部最优解*x是可行的而且满足)()(*xfxf对于*:xxx（0）成立。因此局部解一定是它邻域的可行点中最优的。下面我们考虑的最优性条件仅仅判别局部解，则可能是全局最优解，也可能不是。幸运的是，这里存在一类局部最优解和全局解一致的问题——凸优化问题。附录A中讨论的就是基于凸集的凸优化问题。定理5.1（一阶必要条件）设*x是问题（5.10）的局部最小值，假设*x是这个问题的约束的正则点。则存在i，i使得：0)()(**iiixgxf（5.12）ii,0（5.13）ixgii,0)(*（5.14）注意，（5.12）左边表达的意思是拉格朗日函数,Lx对每个变量x的梯度。一阶条件在局部最小值，局部最大值及鞍点处满足。当目标函数和约束函数是二次连续可微的时候，可以用函数的曲率排除最大值和鞍点。根据定理5.1，我们考虑拉格朗日函数,Lx和这个函数对每个变量x的海森矩阵，来计算目标函数和约束函数在当前点处的曲率。定理5.2（二阶必要条件）假设函数f和ig（i）都是二次连续可微的。假设*x是问题（5.10）局部最小值而且是这个问题的约束正则点。则存在i，i满足（5.12）—（5.14）及下面的条件：iiixgxf)()(*2*2（5.15）在*x处有效约束的切线子空间处是半正定的。定理后半部分可以改写为含有效约束的雅阁比矩阵的形式。设)(*xA表示*x处有效约束的雅阁比矩阵，设)(*xN表示基于)(*xA的零空间。则定理的最后一个条件等价于下面的条件：)()()()(**2*2*xNxgxfxNiiiT（5.16）是半正定的。二阶必要条件并非常常保证给出的解的局部最优性。局部最优性的充分条件更加严格和复杂，因为要考虑到退化的可能性。定理5.3（二阶充分条件）假设函数f和ig，i都是连续二次可微的。同时假设*x是问题（5.10）可行点而且是这个问题的约束正则点。设)(*xA表示*x处有效约束的雅阁比矩阵，设)(*xN表示基于)(*xA的零空间。如果存在i，i满足（5.12）—（5.14）及下面的条件：ixgi,0)(*暗示0i（5.17）和)()()()(**2*2*xNxgxfxNiiiT（5.18）是正定的，则*x是问题（5.10）的局部最小值。定理5.1、5.2和5.3中列出的条件称作Karush-Kuhn-Tucker(KKT)条件，以它们的发明者命名的。一些求解约束优化问题的方法表达成一系列简单的可以用一般迭代步骤求出解的简单优化问题。这些“简单”的问题可以是无约束的，此时可以应用我们前面章节介绍的方法求解。我们在5.5.1中考虑这些策略。在其他情况下，这些简单的问题是二次规划且可以应用第七章中的方法求解。这个策略的典型例子是5.5.2中讨论的连续二次规划问题。5.5.1广义简约梯度法在本节中，我们介绍一种求解有约束的非线性规划的方法。这种方法建立在前文讨论的无约束优化法之最速下降法的基础上的。这种方法的思想是利用约束减少变量的个数，然后用最速下降法去求解简化的无约束的问题。线性等式约束首先我们讨论一个约束是线性方程组的例子。2212341123421234min()()4440()2220fxxxxxgxxxxxgxxxxx在其他变量给定情况下，很容易求解只有两个变量的约束方程。给定1x，4x，令214388xxx和31433xxx。把这些变量代入目标函数，然后得到下面简化的形式：2214114144min(,)38833fxxxxxxxx这个简化形式是无约束的，因此可以利用5.4.1节的最速下降法求解。例1：用最速下降法求minf(x)=f=Matlab程序：M文件：function[R,n]=steel(x0,y0,eps)symsx;symsy;f=(x-2)^4+exp(x-2)+(x-2*y)^2;v=[x,y];j=jacobian(f,v);T=[subs(j(1),x,x0),subs(j(2),y,y0)];temp=sqrt((T(1))^2+(T(2))^2);x1=x0;y1=y0;n=0;symskk;while(tempeps)d=-T;f1=x1+kk*d(1);f2=y1+kk*d(2);fT=[subs(j(1),x,f1),subs(j(2),y,f2)];fun=sqrt((fT(1))^2+(fT(2))^2);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))^2+(T(2))^2);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;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(FuFv)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非线性等式约束现在考虑用一个线性方程去逼近一个拥有非线性约束问题的可能性，而线性问题就可以像上面的例子那样解决。要了解如何工作的，考虑下面的例子，它和前面提到的例子类似，但是它的约束是非线性的。221234211234221234min()()4440()2220fxxxxxgxxxxxgxxxxx在当前点x我们用Taylor级数逼近约束方程：()()()Tgxgxgxxx于是：0)4(442)4,4,1,2()444()(214321144332211143211xxxxxxxxxxxxxxxxxxxxg和0)2(2)(24443212xxxxxxxg广义简约梯度法（GRG）的思想是求解一系列子问题，每个子问题可以利用约束的线性逼近。在算法的每一步迭代中，利用先前获得的点重新计算线性化约束的点。一般来说，即使约束是线性逼近的，但每一步迭代获得值也是逐步逼近最优点的。线性化的一个性质是在最优点，线性化的问题和原问题有相同的解。使用GRG的第一步是选择一个初值。假设我们开始设00,8,3,0x，而这个值恰好逼近公式，我们构造的首个逼近问题如下：22123412342123min()()4440()220fxxxxxgxxxxgxxxx程序思路与例1相似，具体参考例1程序。5.5约束优化现在我们这个逼近问题的等式约束，用其他变量表示其中的两个变量。不妨选择2x和3x，即得：214248xxx和3141232xxx把这些表达式代入目标函数，获得简化的问题：22141141441min(,)(248)232fxxxxxxxx求解这个无约束的最小化问题，得到140.375,0.96875xx再代入上面表达式，得：234.875,1.25xx。因此GRG方法的第一步迭代产生了一个新点1(0.375,4.875,1.25,0.96875)X继续这个求解过程，在新点上我们重新线性化约束函数，利用获得的线性方程组，把其中两个变量用其他变量表示，然后代入目标函数，就可以得到新的简化问题，求解这个新的简化问题得到新的点2X，依此类推。利用停止准则1kkXXT其中=0.0025T。我们得到结果如下表5.7.把这个结果同最优解*(0.500,4.825,1.534,0.610)x比较，其目标值是1.612。观察表5.7，注意到当1k或2k时，函数()kfx的值有时比最小值小，这是怎么回事呢？原因是通过GRG方法计算获得的点kx通常不满足约束条件。它们只对这些约束条件的线性逼近可行。现在我们讨论如何在一个不可行的点使用GRG方法：第一阶段问题是构建一个满足约束条件的点。第一阶段的目标函数是违反约束的绝对值总和。而第一阶段问题的约束都是不违反约束的。假设我们在点01,1,0,1x开始计算，这个点不满足第一个约束，但满足第二个约束，所以第一阶段问题是：2123421234min4442220xxxxxxxx一旦通过解决第一阶段问题获得一个适宜的解，那么上面阐述的方法就可以用来求最优解。线性不等式约束最后，我们讨论GRG是怎样像解决等式问题那样解决有不等式约束的问题。在每次迭代中，只有严格满足不等式约束的量才能进入线性方程组，以消除变量（这些不等式约束通常被认为是有效的）。这个过程是复杂的，由于为了得到好的结果，在当前点的每一个不等式约束都有被舍弃的可能。我们在下面的例子中说明了这一点。2212121212215min(,)()()220002fxxxxxxxxx图5.5广义简约梯度算法的过程这个问题的可行集合显示在图5.5中。图中的可行箭头表示由每个约束指向的可行的超平面。假设我们从)0,1(0x开始。这一点满足所有约束条件。从图5.5可以看出：120xx,10x,22x三个约束条件是无效的，而约束20x是有效的。我们必须决定2x是否应该留在它的下界还是允许它离开边界。00012()21,251,5fxxx。这表明如果我们沿方向00()1,5dfx移动，f减少的最多，即减少1x增