interior point methods 简介

interior point methods 是从 feasible region 的内部开始搜索,一般会 follow 所谓的 central path,逼近到最优解,它 handle 约束的方式与 active set 不同(后者是将约束转换成为等式后利用等式的 solver 求解,因此 active set 可以看成某种意义上单纯型方法的推广)。interior point methods 一般是将不等式放入目标函数作为新的目标函数进行优化,这样一来新的优化问题变成能够用原有方法解决的问题,而此时随着某个参数的变化,最优解就会逼近于原问题。这样我们要讲的一个方法就是如何将约束放入目标函数,但是由于其精度不够,被后面更好地方法所替代。

历史

求解线性规划最初是二战期间 Leonid Kantovorich 表述了这个问题并研究出某种秘密算法,后来 Dantzig 在 1942 年获得的 simplex methods,但是对复杂性理论家来说这个算法即便实际性能不错,但是最坏情况下仍然不是多项式时间的。John von Neumann 同时期为线性规划研究了其 duallty 并用到 game theory 里面。而之后 Naum Shor 引入而由 Arkadi Nemirovski 和 David Yudin 完善的 ellipsoid methods(1972)被 Leonid Khachiyan 证明是多项式时间复杂度,这相当于告诉大家线性规划是 P 问题,但这个方法却非常之慢(复杂性里面蕴含的常数项很大)。interior point methods 有多种思路,其发源正是 von Neumann 在 duality 上的工作,当时他提出了一种通过求解一系列其次线性系统的思路,这被 Narendra Karmarka 在 1984 年改进成为现在线性规划问题上所熟知的内点算法,并被证明这也是多项式时间算法。尽管方法由来是从线性规划开始,但是很快大家意识到这个方法(包括椭圆法)都可以应用到更一般的问题里(如二次规划、凸优化)。

barrier method

所谓的 barrier 实际上是“拒绝解靠近边界”的一种惩罚,比较常用的惩罚方式是对 c(x) \geq 0 的约束改成 -\log c(x) 加入到 primal 问题中,这样由于 log 函数在 0 附近趋于 -\infty 这导致新问题的解不可能出现在边界。这个新的优化问题只涉及到等式约束,而一般来说等式约束等价于某种 manifold 上的限制(比如常见的线性方程组约束要求解落在一个超平面,即 linear manifold 之上,而更广义的比如 L^2 范数约束等价于是球面,又比如正交性约束或者子空间约束对应的是 Stiefel-Grassmann manifold),这种限制常见的做法就是投影,即将 exterior coordinates 上计算得到的梯度等投影到 manifold 的 tangent space,然后沿着 geodesics 进行 line search 即可。我们这里只考虑 Ax = b 这类型的约束,这等价于要求 A \delta x = 0

我们看看新的优化问题

\displaystyle \min_x t f(x) + \phi (x) \qquad \text{s.t.} \quad A^\top x= b

其中 \phi(x) = -\sum_{j = 1}^m \log c_j (x),其中 t 是一个参数,随着 t 的增大,我们的最优解会形成一个 path(所谓的 central path),不难发现其极限对应着原问题的最优解。问题是我们能从这个新问题的最优解了解到一些什么东西?对这个新问题我们写出 Lagrange 函数并写出 KKT 条件,有

\displaystyle 0 = t \nabla f (x^\star(t)) - \sum_{j = 1}^m \frac{1}{f_j (x^\star (t))}\nabla f_j (x^\star (t)) + A \nu

这表明如果令 \lambda_j^\star (t) = \frac{1}{t f_j (x^\star (t))} > 0 作为原问题 c_j 对应的不等式约束的 Lagrange multiplier,就会对应着原问题的一个 dual feasible 解,因此此时的 duality gap 就是 \frac{m}{t},比较 naive 的实现就是这样,我们不停地增大 t 并求解对应的新优化问题,直到 duality gap 足够小就停止下来。

这个方法有个物理解释,即将约束对应成某种概率,而对应的 \phi(x) 是某种势能,这样求导后的方程就是力平衡(合力为零),因此新问题的最优解是目标函数对应某力与约束导致的力平衡的结果。

这个方法还需要 primal strictly feasible 解,我们如果没有可以用如下方式获得:

\min s \qquad \text{s.t.} \quad f_j (x) + s \geq 0, A^\top x = b

这个问题我们随便找个满足 A^\top x = b 的解即可得到一个可行解,而只要找到一个 s < 0 的解就表明是原问题的 strictly feasible 解了。

primal-dual interior point methods

在 barrier methods 里面我们其实仅仅利用了 primal problem 的搜索方向(我们将问题转换成仅有等式约束的优化后,我们可以使用 projected Newton method 进行求解,这时候搜索方向就是由目标函数和等式约束一起决定的),这时不等式约束通过 \phi 在目标函数中产生作用。而 primal-dual interior method 直接考虑以下原问题 KKT 条件的“松弛”解

\displaystyle r(x, \lambda, \nu) = \begin{pmatrix} \nabla f (x) - \nabla F(x)^\top \lambda + A\nu \\ -\mathrm{diag} \{ \lambda\} F(x) - \frac{1}{t}e \\ A^\top x - b\end{pmatrix} \Rightarrow

\displaystyle \begin{pmatrix} \nabla^2 f - \sum_{j = 1}^m \lambda_j \nabla^2 f_j & \nabla F & A \\ -\mathrm{diag}\{\lambda\} \nabla F & - \mathrm{diag}\{F\} & 0 \\ A^\top & 0 & 0 \end{pmatrix}\begin{pmatrix} \delta x \\ \delta \lambda \\ \delta \nu \end{pmatrix} = -\begin{pmatrix} r_\text{dual} \\ r_\text{cent} \\ r_\text{pri}\end{pmatrix}

(这里 F(x) = (f_j (x))^\top)这样一来我们获得的搜索方向并不一定保证 primal feasibility 和 dual feasibility,其搜索方向仅在两者为 feasible 时与 barrier method 相同,这样一来我们不能将中间的 x, \lambda 代入获得 \frac{m}{t} 是我们的 dual gap。为此,一般我们使用 surrogate dual gap 帮助我们判断收敛性,如 \eta = \lambda^\top F(x)。求解以下方程组(将 dual residual 部分通过消元去掉)与 barrier methods 需要求解的是一类的,因此可以 share solver(如 PCG)。

\displaystyle \begin{pmatrix} H_\text{pd} & A \\ A^\top & 0\end{pmatrix} \begin{pmatrix} \delta x \\ \delta \nu\end{pmatrix} = -\begin{pmatrix} r_\text{dual} + \nabla F^\top \mathrm{diag}\{ F\}^{-1} r_\text{cent} \\ r_\text{pri} \end{pmatrix}

其中 H_\text{pd} = \nabla^2 f - \sum_{j = 1}^m \lambda_j \nabla^2 f_j + \sum_{j = 1}^m \frac{\lambda_j}{f_j} \nabla f_j \nabla f_j^\top。最后小结一下 primal-dual interior methods 的过程:选择可行解 x, \lambda, \nu

  • 计算 t \gets \mu m / \eta
  • 然后计算以上方程中的 \delta x, \delta \nu,并代入求出 \delta \lambda
  • 根据以上方向进行 line search 更新 x, \lambda, \nu

判断收敛性一般根据 primal/dual residual 和 surrogate dual gap 进行判断。

———————-
And Sarah died in Kirjatharba; the same is Hebron in the land of Canaan: and Abraham came to mourn for Sarah, and to weep for her.

Advertisements
interior point methods 简介

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s