障碍方法

我们已经看到，点 $x^{\star }(t)$ 至多 $m/t$-次优，并且对偶可行对 $({\lambda }^{\star }(t),{\nu }^{\star }(t))$ 提供了这一精度的证书。这提示一种非常直接的求解方法，可以达到给定的保证精度 $ϵ$：直接取 $t=m/ϵ$，用 Newton 方法求解等式约束问题

$$\mathrm{minimize}(m/ϵ)f_0(x)+\varphi (x)\mathrm{subject}\mathrm{to}Ax=b$$

这个方法可以称为无约束极小化方法——它通过求解一个无约束（或线性约束）问题，把带不等式约束的问题解到保证的精度。虽然该方法对小问题、好的初始点和中等精度（即 $ϵ$ 不太小）可以工作得很好，但在其他情形下效果不佳，因此几乎从不使用。

障碍方法

对上述方法的简单扩展确实有效：求解一序列无约束（或线性约束）极小化问题，用前一次找到的点作为下一次极小化的初始点。也就是说，对递增的 $t$ 值计算 $x^{\star }(t)$，直到 $t⩾m/ϵ$，此时即保证得到原问题的一个 $ϵ$-次优解。该方法由 Fiacco 和 McCormick 在 20 世纪 60 年代提出时称为序贯无约束极小化技术​（SUMT, sequential unconstrained minimization technique）；今天通常称为障碍方法​（barrier method）或路径跟踪方法​（path-following method）。一个简单版本如下。

算法 11.1（障碍方法） 给定严格可行点 $x$，$t:=t^{(0)}>0$，$\mu >1$，容许误差 $ϵ>0$。

1. 中心点步​（centering step）：从 $x$ 出发，通过在约束 $Ax=b$ 下极小化 $t{f}_0+\varphi$ 计算 $x^{\star }(t)$。
2. 更新：$x:=x^{\star }(t)$。
3. 终止准则​：若 $m/t<ϵ$ 则退出。
4. 增大 $t$：$t:=\mu t$。

在每次迭代（第一次除外）中，从上一个中心点出发计算下一个中心点 $x^{\star }(t)$，然后把 $t$ 增大 $\mu >1$ 倍。算法也可以返回 $\lambda ={\lambda }^{\star }(t)$ 与 $\nu ={\nu }^{\star }(t)$，即 $x$ 的对偶 $ϵ$-次优点（精度证书）。

我们把第 1 步的每次执行称为一个中心点步​（此时在计算一个中心点）或一个外层迭代​（outer iteration）；把第一个中心点步（计算 $x^{\star }(t^{(0)})$）称为初始中心点步​。因此当 $t^{(0)}=m/ϵ$ 时，算法只包含初始中心点步。虽然第 1 步可以用任何线性约束极小化方法完成，我们假设使用 Newton 方法；把中心点步中执行的 Newton 迭代称为内层迭代​（inner iterations）。每个内层迭代点都是原始可行的；但只有在外层（中心点）步结束时才有对偶可行点。

中心点的精度

对中心点问题的求解精度需要一些说明。精确计算 $x^{\star }(t)$ 并非必要，因为中心路径的意义只在于当 $t\to \mathrm{\infty }$ 时导出原问题的解；不精确的中心点步仍产生收敛于最优点的点列。不精确的中心点步会使由公式算出的 $({\lambda }^{\star }(t),{\nu }^{\star }(t))$ 不严格对偶可行，这可以通过在公式中加一个修正项来补救——只要算出的 $x$ 靠近中心路径，修正后的点就是对偶可行的。

另一方面，与计算 $t{f}_0+\varphi$ 的一个好极小点相比，计算一个极精确极小点的代价只多几次 Newton 步。因此假设精确的中心点步并不过分。

参数 $\mu$ 的选择

