非线性规划的理论与算法

第五章非线性规划：理论和算法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）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;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非线性等式约束现在考虑用一个线性方程去逼近一个拥有非线性约束问题的可能性，而线性问题就可以像上面的例子那样解决。要了解如何工作的，考虑下面的例子，它和前面提到的例子类似，但是它的约束是非线性的。在当前点我们用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时的二次规划问题的最优性条件相当于在当前迭代下牛顿法直接指向的原来问题的最优化条件。序列二次规划迭代直到该问题收敛。就像牛顿法一样，二次规划方法是非常强大，尤其是当运用线性搜索或信赖域方法来处理非线性和非凸性。我们推荐读者翻阅BoggsandTolle[14]和NocedalandWright[55]来进一步了解二次规划方法。5.6非光滑优化：次梯度方法在这一部分，我们考虑无约束非线性规划的形式当并且是一个不可微的凸函数。由于在此情况下没有定义梯度，所以无法获得基于梯度的最优条件。然而，梯度的概念可被推广如下。在点的次梯度是向量使对任意都成立。当函数是可微的，次梯度和梯度是相同的；当函数在点处不可微，通常在处有许多次梯度。例如，考虑含有一个变量的凸函数 从图5.6可明显看出这个函数在处是不可微的，并且很容易验证任意使得的向量是在点处的次梯度。其中的一些次梯度以及它们所定义的线性逼近可由图5-6所示。请注意每个函数的次梯度在一点处定义了一个函数的切线，而这些切线永远待在函数图像的下边——这是次梯度定义的属性。考虑一个不可微的凸函数。在点处取得最小值当且仅当在点有一个为零的次梯度。在上述例子中，0是在点处的一个次梯度，因此我们得到的最小值点。图5.6最速下降法可以通过计算任何次梯度方向且使用相反的方向扩展到不可微的凸函数来进行下一步。尽管次梯度方向不总是上升的方向，不过可以选择适当的步长保证收敛到最佳点。一般的次梯度方法可以表述为如下：1.初始化：从任一点开始，设；2.迭代：计算函数在点处的一个次梯度。如果或趋近于0，停止。否则，让（表示一个步长，并进行下一次迭代。几种选取步长的方法已在文献中讲过。为了保证收敛到最优点，步长需要非常缓慢的递减（例如