原始—对偶内点法 | Codeboy's Blog

形式陈述

\min c^Tx\quad\text{s.t. }Ax=b,\ x\ge0, \qquad \max b^Ty\quad\text{s.t. }A^Ty+s=c,\ s\ge0.

取整数 $n\ge1$ 、 $0\le m\le n$ ，设 $A\in\mathbb R^{m\times n}$ 满行秩。算法保存 $x>0,s>0$ 与自由变量 $y$ ，不要求初值已经满足两个等式。定义

r_p=Ax-b,\qquad r_d=A^Ty+s-c,\qquad \mu=\frac{x^Ts}{n},\qquad X=\operatorname{diag}(x),\ S=\operatorname{diag}(s).

给定中心化参数 $0<\sigma<1$ ，对方程 $r_p=0,r_d=0,Xs=\sigma\mu\mathbf1$ 作一次Newton 线性化，本轮右端中的 $\mu$ 固定为当前值：

\begin{pmatrix} A&0&0\\ 0&A^T&I\\ S&0&X \end{pmatrix} \begin{pmatrix}\Delta x\\\Delta y\\\Delta s\end{pmatrix} =-\begin{pmatrix}r_p\\r_d\\Xs-\sigma\mu\mathbf1\end{pmatrix}.

接着计算到达非负边界的最大步长

\alpha_{\rm bd}=\min\left\{1, \min_{\Delta x_i<0}\frac{-x_i}{\Delta x_i}, \min_{\Delta s_i<0}\frac{-s_i}{\Delta s_i}\right\},

空的内层最小值按无穷处理。取 $\alpha=\tau\alpha_{\rm bd}$ 、 $0<\tau<1$ ，更新三组变量。必要时再回溯，使残差度量下降或使新点保持在明确的中心邻域。本页数值例用 $\tau=0.9$ ；保正规则本身只保证内部性，不是任意问题上的完整收敛定理。

停止时同时检查 $r_p,r_d$ 与 $x^Ts$ ，并按数据尺度设置容差。若两侧等式精确可行， $x^Ts=c^Tx-b^Ty$ 就是真正的对偶间隙；不可行迭代中，这个恒等式不成立。

直觉

中心路径把每对原变量与对偶松弛的乘积暂时保持为一个小正数。原始—对偶内点法不必先精确走到每个中心点，而是让 Newton 系统同时修正三种失衡：资源等式不满足、价格等式不满足、互补乘积偏离目标。

保正步长像一道护栏：原变量或对偶松弛可以靠近零，却不能一步穿过零。它保护了下一轮的对角逆矩阵，也保留了内点几何。护栏之外，还要决定是否取得足够进展；只保持正数并不意味着正在逼近最优解。

三个残差进入同一个 Newton 系统，方向经保正步长缩放后更新原变量、对偶变量与松弛 — 三个残差与保正更新

例子与边界

一个正但不可行的三变量初值

取

A=(1,1,1),\quad b=1,\quad c=(1,2,3)^T, \quad x=(1,1,1)^T,\ s=(1,1,1)^T,\ y=0.

原最优解是 $(1,0,0)$ ，值为一。当前 $r_p=2,r_d=(0,-1,-2)^T,\mu=1$ 。取 $\sigma=1/5$ ，第三组 Newton 方程为 $\Delta x+\Delta s=-(4/5)\mathbf1$ ，第二组给 $\Delta s=(0,1,2)^T-\Delta y\mathbf1$ 。与 $\sum_i\Delta x_i=-2$ 联立，得到

\Delta y=\frac{17}{15},\quad \Delta x=(1/3,-2/3,-5/3)^T,\quad \Delta s=(-17/15,-2/15,13/15)^T.

原变量第三项最先触零，边界比值为 $3/5$ ；对偶松弛第一项的比值为 $15/17$ ，较大。因此 $\alpha_{\rm bd}=3/5$ ，取 $\tau=9/10$ 后 $\alpha=27/50$ 。更新得到

x^+=(59/50,16/25,1/10)^T, \quad s^+=(97/250,116/125,367/250)^T, \quad y^+=153/250.

六个需要保正的分量均大于零。新残差是

r_p^+=23/25,\qquad r_d^+=(0,-23/50,-23/25)^T.

二者恰好都是旧残差乘以 $1-\alpha=23/50$ ，因为两组等式本来就是线性的。互补量则为

(x^+)^Ts^+=\frac{7491}{6250}=1.19856, \qquad\mu^+=\frac{2497}{6250}=0.39952.

