基于自和谐的复杂度分析

利用 Newton 方法对自和谐函数的复杂度分析，可以对障碍方法进行复杂度分析。该分析适用于许多常见问题，并导出若干有趣的结论：它给出了用障碍方法求解问题所需 Newton 步总数的严格界，并解释了我们的观察——中心点问题并不随 $t$ 增大而变得更难。

自和谐性假设

我们做两个假设：

• 函数 $t{f}_0+\varphi$ 对所有 $t⩾t^{(0)}$ 都是闭的且自和谐的。
• 问题的下水平集有界。

第二个假设意味着中心点问题的下水平集有界，因此中心点问题可解；该假设还蕴含 $t{f}_0+\varphi$ 的 Hessian 处处正定。虽然自和谐性假设把复杂度分析限制在一类特定的问题上，但需要强调：无论自和谐假设是否成立，障碍方法都工作良好。

自和谐性假设对很多问题成立，包括所有线性与二次问题：若 $f_i$ 都是线性或二次函数，则 $t{f}_0-\sum _{i=1}^m\log (-f_i)$ 对所有 $t⩾0$ 自和谐。因此下面的复杂度分析适用于 LP、QP 和 QCQP。

在其他情形，可以通过改写问题使自和谐假设成立。例如线性不等式约束的熵最大化问题（目标 $\sum _i{x}_i\log x_i$，约束 $Fx⪯g$、$Ax=b$）的 $t{f}_0+\varphi$ 不是闭的（除非 $Fx⪯g$ 蕴含 $x⪰0$），也不是自和谐的。但加入冗余不等式约束 $x⪰0$ 得到等价问题后，

$$t{f}_0(x)+\varphi (x)=t\sum _{i=1}^n{x}_i\log x_i-\sum _{i=1}^n\log x_i-\sum _{i=1}^m\log (g_i-f_i^{\mathrm{\top }}x)$$

对任意 $t⩾0$ 都是闭的且自和谐的（函数 $tx\log x-\log x$ 在 ${\mathbf{R}}_{++}$ 上对所有 $t⩾0$ 自和谐）。

一个更特别的例子是 GP：目标 $\log \sum _k\exp (a_{0k}^{\mathrm{\top }}x+b_{0k})$ 与对数和指数约束的 GP 的 $t{f}_0+\varphi$ 是否自和谐并不清楚，因此尽管障碍方法可用，本节的复杂度分析未必适用。不过可以通过引入上界变量 $y_{ik}$（对每个单项式项 $\exp (a_{ik}^{\mathrm{\top }}x+b_{ik})$ 引入 $\exp (a_{ik}^{\mathrm{\top }}x+b_{ik})⩽y_{ik}$）把 GP 改写为

$$\begin{array}{rl}\mathrm{minimize}& \sum _{k=1}^{K_0}{y}_{0k}\\ \mathrm{subject}\mathrm{to}& \sum _{k=1}^{K_i}{y}_{ik}⩽1,i=1,\cdots ,m\\ & a_{ik}^{\mathrm{\top }}x+b_{ik}-\log y_{ik}⩽0,i=0,\cdots ,m,k=1,\cdots ,K_i\\ & y_{ik}⩾0,i=0,\cdots ,m,k=1,\cdots ,K_i\end{array}$$

其相应的对数障碍

$$\sum _{i=0}^m\sum _{k=1}^{K_i}(-\log y_{ik}-\log (\log y_{ik}-a_{ik}^{\mathrm{\top }}x-b_{ik}))-\sum _{i=1}^m\log (1-\sum _{k=1}^{K_i}{y}_{ik})$$

是闭的且自和谐的；由于目标函数是线性的，$t{f}_0+\varphi$ 对任意 $t$ 都闭且自和谐。

每个中心点步的 Newton 迭代次数

自和谐函数的 Newton 方法复杂度理论表明：极小化一个闭的严格凸自和谐函数 $f$ 所需的 Newton 迭代次数不超过

$$\frac{f(x)-p^{\star }}{\gamma }+c$$

其中 $x$ 是初始点，$p^{\star }=\underset{x}{inf}f(x)$。常数 $\gamma$ 只依赖于回溯参数 $\alpha$ 和 $\beta$：

$$\frac{1}{\gamma }=\frac{20-8\alpha }{\alpha \beta (1-2\alpha {)}^2}$$

