非线性规划中的障碍函数法

字数 2978 2025-12-05 10:38:54

非线性规划中的障碍函数法

好的，我们这次来系统性地学习非线性规划中的障碍函数法。我将循序渐进地为您拆解这个重要概念，确保每一步都清晰易懂。

第一步：核心思想与直观比喻

障碍函数法，也称为内点罚函数法，是求解约束优化问题的一类重要算法。它的核心思想非常直观：在可行域的内部“挖”出一条路径，引导迭代点从可行域内部出发，逐渐逼近边界上的最优解，同时避免直接“撞上”边界。

我们可以用一个比喻来理解：假设您要在一片被围墙（约束边界）包围的花园（可行域）里，找到花园中最高的一块石头（最优解）。障碍函数法就像是在围墙内侧均匀地种上一种“仙人掌”（障碍函数）。当您从花园中心开始寻找时，您可以在花园内部自由行走，但越靠近围墙，仙人掌就越密集，对您的“阻碍感”就越强。这样，您寻找最高石头的路径会自然而然地被限制在花园内部，并且会绕过围墙，最终停在离围墙很近但又没碰到围墙的最高点附近。算法就是通过逐步“拔掉”这些仙人掌（减小障碍的影响），让路径最终精确地抵达边界上的最优点。

第二步：问题形式与障碍函数定义

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

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

这里 \(f(x)\) 是目标函数，\(c_i(x) \ge 0\) 是不等式约束。我们假设存在严格内点，即存在 \(x^0\) 使得 \(c_i(x^0) > 0\) 对所有 \(i\) 成立。

障碍函数 \(B(x)\) 被定义在可行域的内部（即 \(c_i(x) > 0\) 的区域）。它需要满足两个关键性质：

内部有界性：当点 \(x\) 在可行域内部且远离边界时，\(B(x)\) 的值是温和、有限的。
边界“爆炸”性：当点 \(x\) 从内部接近任何一个约束边界（即某个 \(c_i(x) \to 0^+\)）时，\(B(x) \to +\infty\)。

第三步：经典障碍函数形式

最常见的障碍函数有两种：

倒数型障碍函数：\(B(x) = \sum_{i=1}^{m} \frac{1}{c_i(x)}\)。当 \(c_i(x) \to 0^+\) 时， \(1/c_i(x) \to +\infty\)。
对数型障碍函数：\(B(x) = -\sum_{i=1}^{m} \ln(c_i(x))\)。当 \(c_i(x) \to 0^+\) 时， \(-\ln(c_i(x)) \to +\infty\)。

其中，对数型障碍函数由于具有良好的解析性质（如可微性和自我协调性），在现代内点法中应用更为广泛。

第四步：构造障碍问题与路径跟踪

障碍函数法的精髓在于，它不直接求解原问题，而是构造一个参数化的、无约束（或只有简单约束）的近似问题，称为障碍问题：

\[\min_{x} \quad \phi_{\mu}(x) = f(x) + \mu B(x) \]

其中，\(\mu > 0\) 是一个很小的正数，称为障碍参数。

\(f(x)\)：驱动我们优化目标。
\(B(x)\)：扮演“守卫”角色，将点推开，使其远离约束边界，从而自动满足 \(c_i(x) > 0\)。
\(\mu\)：权衡两者。当 \(\mu\) 很大时，\(B(x)\) 的“守卫”力量很强，障碍问题的解 \(x^*(\mu)\) 会深深地位于可行域内部，但可能离原问题的最优点很远。当 \(\mu\) 很小时，\(B(x)\) 的影响变弱，\(x^*(\mu)\) 可以非常靠近边界，从而接近原问题的最优解。

中心路径：所有当 \(\mu\) 从 \(+\infty\) 变化到 \(0^+\) 时，障碍问题解 \(x^*(\mu)\) 的集合，形成一条从可行域内部通向原问题最优解的平滑路径。这条路径是算法“跟踪”的对象。

第五步：算法步骤详解