参数 $\mu$ 的选择涉及内层与外层迭代次数之间的折中。若 $\mu$ 小（接近 1），则每次外层迭代 $t$ 只增大很小的因子，上一个迭代点是 Newton 过程非常好的初始点，计算下一个中心点所需的 Newton 步数很少：外层迭代次数多，但每次内层迭代少。此时迭代点（包括内层迭代点）紧密地跟随中心路径——这正是“路径跟踪方法”这一别名的由来。

若 $\mu$ 大，则情况相反：每次外层迭代后 $t$ 增大很多，当前迭代点对下一个中心点的近似较差，因此需要更多内层迭代；但这种“激进”的 $t$ 更新使对偶间隙每次按大因子 $\mu$ 缩减，外层迭代次数更少。$\mu$ 大时迭代点在中心路径上相距很远，内层迭代点则大幅偏离中心路径。

实践中 $\mu$ 较小（接近 1）时外层迭代很多而每次只需几次 Newton 步；在相当大的范围内（从大约 3 到 100 左右），两种效应几乎相互抵消，所需 Newton 步总数近似不变。这意味着 $\mu$ 的选择并不关键，取 10 到 20 左右就很有效。若按使最坏情形 Newton 步总数界最优来选 $\mu$，则应取接近 1 的值。

初始值 $t^{(0)}$ 的选择

初始 $t$ 的选择也很重要，其折中很简单：$t^{(0)}$ 太大，第一次外层迭代需要太多迭代；$t^{(0)}$ 太小，算法需要额外的外层迭代，而且第一次中心点步可能需要太多内层迭代。

由于 $m/t^{(0)}$ 是第一次中心点步之后得到的对偶间隙，一个合理的选择是取 $t^{(0)}$ 使 $m/t^{(0)}$ 与 $f_0(x^{(0)})-p^{\star }$（或其 $\mu$ 倍）大致同阶。例如，若已知对偶可行点 $\lambda ,\nu$（对偶间隙 $\eta =f_0(x^{(0)})-g(\lambda ,\nu )$），则可取 $t^{(0)}=m/\eta$：第一次外层迭代计算出的点对的间隙就与初始原始、对偶可行点的间隙相同。

中心路径条件还提示了另一种可能：可以把

$$\underset{\nu }{inf}{\Vert t\mathrm{\nabla }{f}_0(x^{(0)})+\mathrm{\nabla }\varphi (x^{(0)})+A^{\mathrm{\top }}\nu \Vert }_2$$

解释为 $x^{(0)}$ 偏离 $x^{\star }(t)$ 的程度，并选取使它最小的 $t$（该 $t$ 与 $\nu$ 可以通过求解一个最小二乘问题得到）。这一做法的一个变体使用仿射不变的偏离度量：选取 $t$ 与 $\nu$ 使

$$\alpha (t,\nu )={(t\mathrm{\nabla }{f}_0(x^{(0)})+\mathrm{\nabla }\varphi (x^{(0)})+A^{\mathrm{\top }}\nu )}^{\mathrm{\top }}{H}_0^{-1}(t\mathrm{\nabla }{f}_0(x^{(0)})+\mathrm{\nabla }\varphi (x^{(0)})+A^{\mathrm{\top }}\nu ),H_0=t{\mathrm{\nabla }}^2{f}_0(x^{(0)})+{\mathrm{\nabla }}^2\varphi (x^{(0)})$$

最小（可以证明 $\underset{\nu }{inf}\alpha (t,\nu )$ 就是 $t{f}_0+\varphi$ 在 $x^{(0)}$ 处的 Newton 减量的平方）。$\alpha$ 是 $\nu$ 与 $t$ 的 quadratic-over-linear 函数，因此是凸的。

不可行初始点的 Newton 方法

障碍方法的一个变体是在中心点步中使用不可行初始点 Newton 方法。此时障碍方法以一个满足 $x^{(0)}\in \mathrm{dom}{f}_0$、$f_i(x^{(0)})<0$（但不一定满足 $A{x}^{(0)}=b$）的点初始化。假设问题严格可行，则在第一次中心点步中的某个时刻会取到全步长，此后所有迭代点都原始可行，算法与（标准的）障碍方法一致。

