内点法介绍InteriorPointMethod

1、内点法介绍( Interior Point Method )在面对无约束的优化命题时，我们可以采用牛顿法等方法来求解。而面对有约束的命题时，我们往往需要更高级的 算法。单纯形法（ Simplex Method ）可以用来求解带约束的 线性规划命题（LP），与之类似的有效集法（Active SetMethod ）可以用来求解带约束的二次规划（ QP），而内点法Interior Point Method ）则是另一种用于求解带约束的优化 命题的方法。 而且无论是面对 LP 还是 QP ，内点法都显示出 了相当的极好的性能，例如多项式的算法复杂度。本文主要 介绍两种内点法，障碍函数法（ Barrie

2、r Method ）和原始对 偶法（Primal-Dual Method ）。其中障碍函数法的内容主要来 源于 Stephen Boyd 与 Lieven Vandenberghe 的 ConvexJorgeOptimization 一书，原始对偶法的内容主要来源于Nocedal 和 Stephen J. Wright 的 Numerical Optimization书（第二版） 。为了便于与原书对照理解，后面的命题与公式分别采用了对 应书中的记法，并且两者方法针对的是不同的命题。两种方 法中的同一变量可能在不同的方法中有不同的意义，如 在介绍玩两种方法后会有一些比较。障碍函数法 Barrie

3、rMethodCentral Path举例原始对偶内点法 Primal Dual Interior Point MethodCentral Path举例几个问题障碍函数法( Barrier Method )对于障碍函数法，我们考虑一个一般性的优化命题：minsubject tofO(x)fi(x) 0,i=1,.,mAx=l这里fO,.,fm:Rn住二阶可导的凸函数。同时我也要求命题是有解的，即最优解 x 存在，且其对应的目标函数为p。此外，我们还假设原命题是可行的( feasible )。此时，存在最优的对偶变量入和V ,与原始变量x 一道，满足如下的KKT 条件:fO(x)+ 刀 i=1m

4、 入 ifi(x)+AT v Axfi(x) 入入 ifi(x)=0=b 0 i=1,m(2) 其中，入 ifi(x)=0 被称为 ComplementaryCondition 。我们可以看出， KKT 条件中的不等式使得对KKT 系统的求解难以为继，因此 Barrier Method 的思想就是通过在原始的 目标函数中添加一个障碍函数(也可以理解成惩罚函数)来代替约束条件中的不等式约束。 也就是说， 把命题 (1)变成下面的样子：minsubject tof0(x)+E i=1mI(fi(x)Ax=b(3然 后我 们再考虑 I(u) 这个函数究竟选择什么样的一种函数好呢， 其实最好是像一堵墙

5、的一样的函数，在没有违反约束时，函 数值为 0，当违反约束时，函数值为正无穷，就像下图中红色虚线这样一个函数但是很可惜，红色虚线的这个函数在某些点上是不可导的， 因此并不适用，那么下面的想法就是用类似的函数，比如上t 是用于图中的几条蓝色曲线表示的函数来近似这个函数。这样一个 近似的函数的表达式如下：|A(u)=(1/t)log(u) 其中 调整近似程度的参数，从上图可以看出， t 越大近似效果越 好。将上面的近似函数替换到 (3) 的优化命题中， 可以得到如的一个近似的优化命题： minsubject tofO(x)+ 刀 i=1m(1/t)log(fi(x)Ax=b(4)这里我们定义如下的

6、对数障碍( logarithmic barrier )：(x)= E i=1mlog(fi(x)(5)因此，我们后面的讨论就集中与下面这个命题： minsubject totf0(x)+(x)Ax=b(6)针对 (6)中不同的 t>0 值，我们定义 x(t) 为相应优化命题的解。那么，central path就是指所有点 x(t),t>O的集合，其中的点被称为 central points 。 central path 上的点满足如的充分必要条件，首先 x(t) 都是严格可行的，即：Ax(t)=b,fi(x(t)<0,i=1,.,m此外还存在对偶变量面的等式成立( Lagra

7、ngian 函数的导数为 O)：O=tfO(x(t)+(x(t)+ATv 心tfO(x(t)+ 刀 i=1m1fi(x(t)fi(x(t)+AT(7)我们可以从对偶变量的角度进一步研究上式，给等号两边都乘上 1t，我们有：O=fO(x(t)+ 刀 i=1m1tfi(x(t)fi(x(t)+AT我们发现如果令入i(t)=1tfi(x(t),v就取得了与(2)式中的第一个等式基本一致的结果。也就是说， x(t) 能最小化Lagrangian 函数 L(x,入，v )=fO(x)+ 刀 i=1m 入 ifi(x)+即 T (Axb)入(t)和v (t)是原命题 的一组可行的对偶变量(dualfeas

8、ible )，其实可以理解为能使 Lagrangian 函数倒数为 O的就是 dual feasible 的。那么此时，对偶命题的目标函数值为：g(入(t), v (t)=fO(x(t)+刀 i=1m 入 i(t)fi(x(t)+v (t)T(Ax(t)b)=f0(x(t)：mt 上式中的等号可能有点难以理解，但其实就是把(8) 式代入的结果。，那么由优如果我们记原命题 (1) 的目标函数的最小值为 p化命题的对偶理论可知(可以参考另一篇博文优化命题的对偶性(Duality )fO(x(t)mt 率q fO(x(t)q w 从这里可以形象地看出， 随着 t 取值增大， x(t) 可以最终收敛到

9、最优解。其中，原始命题与对偶命题的解的差，即f0(x(t)q 被称为 duality gap 。因此这里可以给出一个 Barried Method 算法的框架(来自Convex Optimization, Algorithm 11.1)：a >1,tolerance >OBarrier Method given strictly feasible x,t:=t(0)>0, repeatCentering step. Compute x(t) by minimizing tf0+, subject toAx=b, starting at x.Update. x:=x(t).St

10、opping criterion. quit if m/t<.Increase t. t= at举例 这里用一个例子进行一些补充说明。考察一个简单的线性规划： mincTxsubject to x=首0先令 c=(11),t(0)=4 , x 的初始点为 (1.3,1)面两图是第一次迭代， t=4 时的 tf0(x)+(x) 函数图象和平 面的等高图，同时第二张图上还标出了迭代点的轨迹。面是 t=8 时的 tf0(x)+(x) 函数图象和平面的等高图， 同时 第二张图上还标出了迭代点的轨迹。对于本例， central path 就是 x1=x2 这条直线。 从迭代点的 轨迹可以看出， 在

11、第一次迭代后， 迭代点一直在 central path上移动。其实对于 Barrier Method ，我自己之前有个疑问就是，既然 我们知道在 x(t) 处的目标函数值与最优解的差肯定小于mt,那为什么不直接给一个较大的t 值通过较少的几次迭代就能算出最有解了呢。真对这一问题，原因可能是这样的，Barrier Method 的计算量是由内外两层迭代组成的，外层对t进行更新：t=卩t，内层用牛顿法求tf0+的解。有仿真结果顿迭代次数）在呈现一定阶段的下降后并没有明显下降。而对与卩值的选取则是一个内层迭代次数和外层迭代次数的权衡。卩值较大时，外层迭代次数少，内层迭代次数多；卩值较小时情况则相反。

12、一般来说卩的取值在10到20之间比较合适。原始对偶内点法( Primal Dual Interior Point Method ) 在 Primal Dual 的方法中，我们直接考虑一个标准的 LP 命题。mincTx,subject to Ax=b,x 0它的对偶命题为: maxbT入，subject to AT 入 +s=c,s 0(0面两个命题的 KKT条件为： 0.(11a)(11b)(11c)(11d)AT入 +sAxxisi(x,s)=c,=b,=0,i=1,.,n为了后面的推导方便，将上面的 KKT条件化为矩阵形式如下：F(x,入，s)=AT 入 +scAxbXSe(x,s)=0

13、. 0,(12a)(l2b)中,X=diag(x1,x2,.,xn),S=diag(s1,s2,.,sn),e=(1,1,.1)T如同一般的优化算法，这里需要定义一个量来检验当前的迭代点与最优点的差距。在 Barrier Method中，使用 dualitygap 的上界 mt 来检验的，在 Primal Dual Method中，我们定义一个新的 duality measure 来进行某种衡量：卩=1n刀 i=1nxisi=xTsn 注意：这里的 卩与 Barrier Method中的 卩意义不同，为了与各自书中的表达方式对应，分别 选用了各自书中的变量记法。要求解原始的优化命题，需要做的就

14、是去求解 (12) 这样个方程组，由于 F 阵第三行中XS 一项的存在，因此这是个非线性系统。要求解这样一个非线性系统，一种实用的方法就是注意，这里说的牛顿法是一种求解非线性方程组的方法，与求解优化命题的牛顿法并不完全一样， 但核心思路是一致的，都是在迭代点处进行二阶展开。 )在 当前点处求解一个前进方向，并通过迭代逼近非线性系统的 解。J(x,入，s) A x AXA s=F(X其取，S)是F阵的雅各比矩阵。我们将 F 阵中的前两行分别记为： rb=Axb,rc=AT X+sc(13)那么在每次迭代中需要求解的线性系统为：OASATOOIOX A x AXA s=rcrbXSe因此，在求解得

15、到相应的前进方向后，需要做的就是求解确定一个步长a来进行如下的更新(x, X ,s)+ a ( A x, A其中Ase (0,1的选取要使得原始变量和对偶变量都满足相应的约束。看起来这种方法似乎已经可以了，但通过这种被称为affine往往很小。也就是说，scaling direction 的方向所得到的 a很难在迭代中取得进展。一开始看到这个说法时，我也很难 理解这句话的意思。所以在这里我们用一个图来说明， 令 (9)中的 c=(1O1) ，初始点为 (O.7,2) ，这里不考虑等式约束，直接采用 affine scaling direction 的方向得到的迭代点的轨迹从图中可以看出，几乎在

16、从第二次迭代开始，迭代点就一头撞上了约束。后面的迭代也只能贴着约束的边缘来走，因为要保迭代点不能违反约束，因此每次的步长a都只能取得很小。在这一过程中，一共进行了 11 次迭代才使得 duality measure 卩 <105。因此，实际上内点法采用的是一个不那么 aggressive 的 顿方向，也就是控制迭代点使其徐徐想约束边界和最优点处 靠近。具体的方法是，我们在用牛顿法求解非线性系统时，在每次迭代中并不要求直接实现 xisi=0 ，而是令其等于一个逐渐减少的值，具体来说就是xisi= 卩，其中卩是当前的duality measure , (r 0,1是用于控制下降速度的下降因子

17、。也就是说，在每次迭代中要求解的方程组应该是被称为0ASAT00I0X x AXA s=rcrbXSe+ a 卩 e(1其中,center parameter。意在表示我们要通过调整a使得迭代点的轨迹在 central path 附近。Central Path在内点法中， central path 是指满足下面一组方程式的迭代点所组成的所组成的一条弧线AT入 +sAxxisi(x,s)=c,=b,= i=1T.n. >0(15a)(15b)(15c)(15d) 这与 (11)中的 KKT 条件的区别就在于在第三个条件的等式右端的0被T >O替代了。也就是说，对偶内点法的基本思路就是

18、依据 central path 计算出相应的方向，并控制步长a的选择使得迭代点位于central path 的某一个邻域内。 (有关 central path 的邻域的 内容，和具体的原始对偶内点法的算法在这里不作详细说明， 有兴趣这可以参考相应书籍。 ) 关于步长 a 的选取，central parame ter (的更新，以及更 多的收敛性分析的内容，在这里不作展开。举例 与上一张图对应，我们同样取 c=(101) ，初始点为 (0.7,2) ， 不考虑等式约束。采用对偶内点法的迭代点的轨迹为可以看出，引入 central path 后，迭代点能在贴近约束边界 后再次远离约束边界(也就是靠

19、近 central path )，从而保 证下一次迭代能取得更大的进步。在这一过程中，一共进行了 6 次迭代就使得duality measure 卩 <105几个问题1 Barrier Method中的 central path 与 Primal DualMethod中的 central path 是不是一个东西？是一个东西，我们可以从优化命题的 Lagrangian 函数这角度出发分析这一点。Barrier Method中的优化命题的 Lagrangian 函数为：L(x,入，V )=fO(x(t)+刀 i=1m1tfi(x(t)fi(x(t)+V T(Ax(t)b)=f0(x(t)+

20、刀 i=1m 入 ifi(x(t)+V T(Ax(t)b)=f0(x(t)mtPrimal Dual Method中优化命题的 Lagrangian 函数为：L(x,s,入)=cTx E i=1nxisi 入 T(Axb)从这里我们可以看出来， Barrier Method中我们控制 t 使得duality gap 为 mt，在Primal Dual内点法中我们控制E ni=1xisi=o其实是一致的。而且有 mt=这样一个关系的存在。因此我们在 Barrier Method中增加 t 和与在Primal Dual的方法中使 op下降其实是在做一件事情。2 Central Path 有啥好处？ 从上面的举例可以看出，如果没有 central path ，迭代点往 往非常靠近约束边界。如果我们能够将迭代点拉回到central path 附近，那么即使这次迭代对与目标函数下降的 贡献不大，那么也可以使得在下次迭代时目标函数能够取得 较大下降。此外,central path 还对算法的热启动(warm start ) 有影响。因为在很多场合(例如