KNOWECON WIKI

ARTICLE

障碍函数

障碍函数 (Barrier Function) 障碍函数是最优化理论与凸优化中用于将约束优化问题转化为无约束（或近似无约束）问题的核心工具。其基本思想是：在目标函数上叠加一个"障碍项"，当迭代点从可行域内部趋近边界时，障碍项急剧增大（趋于无穷），从而将迭代点"阻挡"在可行域之内，使得无约束优化算法可以在不显式处理约束的情况下自动保持可行性。障碍函数是内点法的

浏览 7 更新 2026-07-18

障碍函数 (Barrier Function)

障碍函数是最优化理论与凸优化中用于将约束优化问题转化为无约束（或近似无约束）问题的核心工具。其基本思想是：在目标函数上叠加一个"障碍项"，当迭代点从可行域内部趋近边界时，障碍项急剧增大（趋于无穷），从而将迭代点"阻挡"在可行域之内，使得无约束优化算法可以在不显式处理约束的情况下自动保持可行性。障碍函数是内点法的理论基石，由Fiacco和McCormick在20世纪60年代系统提出，后经Nesterov和Nemirovski的自协调障碍函数理论发展成为求解线性规划、凸规划的高效算法框架。

定义与构造原理

考虑约束优化问题：

min⁡xf(x)s.t.gi(x)≤0,  i=1,…,m\min_{\mathbf{x}} \quad f(\mathbf{x}) \quad \text{s.t.} \quad g_i(\mathbf{x}) \leq 0, \; i=1,\ldots,m

其中可行域内部为 {x∣gi(x)<0,  ∀i}\{\mathbf{x} \mid g_i(\mathbf{x}) < 0, \; \forall i\}。障碍函数 ϕ(x)\phi(\mathbf{x}) 满足：在可行域内部光滑且有限；当 x\mathbf{x} 趋近边界（即某个 gi(x)→0−g_i(\mathbf{x}) \to 0^-）时，ϕ(x)→+∞\phi(\mathbf{x}) \to +\infty。

引入障碍参数 t>0t > 0，构造障碍问题：

min⁡xf(x)+1tϕ(x)\min_{\mathbf{x}} \quad f(\mathbf{x}) + \frac{1}{t} \phi(\mathbf{x})

当 t→∞t \to \infty 时，障碍项权重趋近于零，障碍问题的解收敛于原问题的最优解。

常用障碍函数

对数障碍函数 (Logarithmic Barrier)

对数障碍函数是应用最广泛的障碍形式：

ϕ(x)=−∑i=1mlog⁡(−gi(x))\phi(\mathbf{x}) = -\sum_{i=1}^{m} \log(-g_i(\mathbf{x}))

当 gi(x)→0−g_i(\mathbf{x}) \to 0^- 时，−log⁡(−gi)→+∞-\log(-g_i) \to +\infty，有效阻止越界。对数障碍函数是自协调函数，满足Nesterov的自协调性条件，这是内点法具有多项式时间复杂度的关键保证。

对于线性规划 min⁡{cTx∣Ax=b,x≥0}\min \{\mathbf{c}^T\mathbf{x} \mid A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}\}，对数障碍简化为 −∑jlog⁡xj-\sum_j \log x_j，障碍问题为：

min⁡xcTx−1t∑j=1nlog⁡xjs.t.Ax=b\min_{\mathbf{x}} \quad \mathbf{c}^T\mathbf{x} - \frac{1}{t}\sum_{j=1}^{n} \log x_j \quad \text{s.t.} \quad A\mathbf{x} = \mathbf{b}

该问题可通过牛顿法高效求解，并沿中心路径逐步增大 tt 来逼近最优解。

逆障碍函数 (Inverse Barrier)

逆障碍函数形如：

ϕ(x)=−∑i=1m1gi(x)\phi(\mathbf{x}) = -\sum_{i=1}^{m} \frac{1}{g_i(\mathbf{x})}

同样满足 gi→0−g_i \to 0^- 时 ϕ→+∞\phi \to +\infty，但其Hessian矩阵性质不如对数障碍，在二阶方法中效率较低，主要用于历史比较和理论分析。

内点法与中心路径

障碍函数方法与内点法的关系通过中心路径（Central Path）来刻画。对于每个障碍参数 t>0t > 0，定义障碍问题的最优解 x∗(t)\mathbf{x}^*(t)。当 tt 从一个小值连续增大到无穷时，x∗(t)\mathbf{x}^*(t) 在可行域内部描绘出一条光滑曲线，即中心路径。算法的基本策略是：从一个初始内点出发，对当前 tt 用牛顿法近似求解障碍问题，随后增大 tt（如 t←μtt \leftarrow \mu t，其中 μ>1\mu > 1），以当前解为初始点继续求解，沿中心路径追踪至最优解。这就是原始内点法（Primal Barrier Method）的基本逻辑。

更一般地，原始-对偶内点法同时使用对数障碍和拉格朗日对偶，通过扰动KKT条件直接追踪原始-对偶中心路径，在实践中具有更优的数值性能。

与惩罚函数的区别

障碍函数与惩罚函数同属约束处理的无约束化方法，但原理截然不同：

  • 障碍函数：要求迭代点始终在可行域内部（内点法），障碍项在边界上发散，只适用于不等式约束。
  • 惩罚函数：允许迭代点位于可行域外部，在违反约束时施加惩罚，可以处理等式约束。

在实践中，两者可结合使用：对不等式约束使用对数障碍，对等式约束保留在约束条件中或用二次惩罚处理。

自协调障碍与复杂度理论

Nesterov和Nemirovski（1994）建立了自协调障碍函数（Self-Concordant Barrier）理论。函数 FF 在凸集 QQ 上是 ν\nu-自协调障碍的，若其满足特定的微分不等式条件且 ν\nu（障碍参数）为常数。理论核心结论：对具有 ν\nu-自协调障碍的凸问题，路径跟踪算法只需 O(νlog⁡(1/ϵ))O(\sqrt{\nu} \log(1/\epsilon)) 次牛顿迭代即可达到 ϵ\epsilon 精度。

对于线性规划，对数障碍 −∑log⁡xj-\sum \log x_j 是 nn-自协调的；对于半定规划，−log⁡det⁡X-\log\det X 是 nn-自协调的。这一理论将线性规划、二次规划、半定规划和二阶锥规划统一在同一个多项式时间算法框架之下。

应用场景

  1. 线性与凸规划求解：现代LP/QP/SDP求解器（如CPLEX、Gurobi、MOSEK、SDPT3）普遍采用基于对数障碍的原始-对偶内点法。
  2. 机器学习：支持向量机训练中，将约束优化转化为障碍问题并使用内点法；LASSO和弹性网的对数障碍重表述也是常用求解策略。
  3. 网络优化：最大流、最小费用流问题可通过障碍函数方法获得强多项式时间算法。
  4. 控制理论：控制障碍函数（Control Barrier Function, CBF）用于保证非线性控制系统的安全性，将安全约束编码为障碍条件，在实时控制中确保系统状态始终保持在安全集合内。这一思想与优化中的障碍函数一脉相承：障碍函数在安全边界上发散，从而将系统轨迹"关"在安全域中。
  5. 博弈论：在纳什均衡计算和变分不等式求解中，障碍函数用于处理策略空间的边界约束。

障碍函数从计算技巧发展为自协调障碍的深刻理论，体现了优化领域中数学结构之美与算法效率之统一的典范。