非线性规划的理论与算法.doc

第五章 非线性规划：理论和算法5.5 约束优化我们现在继续讨论更一般的有约束的线性优化问题特别的,我们考虑一个具有非线性目标函数和（或者）非线性约束的优化问题我们可以将这种问题表示为下面的一般形式： (5.10)在本节的末尾，我们假设和，全部是连续可微的拉格朗日函数是研究有约束的优化问题的一个重要工具为了定义这个函数，我们结合每个约束的乘子——称作拉格朗日乘子对于问题（5.10）拉格朗日函数如下定义： （5.11）本质上，我们考虑的是目标函数违反了可行约束时的惩罚函数选择合适的，最小化无约束函数等价于求解约束问题（5.10）这就是我们对拉格朗日函数感兴趣的最根本的原因与这个问题相关的最重要问题之一是求解最优问题的充要条件总之，这些条件称为最优性条件，也是本节的目的在给出问题（5.10）最优性条件之前，我们先讨论一个叫做正则性的条件，由下面的定义给出：定义5.1：设向量满足和设是使得等号成立的指标集是问题（5.10）约束条件的正则点，如果梯度向量（）相互线性无关在上述定义中与对应的约束，即满足的约束称为在点处的有效约束。

我们讨论第一章提到的两个优化的概念，局部和全局回顾（5.10）的全局最优解向量，它是可行的而且满足对于所有的都成立相比之下，局部最优解是可行的而且满足对于（）成立因此局部解一定是它邻域的可行点中最优的下面我们考虑的最优性条件仅仅判别局部解，则可能是全局最优解，也可能不是幸运的是，这里存在一类局部最优解和全局解一致的问题——凸优化问题附录A中讨论的就是基于凸集的凸优化问题定理5.1 （一阶必要条件）设是问题（5.10）的局部最小值，假设是这个问题的约束的正则点则存在，使得： （5.12） （5.13） （5.14）注意，（5.12）左边表达的意思是拉格朗日函数对每个变量的梯度一阶条件在局部最小值，局部最大值及鞍点处满足当目标函数和约束函数是二次连续可微的时候，可以用函数的曲率排除最大值和鞍点根据定理5.1，我们考虑拉格朗日函数和这个函数对每个变量的海森矩阵，来计算目标函数和约束函数在当前点处的曲率。

定理5.2（二阶必要条件）假设函数和（）都是二次连续可微的假设是问题（5.10）局部最小值而且是这个问题的约束正则点则存在，满足（5.12）—（5.14）及下面的条件： （5.15）在处有效约束的切线子空间处是半正定的定理后半部分可以改写为含有效约束的雅阁比矩阵的形式设表示处有效约束的雅阁比矩阵，设表示基于的零空间则定理的最后一个条件等价于下面的条件： （5.16）是半正定的二阶必要条件并非常常保证给出的解的局部最优性局部最优性的充分条件更加严格和复杂，因为要考虑到退化的可能性定理5.3（二阶充分条件）假设函数和，都是连续二次可微的同时假设是问题（5.10）可行点而且是这个问题的约束正则点设表示处有效约束的雅阁比矩阵，设表示基于的零空间如果存在，满足（5.12）—（5.14）及下面的条件：暗示 （5.17）和 （5.18）是正定的，则是问题（5.10）的局部最小值定理5.1、5.2和5.3中列出的条件称作Karush-Kuhn-Tucker (KKT) 条件，以它们的发明者命名的。

一些求解约束优化问题的方法表达成一系列简单的可以用一般迭代步骤求出解的简单优化问题这些“简单”的问题可以是无约束的，此时可以应用我们前面章节介绍的方法求解我们在5.5.1中考虑这些策略在其他情况下，这些简单的问题是二次规划且可以应用第七章中的方法求解这个策略的典型例子是5.5.2中讨论的连续二次规划问题5.5.1广义简约梯度法在本节中，我们介绍一种求解有约束的非线性规划的方法这种方法建立在前文讨论的无约束优化法之最速下降法的基础上的这种方法的思想是利用约束减少变量的个数，然后用最速下降法去求解简化的无约束的问题线性等式约束首先我们讨论一个约束是线性方程组的例子在其他变量给定情况下，很容易求解只有两个变量的约束方程给定，，令 和把这些变量代入目标函数，然后得到下面简化的形式：这个简化形式是无约束的，因此可以利用5.4.1节的最速下降法求解例1：用最速下降法求min f(x)=f=(x-2)2+(y-4)2Matlab程序：M文件：function [R,n]=steel(x0,y0,eps)syms x;syms y;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;syms kk;while (temp>eps) 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文件：function Mini=Gold(f,a0,b0,eps)syms x;format long;syms kk;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(Fu>Fv) a=u; u=v; v=a+0.618*(b-a); k=k+1; end array(k+1,1)=a;array(k+1,2)=b;endMini=(a+b)/2;输入：[R,n]=steel(0,1,0.0001)R = 1.99999413667642 3.99999120501463n = 1非线性等式约束现在考虑用一个线性方程去逼近一个拥有非线性约束问题的可能性，而线性问题就可以像上面的例子那样解决。

