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

1、可编辑可编辑1 1凸优化理论与应用凸优化理论与应用第第1010章章 内点法内点法可编辑可编辑2 2n则优化问题具有强对偶性，其对偶问题亦可解。则优化问题具有强对偶性，其对偶问题亦可解。不等式约束优化问题n问题描述：问题描述：0minimize ( )subject to ( )0,1,., ifxf ximAxbn 为凸函数，且二次连续可微，且为凸函数，且二次连续可微，且( )if x,rankp nARpnApn假设最优值假设最优值 存在；存在；*pn假设存在假设存在 ，满足严格不等式条件，满足严格不等式条件domxf( )0if x 可编辑可编辑3 3不等式约束的消去n示性函数消去不等式约

2、束：示性函数消去不等式约束：01minimize ( )( ( )subject to miifxIf xAxb00( )0uIuun 不具备良好的连续可微性，考虑用对数阀函数来不具备良好的连续可微性，考虑用对数阀函数来近似替代。近似替代。( )Iu可编辑可编辑4 4对数阀函数n对于对于 ， 是是 的光滑逼近。且的光滑逼近。且当当 时，有时，有( )Iu0t 1/ log()tu1/ log()( )tuIut n令令1( )log( )miixf x 01minimize ( )( ),0subject to fxx ttAxbn带示性函数的优化问题可近似为：带示性函数的优化问题可近似为：可

3、编辑可编辑5 5对数阀函数n对数阀函数对数阀函数 是凸函数是凸函数( ) xn对数阀函数二阶连续可微，导数为：对数阀函数二阶连续可微，导数为：11( )( )( )miiixf xf x2221111( )( )( )( )( )( )mmTiiiiiiixf xf xf xf xf x可编辑可编辑6 6中心线n对数阀近似问题的等价问题：对数阀近似问题的等价问题：0minimize ( )( ),0subject to tfxx tAxbn最优解为最优解为 ，则最优解集，则最优解集 称为优化问称为优化问题的中心线。题的中心线。*( )x t*( )|0 x tt 可编辑可编辑7 7中心线的对偶

4、点n设设 ，则存在，则存在 满足满足KKT条件：条件：*( )xx tw011( )( )0,( )mTiiit fxf xA wAxbf x*1( ),( )/( )iittw ttf x t n令令则则 是拉格朗日函数是拉格朗日函数 的最小值解。的最小值解。*( )xx t*( ,( ),( )L xtt*01( ,( ),( )( )( ) ( )( )()miiiL xttfxt f xtAxbn 为对偶问题的可行解。为对偶问题的可行解。*( ),( )tt可编辑可编辑8 8中心线的对偶点n设设 为原始问题的最优值，则有：为原始问题的最优值，则有：*p*0( ),( ) ( ),( )

5、,( ) ( )/pgttL x tttfx tm tn因此，当因此，当 时，有时，有 。 为原始问为原始问题的题的 次优解。次优解。t *0( )fx tp*( )x t/m t 可编辑可编辑9 9阀方法n终止条件：若终止条件：若 ，则终止退出。，则终止退出。/m tn初始化：给定严格可行解初始化：给定严格可行解 ， ， ，及，及x0t 10nLOOP：n中心步骤：以中心步骤：以 为初始点求解优化问题为初始点求解优化问题 ，x*( )x t0minimize ( )( )subject to tfxxAxbn迭代：迭代：*( )xx tn更新更新 ：ttt可编辑可编辑1010收敛性分析收敛性

6、分析n外层循环迭代次数：外层循环迭代次数：(0)log(/()logmtn中心步骤实质为一个无约束或等式约束优化问题，其收中心步骤实质为一个无约束或等式约束优化问题，其收敛性分析与相应优化问题的收敛性分析结果一致。敛性分析与相应优化问题的收敛性分析结果一致。2200( )( )( )( )00TntntxtfxxtfxxAvA n设设 为对数阀问题的可行解，则牛顿方向为对数阀问题的可行解，则牛顿方向 和对偶和对偶问题的解问题的解 满足：满足：ntxx可编辑可编辑1111例：例：nLP问题：问题：100,50mnn初始值：初始值：(0)61,10t可编辑可编辑1212第一阶段方法n对于不等式约束

7、的优化问题，如何寻找严格可行解或验对于不等式约束的优化问题，如何寻找严格可行解或验证不可解？证不可解？n求解优化问题：求解优化问题：minimize subject to ( ),1,., isf xs imAxbn该问题最优解存在，假设最优值为该问题最优解存在，假设最优值为*pn当当 时，存在严格可行解；时，存在严格可行解；*0p n当当 时，原始问题不可解；时，原始问题不可解；*0p n当当 时，无法准确确定。时，无法准确确定。*0p 可编辑可编辑1313第一阶段方法n优化目标为逐项之和：优化目标为逐项之和：minimize 1subject to ( ),1,., Tiisf xs imAxbn对于固定的对于固定的 ，xmax ( ),0iisf x可编辑可编辑1414寻找严格可行解的方法n牛顿法求解优化问题：牛顿法求解优化问题：minimize subject to ( ),1,., isf xs imAxbn迭代终止条件：当前解迭代终止条件：当前解 ，即终止迭代，严格可，即终止迭代，严格可行解为行解为 。( )0ks( )kx