例子

不等式形式的线性规划

第一个例子是规模 $A\in {\mathbf{R}}^{100\times 50}$ 的小型不等式形式 LP（随机生成数据，严格原始与对偶可行，$p^{\star }=1$）。初始点 $x^{(0)}$ 在中心路径上、对偶间隙为 100；障碍方法终止于对偶间隙小于 ${10}^{-6}$。中心点问题用回溯 Newton 方法（$\alpha =0.01$，$\beta =0.5$）求解，终止准则为 $\lambda (x{)}^2/2⩽{10}^{-5}$（$\lambda (x)$ 是 $t{c}^{\mathrm{\top }}x+\varphi (x)$ 的 Newton 减量）。

对 $\mu =2$、$\mu =50$、$\mu =150$ 三种取值，对偶间隙随累计 Newton 步数的曲线呈阶梯状：每级台阶对应一次外层迭代，台阶踏面（水平部分）的宽度是该次外层迭代所需的 Newton 步数，台阶立板（竖直部分）的高度恰为 $\mu$（对偶间隙按因子 $\mu$ 缩减）。三种情形下对偶间隙都近似线性收敛：$\mu =50$ 与 $\mu =150$ 时，总 Newton 步数在 35 到 40 之间。$\mu =2$ 时踏面短（每次外层约 2–3 步）但立板也短；$\mu =150$ 时踏面典型约 7 步，而立板大得多。

对 $\mu$ 的进一步实验（取 1.2 到 200 之间的 25 个值，终止于间隙 ${10}^{-3}$）表明：障碍方法在 $\mu$ 大约从 3 到 200 的范围内都表现很好；$\mu$ 太小时因外层迭代增多而总步数上升；$\mu$ 很大时性能变得依赖具体实例。由于更大的 $\mu$ 并不带来改进，$\mu$ 取 10 到 100 是好的选择。

待配图​：对应教材图 11.4 与图 11.5 —— 小 LP 的对偶间隙随累计 Newton 步数的阶梯状曲线（$\mu =2,50,150$），以及总 Newton 步数随 $\mu$ 变化的折中曲线。

几何规划

考虑凸形式的几何规划

$$\mathrm{minimize}\log (\sum _{k=1}^{K_0}\exp (a_{0k}^{\mathrm{\top }}x+b_{0k}))\mathrm{subject}\mathrm{to}\log (\sum _{k=1}^{K_i}\exp (a_{ik}^{\mathrm{\top }}x+b_{ik}))⩽0,i=1,\cdots ,m$$

变量 $x\in {\mathbf{R}}^n$，相应的对数障碍为

$$\varphi (x)=-\sum _{i=1}^m\log (-\log \sum _{k=1}^{K_i}\exp (a_{ik}^{\mathrm{\top }}x+b_{ik}))$$

问题实例取 $n=50$、$m=100$（每个目标/约束函数含 $K_i=5$ 项），严格原始与对偶可行、$p^{\star }=1$。初始点在中心路径上（间隙 100），$\mu =2,50,150$，终止于间隙 ${10}^{-6}$；中心点步的 Newton 参数与 LP 例子相同。结果与 LP 的例子非常相似：每次中心点步所需 Newton 步数近似为常数，因此对偶间隙近似线性收敛。把间隙降到 ${10}^{-3}$ 以下所需的总 Newton 步数约为 30（$\mu$ 在 10 到 200 之间时约为 20 到 40）——这里同样建议 $\mu$ 取 10 到 100。

待配图​：对应教材图 11.6 —— 小 GP 的对偶间隙随累计 Newton 步数的曲线。

一族标准形式 LP

为考察障碍方法性能随问题维数的变化，考虑标准形式 LP

