非线性规划的理论与算法

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

2、罚函数。选择合适的i，最小化无约束 函数Lx,等价于求解约束问题(5.10 )。这就是 我们对拉格朗日函数感兴趣的最根本的原因。与这个问题相关的最重要问题之一是求解最 优问题的充要条件。总之，这些条件称为最优性 条件，也是本节的目的。在给出问题(5.10 )最优性条件之前，我们先 讨论一个叫做正则性的条件，由下面的定义给 出：定义5.1 :设向量x满足g") °,i和gi(x) 0，i 。 设J是使得gi(x) 0等号成立的指标集。x是问题（5.10 ）约束条件的正则点，如果梯度向量gi（x）J ）相互线性无关。在上述定义中与J对应的约束，即满足ga 0的约束称为在x点处的

3、有效约束。我们讨论第一章提到的两个优化的概念，局部和全局。回顾（5.10）的全局最优解向量x*，它 是可行的而且满足f（x*） f（x）对于所有的X都成立。 相比之下，局部最优解x*是可行的而且满足 f（x*）f（x）对于x:|x x*|（ 0）成立。因此局部解一定是它邻域的可行点中最优的。 下面我们考虑 的最优性条件仅仅判别局部解，则可能是全局最 优解，也可能不是。幸运的是，这里存在一类局 部最优解和全局解一致的问题一一凸优化问题。 附录A中讨论的就是基于凸集的凸优化问题。定理5.1 （一阶必要条件）设x*是问题（5.10） 的局部最小值，假设x*是这个问题的约束的正则 点。贝U存在i, i

4、 使得：f（x*）i gi（x*） 0i（5.12 ）i 0,i（5.13）igi（x*）0,i(5.14 )注意，(5.12 )左边表达的意思是拉格朗日函 数Lx,对每个变量x的梯度。一阶条件在局部最 小值，局部最大值及鞍点处满足。当目标函数和 约束函数是二次连续可微的时候，可以用函数的 曲率排除最大值和鞍点。根据定理 5.1，我们考 虑拉格朗日函数Lx,和这个函数对每个变量x的 海森矩阵，来计算目标函数和约束函数在当前点 处的曲率。定理5.2 (二阶必要条件)假设函数f和gi (i )都是二次连续可微的。假设X是问题 (5.10 )局部最小值而且是这个问题的约束正则 点。则存在i，i 满足

5、(5.12)( 5.14)及 下面的条件：2 * 2 * f(X ) i gi(x ) i(5.15) 在X*处有效约束的切线子空间处是半正定的。定理后半部分可以改写为含有效约束的雅阁 比矩阵的形式。设A(x*)表示X*处有效约束的雅阁 比矩阵，设N(x*)表示基于A(x*)的零空间。则定理 的最后一个条件等价于下面的条件：T *2*2*N (x ) f(x ) i gi(x ) N(x ) i(5.16)是半正定的。二阶必要条件并非常常保证给出的解的局部 最优性。局部最优性的充分条件更加严格和复 杂，因为要考虑到退化的可能性。定理5.3 (二阶充分条件)假设函数f和5，都是连续二次可微的。同

6、时假设X是问题(5.10 )可行点而且是这个问题的约束正则点。设A(x*)表示x*处有效约束的雅阁比矩阵，设N(x*)表示基于 a(x*)的零空间。如果存在i，i 满足(5.12) (5.14 )及下面的条件：gi(x*) 0,i 暗示 i 0(5.17)和NT(x )2f(x ) i 2gi(x ) N(x )i(5.18)是正定的，则x是问题(5.10 )的局部最小值。定理5.1、5.2和5.3中列出的条件称作 Karush-Kuh n-Tucker(KKT)条件，以它们的发 明者命名的。一些求解约束优化问题的方法表达成一系列 简单的可以用一般迭代步骤求出解的简单优化 问题。这些“简单”的

7、问题可以是无约束的，此 时可以应用我们前面章节介绍的方法求解。我们在中考虑这些策略。在其他情况下，这些 简单的问题是二次规划且可以应用第七章中的 方法求解。这个策略的典型例子是中讨论 的连续二次规划问题。广义简约梯度法在本节中，我们介绍一种求解有约束的非线性 规划的方法。这种方法建立在前文讨论的无约束 优化法之最速下降法的基础上的。 这种方法的思 想是利用约束减少变量的个数，然后用最速下降 法去求解简化的无约束的问题。线性等式约束首先我们讨论一个约束是线性方程组的例子。minf(x) x1 x2 x3 x4g1(x) x1 x2 4x3 4x44 0g2(x) x1 x2 2x3 2x4 2

8、0在其他变量给定情况下，很容易求解只有两个变 量的约束方程。给定xi，X4，令x2 3为 8& 8 和氏3x4 3。把这些变量代入目标函数，然后得到下面简化的 形式：2 2min f(x，x4) x 3x 8x4 8 x, 3x4 3 x4这个简化形式是无约束的，因此可以利用 5.4.1 节的最速下降法求解。例 1:用最速下降法求 min f(x)= f=(?- 2)2+(y-4)2Matlab程序：M文件： fun cti on R, n=steel(xO,yO,eps) syms x;syms y; f=(x-2)A4+exp(x-2)+(x-2*y)A2; v=x,y;j=jac

