非线性规划方案的理论与算法.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=Matlab程序：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 (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文献：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(FuFv) 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.42 3.63n = 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 方向等。同线性规划相比，可以在一种合理计算时间内解决问题普通规模比较小，并且求得成果也也许不是特别精准。此外，可行集合或目的函数潜在非凸性会导致求解成果是局部最优而远非全局解。因而在解释非线性规划成果时需要更加小心。5.5.2序列二次规划考虑普通非线性最优化问题 （5.20）为理解决这个问题，有人试图运用可得到较好算法解决更有条理、更简朴二次规划（参见第七章）。这是持续二次方程背后思想。在当前可行点，问题（5.20）是由一种二次规划来近似：拉格朗日函数近似二次方程可以像近似线性约束同样计算。可以得到如下二次方程规划问题：其中，是拉格朗日函数（5.11）海森矩阵，为当前预计拉格朗日乘数。这个问题可以用解决二次方程规划问题一种特殊算法来解，例如咱们在第七章讨论内点办法。二次规划最优解是用来拟定搜索方向。那么线性搜索或信赖域程序是为了拟定下一种迭代。也许思考序列二次规划最佳方式是将其作为求解有约束条件问题牛顿法优化版扩展。回忆一下，牛顿办法优化版使用目的函数二次逼近，定义这个逼近最小值作为下一次迭代值，这很像咱们描述SQP办法。确，对于一种无约束问题，二次规划与牛顿法是相似。对于约束问题，在解决SQP时二次规划问题最优性条件相称于在当前迭代下牛顿法直接指向本来问题最优化条件。序列二次规划迭代直到该问题收敛。就像牛顿法同样，二次规划办法是非常强大，特别是当运用线性搜索或信赖域办法来解决非线性和非凸性。咱们推荐读者翻阅Boggs and Tolle 14和Nocedal and Wright 55来进一步理解二次规划办法。5.6非光滑优化：次梯度办法在这一某些，咱们考虑无约束非线性规划形式 当并且是一种不可微凸函数。由于在此状况下没有定义梯度，因此无法获得基于梯度最优条件。然而，梯度概念可被推广如下。在点次梯度是向量使对任意都成立。当函数是可微，次梯度和梯度是相似；当函数在点处不可微，普通在处有许多次梯度。例如，考虑具有一种变量凸函数从图5.6可明显看出这个函数在处是不可微，并且很容易验证任意使得向量是在点处次梯度。其中某些次梯度以及它们所定义线性逼近可由图5-6所示。请注意每个函多次梯度在一点处定义了一种函数切线，而这些切线永远待在函数图像下边这是次梯度定义属性。考虑一种不可微凸函数。在点处获得最小值当且仅当在点有一种为零次梯度。在上述例子中，0是在点处一种次梯度，因而咱们得到最小值点。图5.6最速下降法可以通过计算任何次梯度方向且使用相反方向扩展到不可微凸函数来进行下一步。尽管次梯度方向不总是上升方向，但是可以选取恰当步长保证收敛到最佳点。普通次梯度办法可以表述为如下：1.初始化：从任一点开始，设；2.迭代 ：计算函数在点处一种次梯度。如果或趋近于0，停止。否则，让（表达一种步长，并进行下一次迭代。几种选用步长办法已在文献中讲过。为了保证收敛到最长处，步长需要非常缓慢递减（例如使得成立）。但是缓慢减少导致缓慢收敛到最长处。在实际中，为了提高收敛速度，惯用到下面办法:从开始，如果持续（通惯用7或8）次迭代后观测目的值没有改进，则将步长减半。当人们想迅速得到最优解时，或者发现精准地最优解不是那么重要（这是在整数规划中应用，用次梯度最优化办法来迅速获得分枝定界算法中界限）时，这种办法很适当。有了这种思想，在实际中经惯用一种终结准则是一种最大迭代次数（例如200）而不是为或趋近于。咱们将在第12章看到次梯度最优化办法是如何应用在一种构建基金指数模型中。