最优化理论与算法(第八章).docVIP

第八章 约束优化最优性条件 §8.1 约束优化问题 一、 问题基本形式 （8.1） 特别地，当为二次函数，而约束是线性约束时，称为二次规划。 记 ，称之为可行域（约束域）。 ，， 称是在处的积极约束的指标集。积极约束也称有效约束，起作用约束或紧约束（active constraints or binding constraints）。 应该指出的是，如果是（1）的局部最优解，且有某个，使得 则将此约束去掉，仍是余下问题的局部最优解。 事实上，若不是去掉此约束后所得问题的局部极小点，则意味着，存在，使得，且，这里满足新问题的全部约束。注意到当充分小时，由的连续性，必有，由此知是原问题的可行解，但，这与是局部极小点矛盾。 因此如果有某种方式，可以知道在最优解处的积极约束指标集，则问题可转化为等式的约束问题： （8.2） 一般地，这个问题较原问题（8.1）要简单，但遗憾的是，我们无法预先知道。 §8.2 一阶最优性条件 一、几种可行方向 定义8.1 设，是一非零向量。如果存在，使得， 则称是处的一个可行方向。在处的的所有可行方向的集合记为 定义8.2 设，若满足： （8.3） （8.4） 则称是处的线性化可行方向。在处的的所有线性化可行方向的集合记为。 定义8.3 设，，若存在序列和，使得对一切，有，且，，则称是处的序列可行方向。在处的的所有序列可行方向的集合记为。 引理8.4 设，且所有约束函数都在处均可微，则有： （8.5） 证明： 对任何，由定义8.1可知，存在使得 ， 令 ，和 则显然有 ，且 ， 因而，由的任意性，即知。 又对任何，如果，则显然。假定，由定义8.3，存在序列和，使得，且和。由有， 在上两式的左右两端除以，然后令趋于无穷，即得满足 因而，由的任意性，即知，证毕。 二、一阶最优性条件 引理8.5 设是问题（8.1）的局部极小点，若和都在处可微，则必有，。 证明：对任何，存在序列和，使得 ，且和。 由，而且是局部极小点，故对充分大的有： 由上式可知，，引理于是证毕。 引理8.5表明：在极小点处，所有的序列可行方向都不是下降方向。 引理8.6 （Farkas引理）线性方程组和不等式组 无解的充要条件是存在实数和非负实数使得： （8.9） 证明：假定（8.9）式成立，且，那么对任意满足（8.6），（8.7）的，都有 因而不等式组无解。 另一方面，若不存在实数，非负实数，使（8.9）式成立。考虑集合： 易证是中的一个闭凸锥，且。由凸集分离定理：必存在，使得 （是一常数） 由于，所以。又由于是锥，故，有，从而 因而必有 再由 有 类似可得 ， 亦即 由以上讨论可见，是不等式组（8.6）——（8.8）的一个解。 注： 这里介绍的Farkas引理，以及其他教科书上给出的择一定理、Motzkin定理与Gordan定理，均是由凸集分离定理得出的同一类定理，它们在导出约束最优性条件方面起着至关重要的作用。 定理8.7（Karush-Kuhn-Tucker定理）设是（8.1）的局部极小点，若，则必存在，使得： （8.10） 证明：由引理8.5，，有，因而 ，有。由的定义，知 无解。由Farkas引理，知存在和，使得 再令 ，即得，且满足。 注：1) 称为Lagrange函数，称为Lagrange乘子； 2）（8.10）通常称为问题（8.1）的K-T-T条件（或K-T条件），而满足（8.10）的点称为K-T-T点（或K-T点），（8.10）中的第二式称为互补松弛条件； 3）当约束规范性条件不成立时，局部极小点不一定是K-T点。 三、的一些充分条件 定理8.8 若所有的都是线性函数，则。 证明：，有 取，，那么当时，有 当时，有 而当时，由知：当充分大时（），有 。 即有 这表明 即 再由，即得，证毕。 定理8.8 若1) 线性无关； 2）集合非空。 则。 证明：先证 设是中任一向量，令是子空间的正交补中的标准正交基。（由，故与正交，因而上述生成子空间的维数为）。 考虑下面以为参数的非线性方程组