常数 $c$ 只依赖于容许误差 ${ϵ}_{\mathrm{nt}}$：$c={\log }_2{\log }_2(1/{ϵ}_{\mathrm{nt}})$，合理地可近似为 $c=6$。这个界对所需 Newton 步数相当保守，但我们的兴趣只在于建立复杂度界，并关注它随问题规模与算法参数的增长方式。

用该结果可以推导障碍方法一次外层迭代（即从 $x^{\star }(t)$ 出发计算 $x^{\star }(\mu t)$）所需 Newton 步数的界。为简化记号，用 $x$ 表示当前迭代点 $x^{\star }(t)$，$x^{+}$ 表示下一个迭代点 $x^{\star }(\mu t)$；用 $\lambda ,\nu$ 表示 ${\lambda }^{\star }(t),{\nu }^{\star }(t)$。

自和谐性假设意味着

$$\frac{\mu t{f}_0(x)+\varphi (x)-\mu t{f}_0(x^{+})-\varphi (x^{+})}{\gamma }+c$$

是从 $x^{\star }(t)$ 出发计算 $x^{+}$ 所需 Newton 步数的上界。遗憾的是，在真正算出 $x^{+}$ 之前我们并不知道它，因而也不知道这个上界。不过可以对它再作上界估计：

$$\begin{array}{rl}\mu t{f}_0(x)+\varphi (x)-\mu t{f}_0(x^{+})-\varphi (x^{+})& =\mu t{f}_0(x)-\mu t{f}_0(x^{+})+\sum _{i=1}^m\log (-\mu t{\lambda }_i{f}_i(x^{+}))-m\log \mu \\ & ⩽\mu t{f}_0(x)-\mu t\sum _{i=1}^m{\lambda }_i{f}_i(x^{+})-m-m\log \mu \\ & =\mu t{f}_0(x)-\mu t(f_0(x^{+})+\sum _{i=1}^m{\lambda }_i{f}_i(x^{+})+{\nu }^{\mathrm{\top }}(A{x}^{+}-b))-m-m\log \mu \\ & ⩽\mu t{f}_0(x)-\mu tg(\lambda ,\nu )-m-m\log \mu \\ & =m(\mu -1-\log \mu )\end{array}$$

对推导的说明：从第一行到第二行利用 ${\lambda }_i=-1/(t{f}_i(x))$；第一个不等式利用 $\log a⩽a-1$（$a>0$）；第三、四行之间利用 $A{x}^{+}=b$（额外的 ${\nu }^{\mathrm{\top }}(A{x}^{+}-b)$ 项为零）；第二个不等式由对偶函数的定义（$g(\lambda ,\nu )⩽f_0(x^{+})+\sum _i{\lambda }_i{f}_i(x^{+})+{\nu }^{\mathrm{\top }}(A{x}^{+}-b)$）得到；最后一行来自 $g(\lambda ,\nu )=f_0(x)-m/t$。

结论是

$$\frac{m(\mu -1-\log \mu )}{\gamma }+c$$

是障碍方法一次外层迭代所需 Newton 步数的上界。函数 $\mu -1-\log \mu$ 在 $\mu$ 很小时近似二次，在 $\mu$ 很大时近似线性增长。这与直觉一致：$\mu$ 接近 1 时重新中心化所需步数少，$\mu$ 大时步数可能增长。

该界表明：每个中心点步所需 Newton 步数由一个主要依赖于 $\mu$（障碍方法外层步中 $t$ 的更新因子）和 $m$（不等式约束个数）的量控制，它对内层迭代直线搜索参数 $\alpha$、$\beta$ 的依赖较弱，对内层迭代终止容许误差的依赖非常弱。有趣的是，该界不依赖于变量维数 $n$、等式约束个数 $p$，也不依赖于问题的具体数据（只要自和谐假设成立）。最后注意它也不依赖于 $t$：特别地，当 $t\to \mathrm{\infty }$ 时，每次外层迭代所需 Newton 步数有一个一致的上界。

Newton 迭代总次数

现在可以给出障碍方法 Newton 步总数的上界（不计初始中心点步，它将在阶段 I 分析中处理）。把每个外层迭代的界乘以所需外层步数，得

$$N=\lceil \frac{\log (m/(t^{(0)}ϵ))}{\log \mu }\rceil (\frac{m(\mu -1-\log \mu )}{\gamma }+c)$$

该式表明：当自和谐假设成立时，对任意 $\mu >1$ 都可以给出障碍方法所需 Newton 步数的界。

