第八章约束优化最优性条件VIP免费

第八章约束优化最优性条件§8.1约束优化问题一、问题基本形式（8.1）特别地，当为二次函数，而约束是线性约束时，称为二次规划。记，称之为可行域（约束域）。，，称是在处的积极约束的指标集。积极约束也称有效约束，起作用约束或紧约束（activeconstraintsorbindingconstraints）。应该指出的是，如果是（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）集合非空。则。证明：先证设是中任一向量，令是子空间的正交补中的标准正交基。（由，故与正交，因而上述生成子空间的维数为）。考虑下面以为参数的非线性方程组（8.11）它将确定以为参数的一个隐函数。由于在处，上述方程组的Jacobi矩阵非奇异，且是方程组的解。根据隐函数定理，对充分小的，必存在解且满足。事实上，将方程组确定的隐函数对求导，有令，得上述方程组得系数矩阵非奇异，故有唯一解，又显然方程组的解，因而有。下证当充分小时，。事实上，由是由方程组（8.11）确定的隐函数，由方程组（8.11）的第一式知，当时，由的定义，有故当充分小时，有最后一个不等式是由于时，当时，由。故当充分小（）时，有。因此有。现...