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

字数 5027 2025-12-14 07:41:12

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

题目描述：

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

minimize f(x)
subject to c_i(x) ≤ 0, i = 1, 2, ..., m

其中，\(f: \mathbb{R}^n \to \mathbb{R}\) 和 \(c_i: \mathbb{R}^n \to \mathbb{R}\) 是连续可微的函数。
假设当前迭代点为 \(x_k\)，已知对应的拉格朗日乘子估计为 \(\lambda_k\)。
请详细解释原始对偶积极集法的基本思想，并逐步推导在给定点 \((x_k, \lambda_k)\) 处如何识别积极约束集、构建子问题，以及如何更新迭代点和乘子。最后，给出完整的算法步骤框架。

解题过程：

原始对偶积极集法是一种结合了原始变量（决策变量 \(x\)）和对偶变量（拉格朗日乘子 \(\lambda\)）来主动识别有效约束（积极约束），并将原问题转化为一系列等式约束子问题进行求解的方法。它特别适用于求解具有大量不等式约束，但每次只有少量约束起作用的优化问题。

第一步：理解积极约束（Active Constraints）的定义

在不等式约束优化中，一个约束 \(c_i(x) \leq 0\) 被称为在点 \(x\) 处是：

积极（Active） 的，如果 \(c_i(x) = 0\)。
不积极（Inactive） 的，如果 \(c_i(x) < 0\)。
直观上，积极约束在当前点“紧贴”着可行域的边界，可能对最优解有直接影响；不积极约束暂时不起限制作用，可以忽略。

第二步：识别当前的积极约束集

在原始对偶积极集法中，我们不仅利用原始变量 \(x_k\) 的信息，还利用对偶变量（乘子）\(\lambda_k\) 的符号来更准确地预测积极集。

基于原始可行性：计算所有约束在 \(x_k\) 处的值 \(c_i(x_k)\)。
基于对偶可行性（互补松弛条件）：对于不等式约束，最优性条件（KKT条件）要求 \(\lambda_i \geq 0\) 且 \(\lambda_i c_i(x) = 0\)。
积极集预测规则：在迭代中，我们预测一个 工作集（Working Set） \(\mathcal{W}_k\)，它包含我们认为在当前子问题中应作为等式约束处理的约束索引。一个常用的预测准则是：

\[ \mathcal{W}_k = \{ i \mid c_i(x_k) \geq -\mu \lambda_{k,i} \ \text{或} \ \lambda_{k,i} > 0 \} \]

其中，$ \mu > 0 $ 是一个小的容差参数（例如 $ 10^{-6} $）。这个准则的解释是：
- 如果 $ c_i(x_k) $ 非常接近0（即 $ c_i(x_k) \geq -\mu \lambda_{k,i} $），说明该约束在原始空间接近积极。
- 如果 $ \lambda_{k,i} > 0 $，根据互补松弛条件，它强烈暗示对应的约束应该是积极的（$ c_i(x) = 0 $），即使当前 $ c_i(x_k) $ 可能略小于0。
将所有满足上述条件之一的约束索引 $ i $ 放入工作集 $ \mathcal{W}_k $。不在 $ \mathcal{W}_k $ 中的约束被视为不积极，在本次子问题中暂时忽略。

第三步：构建并求解等式约束子问题

基于预测的工作集 \(\mathcal{W}_k\)，我们构建一个等式约束二次规划（EQP）子问题来求解搜索方向 \(d_k\) 和对应的乘子更新。子问题在原问题的基础上，将工作集中的不等式约束视为等式约束，并忽略非工作集约束。

目标函数近似：在 \(x_k\) 处对目标函数 \(f(x)\) 进行二阶泰勒展开（或用拟牛顿法近似Hessian矩阵 \(H_k\)）。
约束线性化：将工作集中的约束在 \(x_k\) 处线性化（因为我们将处理为等式约束，线性化是合理的近似）。
子问题形式：

\[ \begin{aligned} \min_{d \in \mathbb{R}^n} & \quad \nabla f(x_k)^T d + \frac{1}{2} d^T H_k d \\ \text{subject to} & \quad c_i(x_k) + \nabla c_i(x_k)^T d = 0, \quad i \in \mathcal{W}_k \end{aligned} \]