9、obian( 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; 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)A2+(fT(2)A2); Mini=Gold(fu n,0,1,0.00001); x0=x1+Mi ni *d(1);y0=y1+Mi ni *d(2); T=subs(j(1),x,x0

10、),subs(j (2) ,y,y0); temp=sqrt(T(1)A2+(T(2)A2);x1= x0;y1=y0;n=n+1;endR=xO,yO调用黄金分割法：M文件：fun ctio n Mi ni=Gold(f,aO,bO,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)/(bO-aO)>=eps)Fu=subs(f,kk,u);Fv=subs(f,kk,v); if(Fu

11、v=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;endMin i=(a+b)/2;输入：R,n =steel(0,1,0.0001)R =1.999994136676423.99999120501463n =1非线性等式约束现在考虑用一个线性方程去逼近一个拥有非 线性约束问题的可能性，而线性问题就可以像上 面的例子那样解决。要了解如何工作的，考虑下 面的例子，它和前面提到的例子类似，但是它的 约束是非线性的。m

12、in f (x) x； x2 x； x4g/x) n X2 4x3 4x4 4 0g2(x) x X2 2x3 2x： 2 0在当前点x我们用Taylor级数逼近约束方程：一一Tg(x) g(x) g(x) x x于是：x1 x1- -x2 x2gx)(捲 X2 4x3 4x4 4) (2x1,1,4,4)-X3 X3X4 X422x1x1 x2 4x3 4x4 (x14)0和广义简约梯度法(GRG )的思想是求解一系 列子问题，每个子问题可以利用约束的线性逼 近。在算法的每一步迭代中，利用先前获得的点 重新计算线性化约束的点。一般来说，即使约束 是线性逼近的，但每一步迭代获得值也是逐步逼 近

