非线性规划中的内点障碍函数法（Interior Point Barrier Method）基础题

字数 3778 2025-12-20 11:11:39

非线性规划中的内点障碍函数法（Interior Point Barrier Method）基础题

题目描述

考虑一个具有不等式约束的非线性规划问题：

问题P：

\[\begin{aligned} \min_{x \in \mathbb{R}^n} &\quad f(x) \\ \text{s.t.} &\quad c_i(x) \ge 0, \quad i = 1, 2, \dots, m \end{aligned} \]

其中，目标函数 \(f(x)\) 和约束函数 \(c_i(x)\) 都是二阶连续可微的。假设在可行域内部存在一个严格内点 \(x^0\)，即满足 \(c_i(x^0) > 0\) 对所有 \(i\)。本题目要求你使用内点障碍函数法求解该问题，核心思想是通过在目标函数中添加一个“障碍项”来惩罚接近约束边界的点，从而将原约束问题转化为一系列无约束子问题，并通过逐渐减小障碍参数，使子问题的解逼近原问题的最优解。

解题步骤

步骤1：构造障碍函数

障碍函数的作用是：当点 \(x\) 从可行域内部靠近边界（即某个 \(c_i(x) \to 0^+\)）时，函数值急剧增大，从而在数值上阻止迭代点越出可行域。常用的障碍函数有两种形式：

对数障碍函数： \(B(x) = -\sum_{i=1}^m \ln(c_i(x))\)
倒数障碍函数： \(B(x) = \sum_{i=1}^m \frac{1}{c_i(x)}\)

本题目采用对数障碍函数，因为它具有良好的可微性和数值稳定性。

障碍问题（Barrier Problem） 定义为：

\[\min_{x} \quad \phi(x, \mu) = f(x) - \mu \sum_{i=1}^m \ln(c_i(x)) \]

其中 \(\mu > 0\) 称为障碍参数。当 \(\mu\) 固定时，我们求解无约束问题 \(\min_x \phi(x, \mu)\)。注意：因为 \(-\ln(c_i(x))\) 在 \(c_i(x) \to 0^+\) 时趋于 \(+\infty\)，所以迭代点会自动保持在可行域内部（\(c_i(x) > 0\)）。

步骤2：理解障碍参数的作用

当 \(\mu\) 较大时，障碍项 \(-\mu \sum \ln(c_i(x))\) 占主导，最优解 \(x^*(\mu)\) 会远离约束边界，位于可行域内部。
当 \(\mu \to 0^+\) 时，障碍项的影响变小，\(x^*(\mu)\) 会逼近原问题的最优解（通常位于边界上）。
因此，算法将生成一个序列 \(\{\mu_k\}\)，满足 \(\mu_k \to 0\)，并对每个 \(\mu_k\) 求解障碍问题，得到点列 \(\{x_k\}\) 逼近原问题解。

步骤3：最优性条件与中心路径

对固定的 \(\mu\)，障碍问题 \(\min \phi(x, \mu)\) 的一阶必要条件是：

\[\nabla f(x) - \mu \sum_{i=1}^m \frac{1}{c_i(x)} \nabla c_i(x) = 0 \]

定义松弛变量 \(s_i = c_i(x)\)（在可行域内 \(s_i > 0\)），并引入对偶变量（拉格朗日乘子） \(y_i = \frac{\mu}{c_i(x)}\)。则上述条件可重写为：

\[\begin{aligned} \nabla f(x) - \sum_{i=1}^m y_i \nabla c_i(x) &= 0, \\ y_i c_i(x) &= \mu, \quad i=1,\dots,m, \\ c_i(x) &\ge 0, \quad y_i \ge 0. \end{aligned} \]

这类似于原问题的KKT条件，但互补松弛条件被替换为 \(y_i c_i(x) = \mu\)（称为扰动KKT条件）。当 \(\mu > 0\) 固定时，满足该条件的解 \((x(\mu), y(\mu))\) 的集合称为中心路径。随着 \(\mu \to 0\)，中心路径上的点趋近于原问题的KKT点。

步骤4：算法框架

