约束优化问题的积极集方法
字数 1468 2025-10-30 17:43:44

约束优化问题的积极集方法

  1. 基本概念与问题背景
    积极集方法是求解约束优化问题的一类重要算法，特别适用于不等式约束问题。考虑标准形式：

\[ \begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & g_i(\mathbf{x}) \leq 0, \quad i = 1, \dots, m, \\ & h_j(\mathbf{x}) = 0, \quad j = 1, \dots, p, \end{aligned} \]

其中 \(f, g_i, h_j\) 均为连续可微函数。积极集（active set）指在当前点 \(\mathbf{x}\) 处取等号的约束集合，即 \(\mathcal{A}(\mathbf{x}) = \{ i \mid g_i(\mathbf{x}) = 0 \} \cup \{ \text{所有等式约束} \}\)。积极集方法的核心思想是：在每一步迭代中，预测最优解处的积极集，并仅在这些约束下求解子问题。

  1. 积极集的识别与子问题构造
    假设在当前迭代点 \(\mathbf{x}_k\)，我们估计其积极集为 \(\mathcal{A}_k \subseteq \mathcal{A}(\mathbf{x}_k)\)。算法求解以下等式约束子问题：

\[ \begin{aligned} \min_{\mathbf{d}} \quad & f(\mathbf{x}_k + \mathbf{d}) \\ \text{s.t.} \quad & g_i(\mathbf{x}_k) + \nabla g_i(\mathbf{x}_k)^T \mathbf{d} = 0, \quad i \in \mathcal{A}_k, \\ & h_j(\mathbf{x}_k) + \nabla h_j(\mathbf{x}_k)^T \mathbf{d} = 0, \quad j = 1, \dots, p. \end{aligned} \]

若忽略高阶项，该问题可近似为二次规划（若 \(f\) 是二次函数）或线性化约束问题。子问题的解 \(\mathbf{d}_k\) 提供了搜索方向。

  1. 迭代步骤与积极集更新
    • 步长选择：沿方向 \(\mathbf{d}_k\) 计算步长 \(\alpha_k \in (0,1]\)，确保新点 \(\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k\) 满足所有约束，且尽可能减小目标函数。
    • 积极集调整：
  • 若 \(\alpha_k < 1\)，说明遇到新的不等式约束（即某个 \(g_i\) 从非积极变为积极），将其加入 \(\mathcal{A}_{k+1}\)。
  • 若 \(\mathbf{d}_k = 0\) 且拉格朗日乘子对某个不等式约束为负，说明该约束可移除（因对最优解无贡献），从 \(\mathcal{A}_{k+1}\) 中删除对应索引。
    • 重复直至满足最优性条件（如 KKT 条件）。
  1. 算法特性与适用场景
    • 优点：通过逐步修正积极集，避免同时处理所有约束，特别适合稀疏积极集问题（如二次规划）。
    • 缺点：积极集估计错误可能导致迭代效率下降；对于非线性约束，需频繁重新线性化。
    • 扩展：可与序列二次规划（SQP）结合，用于一般非线性规划。
约束优化问题的积极集方法 基本概念与问题背景 积极集方法是求解约束优化问题的一类重要算法，特别适用于不等式约束问题。考虑标准形式： \[ \begin{aligned} \min_ {\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & g_ i(\mathbf{x}) \leq 0, \quad i = 1, \dots, m, \\ & h_ j(\mathbf{x}) = 0, \quad j = 1, \dots, p, \end{aligned} \] 其中 \( f, g_ i, h_ j \) 均为连续可微函数。积极集（active set）指在当前点 \(\mathbf{x}\) 处取等号的约束集合，即 \( \mathcal{A}(\mathbf{x}) = \{ i \mid g_ i(\mathbf{x}) = 0 \} \cup \{ \text{所有等式约束} \} \)。积极集方法的核心思想是：在每一步迭代中，预测最优解处的积极集，并仅在这些约束下求解子问题。 积极集的识别与子问题构造 假设在当前迭代点 \(\mathbf{x}_ k\)，我们估计其积极集为 \(\mathcal{A}_ k \subseteq \mathcal{A}(\mathbf{x} k)\)。算法求解以下等式约束子问题： \[ \begin{aligned} \min {\mathbf{d}} \quad & f(\mathbf{x}_ k + \mathbf{d}) \\ \text{s.t.} \quad & g_ i(\mathbf{x}_ k) + \nabla g_ i(\mathbf{x}_ k)^T \mathbf{d} = 0, \quad i \in \mathcal{A}_ k, \\ & h_ j(\mathbf{x}_ k) + \nabla h_ j(\mathbf{x}_ k)^T \mathbf{d} = 0, \quad j = 1, \dots, p. \end{aligned} \] 若忽略高阶项，该问题可近似为二次规划（若 \(f\) 是二次函数）或线性化约束问题。子问题的解 \(\mathbf{d}_ k\) 提供了搜索方向。 迭代步骤与积极集更新 步长选择 ：沿方向 \(\mathbf{d} k\) 计算步长 \(\alpha_ k \in (0,1]\)，确保新点 \(\mathbf{x} {k+1} = \mathbf{x}_ k + \alpha_ k \mathbf{d}_ k\) 满足所有约束，且尽可能减小目标函数。 积极集调整 ： 若 \(\alpha_ k < 1\)，说明遇到新的不等式约束（即某个 \(g_ i\) 从非积极变为积极），将其加入 \(\mathcal{A}_ {k+1}\)。 若 \(\mathbf{d} k = 0\) 且拉格朗日乘子对某个不等式约束为负，说明该约束可移除（因对最优解无贡献），从 \(\mathcal{A} {k+1}\) 中删除对应索引。 重复直至满足最优性条件（如 KKT 条件）。 算法特性与适用场景 优点：通过逐步修正积极集，避免同时处理所有约束，特别适合稀疏积极集问题（如二次规划）。 缺点：积极集估计错误可能导致迭代效率下降；对于非线性约束，需频繁重新线性化。 扩展：可与序列二次规划（SQP）结合，用于一般非线性规划。