13、最优点的。线性化的一个性质是在最优点，线性化的问题和原问题有相同的解。使用GRG的第一步是选择一个初值。假设 我们开始设x0 0,8,3,0，而这个值恰好逼近公式， 我们构造的首个逼近问题如下：min f (x) x2 x2 xf x4g (x) X2 4% 4x4 4 0g2 (x) X X2 2x3 2 0程序思路与例1相似，具体参考例1程序。5.5约束优化现在我们这个逼近问题的等式约束，用其他变量表示其中的两个变量。不妨选择X2和X3，即得：X2 2xi 4x( 8 禾口 x3 1 x, 2x4 3把这些表达式代入目标函数，获得简化的问题：22 1mi nf(x,x4) x, (2x,

14、4x4 8) -x, 2x4 3 x42求解这个无约束的最小化问题，得到, 0.96875再代入上面表达式，得：X2 4.875X3 1.25。因此GRG方法的第一步迭代产生了一 个新点 X1 ( 0.375, 4.875,1.25,0.96875)继续这个求解过程，在新点上我们重新线性化 约束函数，利用获得的线性方程组，把其中两个 变量用其他变量表示，然后代入目标函数，就可 以得到新的简化问题，求解这个新的简化问题得 到新的点X2，依此类推。利用停止准则|xk1 Xk| T 其中 T= 0.0025。我们得到结果如下表5.7.k(吃临澹胁)心)|xfr -x*|0(0.000, -8.000

15、. 3.000, 0.000)1.0003.7291(-0.375, -4.875, 1.250, 0.969)-2,2030.5722(-0.423, -5.131, L619, 0.620)-1,7110.3533(-0,458, -4.792. 1,537, 0,609)-1,6100.0224(-(L478, -4.002, 1,534, O.GIO)-1,6110.0155(-0.488, -4.813> 1,534, 0.610)-L6120.008(i(j)p494, -4,818? l,534t 0.610)-L612o.m(.(L497,-4,821. L534t 0,

16、010)-L6120.0028(-0.498, 4.823, 1,534, 0,610)-1,612把这个结果同最优解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

17、,0,1开始计算，这个点 不满足第一个约束，但满足第二个约束，所以第 一阶段问题是：2min x1 x2 4x3 4x4 42 为 x2 2x3 2x420一旦通过解决第一阶段问题获得一个适宜的 解，那么上面阐述的方法就可以用来求最优解。 线性不等式约束最后，我们讨论GRG是怎样像解决等式问 题那样解决有不等式约束的问题。在每次迭代 中，只有严格满足不等式约束的量才能进入线性 方程组，以消除变量（这些不等式约束通常被认 为是有效的）。这个过程是复杂的，由于为了得 到好的结果，在当前点的每一个不等式约束都有 被舍弃的可能。我们在下面的例子中说明了这一 点。1 25 2m"f（xi，x2

18、）（xi 2）（x2 2）x1 x20x10x20x22图5.5广义简约梯度算法的过程这个问题的可行集合显示在图5.5中。图中的可行箭头表示由每个约束指向的可行的超平面 假设我们从X。(1,0)开始。这一点满足所有约束条 件。从图5.5可以看出：X1 X2 0,凶0, X， 2三个约 束条件是无效的，而约束X, 0是有效的。我们必 须决定X,是否应该留在它的下界还是允许它离开 边界。f (X0) 2X10 1,2x0 51, 5。这表明如果我们沿方向d0f (x0) 1, 5移动，f减少的最多，即减少X,增大X,。因为这个方向朝 向可行区域内部，我们决定从边界释放X,。新的点变成x1 x0 0

19、d0其中0 0。这个约束引入了 0的 一个上限，也就是0 0.8333。接下来我们通过线性 搜索来确定。在这个范围之内的最优值。结果是0 0.8333，从而 X10.8333,0.8333 ；参见图 5.5。现在，我们重复这个过程：约束Xi施0开始起 作用，其他约束失效。因为活动约束不是一个简 单的上下限约束，我们引入一个剩余变量X3，然后将其中之一用其余变量表示。代入x1 x, X3，我 们得到如下化简的优化问题min f x2,x3x,X30x22X30f (x2, x3) 2x2 2x3 1 2x25,2x2 2x312.667,0.667因此f在2.667, 0.667方向降幅最大，也

20、就是要增 大X2并减小X3。但是X3已经到达其下界，我们 无法再减小它。因此我们保持X3在它的下界处，即我们沿方向 d12.667,0 到达新的点(X2,X3)2 (X2,X3)1 1d1。沿这个方向 的线性搜索 给出1 0.25， (X2,X3)21.5,0。接下来仍然是该约束有效，所以我们仍然在X2和X3的空间中。在(X2,X3)2 1.5,0处 的梯度f(x2,X3) 0,2与当前解X2的边界线垂直，且 指向可行区域的外部，因而f不可能进一步减小。 于是我们找到了最优解。对应于最初的变量空 间，这个最优解就是X! 1.5和冷1.5。这就是一些广泛使用的非线性规划求解方法， 例女口Exce

21、l 的 SOLVER, GINO,CONOPT,GRG2以及一些其他的方法用来求解 非线性规划问题的方法。具体求解时只需附加一 些额外细节，例如线性搜索时的 Newton-Raphson方向等。同线性规划相比，能 够在一个合理的计算时间内解决的问题通常规 模比较小，并且求得的结果也可能不是特别精 确。另外，可行集合或目标函数潜在的非凸性会 导致求解结果是局部最优的而远非全局解。因此在解释非线性规划的结果时需要更加小心。序列二次规划考虑一般的非线性最优化问题minx f (x)gi(x) 0,i(5.20)gi(x) 0,i为了解决这个问题，有人试图利用可得到的较 好的算法解决更有条理、更简单的

22、二次规划（参 见第七章）。这是连续二次方程背后的思想。在 当前可行点xk，问题（5.20）是由一个二次规划 来近似的：拉格朗日函数的近似二次方程可以像 近似的线性约束一样计算。可以得到如下的二次方程规划问题：k Tkmin f (x ) x x/ k XTkgi(x ) x xgi(x ) x xxk TBkgi(xk) 0, igi(xk) 0, ixk(5.21)其中Bk 2xL（xk, k），是拉格朗日函数（5.11）的海 森矩阵，k为当前估计的拉格朗日乘数。这个问题可以用解决二次方程规划问题的一 种特殊算法来解，例如我们在第七章讨论的内点 方法。二次规划的最优解是用来确定搜索方向。 那

23、么线性搜索或信赖域程序是为了确定下一个 迭代。也许思考序列二次规划的最好方式是将其作 为求解有约束条件问题的牛顿法的优化版的扩 展。回想一下，牛顿方法的优化版使用目标函数 的二次逼近，定义这个逼近的最小值作为下一次 迭代值，这很像我们描述的 SQP方法。的确， 对于一个无约束问题，二次规划与牛顿法是相同 的。对于约束问题，在解决 SQP时的二次规划 问题的最优性条件相当于在当前迭代下牛顿法 直接指向的原来问题的最优化条件。序列二次规划迭代直到该问题收敛。 就像牛顿 法一样，二次规划方法是非常强大，尤其是当运 用线性搜索或信赖域方法来处理非线性和非凸 性。我们推荐读者翻阅 Boggs and Tolle 14和 Nocedal and Wright 55来进一步了解二次规划 方法。5.6非光滑优化：次梯度方法在这一部分，我们考虑无约束非线性规划的形 式min f x当x xz, x并且f是一个不可微的凸 函数。由于在此情况下没有定义梯度，所以无法 获得基于梯度的最优条件。然而，梯度的概念可 被推广如下。f在x*点的次梯度是向量s s*,s2,： 使s*(x x*) f(x) f(x*)对任意x都成立。当函数f是可微的，次梯度和梯度是相同的； 当函数f在x点处不可微，通常在x处有许多次梯 度。例如，考虑含有一个变量的凸函数f (x)