非线性规划中的原始对偶积极集法（Primal-Dual Active Set Method）基础题

字数 5034 2025-12-19 05:59:51

非线性规划中的原始对偶积极集法（Primal-Dual Active Set Method）基础题

题目描述

考虑以下非线性规划问题：

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

其中 \(f: \mathbb{R}^n \to \mathbb{R}\) 和 \(c_i: \mathbb{R}^n \to \mathbb{R}\) 是连续可微函数，\(A \in \mathbb{R}^{p \times n}\)，\(b \in \mathbb{R}^p\)，且等式约束是线性的。假设目标函数 \(f\) 和不等式约束函数 \(c_i\) 是凸的（在本基础题中简化处理为凸情形，但原始对偶积极集法也可处理某些非凸问题）。

任务：使用原始对偶积极集法求解该问题。要求详细解释算法每一步的原理，并给出一个简单算例（如二维问题）的完整迭代过程。

解题过程循序渐进讲解

步骤1：理解积极集法的基本思想

积极集法的核心是猜测哪些不等式约束在最优解处是“起作用”的（active），即 \(c_i(x^*) = 0\)，并将这些约束视为等式约束进行求解，同时暂时忽略不起作用的约束（\(c_i(x^*) < 0\)）。

在每次迭代中，我们维护一个积极集 \(\mathcal{A}\)，包含当前被认为是起作用的约束下标。
算法通过求解一个等式约束子问题来更新当前点，并根据最优性条件调整积极集。

对于原始对偶积极集法，我们同时更新原始变量 \(x\) 和对偶变量（拉格朗日乘子）\(\lambda\)，利用互补松弛条件来判定积极集的变化。

步骤2：写出问题的拉格朗日函数与KKT条件

拉格朗日函数为：

\[\mathcal{L}(x, \lambda, \mu) = f(x) + \sum_{i=1}^m \lambda_i c_i(x) + \mu^\top (Ax - b), \]

其中 \(\lambda_i \geq 0\) 是不等式约束的乘子，\(\mu \in \mathbb{R}^p\) 是等式约束的乘子。

KKT条件（一阶必要条件）为：

平稳性：

\[ \nabla_x \mathcal{L} = \nabla f(x) + \sum_{i=1}^m \lambda_i \nabla c_i(x) + A^\top \mu = 0. \]

原始可行性：

\[ c_i(x) \leq 0, \quad Ax = b. \]

对偶可行性：

\[ \lambda_i \geq 0. \]

互补松弛条件：

\[ \lambda_i c_i(x) = 0, \quad i = 1, \dots, m. \]

互补松弛条件意味着：如果 \(c_i(x) < 0\)（约束不起作用），则必须有 \(\lambda_i = 0\)；如果 \(\lambda_i > 0\)，则必须有 \(c_i(x) = 0\)。

步骤3：原始对偶积极集法的算法框架

算法从初始点 \(x^0\) 和初始乘子估计 \(\lambda^0 \geq 0\) 开始，迭代以下步骤：

第3.1步：确定当前积极集
根据当前迭代点 \(x^k\) 和乘子 \(\lambda^k\)：

如果一个不等式约束满足 \(c_i(x^k) \geq 0\) 或 \(\lambda_i^k > 0\)，则将其加入候选积极集 \(\mathcal{W}^k\)（工作集）。
（实际中常用规则：\(\mathcal{W}^k = \{ i \mid c_i(x^k) \geq -\epsilon \text{ 或 } \lambda_i^k > 0 \}\)，其中 \(\epsilon > 0\) 是小容差。）

第3.2步：求解等式约束子问题
将 \(\mathcal{W}^k\) 中的约束视为等式约束，忽略其他不等式约束，求解子问题：

\[\begin{align*} \min_{x} \quad & f(x) \\ \text{s.t.} \quad & c_i(x) = 0, \quad i \in \mathcal{W}^k, \\ & Ax = b. \end{align*} \]

该子问题可通过求解其KKT系统得到搜索方向 \(\Delta x\) 和新乘子估计。

线性化近似：在实际中，常将子问题局部线性化（或二次化，如果目标用二次模型近似），转化为一个二次规划（QP） 或线性方程组。对于基础题，我们考虑线性化约束并保持目标为二次近似：