初始化：选取一个初始障碍参数 \(\mu_0 > 0\)（例如 \(\mu_0 = 10\)），一个衰减因子 \(\sigma \in (0, 1)\)（例如 \(\sigma = 0.1\)），一个初始严格内点 \(x^0\)，以及收敛容忍度 \(\epsilon > 0\)。
外层迭代（障碍参数更新）：对于 \(k = 0, 1, 2, ...\)
a. 内层迭代（无约束优化）：以当前迭代点 \(x^k\) 为初始点，求解障碍问题 \(\min_x \phi_{\mu_k}(x) = f(x) + \mu_k B(x)\)。由于 \(\mu_k\) 固定，这是一个无约束优化问题，可以使用牛顿法、拟牛顿法等高效算法求解。设其（近似）解为 \(x^*(\mu_k)\)。
b. 更新迭代点：令 \(x^{k+1} = x^*(\mu_k)\)。
c. 收敛性检查：检查某种终止条件，例如对偶间隙 \(m \mu_k \le \epsilon\)（对于对数障碍函数，\(m \mu_k\) 是原问题最优值和对偶问题最优值之间间隙的一个上界）。若满足，则停止，输出 \(x^{k+1}\) 作为近似最优解。
d. 衰减障碍参数：若不满足终止条件，则更新障碍参数 \(\mu_{k+1} = \sigma \mu_k\)，然后进入下一轮外层迭代。通过减小 \(\mu\)，我们降低了障碍的强度，允许下一个迭代点更靠近边界。

第六步：关键特性与联系

内点性：在整个算法过程中，只要初始点是内点，并且内层优化能精确求解，所有迭代点 \(x^k\) 都严格满足 \(c_i(x) > 0\)。这是“内点法”名称的由来。
与拉格朗日乘子的关系：在中心路径上，对于对数障碍函数，存在一个重要关系：\(\mu / c_i(x^*(\mu))\) 近似等于原问题在最优解处的拉格朗日乘子 \(\lambda_i^*\)。这为算法提供了重要的对偶信息。
与现代内点法的关系：经典的障碍函数法（如Fiacco-McCormick方法）需要每个 \(\mu_k\) 下都进行高精度无约束优化，计算量可能很大。现代原对偶内点法是其革命性发展。它不再严格区分内外层迭代，而是在每一步同时修正原变量 \(x\) 和对偶变量（乘子） \(\lambda\)，并动态调整 \(\mu\)，并利用牛顿法直接求解由KKT条件和中心路径条件构成的方程组，从而实现了超线性甚至二次收敛速度，成为求解大规模线性规划、凸优化问题的行业标准。

总结来说，障碍函数法通过引入一个在边界处“爆炸”的惩罚项，将约束问题转化为一系列可控的无约束问题，并通过跟踪中心路径来逼近解。它是连接经典优化理论与现代高效内点算法的关键桥梁。

