非线性规划的理论与算法详解.docx

第五章 非线性规划：理论和算法 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广义简约梯度法 在本节中，我们介绍一种求解有约束的非线性规划的方法。这种方法建立在前文讨论的无约束优化法之最速下降法的基础上的。这种方法的思想是利用约束减少变量的个数，然后用最速下降法去求解简化的无约束的问题。 线性等式约束 首先我们讨论一个约束是线性方程组的例子。 在其他变量给定情况下，很容易求解只有两个变量的约束方程。给定，，令 和。 把这些变量代入目标函数，然