初始化：选取初始障碍参数 \(\mu_0 > 0\)，初始内点 \(x^0\) 满足 \(c_i(x^0) > 0\)，设定衰减因子 \(\tau \in (0,1)\)（通常 \(\tau = 0.1 \sim 0.5\)），收敛容差 \(\epsilon > 0\)。
外层循环（障碍参数更新）：对于 \(k = 0, 1, 2, \dots\) 执行：
- 以当前点 \(x^k\) 为初始点，求解障碍问题 \(\min \phi(x, \mu_k)\) 得到近似解 \(x^{k+1}\)。
- 更新障碍参数： \(\mu_{k+1} = \tau \mu_k\)。
- 检查收敛条件：例如，障碍问题的梯度范数 \(\|\nabla \phi(x^{k+1}, \mu_{k+1})\| \le \epsilon\) 且 \(\mu_{k+1}\) 足够小。
内层循环（无约束优化）：对每个固定的 \(\mu_k\)，采用无约束优化方法（如牛顿法、拟牛顿法）求解 \(\min \phi(x, \mu_k)\)。由于 \(\phi\) 是光滑的，可以使用梯度信息加速收敛。

步骤5：内层无约束优化示例（牛顿法步骤）

对于固定的 \(\mu\)，牛顿法迭代格式为：

\[x^{(t+1)} = x^{(t)} - \alpha_t [\nabla^2 \phi(x^{(t)}, \mu)]^{-1} \nabla \phi(x^{(t)}, \mu) \]

其中：

梯度：

\[\nabla \phi(x, \mu) = \nabla f(x) - \mu \sum_{i=1}^m \frac{1}{c_i(x)} \nabla c_i(x) \]

Hessian 矩阵：

\[\nabla^2 \phi(x, \mu) = \nabla^2 f(x) - \mu \sum_{i=1}^m \left[ \frac{1}{c_i(x)} \nabla^2 c_i(x) - \frac{1}{c_i(x)^2} \nabla c_i(x) \nabla c_i(x)^\top \right] \]

步长 \(\alpha_t\) 通过线搜索（如回溯法）确定，确保 \(c_i(x^{(t+1)}) > 0\) 且目标下降。

步骤6：收敛性与注意事项

在适当条件下（如 \(f, c_i\) 凸，且满足约束规范），当 \(\mu_k \to 0\) 时，算法生成的序列收敛到原问题的最优解。
实际中，初始 \(\mu_0\) 不宜过小，否则初始子问题可能病态（Hessian 矩阵接近奇异）。通常可先取较大 \(\mu_0\)，使迭代点靠近“中心”，再逐步减小。
当约束数目 \(m\) 很大时，对数障碍函数可能导致数值问题（如梯度爆炸），需谨慎处理。

举例说明

考虑简单问题：

\[\begin{aligned} \min_{x \in \mathbb{R}} &\quad f(x) = x^2 \\ \text{s.t.} &\quad c(x) = x - 1 \ge 0 \end{aligned} \]

显然最优解为 \(x^* = 1\)，最优值 \(f^* = 1\)。

构造障碍函数： \(\phi(x, \mu) = x^2 - \mu \ln(x-1)\)（定义域 \(x > 1\)）。
一阶条件： \(\nabla \phi = 2x - \frac{\mu}{x-1} = 0\)，解得 \(x(\mu) = 1 + \frac{\mu + \sqrt{\mu^2 + 8\mu}}{4}\)（取正根）。
当 \(\mu = 1\) 时， \(x(1) \approx 1.78\)；当 \(\mu = 0.1\) 时， \(x(0.1) \approx 1.12\)；当 \(\mu \to 0\)， \(x(\mu) \to 1\)。

通过序列 \(\mu_k = 0.1^k\) 求解障碍问题，即可逼近 \(x^* = 1\)。

总结

内点障碍函数法通过引入障碍项将约束问题转化为一系列无约束问题，是求解不等式约束非线性规划的一种经典方法。关键点包括：选择合适的障碍函数、设计障碍参数衰减策略、高效求解无约束子问题。虽然现代内点法多采用原-对偶形式，但障碍函数法是理解内点思想的基础。