这里，$ d = x - x_k $ 是我们要计算的搜索方向。

求解子问题：这是一个等式约束二次规划。我们可以通过求解其KKT系统来得到 \(d_k\) 和对应于工作集约束的新乘子估计 \(\hat{\lambda}_i\)（对于 \(i \in \mathcal{W}_k\)）。KKT系统为：

\[ \begin{bmatrix} H_k & A_k^T \\ A_k & 0 \end{bmatrix} \begin{bmatrix} d \\ \hat{\lambda}_{\mathcal{W}} \end{bmatrix} = \begin{bmatrix} -\nabla f(x_k) \\ -c_{\mathcal{W}}(x_k) \end{bmatrix} \]

其中，$ A_k $ 是工作集约束的雅可比矩阵（行向量为 $ \nabla c_i(x_k)^T, i \in \mathcal{W}_k $），$ c_{\mathcal{W}}(x_k) $ 是工作集约束函数值组成的向量。

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

更新原始变量：得到搜索方向 \(d_k\) 后，我们通过线搜索确定步长 \(\alpha_k\)（通常 \(\alpha_k \in (0, 1]\)），以确保收敛性和可行性改善。

\[ x_{k+1} = x_k + \alpha_k d_k \]

步长 $ \alpha_k $ 可能需要满足某些条件，如Armijo条件（保证充分下降）或确保新点 $ x_{k+1} $ 不会严重违反那些不在工作集中的约束（通过回溯线搜索或过滤器法处理）。

更新对偶变量：
- 对于工作集中的约束 \(i \in \mathcal{W}_k\)，其乘子更新为从子问题求解得到的 \(\hat{\lambda}_i\)。
- 对于非工作集中的约束 \(i \notin \mathcal{W}_k\)，我们通常将其乘子设为0，因为在当前子问题中它们被视为不积极。

\[ \lambda_{k+1, i} = \begin{cases} \hat{\lambda}_i, & i \in \mathcal{W}_k \\ 0, & i \notin \mathcal{W}_k \end{cases} \]

注意：如果从子问题解出的 $ \hat{\lambda}_i $ 对某些 $ i \in \mathcal{W}_k $ 为负（这对应于不等式约束，但我们在子问题中将其作为等式约束处理），这可能意味着该约束不应在当前工作集中，在下一次迭代中应将其从工作集中移除。

第五步：检查收敛性与更新工作集

收敛性检查：计算当前点的最优性误差，例如检查KKT条件的违反程度：
- 原始可行性：\(\max(0, c_i(x_{k+1}))\) 应很小。
- 互补松弛：\(|\lambda_{k+1, i} c_i(x_{k+1})|\) 应很小。
- 梯度条件：\(\| \nabla f(x_{k+1}) + \sum_{i=1}^m \lambda_{k+1, i} \nabla c_i(x_{k+1}) \|\) 应很小。
  如果这些条件低于预设容差，则算法终止。
更新工作集：如果不收敛，则基于新的点 \(x_{k+1}\) 和乘子 \(\lambda_{k+1}\) 重新应用第二步的预测准则，确定下一个工作集 \(\mathcal{W}_{k+1}\)。如果发现新的约束变得积极（\(c_i(x_{k+1}) \approx 0\) 且 \(\lambda_{k+1,i} \approx 0\) 或正），则将其加入工作集；如果工作集中的某个约束对应的乘子 \(\hat{\lambda}_i\) 为负，或该约束在当前点明显不积极（\(c_i(x_{k+1}) \ll 0\) 且 \(\lambda_{k+1,i} = 0\)），则将其从工作集中移除。

完整的算法步骤框架：

初始化：给定初始点 \(x_0\)，初始乘子估计 \(\lambda_0\)（通常可设为零向量），容差 \(\epsilon > 0\)，参数 \(\mu > 0\)。设 \(k = 0\)。
循环直到收敛：
a. 识别工作集：

\[ \mathcal{W}_k = \{ i \mid c_i(x_k) \geq -\mu \lambda_{k,i} \ \text{或} \ \lambda_{k,i} > 0 \} \]

b. **构建并求解EQP子问题**：
   求解关于 $ d_k $ 和 $ \hat{\lambda}_{\mathcal{W}} $ 的KKT系统：

