凸优化理论与应用_内点法.ppt

信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 凸优化理论与应用 第10章 内点法 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 则优化问题具有强对偶性，其对偶问题亦可解。 不等式约束优化问题 问题描述： 为凸函数，且二次连续可微，且 假设最优值 存在； 假设存在 ，满足严格不等式条件 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 不等式约束的消去 示性函数消去不等式约束： 不具备良好的连续可微性，考虑用对数阀函数来近似替代。 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 对数阀函数 对于 ， 是 的光滑逼近。且当 时，有 令 带示性函数的优化问题可近似为： 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 对数阀函数 对数阀函数 是凸函数 对数阀函数二阶连续可微，导数为： 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 中心线 对数阀近似问题的等价问题： 最优解为 ，则最优解集 称为优化问题的中心线。 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 中心线的对偶点 设 ，则存在 满足KKT条件： 令 则 是拉格朗日函数 的最小值解。 为对偶问题的可行解。 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 中心线的对偶点 设 为原始问题的最优值，则有： 因此，当 时，有 。 为原始问题的 次优解。 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 阀方法 终止条件：若 ，则终止退出。 初始化：给定严格可行解 ， ， ，及 LOOP： 中心步骤：以 为初始点求解优化问题 ， 迭代： 更新 ： 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 收敛性分析 外层循环迭代次数： 中心步骤实质为一个无约束或等式约束优化问题，其收敛性分析与相应优化问题的收敛性分析结果一致。 设 为对数阀问题的可行解，则牛顿方向 和对偶问题的解 满足： 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 例： LP问题： 初始值： 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 第一阶段方法 对于不等式约束的优化问题，如何寻找严格可行解或验证不可解？ 求解优化问题： 该问题最优解存在，假设最优值为 当 时，存在严格可行解； 当 时，原始问题不可解； 当 时，无法准确确定。 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 第一阶段方法 优化目标为逐项之和： 对于固定的 ， 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 寻找严格可行解的方法 牛顿法求解优化问题： 迭代终止条件：当前解 ，即终止迭代，严格可行解为 。 * 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn *