内点法介绍（Interior Point Method）
在面对无约束的优化命题时，我们可以采用牛顿法等方法来求解。而面对有约束的命题时，我们往往需要更高级的算法。单纯形法（Simplex Method）可以用来求解带约束的线性规划命题（LP），与之类似的有效集法（Active Set Method）可以用来求解带约束的二次规划（QP），而内点法（Interior Point Method）则是另一种用于求解带约束的优化命题的方法。而且无论是面对LP还是QP，内点法都显示出了相当的极好的性能，例如多项式的算法复杂度。本文主要介绍两种内点法，障碍函数法（Barrier Method）和原始对偶法（Primal-Dual Method）。其中障碍函数法的内容主要来源于Stephen Boyd与Lieven Vandenberghe的Convex Optimization一书，原始对偶法的内容主要来源于Jorge Nocedal和Stephen J. Wright的Numerical Optimization一书（第二版）。
为了便于与原书对照理解，后面的命题与公式分别采用了对应书中的记法，并且两者方法针对的是不同的命题。两种方法中的同一变量可能在不同的方法中有不同的意义，如 μ。在介绍玩两种方法后会有一些比较。障碍函数法Barrier Method Central Path
举例
原始对偶内点法Primal Dual Interior Point Method Central Path 举例
几个问题障碍函数法（Barrier Method）
对于障碍函数法，我们考虑一个一般性的优化命题：minsubject tof0(x)fi(x)≤0,i=1,...,mAx=b(1) 这里
f0,...,fm:Rn→R 是二阶可导的凸函数。同时我也要求命题是有解的，即最优解 x 存在，且其对应的目标函数为 p。此外，我们还假设原命题是可行的（feasible）。此时，存在最优的对偶变量 λ 和 ν ，与原始变量 x 一道，满足如下的KKT条件:
f0(x)+∑i=1mλifi(x)+ATνAxfi(x)λλifi(x)=0=b≤0,i=1,...,m≥0=0,i=1,...,m(2) 其中，λifi(x)=0 被称为Complementary Condition。
我们可以看出，KKT条件中的不等式使得对KKT系统的求解难以为继，因此Barrier Method的思想就是通过在原始的目标函数中添加一个障碍函数（也可以理解成惩罚函数）来
代替约束条件中的不等式约束。也就是说，把命题(1)变成下面的样子：minsubject tof0(x)+∑i=1mI(fi(x))Ax=b(3) 然后我们再考虑 I(u) 这个函数究竟选择什么样的一种函数好呢，其实最好是像一堵墙的一样的函数，在没有违反约束时，函数值为0，当违反约束时，函数值为正无穷，就像下图中红色虚线这样一个函数
但是很可惜，红色虚线的这个函数在某些点上是不可导的，因此并不适用，那么下面的想法就是用类似的函数，比如上图中的几条蓝色曲线表示的函数来近似这个函数。这样一个近似的函数的表达式如下：I^(u)=(1/t)log(u) 其中 t 是用于调整近似程度的参数，从上图可以看出，t 越大近似效果越好。将上面的近似函数替换到(3)的优化命题中，可以得到如下的一个近似的优化命题：minsubject tof0(x)+∑i=1m(1/t)log(fi(x))Ax=b(4)
这里我们定义如下的对数障碍（logarithmic barrier）：(x)=∑i=1mlog(fi(x))(5) 因此，我们后面的讨论就集中与下面这个命题：minsubject totf0(x)+(x)Ax=b(6) Central Path
针对(6)中不同的 t>0 值，我们定义 x(t) 为相应优化命题的解。那么，central path 就是指所有点 x(t),t>0 的集合，其中的点被称为 central points。central path 上的点满足如下的充分必要条件，首先 x(t) 都是严格可行的，即：Ax(t)=b,fi(x(t))<0,i=1,...,m此外还存在对偶变量 ν^ 使得下面的等式成立（Lagrangian函数的导数为0）：
0=tf0(x(t))+(x(t))+ATν^=tf0(x(t))+∑i=1m1fi(x(t))fi(x(t))+ATν^(7)
我们可以从对偶变量的角度进一步研究上式，给等号两边都乘上 1t ，我们有：0=f0(x(t))+∑i=1m1tfi(x(t))fi(x(t))+ATν^t 我们发现如果令λi(t)=1tfi(x(t)),ν=ν^t(8) 就取得了与(2)式中的第一个等式基本一致的结果。也就是说，x(t) 能最小化 Lagrangian函数 L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+νT(Axb) 即，λ(t) 和 ν(t) 是原命题(1)的一组可行的对偶变量（dual feasible），其实可以理解为能使 Lagrangian函数倒数为0的就是 dual feasible 的。
那么此时，对偶命题的目标函数值为：
g(λ(t),ν(t))=f0(x(t))+∑i=1mλi(t)fi(x(t))+ν(t)T(Ax(t)b)=f0(x(t))mt 上式中的等号可能有点难以理解，但其实就是把(8)式代入的结果。
如果我们记原命题(1)的目标函数的最小值为 p ，那么由优化命题的对偶理论可知（可以参考另一篇博文——优化命题
的对偶性（Duality））f0(x(t))mt≤q 即 f0(x(t))q≤mt 从这里可以形象地看出，随着 t 取值增大，x(t) 可以最终收敛到最优解。其中，原始命题与对偶命题的解的差，即 f0(x(t))q 被称为 duality gap。
因此这里可以给出一个 Barried Method 算法的框架（来自Convex Optimization, Algorithm 11.1）：
Barrier Method
given strictly feasible x,t:=t(0)>0,μ>1,tolerance >0 repeat
Centering step. Compute x(t) by minimizing tf0+, subject to Ax=b, starting at x. Update. x:=x(t).
Stopping criterion. quit if m/t<. Increase t. t=μt 举例
这里用一个例子进行一些补充说明。考察一个简单的线性规