令当前点为 \(x^k\)，令 \(d = x - x^k\)。
线性化约束：\(c_i(x^k) + \nabla c_i(x^k)^\top d = 0\) 对于 \(i \in \mathcal{W}^k\)。
目标用二次模型：\(f(x^k + d) \approx f(x^k) + \nabla f(x^k)^\top d + \frac{1}{2} d^\top H^k d\)，其中 \(H^k\) 是 Hessian 或其近似（如 BFGS 矩阵）。
求解该 QP 得到方向 \(d^k\) 和对应乘子 \(\lambda_i^{k+1}\)（对于 \(i \in \mathcal{W}^k\)）以及 \(\mu^{k+1}\)。

第3.3步：更新原始变量与对偶变量

原始变量更新：\(x^{k+1} = x^k + \alpha^k d^k\)，其中步长 \(\alpha^k \in (0, 1]\) 需保证满足所有约束（通过线搜索确定）。
对偶变量更新：对于 \(i \in \mathcal{W}^k\)，乘子设为 QP 解中对应的 \(\lambda_i^{k+1}\)；对于 \(i \notin \mathcal{W}^k\)，设 \(\lambda_i^{k+1} = 0\)。

第3.4步：检查收敛
如果 \(x^{k+1}\) 和 \(\lambda^{k+1}\) 满足 KKT 条件（在一定容差内），则停止；否则，返回第3.1步。

步骤4：简单算例演示

考虑如下二维问题（凸）：

\[\begin{align*} \min_{x_1, x_2} \quad & f(x) = x_1^2 + x_2^2 \\ \text{s.t.} \quad & c_1(x) = x_1 + x_2 - 2 \leq 0, \\ & c_2(x) = -x_1 \leq 0, \\ & c_3(x) = -x_2 \leq 0. \end{align*} \]

该问题无等式约束（\(A, b\) 为空），最优解为 \(x^* = (1, 1)\)，此时 \(c_1(x^*) = 0\)，\(c_2(x^*) = -1\)，\(c_3(x^*) = -1\)，且 \(\lambda_1^* = 2\)，\(\lambda_2^* = \lambda_3^* = 0\)。

迭代过程（简化版，假设使用精确 Hessian \(H^k = \nabla^2 f = 2I\)）：

初始点：选 \(x^0 = (0.5, 0.5)\)，\(\lambda^0 = (0, 0, 0)\)。
- 计算约束值：\(c_1 = -1\)，\(c_2 = -0.5\)，\(c_3 = -0.5\)。
- 由于所有 \(c_i < 0\) 且 \(\lambda_i^0 = 0\)，初始积极集 \(\mathcal{W}^0 = \emptyset\)。
第一次子问题：无等式约束，子问题为无约束最小化 \(f\)，解为 \(x^1 = (0, 0)\)。
- 更新：\(x^1 = (0, 0)\)，\(\lambda^1 = (0, 0, 0)\)。
第二次迭代：
- 计算约束：\(c_1 = -2\)，\(c_2 = 0\)，\(c_3 = 0\)。
- 由于 \(c_2 = 0\) 且 \(c_3 = 0\)，将 \(i=2,3\) 加入 \(\mathcal{W}^1\)。
- 求解子问题（约束 \(x_1 = 0, x_2 = 0\)）：直接得 \(x^2 = (0, 0)\)，乘子由 KKT 系统解得 \(\lambda_2^2 = 0\)，\(\lambda_3^2 = 0\)。
- 更新后，\(c_1\) 仍不满足积极条件，检查互补松弛：\(\lambda_1 = 0\) 但 \(c_1 < 0\)，没问题。
第三次迭代：
- 此时 \(\mathcal{W}^2 = \{2, 3\}\)，但发现对应乘子均为零，且约束 \(c_2, c_3\) 是等式但乘子为零，意味着它们可能不是积极约束（因为乘子应非负，零表示可能不起作用）。根据规则，若乘子为零且约束为等式，可尝试将其从积极集移除。
- 移除 \(i=2,3\) 后，积极集变为空，再次解无约束问题，又会回到 \(x = (0,0)\)，陷入循环。
调整策略：实际上，在原始对偶积极集法中，我们根据乘子符号和约束违反来调整。更稳健的规则是：
- 如果解出的乘子 \(\lambda_i^{k+1} < 0\)（对应该约束不应积极），则将其从积极集移除。
- 如果 \(c_i(x^{k+1}) > 0\)（约束被违反），则将其加入积极集。
在本例中，从 \(x^2 = (0,0)\) 开始：
- 检查 \(c_1 = -2 < 0\)，不违反。
- 求解无约束问题得 \((0,0)\) 并非最优，因为梯度 \(\nabla f = (0,0)\) 但约束 \(c_1\) 在最优时应积极。因此，我们需要将 \(c_1\) 加入积极集。
加入 \(c_1\) 后：
- 积极集 \(\mathcal{W} = \{1\}\)。
- 求解等式约束子问题：\(c_1(x) = x_1 + x_2 - 2 = 0\)。
- 目标 \(f\) 在直线 \(x_1 + x_2 = 2\) 上最小化，易得解 \(x^* = (1,1)\)，对应乘子 \(\lambda_1 = 2\)（通过解 KKT 系统得到）。
- 验证：\(c_2 = -1 < 0\)，\(c_3 = -1 < 0\)，乘子 \(\lambda_2 = \lambda_3 = 0\)，满足 KKT 条件，算法终止。

