《凸优化理论与应用-等式约束优化课件》由会员分享，可在线阅读，更多相关《凸优化理论与应用-等式约束优化课件（14页珍藏版）》请在金锄头文库上搜索。
1、1 1凸优化理论与应用凸优化理论与应用第第9 9章章 等式约束优化等式约束优化2 2等式约束优化问题n问题描述：问题描述：n 为凸函数，且二次连续可微，且为凸函数，且二次连续可微，且n假设最优值假设最优值 存在，则存在，则 为最优解当且仅当存在为最优解当且仅当存在 ，满足（满足（KKT条件）：条件）：3 3例KKT系统：系统：n二次优化：二次优化：nKKT系统可解，则二次优化问题存在最优解。系统可解，则二次优化问题存在最优解。n系数矩阵称为系数矩阵称为KKT矩阵。矩阵。KKT矩阵非奇异当且仅当：矩阵非奇异当且仅当：4 4消去等式约束消去等式约束n方程组方程组 的解集：的解集：n 为方程组的一个
2、特解，为方程组的一个特解， 为为 的零空间范围。的零空间范围。n无约束优化形式：无约束优化形式：n若若 为最优解，则有为最优解，则有5 5对偶问题对偶问题n对偶形式：对偶形式：6 6牛顿法n牛顿减量牛顿减量n 为等式约束优化的可行解，则在为等式约束优化的可行解，则在 附近原问题的二附近原问题的二次近似为：次近似为：n设设 和和 分别为该问题和对偶问题的最优解，则满分别为该问题和对偶问题的最优解，则满足：足：7 7n性质性质2：牛顿减量具有仿射不变性。：牛顿减量具有仿射不变性。牛顿减量n牛顿减量牛顿减量n牛顿减量的性质：牛顿减量的性质：8 8可行下降方向n可行下降方向：设可行下降方向：设 满足方
3、程组满足方程组 。若。若 满足方满足方程组程组 ，则，则 。 称为可行方向。称为可行方向。若对于较小的若对于较小的 ，有，有 ，则，则 为可为可行下降方向。行下降方向。9 9等式约束的牛顿方法nLOOP：n计算计算 及及 ；n若若 则终止退出；则终止退出；n一维线性搜索：计算步长因子一维线性搜索：计算步长因子 ；n迭代：迭代：n初始化：给定初始解初始化：给定初始解 满足满足 ，以及，以及1010消去等式约束的牛顿方法n转换为等式约束下的牛顿方法：转换为等式约束下的牛顿方法：n初始值初始值 ，第，第 次迭代值次迭代值 ；n初始值：初始值：n迭代值：迭代值：1111非可行解为初始点的牛顿法n函数函
4、数 二阶连续可微，因此有二阶连续可微，因此有n 为等式约束优化的非可行解，则增量为等式约束优化的非可行解，则增量 应尽可能应尽可能使使 满足满足KKT条件，即：条件，即：n设设 和和 为为KKT条件的解，即有：条件的解，即有：1212非可行解为初始点的牛顿法n则则KKT条件可表示为：条件可表示为：n令令n设设 为不满足为不满足KKT条件，则其迭代量需满足：条件，则其迭代量需满足：即即1313n当当 且且 时，终止迭代。时，终止迭代。非可行解为初始点的牛顿法nLOOP：n计算计算 和和 ；n回溯一维线性搜索：回溯一维线性搜索：n迭代：迭代：n初始化：给定初始解初始化：给定初始解 及及 ，以及，以及n令令 ；nWhile 1414其中其中 ，且满足，且满足 。KKT系统的求解n1. 分解；分解；n2.若若 非奇异，则可消元：非奇异，则可消元：n3.若若 奇异，则奇异，则KKT系统可改写为：系统可改写为：nKKT系统：系统：
