KNOWECON WIKI

ARTICLE

内点法

内点法 (Interior Point Method) 内点法是一类求解带约束优化问题的核心算法，其基本思想是：迭代点始终保持在可行域的内部（严格满足不等式约束），通过沿"中心路径"逐步逼近最优解。与在可行域边界上移动的单纯形法形成鲜明对比，内点法沿着可行域的内部路径收敛到最优解附近的边界点。内点法具有多项式时间复杂度，是求解线性规划、二次规划、半正定规划和

浏览 3 更新 2025-10-29

内点法 (Interior Point Method)

内点法是一类求解带约束优化问题的核心算法，其基本思想是：迭代点始终保持在可行域的内部（严格满足不等式约束），通过沿"中心路径"逐步逼近最优解。与在可行域边界上移动的单纯形法形成鲜明对比，内点法沿着可行域的内部路径收敛到最优解附近的边界点。内点法具有多项式时间复杂度，是求解线性规划、二次规划、半正定规划和二阶锥规划的主流数值方法，也是 Gurobi、CPLEX、CVX 等现代优化求解器的底层核心技术之一。

历史背景

内点法的思想可追溯至 20 世纪 60 年代。Fiacco 和 McCormick 于 1968 年在非线性规划中系统提出了序列无约束极小化技术（SUMT），其核心即对数障碍函数法——在目标函数中引入障碍项惩罚靠近边界的点，将带约束问题转化为一系列无约束子问题。然而，该方法在当时并未引起线性规划领域的重视，因为单纯形法在实践中表现出色。

1984 年，AT\&T 贝尔实验室的 Narendra Karmarkar 发表了一项里程碑式成果：针对线性规划问题，他提出了一种多项式时间的内点算法，其理论复杂度为 O(n3.5L)O(n^{3.5} L)（其中 nn 为变量维数，LL 为输入数据的比特长度），显著优于单纯形法在最坏情况下的指数复杂度。这一突破在当时引发了巨大震动，被《纽约时报》等主流媒体广泛报道，直接推动了内点法此后三十余年的高速发展。

随后，研究者发现 Karmarkar 的方法与 Fiacco-McCormick 对数障碍法在数学上等价，并在此基础上发展出更为高效的原始-对偶内点法。Lustig、Marsten 和 Shanno 等人于 1990 年代将原始-对偶内点法推广至大规模线性规划，Megiddo、Kojima 等人则建立了中心路径和预测-校正算法的理论框架。至 21 世纪初，内点法已在理论和实践中全面成熟。

核心数学框架

障碍函数与中心路径

考虑标准形式的线性规划问题：

minimize⁡c⊤xsubject toAx=b,x≥0\begin{aligned} \operatorname{minimize} \quad & c^\top x \\ \text{subject to} \quad & Ax = b, \\ & x \geq 0 \end{aligned}

内点法将非负约束 x≥0x \geq 0 通过对数障碍函数 −μ∑j=1nln⁡xj-\mu \sum_{j=1}^{n} \ln x_j 纳入目标函数，其中 μ>0\mu > 0 为障碍参数（barrier parameter）。由此构造障碍问题：

minimize⁡c⊤x−μ∑j=1nln⁡xjs.t. Ax=b\operatorname{minimize} \quad c^\top x - \mu \sum_{j=1}^{n} \ln x_j \quad \text{s.t. } Ax = b

当 xj→0+x_j \to 0^+ 时，−ln⁡xj→+∞-\ln x_j \to +\infty，强制迭代点严格保持在 {x∣xj>0}\{x \mid x_j > 0\} 的正象限内部。

对每个固定的 μ>0\mu > 0，障碍问题存在唯一的最优解 x∗(μ)x^*(\mu)。令 μ→0+\mu \to 0^+，x∗(μ)x^*(\mu) 的轨迹构成一条光滑曲线，称为中心路径（central path）。中心路径的参数方程为 x∗(μ)x^*(\mu)，且满足 lim⁡μ→0+x∗(μ)=x∗\lim_{\mu \to 0^+} x^*(\mu) = x^*，即原问题的最优解。内点法的核心策略是沿中心路径逐步减小 μ\mu，求解一系列近似问题，最终收敛到最优解。

原始-对偶内点法

现代内点法的主流实现是原始-对偶内点法，其同时处理原始变量 xx 和对偶变量（乘子）y,sy, s。线性规划的标准对偶问题为：

maximize⁡b⊤ysubject toA⊤y+s=c,s≥0\begin{aligned} \operatorname{maximize} \quad & b^\top y \\ \text{subject to} \quad & A^\top y + s = c, \\ & s \geq 0 \end{aligned}

KKT 条件在加入障碍项 μ\mu 后变形为扰动 KKT 系统：

A⊤y+s=c,Ax=b,xjsj=μ,j=1,…,n,x,s>0\begin{aligned} A^\top y + s &= c, \\ Ax &= b, \\ x_j s_j &= \mu, \quad j = 1, \ldots, n, \\ x, s &> 0 \end{aligned}