$$\mathrm{minimize}{c}^{\mathrm{\top }}x\mathrm{subject}\mathrm{to}Ax=b,x⪰0$$

随机生成一族问题实例（$n=2m$，$m$ 从 10 到 1000）。算法参数：$\mu =100$，中心点步用 $\alpha =0.01$、$\beta =0.5$ 与终止准则 $\lambda (x{)}^2/2⩽{10}^{-5}$；初始点在中心路径上（$t^{(0)}=1$，间隙 $n$）；终止于初始对偶间隙缩小 ${10}^4$ 倍（即两次外层迭代）。

$m=50$、$m=500$、$m=1000$ 三个实例的对偶间隙曲线与其他例子非常相似，近似线性收敛；问题规模从 50 个约束增大到 1000 个约束时，所需 Newton 步数只有轻微增加。对 20 个 $m$ 值各生成 100 个实例共 2000 个问题的统计表明：标准差约为 2 次迭代且与问题规模无关（平均约 25 步，波动约 ±10%）；问题维数增大 100 倍时，所需 Newton 步数只从约 21 增长到约 27。这是障碍方法的典型行为：所需 Newton 步数随问题维数增长极慢，几乎总是在几十步的量级（当然，单次 Newton 步的计算量随维数增长）。

待配图​：对应教材图 11.7 与图 11.8 —— 三个不同维数标准形式 LP 的对偶间隙曲线，以及平均 Newton 步数随 $m$ 的变化（含标准差误差条）。

收敛性分析

障碍方法的收敛性分析很直接。假设 $t{f}_0+\varphi$ 对 $t=t^{(0)},\mu t^{(0)},{\mu }^2{t}^{(0)},\cdots$ 都可以用 Newton 方法极小化，则初始中心点步加上 $k$ 次中心点步之后的对偶间隙为 $m/({\mu }^k{t}^{(0)})$。因此恰好需要

$$\lceil \frac{\log (m/(ϵt^{(0)}))}{\log \mu }\rceil$$

次中心点步（外加初始中心点步）即可达到要求的精度 $ϵ$。

由此可见，只要对 $t⩾t^{(0)}$，中心点问题可以用 Newton 方法求解，障碍方法就有效。对标准 Newton 方法，充分条件是：对 $t⩾t^{(0)}$，$t{f}_0+\varphi$ 满足带等式约束 Newton 方法收敛分析中的条件——初始下水平集是闭集、相应的 KKT 矩阵的逆有界、Hessian 满足 Lipschitz 条件。（基于自和谐的另一组充分条件将在复杂度分析一节详细讨论。）若中心点步采用不可行初始点 Newton 方法，则不可行初始点 Newton 方法收敛分析中列出的条件足以保证收敛。

假设 $f_0,\cdots ,f_m$ 都是闭函数，对原问题做一个简单修改即可保证上述条件成立：在问题中增加形如 $\parallel x{\parallel }_2^2⩽R^2$ 的约束，则 $t{f}_0+\varphi$ 对每个 $t⩾0$ 都强凸，从而中心点步的 Newton 方法收敛得到保证。

这一分析表明障碍方法在合理假设下确实收敛，但没有回答一个基本问题：随着 $t$ 增大，中心点问题是否变得更难（因而需要越来越多的迭代）？数值证据表明，对各种问题答案是否定的——中心点问题所需的 Newton 步数似乎近似为常数，即使 $t$ 不断增大。对满足某些自和谐条件的问题，这个问题可以得到肯定的解决。

修正 KKT 方程的 Newton 步

在障碍方法中，Newton 步 $\mathrm{\Delta }{x}_{\mathrm{nt}}$ 及相应的对偶变量由线性方程

