非线性规划方案的理论与算法

ii第五章非线性规划：理论和算法5.5约束优化咱们当前继续讨论更普通有约束线性优化问题。特别,咱们考虑一种具备非线性目的函数和（或者）非线性约束优化问题。咱们可以将这种问题表达为下面普通形式：minxf(x)g(x)0,i(5.10)ig(x)0,ii在本节末尾，咱们假设f和g，i所有是持续可微。i拉格朗日函数是研究有约束优化问题一种重要工具。为了定义这个函数，咱们结合每个约束乘子i——称作拉格朗日乘子。对于问题（5.10）拉格朗日函数如下定义：L(x,):f(x)g(x)（5.11）i本质上，咱们考虑是目的函数违背了可行约束时惩罚函数。选取适当i，最小化无约束函数Lx,等价于求解约束问题（5.10）。这就是咱们对拉格朗日函数感兴趣最主线因素。与这个问题有关最重要问题之一是求解最优问题充要条件。总之，这些条件称为最优性条件，也是本节目。在给出问题（5.10）最优性条件之前，咱们先讨论一种叫做正则性条件，由下面定义给出：定义5.1：设向量x满足g(x)0,i和g(x)0,i。设J是使得g(x)0iii等号成立指标集。x是问题（5.10）约束条件正则点，如果梯度向量g(x)（iJ）i互相线性无关。在上述定义中与J相应约束，即满足g(x)0约束称为在x点处有效约束。i咱们讨论第一章提到两个优化概念，局部和全局。回顾（5.10）全局最优解向量x*，它是可行并且满足f(x*)f(x)对于所有x都成立。相比之下，局部最优解x*是可行并且满足f(x*)f(x)对于x:xx*（0）成立。因而局部解一定是它邻域可行点中最优。下面咱们考虑最优性条件仅仅鉴别局部解，则也许是全局最优解，也也许不是。幸运是，这里存在一类局部最优解和全局解一致问题——凸优化问题。附录A中讨论就是基于凸集凸优化问题。定理5.1（一阶必要条件）设x*是问题（5.10）局部最小值，假设x*是这个问题约束正则点。则存在i，i∪使得：f(x*)g(x*)0ii（5.12）i∪0,i（5.13）ig(x*)0,i（5.14）ii注意，（5.12）左边表达意思是拉格朗日函数Lx,对每个变量x梯度。一阶条件在局部最小值，局部最大值及鞍点处满足。当目的函数和约束函数是二次持续可微时候，可以用函数曲率排除最大值和鞍点。依照定理5.1，咱们考虑拉格朗日函数Lx,和这个函数对每个变量x海森矩阵，来计算目的函数和约束函数在当前点处曲率。定理5.2（二阶必要条件）假设函数f和g（i）都是二次持续可微。假设x*i是问题（5.10）局部最小值并且是这个问题约束正则点。则存在i，i满足（5.12）—（5.14）及下面条件：2f(x*)2gii(x*)（5.15）i∪在x*处有效约束切线子空间处是半正定。定理后半某些可以改写为具有效约束雅阁比矩阵形式。设A(x*)表达x*处有效约束雅阁比矩阵，设N(x*)表达基于A(x*)零空间。则定理最后一种条件等价于下面条件：NT(x*)2f(x*)2g(x*)N(x*)（5.16）iii∪是半正定。二阶必要条件并非经常保证给出解局部最优性。局部最优性充分条件更加严格和复杂，由于要考虑到退化也许性。定理5.3（二阶充分条件）假设函数f和g，i都是持续二次可微。同步假设x*i是问题（5.10）可行点并且是这个问题约束正则点。设A(x*)表达x*处有效约束雅阁比矩阵，设N(x*)表达基于A(x*)零空间。如果存在，i满足（5.12）—（5.14）及下i面条件：g(x*)0,i暗示0（5.17）ii和NT(x*)2f(x*)2g(x*)N(x*)（5.18）iii是正定，则x*是问题（5.10）局部最小值。定理5.1、5.2和5.3中列出条件称作Karush-Kuhn-Tucker(KKT)条件，以它们创造者命名。某些求解约束优化问题办法表达到一系列简朴可以用普通迭代环节求出解简朴优化问题。这些“简朴”问题可以是无约束，此时可以应用咱们前面章节简介办法求解。咱们在5.5.1中考虑这些方略。在其她状况下，这些简朴问题是二次规划且可以应用第七章中办法求解。这个方略典型例子是5.5.2中讨论持续二次规划问题。5.5.1广义简约梯度法在本节中，咱们简介一种求解有约束非线性规划办法。这种办法建立在前文讨论无约束优化法之最速下降法基本上。这种办法思想是运用约束减少变量个数，然后用最速下降法去求解简化无约束问题。线性等式约束一方面咱们讨论一种约束是线性方程组例子。minf(x)x2xx2x1g(x)xx234x44x40112g(x)xx21232x342x420在其她变量给定状况下，很容易求解只有两个变量约束方程。给定x1，x4，令x3x218x48和x3x13x43。把这些变量代入目的函数，然后得到下面简化形式：minf(x,x)x23x8x8x3x32x14114144这个简化形式是无约束，因而可以运用5.4.1节最速下降法求解。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);例1：用最速下降法求minf(x)=f=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;xendarray(k+1,1)=a;array(k+1,2)=b;endMini=(a+b)/2;输入：[R,n]=steel(0,1,0.0001)R=1.423.63n=1非线性等式约束当前考虑用一种线性方程去逼近一种拥有非线性约束问题也许性，而线性问题就可以像上面例子那样解决。要理解如何工作，考虑下面例子，它和前面提到例子类似，但是它约束是非线性。minf(x)x2xx2x12g(x)x2x34x44x40112g(x)xx21232x342x2204在当前点x咱们用Taylor级数逼近约束方程：Tg(x)g(x)g(x)xx于是：xx11g(x)(xx1124x34x44)(2x1x,1,4,4)2x2x332xxx1124x34x4(x24)01xx44和g(x)xx2122x3xx44(x22)04广义简约梯度法（GRG）思想是求解一系列子问题，每个子问题可以运用约束线性逼近。在算法每一步迭代中，运用先前获得点重新计算线性化约束点。普通来说，虽然约束是线性逼近，但每一步迭代获得值也是逐渐逼近最长处。线性化一种性质是在最长处，线性化问题和原问题有相似解。使用GRG第一步是选取一种初值。假设咱们开始设x00,8,3,0，而这个值正好逼近公式，咱们构造首个逼近问题如下：minf(x)x2xx2x1g(x)x1224x334x4440g(x)xx2122x320程序思路与例1相似，详细参照例1程序。5.5约束优化当前咱们这个逼近问题等式约束，用其她变量表达其中两个变量。不妨选取x和x，23即得：x2x4x8和x1x2x32143214把这些表达式代入目的函数，获得简化问题：12minf(x,x)x2(2x4x8)x2x3x141142144求解这个无约束最小化问题，得到x10.375,x40.96875再代入上面表达式，得：x4.875,x231.25。因而GRG办法第一步迭代产生了一种新点X1(0.375,4.875,1.25,0.96875)继续这个求解过程，在新点上咱们重新线性化约束函数，运用获得线性方程组，把其中两个变量用其她变量表达，然后裔入目的函数，就可以得到新简化问题，求解这个新简化问题得到新点X2，依此类推。运用停止准则Xk1XkT其中T=0.0025。咱们得到成果如下表5.7.把这个成果同最优解x*(0.500,4.825,1.534,0.610)比较，其目的值是1.612。观测表5.7，注意到当k1或k2时，函数f(xk)值有时比最小值小，这是怎么回事呢？因素是通过GRG办法计算获得点xk普通不满足约束条件。它们只对这些约束条件线性逼近可行。当前咱们讨论如何在一种不可行点使用GRG办法：第一阶段问题是构建一种满足约束条件点。第一阶段目的函数是违背约束绝对值总和。而第一阶段问题约束都是不违背约束。假设咱们在点x01,1,0,1开始计算，这个点不满足第一种约束，但满足第二个约束，因此第一阶段问题是：minx2x4x4x412xx1232x342x2204一旦通过解决第一阶段问题获得一种适当解，那么上面阐述办法就可以用来求最优解。线性不等式约束最后，咱们讨论GRG是如何像解决等式问题那样解决有不等式约束问题。在每次迭代中，只有严格满足不等式约束量才干进入线性方程组，以消除变量（这些不等式约束普通被以为是有效）。这个过程是复杂，由于为了得到好成果，在当前点每一种不等式约束均有被舍弃也许。咱们在下面例子中阐明了这一点。15minf(x,x)(x)2(x)2121222xx012x01x02x22图5.5广义简约梯度算法过程这个问题可行集合显示在图5.5中。图中可行箭头表达由每个约束指向可行超平面。假设咱们从x0(1,0)开始。这一点满足所有约束条件。从图5.5可以看出：xx120,x10,x22三个约束条件是无效，而约束x20是有效。咱们必要决定x与2否应当留在它下界还是容许它离开边界。f(x0)2x01,2x051,5。12这表白如果咱们沿方向d0f(x0)1,5移动，f减少最多，即减少x1增大x2。由于这个方向朝向可行区域内部，咱们决定从边界释放x2。新点变成x1x00d0其中00。这个约束引入了0一种上限，也就是00.8333。接下来咱们通过线性搜索来拟定0在这个范畴之内最优值。成果是00.8333，从而x10.8333,0.8