GZ Cloudhome Logo

内点法

发布于：2023 年 6 月 9 日

内点法是一个用来解决同时有有等式约束和不等式约束的凸优化问题的方法。

arg⁡min⁡xf(x)subject tofi(x)≤0,    i=1,…,pAx=0,    rank(A)<n.\begin{align*} \underset{\boldsymbol{x}}{\arg \min} && & f(\boldsymbol{x})\\ \mathrm{subject~to} && & f_i(\boldsymbol{x}) \le 0, ~~~~ i = 1, \dots, p\\ && & \mathbf{A} \boldsymbol{x} = \boldsymbol{0}, ~~~~ \mathrm{rank}(\mathbf{A}) < n. \end{align*}

我们知道，对于无约束凸优化问题，我们可以选择下降法，如

当无约束问题升级为等式约束问题时，牛顿法仍然可用。在牛顿法中，我们实质上是把原问题化为一系列的等式约束的二次规划问题来求解。

对于同时有等式约束和不等式约束的情形，我们可以考虑相同的思想：把原问题转化为一系列的等式约束的凸优化问题。为了完成上述的转化，需要介绍对数障碍函数（logarithmic barriers）：

bt(u)=−1tlog⁡(−u),    t>0.b_t(u) = -\frac{1}{t} \log(-u), ~~~~ t > 0.

随着 tt 的增大，bt(u)b_t(u) 的曲线将会越来越接近 xx-yy 坐标线。因此，bt(u)b_t(u) 可以看作是指示函数（indicator function）的一个合理近似。指示函数定义为

I−(u)={0u≤0∞u>0.I_-(u) = \left\{ \begin{align*} &0 && u \le 0 \\ &\infty && u > 0. \end{align*} \right.

因此，基于对数障碍函数我们可以把原问题近似地转化为

arg⁡min⁡xf(x)+∑i=1pbt(fi(x))⇔ tf(x)+∑i=1p−log⁡(−fi(x))⇔ tf(x)+ϕ(x),    i=1,…psubject toAx=0,    rank(A)<n,\begin{align*} \underset{\boldsymbol{x}}{\arg \min} && & f(\boldsymbol{x}) + \sum_{i=1}^p b_t(f_i(\boldsymbol{x})) \\ && \Leftrightarrow~ & t f(\boldsymbol{x}) + \sum_{i=1}^p -\log(- f_i(\boldsymbol{x})) \\ && \Leftrightarrow~ & t f(\boldsymbol{x}) + \phi(\boldsymbol{x}), ~~~~ i = 1, \dots p \\ \mathrm{subject~to} && & \mathbf{A} \boldsymbol{x} = \boldsymbol{0}, ~~~~ \mathrm{rank}(\mathbf{A}) < n, \end{align*}

其中 ϕ(x)=∑i=1p−log⁡(−fi(x))\phi(\boldsymbol{x}) = \sum_{i=1}^p -\log(- f_i(\boldsymbol{x}))。这是一个有等式约束的凸优化问题，可以直接使用牛顿法求解。

在实践中，我们并不简单地选择一个较大的 tt，然后求解近似问题来得到解。这样的方式容易导致数值问题。相反地，我们采取迭代近似的策略：在第 kk 次迭代时，我们令 tk=μtkt_k=μ t_k，以及令初始点为 xk=xk−1∗\boldsymbol{x}_k = \boldsymbol{x}_{k-1}^*，其中 xk−1∗\boldsymbol{x}_{k-1}^* 是第 k−1k-1 迭代中基于牛顿法得到的最优解。