凸优化理论与应用内点法PPT课件.ppt

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