$$\left[\begin{array}{cc}t{\mathrm{\nabla }}^2{f}_0(x)+{\mathrm{\nabla }}^2\varphi (x)& A^{\mathrm{\top }}\\ A& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }{x}_{\mathrm{nt}}\\ {\nu }_{\mathrm{nt}}\end{array}\right]=-\left[\begin{array}{c}t\mathrm{\nabla }{f}_0(x)+\mathrm{\nabla }\varphi (x)\\ 0\end{array}\right]$$

给出。本节说明：中心点问题的这些 Newton 步，可以解释为用一种特殊方式直接求解修正 KKT 方程

$$\begin{array}{rl}& \mathrm{\nabla }{f}_0(x)+\sum _{i=1}^m{\lambda }_i\mathrm{\nabla }{f}_i(x)+A^{\mathrm{\top }}\nu =0\\ & -{\lambda }_i{f}_i(x)=1/t,i=1,\cdots ,m\\ & Ax=b\end{array}$$

的 Newton 步。

这是一组关于 $n+p+m$ 个变量 $x,\nu ,\lambda$ 的 $n+p+m$ 个非线性方程。先消去变量 ${\lambda }_i$：由第二个方程 ${\lambda }_i=-1/(t{f}_i(x))$，代入第一式得

$$\mathrm{\nabla }{f}_0(x)+\sum _{i=1}^m\frac{1}{-t{f}_i(x)}\mathrm{\nabla }{f}_i(x)+A^{\mathrm{\top }}\nu =0,Ax=b$$

这是关于 $x,\nu$ 的 $n+p$ 个方程。对第一式中的非线性项作 Taylor 近似（对小的 $v$）：

$$\mathrm{\nabla }{f}_0(x+v)+\sum _{i=1}^m\frac{1}{-t{f}_i(x+v)}\mathrm{\nabla }{f}_i(x+v)\approx \mathrm{\nabla }{f}_0(x)+\sum _{i=1}^m\frac{1}{-t{f}_i(x)}\mathrm{\nabla }{f}_i(x)+{\mathrm{\nabla }}^2{f}_0(x)v+\sum _{i=1}^m\frac{1}{-t{f}_i(x)}{\mathrm{\nabla }}^2{f}_i(x)v+\sum _{i=1}^m\frac{1}{t{f}_i(x{)}^2}\mathrm{\nabla }{f}_i(x)\mathrm{\nabla }{f}_i(x{)}^{\mathrm{\top }}v$$

用该 Taylor 近似代替非线性项，得到线性方程 $Hv+A^{\mathrm{\top }}\nu =-g$，$Av=0$，其中

$$H={\mathrm{\nabla }}^2{f}_0(x)+\sum _{i=1}^m\frac{1}{-t{f}_i(x)}{\mathrm{\nabla }}^2{f}_i(x)+\sum _{i=1}^m\frac{1}{t{f}_i(x{)}^2}\mathrm{\nabla }{f}_i(x)\mathrm{\nabla }{f}_i(x{)}^{\mathrm{\top }},g=\mathrm{\nabla }{f}_0(x)+\sum _{i=1}^m\frac{1}{-t{f}_i(x)}\mathrm{\nabla }{f}_i(x)$$

注意到 $H={\mathrm{\nabla }}^2{f}_0(x)+(1/t){\mathrm{\nabla }}^2\varphi (x)$，$g=\mathrm{\nabla }{f}_0(x)+(1/t)\mathrm{\nabla }\varphi (x)$，与障碍方法中心点步的 Newton 方程比较可知

$$v=\mathrm{\Delta }{x}_{\mathrm{nt}},\nu =(1/t){\nu }_{\mathrm{nt}}$$

即中心点问题的 Newton 步（在对偶变量缩放 $1/t$ 之后）就是求解修正 KKT 方程的 Newton 步。

在这个做法中，我们先从修正 KKT 方程中消去 $\lambda$，再应用 Newton 方法。另一种变化是不消去 $\lambda$ 而直接对修正 KKT 方程应用 Newton 方法，由此得到所谓的原始—对偶搜索方向​（primal-dual search directions）。