\[ \begin{bmatrix} H_k & A_k^T \\ A_k & 0 \end{bmatrix} \begin{bmatrix} d \\ \hat{\lambda}_{\mathcal{W}} \end{bmatrix} = \begin{bmatrix} -\nabla f(x_k) \\ -c_{\mathcal{W}}(x_k) \end{bmatrix} \]

c. **线搜索**：找到步长 $ \alpha_k \in (0, 1] $，使得 $ x_{k+1} = x_k + \alpha_k d_k $ 在满足足够下降条件的同时，不严重违反约束（例如，使用Armijo型回溯线搜索，并惩罚约束违反）。
d. **更新变量**：

\[ x_{k+1} = x_k + \alpha_k d_k \]

\[ \lambda_{k+1, i} = \begin{cases} \hat{\lambda}_i, & i \in \mathcal{W}_k \\ 0, & i \notin \mathcal{W}_k \end{cases} \]

e. **收敛性检查**：如果 $ \| \nabla f(x_{k+1}) + \sum_i \lambda_{k+1, i} \nabla c_i(x_{k+1}) \| < \epsilon $，且 $ \| \max(0, c_i(x_{k+1})) \| < \epsilon $，则停止。
f. **准备下一次迭代**：$ k \leftarrow k+1 $，更新Hessian近似 $ H_k $（如果用拟牛顿法如BFGS）。

输出：近似最优解 \(x^* \approx x_{k+1}\) 和对应的拉格朗日乘子 \(\lambda^* \approx \lambda_{k+1}\)。

核心思想总结：原始对偶积极集法通过联合利用当前点的约束函数值（原始信息）和拉格朗日乘子符号（对偶信息）来预测哪些约束是“活跃”的。在每次迭代中，只将这些活跃约束作为等式约束处理，从而将复杂的非线性不等式约束问题简化为一个更易求解的等式约束子问题。通过迭代更新工作集，算法能动态地调整对有效约束集的估计，并最终收敛到满足KKT条件的最优点。