它不是把旧 $\mu$ 简单乘以 $\sigma$ ；有限步长与乘积的二阶交叉项都会影响实际结果。

不可行时，互补量不能冒充目标间隙

同一新点的目标差为

c^Tx^+-b^Ty^+=2.148,

与 $1.19856$ 不同。一般恒等式是

c^Tx-b^Ty=x^Ts-x^Tr_d+y^Tr_p.

只有 $r_p=r_d=0$ 时，后两项才消失。当前原变量不满足资源等式，对偶变量也不满足对偶等式，所以两侧目标没有各自合法上界与下界的含义。一个小的互补量如果伴随大可行性残差，不能作为停止证书。

推论与应用

块方程可以怎样消元

由第三行解出

\Delta s=-s+\sigma\mu X^{-1}\mathbf1-X^{-1}S\Delta x.

代入第二行，记 $D=XS^{-1}\succ0$ ，得到

\Delta x=D A^T\Delta y+D r_d-x+\sigma\mu S^{-1}\mathbf1.

再代入第一行，便得到较小的Schur 补系统

A D A^T\Delta y =-r_p-A D r_d+Ax-\sigma\mu A S^{-1}\mathbf1.

$A$ 满行秩、 $D$ 正定，故 $ADA^T$ 正定。解出 $\Delta y$ 后回代即可。接近最优解时 $x_i/s_i$ 的尺度可能悬殊，正规方程式消元也可能放大条件问题；稀疏对称不定分解是另一种实现路线，不能因为代数上正定就忽略数值条件。

哪些量严格保持，哪些只近似改善

采用公共步长时，精确线性求解给出 $r_p^+=(1-\alpha)r_p$ 、 $r_d^+=(1-\alpha)r_d$ 。若初值两侧可行，这两个不变量会一直保持。保正规则则使 $x^+,s^+>0$ 。互补乘积满足

X^+s^+ =(1-\alpha)Xs+\alpha\sigma\mu\mathbf1 +\alpha^2\operatorname{diag}(\Delta x)\Delta s.

最后一项解释了预测与实际互补量的差别。将 Newton 方程中的 $\sigma$ 设为零，得到仿射缩放预测方向；Mehrotra 型预测—校正方法再根据预测结果选择中心化强度，并把这个乘积交叉项纳入校正右端，但那是本基本步骤的扩展，不应把一次线性化当成完整预测—校正算法。

收敛保证与运行成本

若原、对偶都有严格可行点，取足够接近中心路径的可行初值，使用保持标准中心邻域的短步规则，且目标尚未达到（ $0<\varepsilon<\mu_0$ ）时，可以得到 $O(\sqrt n\log(\mu_0/\varepsilon))$ 量级的迭代界，其中目标是将平均互补量压到 $\varepsilon$ 。这个结论依赖邻域、中心化参数与步长的配合；不可行初值还要额外控制两类可行性残差。本文的一个数值步展示方程怎样执行，没有把单独的 fraction-to-boundary 规则说成上述复杂度算法。

稠密形成 $ADA^T$ 的成本为 $O(m^2n)$ ，分解为 $O(m^3)$ ，方向恢复、向量更新及矩阵向量积另需 $O(n+mn)$ ；稀疏系统的成本由非零模式和填充决定。应重算三组真实残差，并区分达到精度、线性求解失败、停滞和预算耗尽。

对于仅含线性不等式 $Ax\le b$ 的凸 QP，可以把驻点残差改为 $Hx+c+A^T\lambda$ ，并显式保存松弛 $s=b-Ax$ 与非负乘子 $\lambda$ 。此时一阶块带有 $H$ ，但“线性化三组条件，再保正并验收”的组织方式不变。通用的原始—对偶设计思想在这里落实为一个具体的数值线性系统。

参考资料

Stephen Boyd and Lieven Vandenberghe, Convex Optimization, 2004，§11.7 的原始—对偶残差、Newton 方向与回溯，§11.8 的消元实现。
Stephen J. Wright, Primal-Dual Interior-Point Methods, SIAM, 1997，Chs. 2–5，中心邻域和路径跟随复杂度。
Sanjay Mehrotra, “On the Implementation of a Primal-Dual Interior Point Method”, SIAM Journal on Optimization 2(4), 1992, pp. 575–601，预测—校正实现的原始研究。

形式陈述 ​

一个正但不可行的三变量初值 ​

不可行时，互补量不能冒充目标间隙 ​

块方程可以怎样消元 ​

哪些量严格保持，哪些只近似改善 ​

收敛保证与运行成本 ​