若固定 $\mu$ 和 $m$，则 $N$ 与 $\log (m/(t^{(0)}ϵ))$ 成正比——即初始对偶间隙 $m/t^{(0)}$ 与最终对偶间隙 $ϵ$ 之比（要求的对偶间隙缩减倍数）的对数。因此可以说障碍方法至少线性收敛：达到给定精度所需步数随精度的倒数按对数增长。

若 $\mu$ 和所需的对偶间隙缩减倍数固定，则界 $N$ 随 $m$（不等式个数）线性增长；$N$ 不依赖于其他问题维数 $n$、$p$，也不依赖于具体的问题数据或函数。下面会看到，通过选取依赖于 $m$ 的特定 $\mu$ 值，可以得到只按 $\sqrt{m}$（而不是 $m$）增长的界。

最后分析 $N$ 关于算法参数 $\mu$ 的变化：当 $\mu$ 趋于 1 时，$N$ 的第一项增大，因此 $N$ 增大——这与 $\mu$ 接近 1 时外层迭代极多的直觉和观察一致；$\mu$ 大时，$N$ 近似按 $\mu /\log \mu$ 增长——因为每次外层迭代所需步数的界增大，同样符合观察。因此 $N$ 作为 $\mu$ 的函数有最小值。以 $c=6$、$\gamma =1/375$、$m/(t^{(0)}ϵ)={10}^5$、$m=100$ 为例，界 $N$ 在 $\mu \approx 1.02$ 处最小，约为 8000 次 Newton 迭代。该复杂度分析是保守的，但选择 $\mu$ 的基本折中确实反映在曲线中。（实践中大得多的 $\mu$（约 2 到 100）都工作很好，所需 Newton 迭代总数只是几十的量级。）

待配图​：对应教材图 11.13 与图 11.14 —— 函数 $\mu -1-\log \mu$ 的曲线；以及总 Newton 迭代次数上界 $N$ 随 $\mu$ 变化的曲线（含最小值）。

把 $\mu$ 取为 $m$ 的函数

当 $\mu$（及所需对偶间隙缩减倍数）固定时，界 $N$ 随 $m$ 线性增长；但通过把 $\mu$ 取为 $m$ 的函数，可以得到更好的增长阶。取

$$\mu =1+1/\sqrt{m}$$

利用 $-\log (1+a)⩽-a+a^2/2$（$a⩾0$）与对数函数的凹性（$\log (1+1/\sqrt{m})⩾(\log 2)/\sqrt{m}$），可得 $\mu -1-\log \mu ⩽1/(2m)$，于是总步数满足

$$N⩽\lceil \sqrt{m}\frac{{\log }_2(m/(t^{(0)}ϵ))}{m}\rceil (\frac{1}{2\gamma }+c)⩽c_1+c_2\sqrt{m}$$

其中

$$c_1=\frac{1}{2\gamma }+c,c_2={\log }_2(m/(t^{(0)}ϵ))(\frac{1}{2\gamma }+c)$$

这里 $c_1$（只弱依赖于中心点 Newton 步的算法参数）与 $c_2$（还依赖于所需的对偶间隙缩减倍数）中，${\log }_2(m/(t^{(0)}ϵ))$ 正好是所需对偶间隙缩减的位数。

对固定的对偶间隙缩减要求，界随 $\sqrt{m}$ 增长，而固定 $\mu$ 时的界按 $m$ 增长。因此取参数值 $\mu =1+1/\sqrt{m}$ 的障碍方法被称为阶 $\sqrt{m}$ 方法​（order $\sqrt{m}$ method）。

实践中我们不会使用 $\mu =1+1/\sqrt{m}$（它太小了），也不会随 $m$ 减小 $\mu$。我们对这个值的唯一兴趣在于：它（近似地）极小化我们（非常保守的）Newton 步数上界，并给出按 $\sqrt{m}$（而不是 $m$）增长的整体估计。

可行性问题

本节分析基本阶段 I 方法的一个（小的）变体用于求解凸不等式组

$$f_1(x)⩽0,\cdots ,f_m(x)⩽0$$

的复杂度（$f_i$ 凸、二阶导数连续；等式约束稍后考虑）。假设阶段 I 问题

$$\mathrm{minimize}s\mathrm{subject}\mathrm{to}{f}_i(x)⩽s,i=1,\cdots ,m$$

满足前述自和谐性条件。特别地，假设不等式组的可行集（当然可能为空）包含在半径为 $R$ 的欧氏球内：