非线性规划中的内点障碍函数法（Interior Point Barrier Method）基础题题目描述考虑一个具有不等式约束的非线性规划问题：问题P ： \[ \begin{aligned} \min_ {x \in \mathbb{R}^n} &\quad f(x) \\ \text{s.t.} &\quad c_ i(x) \ge 0, \quad i = 1, 2, \dots, m \end{aligned} \] 其中，目标函数 \( f(x) \) 和约束函数 \( c_ i(x) \) 都是二阶连续可微的。假设在可行域内部存在一个严格内点 \( x^0 \)，即满足 \( c_ i(x^0) > 0 \) 对所有 \( i \)。本题目要求你使用内点障碍函数法求解该问题，核心思想是通过在目标函数中添加一个“障碍项”来惩罚接近约束边界的点，从而将原约束问题转化为一系列无约束子问题，并通过逐渐减小障碍参数，使子问题的解逼近原问题的最优解。解题步骤步骤1：构造障碍函数障碍函数的作用是：当点 \( x \) 从可行域内部靠近边界（即某个 \( c_ i(x) \to 0^+ \)）时，函数值急剧增大，从而在数值上阻止迭代点越出可行域。常用的障碍函数有两种形式：对数障碍函数： \( B(x) = -\sum_ {i=1}^m \ln(c_ i(x)) \) 倒数障碍函数： \( B(x) = \sum_ {i=1}^m \frac{1}{c_ i(x)} \) 本题目采用对数障碍函数，因为它具有良好的可微性和数值稳定性。障碍问题（Barrier Problem）定义为： \[ \min_ {x} \quad \phi(x, \mu) = f(x) - \mu \sum_ {i=1}^m \ln(c_ i(x)) \] 其中 \( \mu > 0 \) 称为障碍参数。当 \( \mu \) 固定时，我们求解无约束问题 \( \min_ x \phi(x, \mu) \)。注意：因为 \( -\ln(c_ i(x)) \) 在 \( c_ i(x) \to 0^+ \) 时趋于 \( +\infty \)，所以迭代点会自动保持在可行域内部（\( c_ i(x) > 0 \)）。步骤2：理解障碍参数的作用当 \( \mu \) 较大时，障碍项 \( -\mu \sum \ln(c_ i(x)) \) 占主导，最优解 \( x^* (\mu) \) 会远离约束边界，位于可行域内部。当 \( \mu \to 0^+ \) 时，障碍项的影响变小，\( x^* (\mu) \) 会逼近原问题的最优解（通常位于边界上）。因此，算法将生成一个序列 \( \{\mu_ k\} \)，满足 \( \mu_ k \to 0 \)，并对每个 \( \mu_ k \) 求解障碍问题，得到点列 \( \{x_ k\} \) 逼近原问题解。步骤3：最优性条件与中心路径对固定的 \( \mu \)，障碍问题 \( \min \phi(x, \mu) \) 的一阶必要条件是： \[ \nabla f(x) - \mu \sum_ {i=1}^m \frac{1}{c_ i(x)} \nabla c_ i(x) = 0 \] 定义松弛变量 \( s_ i = c_ i(x) \)（在可行域内 \( s_ i > 0 \)），并引入对偶变量（拉格朗日乘子） \( y_ i = \frac{\mu}{c_ i(x)} \)。则上述条件可重写为： \[ \begin{aligned} \nabla f(x) - \sum_ {i=1}^m y_ i \nabla c_ i(x) &= 0, \\ y_ i c_ i(x) &= \mu, \quad i=1,\dots,m, \\ c_ i(x) &\ge 0, \quad y_ i \ge 0. \end{aligned} \] 这类似于原问题的KKT条件，但互补松弛条件被替换为 \( y_ i c_ i(x) = \mu \)（称为扰动KKT条件）。当 \( \mu > 0 \) 固定时，满足该条件的解 \( (x(\mu), y(\mu)) \) 的集合称为中心路径。随着 \( \mu \to 0 \)，中心路径上的点趋近于原问题的KKT点。步骤4：算法框架初始化：选取初始障碍参数 \( \mu_ 0 > 0 \)，初始内点 \( x^0 \) 满足 \( c_ i(x^0) > 0 \)，设定衰减因子 \( \tau \in (0,1) \)（通常 \( \tau = 0.1 \sim 0.5 \)），收敛容差 \( \epsilon > 0 \)。外层循环（障碍参数更新）：对于 \( k = 0, 1, 2, \dots \) 执行：以当前点 \( x^k \) 为初始点，求解障碍问题 \( \min \phi(x, \mu_ k) \) 得到近似解 \( x^{k+1} \)。更新障碍参数： \( \mu_ {k+1} = \tau \mu_ k \)。检查收敛条件：例如，障碍问题的梯度范数 \( \|\nabla \phi(x^{k+1}, \mu_ {k+1})\| \le \epsilon \) 且 \( \mu_ {k+1} \) 足够小。内层循环（无约束优化）：对每个固定的 \( \mu_ k \)，采用无约束优化方法（如牛顿法、拟牛顿法）求解 \( \min \phi(x, \mu_ k) \)。由于 \( \phi \) 是光滑的，可以使用梯度信息加速收敛。步骤5：内层无约束优化示例（牛顿法步骤）对于固定的 \( \mu \)，牛顿法迭代格式为： \[ x^{(t+1)} = x^{(t)} - \alpha_ t [ \nabla^2 \phi(x^{(t)}, \mu) ]^{-1} \nabla \phi(x^{(t)}, \mu) \] 其中：梯度： \[ \nabla \phi(x, \mu) = \nabla f(x) - \mu \sum_ {i=1}^m \frac{1}{c_ i(x)} \nabla c_ i(x) \] Hessian 矩阵： \[ \nabla^2 \phi(x, \mu) = \nabla^2 f(x) - \mu \sum_ {i=1}^m \left[ \frac{1}{c_ i(x)} \nabla^2 c_ i(x) - \frac{1}{c_ i(x)^2} \nabla c_ i(x) \nabla c_ i(x)^\top \right ] \] 步长 \( \alpha_ t \) 通过线搜索（如回溯法）确定，确保 \( c_ i(x^{(t+1)}) > 0 \) 且目标下降。步骤6：收敛性与注意事项在适当条件下（如 \( f, c_ i \) 凸，且满足约束规范），当 \( \mu_ k \to 0 \) 时，算法生成的序列收敛到原问题的最优解。实际中，初始 \( \mu_ 0 \) 不宜过小，否则初始子问题可能病态（Hessian 矩阵接近奇异）。通常可先取较大 \( \mu_ 0 \)，使迭代点靠近“中心”，再逐步减小。当约束数目 \( m \) 很大时，对数障碍函数可能导致数值问题（如梯度爆炸），需谨慎处理。举例说明考虑简单问题： \[ \begin{aligned} \min_ {x \in \mathbb{R}} &\quad f(x) = x^2 \\ \text{s.t.} &\quad c(x) = x - 1 \ge 0 \end{aligned} \] 显然最优解为 \( x^* = 1 \)，最优值 \( f^* = 1 \)。构造障碍函数： \( \phi(x, \mu) = x^2 - \mu \ln(x-1) \)（定义域 \( x > 1 \)）。一阶条件： \( \nabla \phi = 2x - \frac{\mu}{x-1} = 0 \)，解得 \( x(\mu) = 1 + \frac{\mu + \sqrt{\mu^2 + 8\mu}}{4} \)（取正根）。当 \( \mu = 1 \) 时， \( x(1) \approx 1.78 \)；当 \( \mu = 0.1 \) 时， \( x(0.1) \approx 1.12 \)；当 \( \mu \to 0 \)， \( x(\mu) \to 1 \)。通过序列 \( \mu_ k = 0.1^k \) 求解障碍问题，即可逼近 \( x^* = 1 \)。总结内点障碍函数法通过引入障碍项将约束问题转化为一系列无约束问题，是求解不等式约束非线性规划的一种经典方法。关键点包括：选择合适的障碍函数、设计障碍参数衰减策略、高效求解无约束子问题。虽然现代内点法多采用原-对偶形式，但障碍函数法是理解内点思想的基础。