Ch11 内点法.pdfVIP

/ 来自我的同事 LPJ 内点法 凸优化第十一章 2014年1月20 日 / 提纲  不等式约束的极小化问题  对数障碍函数和中心路径  障碍方法  可行性和阶段1方法  自和谐条件下的复杂性分析  广义不等式问题  原对偶内点法 / 不等式约束的极小化问题 （1） 其中 是二次可微的凸函数； / 不等式约束的极小化问题  假设：目标函数、不等式约束函数是凸函数，并二 次可微，等式约束是仿射函数。最优原变量及最优 对偶变量满足KKT条件。  Newton方法用来解决线性等式约束优化问题，目 标函数二次可微，通过reducing为一系列线性等式 约束二次问题来解决。  而内点法用来解决具有线性等式和不等式约束问题， 通过reducing为一系列线性等式约束问题来解决。 / 对数障碍函数和中心路径  把不等式约束问题近似转换成等式约束问题  障碍方法的基本思想是用以下函数近似示性函数 / 对数障碍函数和中心路径  对数障碍函数 对任意t0,我们用 表示上式的解，称 ,t0为 中心点，将这些点的集合定义为问题（1）的中心路径。 / 对数障碍函数和中心路径  中心路径的重要性质：每个中心点产生对偶可行解， 因而给出最优值的一个下界。  无约束极小化方法:保证达到预定精度 / 障碍方法  选择 / 可行性和阶段1方法  定义：障碍方法需要一个严格可行的初始点，如果不知道这样一个可 行点，在应用障碍方法之前需要一个预备阶段称为阶段1.  基本的阶段1方法  考虑 的一组不等式和等式方程  是凸的，具有连续的二阶导数  阶段1优化问题：  极小化不可行值的最大值  极小化不可行值的和 / 可行性和阶段1方法  采用不可行初始点Newton方法求解阶段1问题  当问题不可行时没有好的停止准则，残差不能收敛 到0 / 自和谐条件下的复杂性分析 自和谐假设 对于所有的 ， 是闭的自和谐性函数 水平集有界。 如果 是线性的或二次的，那么对于 ，下式是 自和谐的。 / 自和谐条件下的复杂性分析 / 自和谐条件下的复杂性分析  中心点步骤的Newton迭代次数  总的Newton迭代次数 / 自和谐条件下的复杂性分析 /