非线性规划中的原始对偶积极集法（Primal-Dual Active Set Method）基础题题目描述：考虑一个带不等式约束的非线性规划问题：其中，\( f: \mathbb{R}^n \to \mathbb{R} \) 和 \( c_ i: \mathbb{R}^n \to \mathbb{R} \) 是连续可微的函数。假设当前迭代点为 \( x_ k \)，已知对应的拉格朗日乘子估计为 \( \lambda_ k \)。请详细解释原始对偶积极集法的基本思想，并逐步推导在给定点 \( (x_ k, \lambda_ k) \) 处如何识别积极约束集、构建子问题，以及如何更新迭代点和乘子。最后，给出完整的算法步骤框架。解题过程：原始对偶积极集法是一种结合了原始变量（决策变量 \( x \)）和对偶变量（拉格朗日乘子 \( \lambda \)）来主动识别有效约束（积极约束），并将原问题转化为一系列等式约束子问题进行求解的方法。它特别适用于求解具有大量不等式约束，但每次只有少量约束起作用的优化问题。第一步：理解积极约束（Active Constraints）的定义在不等式约束优化中，一个约束 \( c_ i(x) \leq 0 \) 被称为在点 \( x \) 处是：积极（Active）的，如果 \( c_ i(x) = 0 \)。不积极（Inactive）的，如果 \( c_ i(x) < 0 \)。直观上，积极约束在当前点“紧贴”着可行域的边界，可能对最优解有直接影响；不积极约束暂时不起限制作用，可以忽略。第二步：识别当前的积极约束集在原始对偶积极集法中，我们不仅利用原始变量 \( x_ k \) 的信息，还利用对偶变量（乘子）\( \lambda_ k \) 的符号来更准确地预测积极集。基于原始可行性：计算所有约束在 \( x_ k \) 处的值 \( c_ i(x_ k) \)。基于对偶可行性（互补松弛条件）：对于不等式约束，最优性条件（KKT条件）要求 \( \lambda_ i \geq 0 \) 且 \( \lambda_ i c_ i(x) = 0 \)。积极集预测规则：在迭代中，我们预测一个工作集（Working Set） \( \mathcal{W} k \)，它包含我们认为在当前子问题中应作为等式约束处理的约束索引。一个常用的预测准则是： \[ \mathcal{W} k = \{ i \mid c_ i(x_ k) \geq -\mu \lambda {k,i} \ \text{或} \ \lambda {k,i} > 0 \} \] 其中，\( \mu > 0 \) 是一个小的容差参数（例如 \( 10^{-6} \)）。这个准则的解释是：如果 \( c_ i(x_ k) \) 非常接近0（即 \( c_ i(x_ k) \geq -\mu \lambda_ {k,i} \)），说明该约束在原始空间接近积极。如果 \( \lambda_ {k,i} > 0 \)，根据互补松弛条件，它强烈暗示对应的约束应该是积极的（\( c_ i(x) = 0 \)），即使当前 \( c_ i(x_ k) \) 可能略小于0。将所有满足上述条件之一的约束索引 \( i \) 放入工作集 \( \mathcal{W}_ k \)。不在 \( \mathcal{W}_ k \) 中的约束被视为不积极，在本次子问题中暂时忽略。第三步：构建并求解等式约束子问题基于预测的工作集 \( \mathcal{W}_ k \)，我们构建一个等式约束二次规划（EQP）子问题来求解搜索方向 \( d_ k \) 和对应的乘子更新。子问题在原问题的基础上，将工作集中的不等式约束视为等式约束，并忽略非工作集约束。目标函数近似：在 \( x_ k \) 处对目标函数 \( f(x) \) 进行二阶泰勒展开（或用拟牛顿法近似Hessian矩阵 \( H_ k \)）。约束线性化：将工作集中的约束在 \( x_ k \) 处线性化（因为我们将处理为等式约束，线性化是合理的近似）。子问题形式： \[ \begin{aligned} \min_ {d \in \mathbb{R}^n} & \quad \nabla f(x_ k)^T d + \frac{1}{2} d^T H_ k d \\ \text{subject to} & \quad c_ i(x_ k) + \nabla c_ i(x_ k)^T d = 0, \quad i \in \mathcal{W}_ k \end{aligned} \] 这里，\( d = x - x_ k \) 是我们要计算的搜索方向。求解子问题：这是一个等式约束二次规划。我们可以通过求解其KKT系统来得到 \( d_ k \) 和对应于工作集约束的新乘子估计 \( \hat{\lambda}_ i \)（对于 \( i \in \mathcal{W} k \)）。KKT系统为： \[ \begin{bmatrix} H_ k & A_ k^T \\ A_ k & 0 \end{bmatrix} \begin{bmatrix} d \\ \hat{\lambda} {\mathcal{W}} \end{bmatrix} \begin{bmatrix} -\nabla f(x_ k) \\ -c_ {\mathcal{W}}(x_ k) \end{bmatrix} \] 其中，\( A_ k \) 是工作集约束的雅可比矩阵（行向量为 \( \nabla c_ i(x_ k)^T, i \in \mathcal{W} k \)），\( c {\mathcal{W}}(x_ k) \) 是工作集约束函数值组成的向量。第四步：更新原始变量与对偶变量更新原始变量：得到搜索方向 \( d_ k \) 后，我们通过线搜索确定步长 \( \alpha_ k \)（通常 \( \alpha_ k \in (0, 1 ] \)），以确保收敛性和可行性改善。 \[ x_ {k+1} = x_ k + \alpha_ k d_ k \] 步长 \( \alpha_ k \) 可能需要满足某些条件，如Armijo条件（保证充分下降）或确保新点 \( x_ {k+1} \) 不会严重违反那些不在工作集中的约束（通过回溯线搜索或过滤器法处理）。更新对偶变量：对于工作集中的约束 \( i \in \mathcal{W}_ k \)，其乘子更新为从子问题求解得到的 \( \hat{\lambda}_ i \)。对于非工作集中的约束 \( i \notin \mathcal{W} k \)，我们通常将其乘子设为0，因为在当前子问题中它们被视为不积极。 \[ \lambda {k+1, i} = \begin{cases} \hat{\lambda}_ i, & i \in \mathcal{W}_ k \\ 0, & i \notin \mathcal{W}_ k \end{cases} \] 注意：如果从子问题解出的 \( \hat{\lambda}_ i \) 对某些 \( i \in \mathcal{W}_ k \) 为负（这对应于不等式约束，但我们在子问题中将其作为等式约束处理），这可能意味着该约束不应在当前工作集中，在下一次迭代中应将其从工作集中移除。第五步：检查收敛性与更新工作集收敛性检查：计算当前点的最优性误差，例如检查KKT条件的违反程度：原始可行性：\( \max(0, c_ i(x_ {k+1})) \) 应很小。互补松弛：\( |\lambda_ {k+1, i} c_ i(x_ {k+1})| \) 应很小。梯度条件：\( \| \nabla f(x_ {k+1}) + \sum_ {i=1}^m \lambda_ {k+1, i} \nabla c_ i(x_ {k+1}) \| \) 应很小。如果这些条件低于预设容差，则算法终止。更新工作集：如果不收敛，则基于新的点 \( x_ {k+1} \) 和乘子 \( \lambda_ {k+1} \) 重新应用第二步的预测准则，确定下一个工作集 \( \mathcal{W} {k+1} \)。如果发现新的约束变得积极（\( c_ i(x {k+1}) \approx 0 \) 且 \( \lambda_ {k+1,i} \approx 0 \) 或正），则将其加入工作集；如果工作集中的某个约束对应的乘子 \( \hat{\lambda} i \) 为负，或该约束在当前点明显不积极（\( c_ i(x {k+1}) \ll 0 \) 且 \( \lambda_ {k+1,i} = 0 \)），则将其从工作集中移除。完整的算法步骤框架：初始化：给定初始点 \( x_ 0 \)，初始乘子估计 \( \lambda_ 0 \)（通常可设为零向量），容差 \( \epsilon > 0 \)，参数 \( \mu > 0 \)。设 \( k = 0 \)。循环直到收敛： a. 识别工作集： \[ \mathcal{W} k = \{ i \mid c_ i(x_ k) \geq -\mu \lambda {k,i} \ \text{或} \ \lambda_ {k,i} > 0 \} \] b. 构建并求解EQP子问题：求解关于 \( d_ k \) 和 \( \hat{\lambda} {\mathcal{W}} \) 的KKT系统： \[ \begin{bmatrix} H_ k & A_ k^T \\ A_ k & 0 \end{bmatrix} \begin{bmatrix} d \\ \hat{\lambda} {\mathcal{W}} \end{bmatrix} \begin{bmatrix} -\nabla f(x_ k) \\ -c_ {\mathcal{W}}(x_ k) \end{bmatrix} \] c. 线搜索：找到步长 \( \alpha_ k \in (0, 1] \)，使得 \( x_ {k+1} = x_ k + \alpha_ k d_ k \) 在满足足够下降条件的同时，不严重违反约束（例如，使用Armijo型回溯线搜索，并惩罚约束违反）。 d. 更新变量： \[ x_ {k+1} = x_ k + \alpha_ k d_ k \] \[ \lambda_ {k+1, i} = \begin{cases} \hat{\lambda} i, & i \in \mathcal{W} k \\ 0, & i \notin \mathcal{W} k \end{cases} \] e. 收敛性检查：如果 \( \| \nabla f(x {k+1}) + \sum_ i \lambda {k+1, i} \nabla c_ i(x {k+1}) \| < \epsilon \)，且 \( \| \max(0, c_ i(x_ {k+1})) \| < \epsilon \)，则停止。 f. 准备下一次迭代：\( k \leftarrow k+1 \)，更新Hessian近似 \( H_ k \)（如果用拟牛顿法如BFGS）。输出：近似最优解 \( x^* \approx x_ {k+1} \) 和对应的拉格朗日乘子 \( \lambda^* \approx \lambda_ {k+1} \)。核心思想总结：原始对偶积极集法通过联合利用当前点的约束函数值（原始信息）和拉格朗日乘子符号（对偶信息）来预测哪些约束是“活跃”的。在每次迭代中，只将这些活跃约束作为等式约束处理，从而将复杂的非线性不等式约束问题简化为一个更易求解的等式约束子问题。通过迭代更新工作集，算法能动态地调整对有效约束集的估计，并最终收敛到满足KKT条件的最优点。