$$\{x\mid f_i(x)⩽0,i=1,\cdots ,m\}\subseteq \{x\mid \parallel x{\parallel }_2⩽R\}$$

可以把 $R$ 解释为对可行集内任何点的范数的一个先验上界；该假设保证了阶段 I 问题的下水平集有界。不失一般性，从 $x=0$ 出发。定义 $F=\underset{i}{max}{f}_i(0)$（最大约束违反量，设为正，否则 $x=0$ 已满足不等式组），${\overline{p}}^{\star }$ 为阶段 I 问题的最优值。

${\overline{p}}^{\star }$ 的符号决定不等式组是否可行；其大小也有含义。若 ${\overline{p}}^{\star }$ 为正且较大（接近其可能的最大值 $F$），说明不等式组相当不可行——对每个 $x$，至少有一个不等式被至少 ${\overline{p}}^{\star }$ 地违反。若 ${\overline{p}}^{\star }$ 为负且绝对值大，说明不等式组相当可行——不仅存在使所有 $f_i$ 非正的 $x$，而且存在使它们都相当负（至多 ${\overline{p}}^{\star }$）的 $x$。因此 $|{\overline{p}}^{\star }|$ 度量了不等式组可行或不可行的“明显程度”，从而与判定可行性的难度相关：$|{\overline{p}}^{\star }|$ 小意味着问题接近可行与不可行的边界。

为判定可行性，对阶段 I 问题做一个变体：增加一条冗余的线性不等式 $a^{\mathrm{\top }}x⩽1$（$a$ 稍后确定，将满足 $\parallel a{\parallel }_2⩽1/R$，故 $\parallel x{\parallel }_2⩽R$ 蕴含 $a^{\mathrm{\top }}x⩽1$，即该约束是冗余的）：

$$\mathrm{minimize}s\mathrm{subject}\mathrm{to}{f}_i(x)⩽s,i=1,\cdots ,m,a^{\mathrm{\top }}x⩽1$$

选取 $a$ 与 $s^{(0)}$，使 $x=0$、$s=s^{(0)}$ 位于该问题中心路径上参数 $t^{(0)}$ 对应的点，即它们极小化

$$t^{(0)}s-\sum _{i=1}^m\log (s-f_i(x))-\log (1-a^{\mathrm{\top }}x)$$

令对 $s$ 的导数为零得

$$t^{(0)}=\sum _{i=1}^m\frac{1}{s^{(0)}-f_i(0)}$$

令对 $x$ 的梯度为零得

$$a=-\sum _{i=1}^m\frac{1}{s^{(0)}-f_i(0)}\mathrm{\nabla }{f}_i(0)$$

因此只需选取参数 $s^{(0)}$：选定后 $a$ 与 $t^{(0)}$ 分别由上两式给出。为保证 $x=0$、$s=s^{(0)}$ 对阶段 I 问题严格可行，必须 $s^{(0)}>F$；为保证 $\parallel a{\parallel }_2⩽1/R$，由上式有 $\parallel a{\parallel }_2⩽\sum _i\parallel \nabla f_i(0){\parallel }_2/(s^{(0)}-F)⩽mG/(s^{(0)}-F)$（$G=\underset{i}{max}\parallel \mathrm{\nabla }{f}_i(0){\parallel }_2$），故可取

$$s^{(0)}=mGR+F$$

由此 $\parallel a{\parallel }_2⩽1/R$，冗余线性不等式确实冗余。再由 $t^{(0)}$ 的表达式（注意 $F=\underset{i}{max}{f}_i(0)$）可得 $t^{(0)}⩾1/(mGR)$，因此 $x=0$、$s=s^{(0)}$ 位于阶段 I 问题中心路径上、初始对偶间隙为

$$\frac{m+1}{t^{(0)}}⩽(m+1)mGR$$

求解原不等式组需要确定 ${\overline{p}}^{\star }$ 的符号。当问题的对偶间隙小于 $|{\overline{p}}^{\star }|$ 时，原问题目标值为负（说明可行）或对偶目标值为正（说明不可行）两个条件之一必然发生。用障碍方法求解（从一个对偶间隙不超过 $(m+1)mGR$ 的中心点出发，在对偶间隙小于 $|{\overline{p}}^{\star }|$ 时或之前终止），所需 Newton 步数不超过

$$\lceil \sqrt{m+1}{\log }_2\frac{m(m+1)GR}{|{\overline{p}}^{\star }|}\rceil (\frac{1}{2\gamma }+c)$$