非线性规划中的障碍函数法好的，我们这次来系统性地学习非线性规划中的障碍函数法。我将循序渐进地为您拆解这个重要概念，确保每一步都清晰易懂。第一步：核心思想与直观比喻障碍函数法，也称为内点罚函数法，是求解约束优化问题的一类重要算法。它的核心思想非常直观：在可行域的内部“挖”出一条路径，引导迭代点从可行域内部出发，逐渐逼近边界上的最优解，同时避免直接“撞上”边界。我们可以用一个比喻来理解：假设您要在一片被围墙（约束边界）包围的花园（可行域）里，找到花园中最高的一块石头（最优解）。障碍函数法就像是在围墙内侧均匀地种上一种“仙人掌”（障碍函数）。当您从花园中心开始寻找时，您可以在花园内部自由行走，但越靠近围墙，仙人掌就越密集，对您的“阻碍感”就越强。这样，您寻找最高石头的路径会自然而然地被限制在花园内部，并且会绕过围墙，最终停在离围墙很近但又没碰到围墙的最高点附近。算法就是通过逐步“拔掉”这些仙人掌（减小障碍的影响），让路径最终精确地抵达边界上的最优点。第二步：问题形式与障碍函数定义我们考虑标准形式的非线性规划问题： \[ \begin{aligned} \min_ {x} \quad & f(x) \\ \text{s.t.} \quad & c_ i(x) \ge 0, \quad i = 1, 2, ..., m. \end{aligned} \] 这里 \( f(x) \) 是目标函数，\( c_ i(x) \ge 0 \) 是不等式约束。我们假设存在严格内点，即存在 \( x^0 \) 使得 \( c_ i(x^0) > 0 \) 对所有 \( i \) 成立。障碍函数 \( B(x) \) 被定义在可行域的内部（即 \( c_ i(x) > 0 \) 的区域）。它需要满足两个关键性质：内部有界性：当点 \( x \) 在可行域内部且远离边界时，\( B(x) \) 的值是温和、有限的。边界“爆炸”性：当点 \( x \) 从内部接近任何一个约束边界（即某个 \( c_ i(x) \to 0^+ \)）时，\( B(x) \to +\infty \)。第三步：经典障碍函数形式最常见的障碍函数有两种：倒数型障碍函数：\( B(x) = \sum_ {i=1}^{m} \frac{1}{c_ i(x)} \)。当 \( c_ i(x) \to 0^+ \) 时， \( 1/c_ i(x) \to +\infty \)。对数型障碍函数：\( B(x) = -\sum_ {i=1}^{m} \ln(c_ i(x)) \)。当 \( c_ i(x) \to 0^+ \) 时， \( -\ln(c_ i(x)) \to +\infty \)。其中，对数型障碍函数由于具有良好的解析性质（如可微性和自我协调性），在现代内点法中应用更为广泛。第四步：构造障碍问题与路径跟踪障碍函数法的精髓在于，它不直接求解原问题，而是构造一个参数化的、无约束（或只有简单约束）的近似问题，称为障碍问题： \[ \min_ {x} \quad \phi_ {\mu}(x) = f(x) + \mu B(x) \] 其中，\( \mu > 0 \) 是一个很小的正数，称为障碍参数。 \( f(x) \)：驱动我们优化目标。 \( B(x) \)：扮演“守卫”角色，将点推开，使其远离约束边界，从而自动满足 \( c_ i(x) > 0 \)。 \( \mu \)：权衡两者。当 \( \mu \) 很大时，\( B(x) \) 的“守卫”力量很强，障碍问题的解 \( x^ (\mu) \) 会深深地位于可行域内部，但可能离原问题的最优点很远。当 \( \mu \) 很小时，\( B(x) \) 的影响变弱，\( x^ (\mu) \) 可以非常靠近边界，从而接近原问题的最优解。中心路径：所有当 \( \mu \) 从 \( +\infty \) 变化到 \( 0^+ \) 时，障碍问题解 \( x^* (\mu) \) 的集合，形成一条从可行域内部通向原问题最优解的平滑路径。这条路径是算法“跟踪”的对象。第五步：算法步骤详解初始化：选取一个初始障碍参数 \( \mu_ 0 > 0 \)（例如 \( \mu_ 0 = 10 \)），一个衰减因子 \( \sigma \in (0, 1) \)（例如 \( \sigma = 0.1 \)），一个初始严格内点 \( x^0 \)，以及收敛容忍度 \( \epsilon > 0 \)。外层迭代（障碍参数更新）：对于 \( k = 0, 1, 2, ... \) a. 内层迭代（无约束优化）：以当前迭代点 \( x^k \) 为初始点，求解障碍问题 \( \min_ x \phi_ {\mu_ k}(x) = f(x) + \mu_ k B(x) \)。由于 \( \mu_ k \) 固定，这是一个无约束优化问题，可以使用牛顿法、拟牛顿法等高效算法求解。设其（近似）解为 \( x^ (\mu_ k) \)。 b. 更新迭代点：令 \( x^{k+1} = x^ (\mu_ k) \)。 c. 收敛性检查：检查某种终止条件，例如对偶间隙 \( m \mu_ k \le \epsilon \)（对于对数障碍函数，\( m \mu_ k \) 是原问题最优值和对偶问题最优值之间间隙的一个上界）。若满足，则停止，输出 \( x^{k+1} \) 作为近似最优解。 d. 衰减障碍参数：若不满足终止条件，则更新障碍参数 \( \mu_ {k+1} = \sigma \mu_ k \)，然后进入下一轮外层迭代。通过减小 \( \mu \)，我们降低了障碍的强度，允许下一个迭代点更靠近边界。第六步：关键特性与联系内点性：在整个算法过程中，只要初始点是内点，并且内层优化能精确求解，所有迭代点 \( x^k \) 都严格满足 \( c_ i(x) > 0 \)。这是“内点法”名称的由来。与拉格朗日乘子的关系：在中心路径上，对于对数障碍函数，存在一个重要关系：\( \mu / c_ i(x^ (\mu)) \) 近似等于原问题在最优解处的拉格朗日乘子 \( \lambda_ i^ \)。这为算法提供了重要的对偶信息。与现代内点法的关系：经典的障碍函数法（如Fiacco-McCormick方法）需要每个 \( \mu_ k \) 下都进行高精度无约束优化，计算量可能很大。现代原对偶内点法是其革命性发展。它不再严格区分内外层迭代，而是在每一步同时修正原变量 \( x \) 和对偶变量（乘子） \( \lambda \)，并动态调整 \( \mu \)，并利用牛顿法直接求解由KKT条件和中心路径条件构成的方程组，从而实现了超线性甚至二次收敛速度，成为求解大规模线性规划、凸优化问题的行业标准。总结来说，障碍函数法通过引入一个在边界处“爆炸”的惩罚项，将约束问题转化为一系列可控的无约束问题，并通过跟踪中心路径来逼近解。它是连接经典优化理论与现代高效内点算法的关键桥梁。