对数障碍函数与中心路径

形式陈述

取整数 $n\ge1$ 、 $m\ge1$ ，考虑定义在 $\mathbb R^n$ 上、目标及不等式函数均二次连续可微的凸问题

\min f_0(x),\qquad f_i(x)\le0\ (i=1,\ldots,m),\qquad Ax=b,

其中 $f_0,f_i$ 凸， $A$ 满行秩。假设存在严格可行点 $Ax=b,f_i(x)<0$ ，并且对每个所用的 $t>0$ ，下述障碍子问题的最小值都能取到：

\min_{Ax=b}\ t f_0(x)+\phi(x),\qquad \phi(x)=-\sum_{i=1}^m\log(-f_i(x)).

障碍函数只在严格可行域内定义。将子问题解记为 $x(t)$ ；若子问题在等式仿射空间上严格凸，解唯一，随 $t$ 变化的这族点称为中心路径。缺少唯一性时，应理解为中心点集合，而不能先假定有一条唯一曲线。

若 $\widehat\nu(t)$ 为障碍子问题的等式乘子，定义

\lambda_i(t)=-\frac1{t f_i(x(t))}>0,\qquad \nu(t)=\widehat\nu(t)/t.

它们满足

\nabla f_0(x(t))+\sum_i\lambda_i(t)\nabla f_i(x(t))+A^T\nu(t)=0, \qquad -\lambda_i(t)f_i(x(t))=\frac1t.

这是把KKT 互补松弛从零改为小正数的系统。中心点给出真正的原始—对偶间隙 $m/t$ ，故

0\le f_0(x(t))-f_*\le\frac mt.

这个界属于精确中心点及其对应对偶变量，不是任意内部点的自动误差界。

直觉

对数在松弛趋于零时趋于负无穷，所以负对数会把临近边界的代价推高。参数 $t$ 增大时，原目标相对于障碍越来越重要，中心点才逐渐向可能位于边界的最优解靠近。

等价地，把整个目标除以 $t$ ，得到 $f_0+\mu\phi$ ，其中 $\mu=1/t$ 。这时是令障碍权重趋于零。与二次罚不同，障碍点留在严格可行侧；罚函数则允许走到约束外。两者的参数方向也不同。

可行线段内的中心点随参数增大靠近边界最优点，松弛与乘子的乘积始终为一除以参数 — 内部路径与间隙证书

例子与边界

一条线段上的完整中心路径

求 $\min x+2y$ ，约束 $x+y=1,x\ge0,y\ge0$ 。唯一最优点为 $(1,0)$ ，最优值为一。严格可行时 $0<y<1$ 、 $x=1-y$ ，障碍子问题化为

\min_{0<y<1}\ t(1+y)-\log y-\log(1-y).

导数为 $t-1/y+1/(1-y)$ 。令其为零并化简，得到

ty^2-(t+2)y+1=0, \qquad y(t)=\frac{2}{t+2+\sqrt{t^2+4}},\quad x(t)=1-y(t).

这里采用的根始终在 $(0,1)$ ；有理化形式避免了大 $t$ 时两个相近数相减。

$t$	$x(t)$	$y(t)$	真正目标误差	可认证上界
$1$	$0.618034$	$0.381966$	$0.381966$	$2$
$4$	$0.809017$	$0.190983$	$0.190983$	$1/2$
$16$	$0.941391$	$0.058609$	$0.058609$	$1/8$

对应不等式写作 $-x\le0,-y\le0$ ，乘子为 $\lambda_x=1/(tx)$ 、 $\lambda_y=1/(ty)$ 。中心方程保证

\lambda_y-\lambda_x=1, \qquad\nu=\lambda_x-1=\lambda_y-2.

于是 $1+\nu-\lambda_x=0$ 、 $2+\nu-\lambda_y=0$ ，对偶可行。等式采用 $x+y-1=0$ 时，对偶目标为 $-\nu$ ；直接计算

(x+2y)-(-\nu)=\lambda_xx+\lambda_yy=\frac2t.