其中 xjsj=μx_j s_j = \mu 为扰动互补松弛条件，替代原互补条件 xjsj=0x_j s_j = 0。

原始-对偶内点法应用牛顿法求解上述非线性系统：在当前迭代点 (x,y,s)(x, y, s) 处线性化，求解牛顿步 (Δx,Δy,Δs)(\Delta x, \Delta y, \Delta s)，再沿该方向进行步长选择，确保 xx 和 ss 保持正性。障碍参数 μ\mu 按 μ←σ⋅(x⊤s)/n\mu \leftarrow \sigma \cdot (x^\top s) / n 更新，其中 σ∈(0,1)\sigma \in (0, 1) 为中心参数，控制沿中心路径推进的激进程度。

预测-校正策略

实践中广泛使用的 Mehrotra 预测-校正算法包含两个步骤：

  • 预测步：设 μ=0\mu = 0（即目标互补间隙为零），求解仿射方向 (Δxaff,Δyaff,Δsaff)(\Delta x_{\text{aff}}, \Delta y_{\text{aff}}, \Delta s_{\text{aff}})。该步骤追求快速减小对偶间隙，但不保证迭代点严格在正象限内。
  • 校正步：基于预测步结果估计真实的中心路径方向，并自适应选择中心参数 σ\sigma，再求解校正后的牛顿步。该步骤将迭代拉回中心路径附近，保证后续迭代的稳定性。

Mehrotra 预测-校正算法在实践中通常比纯原始-对偶方法快 30\%–50\%，是当前大多数商业求解器的默认实现。

与单纯形法的对比

内点法与单纯形法的主要差异如下：

  • 迭代路径：单纯形法沿可行域多面体的顶点（基本可行解）移动，每次迭代切换到一个相邻顶点；内点法穿越可行域内部，不限定在顶点上。
  • 理论复杂度：单纯形法在最坏情况下可能访问指数级数量的顶点（Klee-Minty 反例），而内点法具有多项式时间复杂度 O(n3.5L)O(n^{3.5} L)，理论上有保证。
  • 实际表现：对于大规模稀疏线性规划问题，内点法通常显著快于单纯形法；对于中小规模或需要频繁重优化（如分支定界中的割平面）的场景，单纯形法的热启动能力使其更具优势。
  • 解的性质：单纯形法返回严格的基本可行解（位于顶点），解是精确的；内点法收敛到最优面的内部点，需要通过"交叉"(crossover)步骤从内部最优解移动到边界顶点以获取基本可行解。

二者在实践中互补，现代优化求解器通常同时提供两种算法供用户选择。

算法扩展

内点法不仅限于线性规划，其框架已成功扩展至：

  • 二次规划 (QP)：目标函数为二次，约束为线性。对数障碍函数与正定二次目标相容，原始-对偶框架可直接推广。
  • 半正定规划 (SDP)：变量为对称矩阵，约束包含半正定性条件 X⪰0X \succeq 0。利用障碍函数 −μln⁡det⁡X-\mu \ln \det X（对数-行列式障碍），内点法成为 SDP 的主流算法，在组合优化和控制理论中有广泛应用。
  • 二阶锥规划 (SOCP)：约束包含二阶锥 ∥Ax+b∥2≤c⊤x+d \|Ax + b\|_2 \leq c^\top x + d 。内点法可处理此类非线性但保持良好结构的约束，在稳健优化和机器学习中频繁出现。
  • 非线性凸规划：对于一般的非线性凸约束 fi(x)≤0f_i(x) \leq 0，对数障碍 −μ∑ln⁡(−fi(x))-\mu \sum \ln(-f_i(x)) 保持内点性质，与逐次二次规划 (SQP) 结合形成内点 SQP 算法。

在经济学中的应用

内点法在经济学中扮演着日益重要的角色。

可计算一般均衡 (CGE) 模型通常涉及大规模、稀疏的非线性方程组，内点法在求解 CGE 模型的互补问题形式时表现出优良的收敛性和数值稳定性。资产组合优化中，带有大量不等式约束和半正定约束的投资组合问题是内点法求解半正定规划的典型应用，能够得到严格满足风险预算约束的最优配置。拍卖与机制设计研究中，激励相容约束常转化为线性不等式系统，内点法在高维投标空间下优于单纯形法。计量经济学中，大规模 LASSO 回归和带约束的广义矩方法（GMM）估计均可归结为二次锥规划，内点法是稳健且高效的选择。

局限性与注意事项

尽管内点法理论优美、实践强大，但也存在若干局限。首先，内点法求解的是近似解，最终结果位于最优面的内部而非顶点，若需要精确的顶点解则需额外交叉步骤。其次，热启动困难是内点法相对于单纯形法的显著劣势——在分支定界等需要反复求解相似问题的框架中，内点法难以有效利用前次求解的信息。此外，对于某些特定结构的病态问题，中心路径可能变得极窄，导致数值不稳定性。最后，超大规模问题上（变量数超过 10710^7），矩阵分解的存储和计算成本仍构成瓶颈，需要结合一阶方法（如 ADMM 和随机梯度法）进行互补使用。