（这里取 $\mu =1+1/\sqrt{m+1}$，它比固定的 $\mu$ 给出更好的复杂度增长阶。）该界只比 $\sqrt{m}$ 略快，且对中心点步算法参数的依赖较弱；它近似正比于 ${\log }_2((GR)/|{\overline{p}}^{\star }|)$，后者可以解释为该可行性问题的难度（或其接近可行/不可行边界的程度）的度量。

带等式约束的可行性问题​：可以通过消去等式约束把同样的分析应用于带等式约束的可行性问题。这不影响问题的自和谐性，但意味着 $G$ 与 $R$ 指的是约简（消去后）问题的相应量。

阶段 I 与阶段 II 的组合复杂度

本节给出用障碍方法求解问题

$$\mathrm{minimize}{f}_0(x)\mathrm{subject}\mathrm{to}{f}_i(x)⩽0,i=1,\cdots ,m,Ax=b$$

的端到端复杂度分析（含阶段 I 的变体）。先求解阶段 I 问题

$$\mathrm{minimize}s\mathrm{subject}\mathrm{to}{f}_i(x)⩽s,i=1,\cdots ,m,f_0(x)⩽M,Ax=b,a^{\mathrm{\top }}x⩽1$$

假设它满足自和谐与有界下水平集假设。这里增加了两条冗余不等式：约束 $f_0(x)⩽M$ 保证阶段 I 中心路径与阶段 II 中心路径相交（$M$ 是最优值的一个先验上界）；第二条是线性不等式 $a^{\mathrm{\top }}x⩽1$（$a$ 按上文方式选取）。用 $\mu =1+1/\sqrt{m+2}$ 与初始点 $x=0$、$s=s^{(0)}$ 求解该问题。

要找到严格可行点或判定问题不可行，所需 Newton 步数不超过

$$N_{\mathrm{I}}=\lceil \sqrt{m+2}{\log }_2\frac{(m+1)(m+2)GR}{|{\overline{p}}^{\star }|}\rceil (\frac{1}{2\gamma }+c)$$

其中 $G$、$R$ 按上文定义。若问题不可行，到此结束；若可行，则在阶段 I 中得到一个与 $s=0$ 相关联、位于阶段 II 问题（含冗余约束 $a^{\mathrm{\top }}x⩽1$）中心路径上的点，其初始对偶间隙不超过 $(m+1)(M-p^{\star })$。假设阶段 II 问题同样满足自和谐与有界下水平集假设。

接下来进入阶段 II，再次使用障碍方法：把对偶间隙从初始值（不超过 $(m+1)(M-p^{\star })$）降到某个容许误差 $ϵ>0$，至多需要

$$N_{\mathrm{II}}=\lceil \sqrt{m+1}{\log }_2\frac{(m+1)(M-p^{\star })}{ϵ}\rceil (\frac{1}{2\gamma }+c)$$

次 Newton 步。因此总步数不超过 $N_{\mathrm{I}}+N_{\mathrm{II}}$。该界随不等式个数 $m$ 近似按 $\sqrt{m}$ 增长，并包含两个依赖于具体问题实例的项：

$${\log }_2\frac{GR}{|{\overline{p}}^{\star }|},{\log }_2\frac{M-p^{\star }}{ϵ}$$

总结

本节给出的复杂度分析主要具有理论意义。特别要提醒读者：这里讨论的 $\mu =1+1/\sqrt{m}$ 在实践中是一个非常糟糕的选择；它的唯一优点是使界按 $\sqrt{m}$ 而不是 $m$ 增长。同样，实践中也不建议添加冗余不等式 $a^{\mathrm{\top }}x⩽1$。

这里分析得到的界远高于实际观察到的迭代次数；甚至界中的增长阶看起来也是保守的：最好的界按 $\sqrt{m}$ 增长，而实际经验表明所需 Newton 步数几乎不随 $m$（或任何其他参数）增长。

尽管如此，知道以下事实是令人安心的：当自和谐条件成立时，可以对障碍方法的每个中心点步所需 Newton 步数给出一致上界。障碍方法一个潜在的缺陷是：随着 $t$ 增长，相应的中心点问题可能变得更难、需要更多 Newton 步。实践表明情况并非如此，而一致界增强了我们“这不可能发生”的信心。

最后我们指出：把问题改写成使自和谐条件成立的形式是否具有实际好处，目前尚不清楚。我们所能说的是：当自和谐条件成立时，障碍方法在实践中工作良好，并且我们可以给出最坏情形复杂度界。