简单介绍处理不等式约束问题的内点法的算法流程。

不等式约束的极小化问题

$\min f_0(x)$

$s.t.\quad f_i(x)\le0$

$Ax=b$

假设该问题可解，即存在最优的 $x^\star$ ，用 $p^\star$ 表示最优值 $f_0(x^\star)$ 。

用内点法求解问题，主要分为两种：

这里只讨论一种特殊的内点法--障碍法。

对数障碍函数和中心路径

一种尝试是将不等式约束问题近似转化为等式约束问题，从而应用Newton方法求解。因此，可以将原问题写成：

$\min f_0(x)+\sum_{i=1}^m I(f_i(x))$

$s.t.\quad Ax= b$

其中 $I()$ 是非正实数的示性函数：

$I(u)\left\{\begin{array}{ll} 0 & u \leq 0 \\ \infty & u>0 \end{array}\right.$ 这样，我们就成功转化为等式约束，可以，目标函数一般情况下不可微，因此不能运用Newton方法。

既然示性函数不可微，我们很自然的想法就是找一个近似的可微函数来代替：

$\hat{I}(u)=-(1 / t) \log (-u)$ 我们可以画出对数障碍函数的图像发现，是非减函数，并且当 $u>0$ 时取值为 $\infty$ ，符合我们的要求。

我们将函数 $\phi (x) = -\sum_{i=1}^m \log (-f_i(x))$ 称为对数障碍函数。可以将等式约束问题重写为：

$\min f_{0}(x)+\sum_{i=1}^{m}-(1 / t) \log \left(-f_{i}(x)\right)$

$s.t.\quad Ax= b$

既然对数障碍只是原问题的近似，因此需要回答的问题就是其解的效果与最优解差距多大？这个问题将在中心路径中解决。

先给出对数障碍的梯度和Hessian矩阵：

$\nabla \phi(x)=\sum_{i=1}^{m} \frac{1}{-f_{i}(x)} \nabla f_{i}(x)$

$\nabla^{2} \phi(x)=\sum_{i=1}^{m} \frac{1}{f_{i}(x)^{2}} \nabla f_{i}(x) \nabla f_{i}(x)^{T}+\sum_{i=1}^{m} \frac{1}{-f_{i}(x)} \nabla^{2} f_{i}(x)$

考虑等价问题：

$\min tf_0(x)+\phi (x)$

$s.t.\quad Ax= b$

这里只是多乘了一个 $t$ ，对最优解没有影响。

对任意 $t>0$ ，我们用 $x^\star(t)$ 表示问题的最优解， $t$ 为中心点，将这些点的集合定义为问题的中心路径。

所有中心路径上的点满足以下充要条件：

$Ax^\star(t)=b,\quad f_i(x^\star(t))<0$

$t\triangledown f_{0}(x^\star(t))+\triangledown \phi (x^\star(t))+A^T \hat{v} = 0$

$g(\lambda^\star(t),v^\star(t)) = f_0(x^\star(t)) - m/t \le p^\star$

证明了 $x^\star(t)$ 随着 $t \Rightarrow \infty$ 而收敛于最优解。