08凸优化理论与应用_等式约束优化.ppt

信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn 凸优化理论与应用 第8章 等式约束优化 等式约束优化问题 例 消去等式约束 对偶问题 牛顿法 牛顿减量 可行下降方向 等式约束的牛顿方法 消去等式约束的牛顿方法 非可行解为初始点的牛顿法 非可行解为初始点的牛顿法 非可行解为初始点的牛顿法 KKT系统的求解 * * 问题描述： 为凸函数，且二次连续可微，且 假设最优值 存在，则 为最优解当且仅当存在 ，满足（KKT条件）： KKT系统： 二次优化： KKT系统可解，则二次优化问题存在最优解。 系数矩阵称为KKT矩阵。KKT矩阵非奇异当且仅当： 方程组 的解集： 为方程组的一个特解， 为 的零空间范围。 无约束优化形式： 若 为最优解，则有 对偶形式： 牛顿减量 为等式约束优化的可行解，则在 附近原问题的二次近似为： 设 和 分别为该问题和对偶问题的最优解，则满足： 性质2：牛顿减量具有仿射不变性。 牛顿减量 牛顿减量的性质： 可行下降方向：设 满足方程组 。若 满足方程组 ，则 。 称为可行方向。若对于较小的 ，有 ，则 为可行下降方向。 LOOP： 计算 及 ； 若 则终止退出； 一维线性有哪些信誉好的足球投注网站：计算步长因子 ； 迭代： 初始化：给定初始解 满足 ，以及 转换为等式约束下的牛顿方法： 初始值 ，第 次迭代值 ； 初始值： 迭代值： 函数 二阶连续可微，因此有 为等式约束优化的非可行解，则增量 应尽可能使 满足KKT条件，即： 设 和 为KKT条件的解，即有： 则KKT条件可表示为： 令 设 为不满足KKT条件，则其迭代量需满足： 即 当 且 时，终止迭代。 LOOP： 计算 和 ； 回溯一维线性有哪些信誉好的足球投注网站： 迭代： 初始化：给定初始解 及 ，以及 令 ； While *