最优化理论与算法(第九章)

第九章二次规划§9.1二次规划问题称形如（9.1）的非线性规划问题为二次规划问题。对二次规划问题，有如下的最优性条件。定理9.1设是（9.1）的局部极小点，则必存在乘子，使得（9.2）且对于一切满足于：的，都有。注：1）上述定理的前后两部分分别对应于一、二阶的必要条件；2）满足上述条件的，都有；3）当约束条件均为线性函数时，容易证明：及上面给出的是二次规划的必要性条件，下面给出充分性条件。定理9.2设是K-T点，是相应的Lagrange乘子，如果对满足（9.3）的一切非零向量，都有，则是（9.1）的局部严格极小点。注：条件组（9.3）表示的正好是的条件，因此这个定理实际上是上一节二阶充分性条件在二次规划情形的特殊表述。对二次规划问题还有如下充分必要条件定理9.3设是（9.1）的可行解，则是一局部最小点的充要条件是：存在乘子，使得（9.2）满足，且对一切满足（9.3）的都有注：这个定理的证明可参见韩继业《二次规划理论与算法》，曲阜师范学院学报，1985年第一期1~8。特别地，当为正定或半正定时，目标函数为凸函数，二次规划为凸规划。因此任何K-T点必为二次规划的全局极小点，此时求解（9.1）等价于求解（9.4）其中，，，§9.2对偶性质二次规划问题：（9.5）的Wolfe对偶为：(9.6)在正定时，若令，则（9.6）可改写为：（9.7）假定是（9.5）的可行解，而是对偶问题（9.7）的可行解，则有：由于时，，及，并且正定，即得：等式成立当且仅当：同时。定理9.4（对偶定理）设是原问题（9.5）的可行解，而是对偶问题（9.7）的可行解，则总有：；若存在（9.5）的可行点，（9.7）的可行点，使得：，则，分别为原问题与对偶问题的最优解。由于当且仅当：且时，。从而有下面定理：定理9.5设正定，则（9.5）的可行点是最优解的充要条件是存在对偶问题（9.7）的可行解满足：，及。定理9.6设正定，则原问题不可行当且仅当对偶问题无界。证明：1）若原问题可行，则由知对偶问题有界；2）若原问题不可行，利用Farkas引理，可构造一无界的对偶可行解，故对偶问题无界。我们已经看到，原问题的Lagrange函数与对偶问题有密切联系，实际上它正是对偶形式（9.6）的目标函数。求解问题（9.5）求解上节的K-T问题（9.4）求Lagrange函数在区域上的稳定点。由的Hessian矩阵为利用可知恰为个正特征值，而且它的负特征值的个数正好为的秩。因而，的稳定点一般是一个鞍点，下面证明的确是的鞍点。事实上，我们有这里是对偶问题（9.7）的可行域。而对任何，若令则是（9.7）的可行点，而且（由于对给定的，是的凸函数，的最优解可由解出得，同时注意到即可得到上式。）设是K-T问题（9.4）的解，令，则知是对偶问题（9.7）的可行点。于是和都有：即：故是的鞍点。反之，我们还可以证明，若是的鞍点，则必为原始问题（9.1）的极小点。上面讨论给出了鞍点问题解与原极小化问题解之间的关系：定理9.7设正定，则是原始问题极小点的充要条件是：存在，使得对一切，和一切，都有。§9.3等式约束问题问题形式：（假定）（9.8）一、消去法记，则可改写为解出得将其代人目标函数得无约束问题：（9.9）最优性条件：1）若正定，2）若半正定，借助广义逆，有（任意，解不唯一）3）若有负特征值，则问题无界。注：问题（9.9）可利用无约束优化问题的各种算法求解。二、广义消去法设是域空间的一组线性无关的向量（即的一组基），是的一组线性无关向量，显然与互为正交补。若记，则有：非奇异，而。事实上，由于与的列向量组均为的基，故有：(为两组基之间的过渡矩阵)进一步有：由列满秩知是正定矩阵，再由可逆，故有非奇异。而由于中列向量均在中，故有。显然，，可表示为。特别地，对满足的有得因此将此代入目标函数并略去常数项，得到：（9.10）称为既约Hessian矩阵，而为既约梯度。三、Lagrange乘子法直接求Lagrange函数的稳定点：（9.11）§9.4积极集法（有效集法）一、算法的理论基础积极集法是通过求解有限多个等式约束二次规划问题，来求解一般约束二次规划问题，下面引理是其理论基础。定理9.8设是二次规划问题（9.1）的局部极小点，则也必是问题（9.12）的局部极小点；反之，若是（9.12）的K-T点，且还是原问题（9.1）的可行点。相应Lagrange乘子满足：，。则也是原问题的K-T点。证明：设是原问题的解，若它不是（9.12）的极小点，那么必有充分靠近的点使得，而当充分靠近时，也必是原问题的可行点，这与是最优点矛盾。另一方面，设是原问题的可行点，且满足（9.12）的K-T条件，则存在，使得且还有，。进一步地，当时，令，则有且满足，，由可行，即知是原问题的K-T点。积极集法是一个可行点法，在迭代过程中，始终保持迭代点可行。而每次迭代求解一个只含等式约束的二次规划。如果等式约束问题的解是原约束问题的可行解，则进一步检验，是否满足。若满足，则停止计算，否则，可去掉一约束重新求解约束问题。若等式约束二次规划之解不是原问题的可行解，则需要增加约束，然后重新求解等式约束问题。二、算法的迭代步骤1．给出初始可行点，令。2．求解等式约束问题得，若，则转3.若（），算法停止；令，置，，转4.3.令，；若，转4；否则，找到使得，令。4．转2.三、算法的有限终止性定理9.8设是由积极集法产生的点列，若对任何都有线性无关，则算法必有限终止于问题的K-T