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