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