要了解如何工作的，考虑下面的例子，它和前面提到的例子类似，但是它的约束是非线性的在当前点我们用Taylor级数逼近约束方程：于是：和广义简约梯度法（GRG）的思想是求解一系列子问题，每个子问题可以利用约束的线性逼近在算法的每一步迭代中，利用先前获得的点重新计算线性化约束的点一般来说，即使约束是线性逼近的，但每一步迭代获得值也是逐步逼近最优点的线性化的一个性质是在最优点，线性化的问题和原问题有相同的解 使用GRG的第一步是选择一个初值假设我们开始设，而这个值恰好逼近公式，我们构造的首个逼近问题如下： 程序思路与例1相似，具体参考例1程序 5.5 约束优化 现在我们这个逼近问题的等式约束，用其他变量表示其中的两个变量不妨选择和，即得：和把这些表达式代入目标函数，获得简化的问题：求解这个无约束的最小化问题，得到再代入上面表达式，得：因此GRG方法的第一步迭代产生了一个新点继续这个求解过程，在新点上我们重新线性化约束函数，利用获得的线性方程组，把其中两个变量用其他变量表示，然后代入目标函数，就可以得到新的简化问题，求解这个新的简化问题得到新的点，依此类推利用停止准则其中我们得到结果如下表5.7.把这个结果同最优解比较，其目标值是。

观察表5.7，注意到当或时，函数的值有时比最小值小，这是怎么回事呢？原因是通过GRG方法计算获得的点通常不满足约束条件它们只对这些约束条件的线性逼近可行现在我们讨论如何在一个不可行的点使用GRG方法：第一阶段问题是构建一个满足约束条件的点第一阶段的目标函数是违反约束的绝对值总和而第一阶段问题的约束都是不违反约束的假设我们在点开始计算，这个点不满足第一个约束，但满足第二个约束，所以第一阶段问题是：一旦通过解决第一阶段问题获得一个适宜的解，那么上面阐述的方法就可以用来求最优解线性不等式约束 最后，我们讨论GRG是怎样像解决等式问题那样解决有不等式约束的问题在每次迭代中，只有严格满足不等式约束的量才能进入线性方程组，以消除变量（这些不等式约束通常被认为是有效的）这个过程是复杂的，由于为了得到好的结果，在当前点的每一个不等式约束都有被舍弃的可能我们在下面的例子中说明了这一点图5.5广义简约梯度算法的过程这个问题的可行集合显示在图5.5中图中的可行箭头表示由每个约束指向的可行的超平面假设我们从开始这一点满足所有约束条件从图5.5可以看出：,,三个约束条件是无效的，而约束是有效的我们必须决定是否应该留在它的下界还是允许它离开边界。

这表明如果我们沿方向 移动，减少的最多，即减少增大因为这个方向朝向可行区域内部，我们决定从边界释放新的点变成 其中这个约束引入了的一个上限，也就是接下来我们通过线性搜索来确定在这个范围之内的最优值结果是，从而；参见图 5.5现在，我们重复这个过程：约束开始起作用，其他约束失效因为活动约束不是一个简单的上下限约束，我们引入一个剩余变量 ，然后将其中之一用其余变量表示代入，我们得到如下化简的优化问题在简约梯度为因此 在方向降幅最大，也就是要增大 并减小但是 已经到达其下界，我们无法再减小它因此我们保持 在它的下界处，即我们沿方向到达新的点沿这个方向的线性搜索给出，接下来仍然是该约束有效，所以我们仍然在和的空间中在处的梯度与当前解的边界线垂直，且指向可行区域的外部，因而不可能进一步减小于是我们找到了最优解对应于最初的变量空间，这个最优解就是和这就是一些广泛使用的非线性规划求解方法，例如 Excel 的 SOLVER, GINO, CONOPT,GRG2以及一些其他的方法用来求解非线性规划问题的方法具体求解时只需附加一些额外细节，例如线性搜索时的 Newton-Raphson 方向等同线性规划相比，能够在一个合理的计算时间内解决的问。