真实目标误差等于 $y(t)$ ，一般小于间隙；对偶下界尚未达到一，所以二者不应混为同一个数。

没有严格可行点时不能直接取对数

约束 $x\le0,-x\le0$ 只允许 $x=0$ ，不存在同时满足两个严格不等式的点。原问题可以很好地定义，但这份对数障碍的定义域为空；应识别等式结构或在适当的低维空间中重新表示，不能向松弛统一加小常数后声称求的是同一障碍问题。

严格可行也不保证障碍子问题有解。取 $f_0(x)=0$ 、约束 $x\ge0$ ，障碍目标为 $-\log x$ ，随 $x\to\infty$ 趋于负无穷。因此最开始的子问题可解性假设有实际内容。

推论与应用

为什么中心点带来合法下界

由中心方程， $x(t)$ 是凸 Lagrangian

L(x,\lambda(t),\nu(t)) =f_0(x)+\sum_i\lambda_i(t)f_i(x)+\nu(t)^T(Ax-b)

的全局最小点。按照对偶函数定义，

d(\lambda(t),\nu(t))=f_0(x(t))-\frac mt.

对偶乘子非负、等式乘子自由，这个值是原最优值的下界。另一方面中心点原始可行，目标是上界。将两界相减就得到 $m/t$ 。证明依赖驻点式与凸性；仅仅设置 $\lambda_i=1/(ts_i)$ ，却没有达到中心方程时，不能把同一计算当作有效对偶值。

障碍法怎样沿着路径计算

一种外层规则是：从严格可行点开始，先近似解给定 $t$ 的障碍问题；然后令 $t\leftarrow4t$ ，用上一个中心点暖启动；重复到精确理论中的 $m/t\le\varepsilon$ 。内层可用等式约束Newton 步，其障碍梯度与 Hessian 为

\nabla\phi=-\sum_i\frac{\nabla f_i}{f_i},\qquad \nabla^2\phi=\sum_i\left( \frac{\nabla f_i\nabla f_i^T}{f_i^2} -\frac{\nabla^2 f_i}{f_i}\right).

两个 Hessian 项都半正定。若在等式切空间上正定，Newton 方向唯一；回溯首先保持所有 $f_i(x+\alpha p)<0$ ，再检查障碍目标下降。每次接受点都保持原始可行，这是该版本的核心不变量。

内层只能近似中心化时，还要记录中心方程残差，并用实际可行对偶点重算间隙，或使用带内层误差项的理论界。对于 LP，原始与对偶可行时直接计算目标差即可。原始—对偶内点法进一步把乘子作为独立变量，联合修正驻点、可行性和互补残差，省去每个外层参数都精确中心化的要求。

复杂度结论的适用范围

直接稠密解一次等式 Newton 块系统，成本通常为 $O((n+p)^3)$ ，其中 $p$ 是等式条数，函数与导数组装另计。对目标和约束均为线性的线性规划，采用标准对数障碍时，若初始间隙尚未达标，即 $0<\varepsilon<m/t_0$ ，配合自协调分析和保持中心邻域的短步路径跟随，可以得到 $O(\sqrt m\log(m/(t_0\varepsilon)))$ 量级的 Newton 步数界；这不是任意增大四倍规则或任意光滑凸障碍都具有的复杂度保证。

靠近边界时，某些松弛很小，障碍 Hessian 中的逆平方项会很大。变量缩放、稳定块消元和实际残差检查因此仍然重要。间隙认证的是目标误差，若还需要变量距离误差，要另加强凸性或相应的误差界。

参考资料

Stephen Boyd and Lieven Vandenberghe, Convex Optimization, 2004，§§11.2–11.3，中心路径、对偶点与障碍法；§11.5，自协调条件下的复杂度。
Robert M. Freund, Penalty and Barrier Methods, MIT, 2004，§3，障碍定义域与极限思想。

形式陈述 ​

一条线段上的完整中心路径 ​

没有严格可行点时不能直接取对数 ​

为什么中心点带来合法下界 ​

障碍法怎样沿着路径计算 ​

复杂度结论的适用范围 ​

反向链接