步骤5：算法要点总结

积极集调整：基于当前约束违反与乘子符号，动态增删约束。
子问题求解：通常转化为一个等式约束二次规划，可通过解线性 KKT 系统实现。
收敛性：对于凸问题，算法在有限步内收敛（因为积极集组合有限）；对于非凸问题，可能收敛到局部解且积极集变化可能循环，需要加入防循环策略（如 Wolfe 规则）。
与单纯积极集法的区别：原始对偶法同时更新乘子，利用乘子符号指导积极集调整，通常比单纯原始积极集法更稳定。

通过以上步骤，你可以理解原始对偶积极集法的基本原理和迭代过程。在实际编程中，需要处理约束线性化、QP求解、步长选择等细节，但核心思想是通过猜测积极集并求解等式约束子问题，逐步逼近最优解。

非线性规划中的原始对偶积极集法（Primal-Dual Active Set Method）基础题题目描述考虑以下非线性规划问题： \[ \begin{align* } \min_ {x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & c_ i(x) \leq 0, \quad i = 1, 2, \dots, m, \\ & Ax = b, \end{align* } \] 其中 \( f: \mathbb{R}^n \to \mathbb{R} \) 和 \( c_ i: \mathbb{R}^n \to \mathbb{R} \) 是连续可微函数，\( A \in \mathbb{R}^{p \times n} \)，\( b \in \mathbb{R}^p \)，且等式约束是线性的。假设目标函数 \( f \) 和不等式约束函数 \( c_ i \) 是凸的（在本基础题中简化处理为凸情形，但原始对偶积极集法也可处理某些非凸问题）。任务：使用原始对偶积极集法求解该问题。要求详细解释算法每一步的原理，并给出一个简单算例（如二维问题）的完整迭代过程。解题过程循序渐进讲解步骤1：理解积极集法的基本思想积极集法的核心是猜测哪些不等式约束在最优解处是“起作用”的（active），即 \( c_ i(x^ ) = 0 \)，并将这些约束视为等式约束进行求解，同时暂时忽略不起作用的约束（\( c_ i(x^ ) < 0 \)）。在每次迭代中，我们维护一个积极集 \( \mathcal{A} \)，包含当前被认为是起作用的约束下标。算法通过求解一个等式约束子问题来更新当前点，并根据最优性条件调整积极集。对于原始对偶积极集法，我们同时更新原始变量 \( x \) 和对偶变量（拉格朗日乘子）\( \lambda \) ，利用互补松弛条件来判定积极集的变化。步骤2：写出问题的拉格朗日函数与KKT条件拉格朗日函数为： \[ \mathcal{L}(x, \lambda, \mu) = f(x) + \sum_ {i=1}^m \lambda_ i c_ i(x) + \mu^\top (Ax - b), \] 其中 \( \lambda_ i \geq 0 \) 是不等式约束的乘子，\( \mu \in \mathbb{R}^p \) 是等式约束的乘子。 KKT条件（一阶必要条件）为：平稳性： \[ \nabla_ x \mathcal{L} = \nabla f(x) + \sum_ {i=1}^m \lambda_ i \nabla c_ i(x) + A^\top \mu = 0. \] 原始可行性： \[ c_ i(x) \leq 0, \quad Ax = b. \] 对偶可行性： \[ \lambda_ i \geq 0. \] 互补松弛条件： \[ \lambda_ i c_ i(x) = 0, \quad i = 1, \dots, m. \] 互补松弛条件意味着：如果 \( c_ i(x) < 0 \)（约束不起作用），则必须有 \( \lambda_ i = 0 \)；如果 \( \lambda_ i > 0 \)，则必须有 \( c_ i(x) = 0 \)。步骤3：原始对偶积极集法的算法框架算法从初始点 \( x^0 \) 和初始乘子估计 \( \lambda^0 \geq 0 \) 开始，迭代以下步骤：第3.1步：确定当前积极集根据当前迭代点 \( x^k \) 和乘子 \( \lambda^k \)：如果一个不等式约束满足 \( c_ i(x^k) \geq 0 \) 或 \( \lambda_ i^k > 0 \)，则将其加入候选积极集 \( \mathcal{W}^k \)（工作集）。（实际中常用规则：\( \mathcal{W}^k = \{ i \mid c_ i(x^k) \geq -\epsilon \text{ 或 } \lambda_ i^k > 0 \} \)，其中 \( \epsilon > 0 \) 是小容差。）第3.2步：求解等式约束子问题将 \( \mathcal{W}^k \) 中的约束视为等式约束，忽略其他不等式约束，求解子问题： \[ \begin{align* } \min_ {x} \quad & f(x) \\ \text{s.t.} \quad & c_ i(x) = 0, \quad i \in \mathcal{W}^k, \\ & Ax = b. \end{align* } \] 该子问题可通过求解其 KKT系统得到搜索方向 \( \Delta x \) 和新乘子估计。线性化近似：在实际中，常将子问题局部线性化（或二次化，如果目标用二次模型近似），转化为一个二次规划（QP）或线性方程组。对于基础题，我们考虑线性化约束并保持目标为二次近似：令当前点为 \( x^k \)，令 \( d = x - x^k \)。线性化约束：\( c_ i(x^k) + \nabla c_ i(x^k)^\top d = 0 \) 对于 \( i \in \mathcal{W}^k \)。目标用二次模型：\( f(x^k + d) \approx f(x^k) + \nabla f(x^k)^\top d + \frac{1}{2} d^\top H^k d \)，其中 \( H^k \) 是 Hessian 或其近似（如 BFGS 矩阵）。求解该 QP 得到方向 \( d^k \) 和对应乘子 \( \lambda_ i^{k+1} \)（对于 \( i \in \mathcal{W}^k \)）以及 \( \mu^{k+1} \)。第3.3步：更新原始变量与对偶变量原始变量更新：\( x^{k+1} = x^k + \alpha^k d^k \)，其中步长 \( \alpha^k \in (0, 1 ] \) 需保证满足所有约束（通过线搜索确定）。对偶变量更新：对于 \( i \in \mathcal{W}^k \)，乘子设为 QP 解中对应的 \( \lambda_ i^{k+1} \)；对于 \( i \notin \mathcal{W}^k \)，设 \( \lambda_ i^{k+1} = 0 \)。第3.4步：检查收敛如果 \( x^{k+1} \) 和 \( \lambda^{k+1} \) 满足 KKT 条件（在一定容差内），则停止；否则，返回第3.1步。步骤4：简单算例演示考虑如下二维问题（凸）： \[ \begin{align* } \min_ {x_ 1, x_ 2} \quad & f(x) = x_ 1^2 + x_ 2^2 \\ \text{s.t.} \quad & c_ 1(x) = x_ 1 + x_ 2 - 2 \leq 0, \\ & c_ 2(x) = -x_ 1 \leq 0, \\ & c_ 3(x) = -x_ 2 \leq 0. \end{align* } \] 该问题无等式约束（\( A, b \) 为空），最优解为 \( x^* = (1, 1) \)，此时 \( c_ 1(x^ ) = 0 \)，\( c_ 2(x^ ) = -1 \)，\( c_ 3(x^ ) = -1 \)，且 \( \lambda_ 1^ = 2 \)，\( \lambda_ 2^* = \lambda_ 3^* = 0 \)。迭代过程（简化版，假设使用精确 Hessian \( H^k = \nabla^2 f = 2I \)）：初始点：选 \( x^0 = (0.5, 0.5) \)，\( \lambda^0 = (0, 0, 0) \)。计算约束值：\( c_ 1 = -1 \)，\( c_ 2 = -0.5 \)，\( c_ 3 = -0.5 \)。由于所有 \( c_ i < 0 \) 且 \( \lambda_ i^0 = 0 \)，初始积极集 \( \mathcal{W}^0 = \emptyset \)。第一次子问题：无等式约束，子问题为无约束最小化 \( f \)，解为 \( x^1 = (0, 0) \)。更新：\( x^1 = (0, 0) \)，\( \lambda^1 = (0, 0, 0) \)。第二次迭代：计算约束：\( c_ 1 = -2 \)，\( c_ 2 = 0 \)，\( c_ 3 = 0 \)。由于 \( c_ 2 = 0 \) 且 \( c_ 3 = 0 \)，将 \( i=2,3 \) 加入 \( \mathcal{W}^1 \)。求解子问题（约束 \( x_ 1 = 0, x_ 2 = 0 \)）：直接得 \( x^2 = (0, 0) \)，乘子由 KKT 系统解得 \( \lambda_ 2^2 = 0 \)，\( \lambda_ 3^2 = 0 \)。更新后，\( c_ 1 \) 仍不满足积极条件，检查互补松弛：\( \lambda_ 1 = 0 \) 但 \( c_ 1 < 0 \)，没问题。第三次迭代：此时 \( \mathcal{W}^2 = \{2, 3\} \)，但发现对应乘子均为零，且约束 \( c_ 2, c_ 3 \) 是等式但乘子为零，意味着它们可能不是积极约束（因为乘子应非负，零表示可能不起作用）。根据规则，若乘子为零且约束为等式，可尝试将其从积极集移除。移除 \( i=2,3 \) 后，积极集变为空，再次解无约束问题，又会回到 \( x = (0,0) \)，陷入循环。调整策略：实际上，在原始对偶积极集法中，我们根据乘子符号和约束违反来调整。更稳健的规则是：如果解出的乘子 \( \lambda_ i^{k+1} < 0 \)（对应该约束不应积极），则将其从积极集移除。如果 \( c_ i(x^{k+1}) > 0 \)（约束被违反），则将其加入积极集。在本例中，从 \( x^2 = (0,0) \) 开始：检查 \( c_ 1 = -2 < 0 \)，不违反。求解无约束问题得 \( (0,0) \) 并非最优，因为梯度 \( \nabla f = (0,0) \) 但约束 \( c_ 1 \) 在最优时应积极。因此，我们需要将 \( c_ 1 \) 加入积极集。加入 \( c_ 1 \) 后：积极集 \( \mathcal{W} = \{1\} \)。求解等式约束子问题：\( c_ 1(x) = x_ 1 + x_ 2 - 2 = 0 \)。目标 \( f \) 在直线 \( x_ 1 + x_ 2 = 2 \) 上最小化，易得解 \( x^* = (1,1) \)，对应乘子 \( \lambda_ 1 = 2 \)（通过解 KKT 系统得到）。验证：\( c_ 2 = -1 < 0 \)，\( c_ 3 = -1 < 0 \)，乘子 \( \lambda_ 2 = \lambda_ 3 = 0 \)，满足 KKT 条件，算法终止。步骤5：算法要点总结积极集调整：基于当前约束违反与乘子符号，动态增删约束。子问题求解：通常转化为一个等式约束二次规划，可通过解线性 KKT 系统实现。收敛性：对于凸问题，算法在有限步内收敛（因为积极集组合有限）；对于非凸问题，可能收敛到局部解且积极集变化可能循环，需要加入防循环策略（如 Wolfe 规则）。与单纯积极集法的区别：原始对偶法同时更新乘子，利用乘子符号指导积极集调整，通常比单纯原始积极集法更稳定。通过以上步骤，你可以理解原始对偶积极集法的基本原理和迭代过程。在实际编程中，需要处理约束线性化、QP求解、步长选择等细节，但核心思想是通过猜测积极集并求解等式约束子问题，逐步逼近最优解。