非线性规划中的逐步二次逼近法（Sequential Quadratic Approximation, SQA）进阶题：处理具有高度非线性目标与线性不等式约束的大规模优化问题
字数 5977 2025-12-21 00:30:59

非线性规划中的逐步二次逼近法（Sequential Quadratic Approximation, SQA）进阶题：处理具有高度非线性目标与线性不等式约束的大规模优化问题

1. 问题描述

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

\[\begin{aligned} \min_{\mathbf{x} \in \mathbb{R}^n} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & A\mathbf{x} \leq \mathbf{b} \end{aligned} \]

其中：

  • \(f(\mathbf{x})\) 是一个高度非线性（非二次、非凸且可能非光滑）的目标函数，计算其梯度 \(\nabla f(\mathbf{x})\) 是可行的，但计算 Hessian 矩阵 \(\nabla^2 f(\mathbf{x})\) 非常昂贵或不稳定。
  • 约束是 \(m\) 个线性不等式，\(A \in \mathbb{R}^{m \times n}\)，\(\mathbf{b} \in \mathbb{R}^m\)，且约束数量 \(m\) 很大（例如 \(m \sim 10^4 \sim 10^6\)），但 \(A\) 可能是稀疏的。
  • 决策变量维度 \(n\) 也较大（例如 \(n \sim 10^3 \sim 10^4\)）。

任务：设计一种逐步二次逼近法（SQA）的变体，在每次迭代中构造一个简单且易于求解的二次子问题来逼近原问题，并确保算法在大规模设置下高效收敛到原问题的一个稳定点（例如 KKT 点）。

2. 关键挑战

  1. 目标函数的高度非线性：直接使用精确的 Hessian 不可行，需要低成本的 Hessian 近似。
  2. 大规模线性不等式：即使子问题是二次规划（QP），当 \(m\) 很大时，直接求解完整的 QP 可能计算量过大。
  3. 可行性保持：迭代点必须始终保持满足 \(A\mathbf{x} \leq \mathbf{b}\)，否则二次子问题可能无解。
  4. 收敛保证：需要确保迭代序列的极限点满足原问题的一阶必要条件。

3. 逐步二次逼近法（SQA）的核心思想

SQA 是一种序列二次规划（SQP） 的简化版本，特别适合目标非线性但约束线性的问题。其基本思路如下：

  1. 在当前迭代点 \(\mathbf{x}_k\)，构造目标函数 \(f\) 的一个二次逼近模型 \(q_k(\mathbf{d})\)：

\[ q_k(\mathbf{d}) = f(\mathbf{x}_k) + \nabla f(\mathbf{x}_k)^T \mathbf{d} + \frac{1}{2} \mathbf{d}^T B_k \mathbf{d} \]

其中 \(\mathbf{d} = \mathbf{x} - \mathbf{x}_k\) 是步长，\(B_k\) 是 \(\nabla^2 f(\mathbf{x}_k)\) 的一个对称近似矩阵（例如 BFGS 拟牛顿更新）。

  1. 求解以下二次规划子问题得到步长 \(\mathbf{d}_k\)：

\[ \begin{aligned} \min_{\mathbf{d} \in \mathbb{R}^n} \quad & q_k(\mathbf{d}) \\ \text{s.t.} \quad & A(\mathbf{x}_k + \mathbf{d}) \leq \mathbf{b} \end{aligned} \]

注意：由于约束是线性的，子问题是一个凸二次规划（如果 \(B_k \succeq 0\)）。

  1. 更新迭代点：\(\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k\)，其中 \(\alpha_k \in (0,1]\) 是步长，通常通过线搜索（例如 Armijo 条件）确定，以保证目标函数充分下降。

  2. 更新近似 Hessian \(B_k\)（例如用 BFGS 公式），重复直到收敛。

4. 针对大规模线性约束的改进策略

为应对约束数量 \(m\) 很大的情况，可以采用以下两种互补的策略：

策略 A：积极集方法（Active Set Method）

  • 在每次迭代中，仅考虑可能起作用的约束（即积极约束或接近积极的约束），大大减少 QP 子问题的约束数量。
  • 步骤：
    1. 在当前点 \(\mathbf{x}_k\)，计算约束违反度：\(\mathbf{c}_k = A\mathbf{x}_k - \mathbf{b}\)。
    2. 选择积极集 \(\mathcal{A}_k = \{ i \mid c_{k,i} \geq -\epsilon \}\)，其中 \(\epsilon > 0\) 是一个小阈值（例如 \(10^{-6}\)）。
    3. 求解仅包含 \(\mathcal{A}_k\) 中约束的 QP 子问题，得到步长 \(\mathbf{d}_k\)。
    4. 若新步长导致某个不在 \(\mathcal{A}_k\) 中的约束被违反，则将其加入积极集，重新求解 QP。
    5. 通过迭代更新积极集，最终得到子问题的精确解。

策略 B：梯度投影 + 截断共轭梯度法

  • 当 \(B_k\) 是对角占优或简单结构时，可以结合梯度投影和共轭梯度法来近似求解 QP。
  • 步骤：
    1. 将 QP 子问题改写为：

\[ \min_{\mathbf{d}} \frac{1}{2} \mathbf{d}^T B_k \mathbf{d} + \nabla f(\mathbf{x}_k)^T \mathbf{d} \quad \text{s.t.} \quad A\mathbf{d} \leq \mathbf{b} - A\mathbf{x}_k \]

  1. 使用梯度投影法：迭代更新 \(\mathbf{d}\)：

\[ \mathbf{d}^{(t+1)} = P_\Omega \left( \mathbf{d}^{(t)} - \eta (B_k \mathbf{d}^{(t)} + \nabla f(\mathbf{x}_k)) \right) \]

 其中 $ P_\Omega $ 是到线性约束集 $ \Omega = \{ \mathbf{d} \mid A\mathbf{d} \leq \mathbf{b} - A\mathbf{x}_k \} $ 的投影，可通过**稀疏矩阵投影算法**高效计算。
  1. 当投影迭代达到一定精度或最大迭代次数时停止，得到近似步长 \(\mathbf{d}_k\)。

5. 完整算法流程（结合积极集与拟牛顿更新）

  1. 初始化：选择初始点 \(\mathbf{x}_0\) 满足 \(A\mathbf{x}_0 \leq \mathbf{b}\)，初始正定矩阵 \(B_0 = I\)（单位阵），容忍误差 \(\epsilon > 0\)，令 \(k = 0\)。

  2. 主循环（直到满足停止条件 \(\| \nabla f(\mathbf{x}_k) + A^T \boldsymbol{\lambda}_k \|_\infty \leq \epsilon\) 且约束违反度足够小）：

    • 步骤 1：梯度计算：计算 \(g_k = \nabla f(\mathbf{x}_k)\)。
    • 步骤 2：积极集识别：计算 \(\mathbf{c}_k = A\mathbf{x}_k - \mathbf{b}\)，定义积极集 \(\mathcal{A}_k = \{ i \mid c_{k,i} \geq -\epsilon_{act} \}\)，其中 \(\epsilon_{act} = 10^{-6}\)。
    • 步骤 3：构造并求解简化 QP：

\[ \begin{aligned} \min_{\mathbf{d}} \quad & g_k^T \mathbf{d} + \frac{1}{2} \mathbf{d}^T B_k \mathbf{d} \\ \text{s.t.} \quad & A_i \mathbf{d} \leq b_i - A_i \mathbf{x}_k, \quad i \in \mathcal{A}_k \end{aligned} \]

 使用**稀疏 QP 求解器**（如基于内点法或有效集法）求解，得到步长 $ \mathbf{d}_k $ 和对偶变量 $ \boldsymbol{\lambda}_k^{(a)} $（对应积极约束）。
  • 步骤 4：步长接受与线搜索：
    • 令 \(\alpha_k = 1\)。
    • 回溯线搜索：当 \(f(\mathbf{x}_k + \alpha_k \mathbf{d}_k) > f(\mathbf{x}_k) + \beta \alpha_k g_k^T \mathbf{d}_k\)（Armijo 条件，\(\beta \in (0,1)\)）或 \(A(\mathbf{x}_k + \alpha_k \mathbf{d}_k) \nleq \mathbf{b}\) 时，令 \(\alpha_k \leftarrow \tau \alpha_k\)（\(\tau \in (0,1)\)）。
    • 若 \(\alpha_k\) 小于最小值（例如 \(10^{-8}\)），则重启（例如减小积极集阈值或重置 \(B_k = I\)）。
  • 步骤 5：更新迭代点：\(\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k\)。
  • 步骤 6：更新拟牛顿矩阵：
    • 计算梯度差 \(\mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k\)，\(\mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)\)。
    • 使用 BFGS 公式更新 \(B_{k+1}\)：

\[ B_{k+1} = B_k - \frac{B_k \mathbf{s}_k \mathbf{s}_k^T B_k}{\mathbf{s}_k^T B_k \mathbf{s}_k} + \frac{\mathbf{y}_k \mathbf{y}_k^T}{\mathbf{s}_k^T \mathbf{y}_k}, \quad \text{若 } \mathbf{s}_k^T \mathbf{y}_k > 0 \]

   若 $ \mathbf{s}_k^T \mathbf{y}_k \leq 0 $，则跳过更新（保持 $ B_{k+1} = B_k $）或使用 Powell 修正。
  • 步骤 7：检查收敛：计算 KKT 残差：

\[ r_k = \| \nabla f(\mathbf{x}_k) + A^T \boldsymbol{\lambda}_k \|_\infty, \quad \text{其中 } \boldsymbol{\lambda}_k \text{ 由 } \mathcal{A}_k \text{ 对应的对偶变量扩展得到（非积极约束对应零）}. \]

 若 $ r_k \leq \epsilon $ 且 $ \max(0, A\mathbf{x}_k - \mathbf{b}) \leq \epsilon $，则停止；否则令 $ k \leftarrow k+1 $ 继续。

6. 收敛性分析要点

  • 全局收敛：在适当假设下（如 \(f\) 连续可微且有下界，约束集有内点，BFGS 更新保持一致正定性），结合 Armijo 线搜索，算法生成的序列 \(\{ \mathbf{x}_k \}\) 的任何极限点都是原问题的KKT 点。
  • 局部超线性收敛：如果 \(B_k\) 通过 BFGS 更新渐近逼近真实 Hessian，且积极集识别准确，则在极限点附近步长 \(\alpha_k = 1\) 最终被接受，算法呈现超线性收敛速度。
  • 大规模计算复杂度：积极集策略将每次 QP 的约束数降至 \(O(|\mathcal{A}_k|)\)，通常远小于 \(m\)。若使用稀疏 QP 求解器，每次迭代的复杂度为 \(O(n^{1.5} \sim n^2)\)（取决于稀疏结构），内存需求为 \(O(nnz(A) + n^2)\)，其中 \(nnz(A)\) 是 \(A\) 的非零元个数。

7. 举例说明

考虑问题：

\[\min_{x_1,x_2} \quad f(x_1,x_2) = e^{x_1} + x_1 x_2 + \sin(x_2^2), \quad \text{s.t.} \quad x_1 + 2x_2 \leq 1, \; -x_1 \leq 0, \; -x_2 \leq 0 \]

  • 初始化：\(\mathbf{x}_0 = (0.2, 0.2)\)，满足约束。
  • 迭代 1：计算梯度 \(g_0\)，识别积极集（可能为空），构造并求解 QP 得到步长 \(\mathbf{d}_0\)，线搜索确定 \(\alpha_0\)，更新点，BFGS 更新 \(B_1\)。
  • 迭代 k：重复直至梯度与约束满足收敛条件。

8. 总结

逐步二次逼近法（SQA） 通过序列求解二次规划子问题来处理非线性目标与线性约束的优化。针对大规模约束，结合积极集策略可以显著降低计算量。BFGS 拟牛顿更新避免了昂贵的 Hessian 计算，而梯度投影可作为备选方案来加速子问题求解。该算法在工程优化、机器学习参数调优等领域有广泛应用，尤其在目标函数复杂但约束相对简单的大规模问题中表现高效。

非线性规划中的逐步二次逼近法（Sequential Quadratic Approximation, SQA）进阶题：处理具有高度非线性目标与线性不等式约束的大规模优化问题 1. 问题描述 考虑以下 非线性规划（NLP）问题 ： \[ \begin{aligned} \min_ {\mathbf{x} \in \mathbb{R}^n} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & A\mathbf{x} \leq \mathbf{b} \end{aligned} \] 其中： \( f(\mathbf{x}) \) 是一个 高度非线性 （非二次、非凸且可能非光滑）的目标函数，计算其梯度 \( \nabla f(\mathbf{x}) \) 是可行的，但计算 Hessian 矩阵 \( \nabla^2 f(\mathbf{x}) \) 非常昂贵或不稳定。 约束是 \( m \) 个线性不等式 ，\( A \in \mathbb{R}^{m \times n} \)，\( \mathbf{b} \in \mathbb{R}^m \)，且约束数量 \( m \) 很大（例如 \( m \sim 10^4 \sim 10^6 \)），但 \( A \) 可能是稀疏的。 决策变量维度 \( n \) 也较大（例如 \( n \sim 10^3 \sim 10^4 \)）。 任务 ：设计一种 逐步二次逼近法（SQA） 的变体，在每次迭代中构造一个 简单且易于求解的二次子问题 来逼近原问题，并确保算法在大规模设置下 高效收敛 到原问题的一个 稳定点 （例如 KKT 点）。 2. 关键挑战 目标函数的高度非线性 ：直接使用精确的 Hessian 不可行，需要 低成本的 Hessian 近似 。 大规模线性不等式 ：即使子问题是二次规划（QP），当 \( m \) 很大时，直接求解完整的 QP 可能计算量过大。 可行性保持 ：迭代点必须始终保持满足 \( A\mathbf{x} \leq \mathbf{b} \)，否则二次子问题可能无解。 收敛保证 ：需要确保迭代序列的极限点满足原问题的 一阶必要条件 。 3. 逐步二次逼近法（SQA）的核心思想 SQA 是一种 序列二次规划（SQP） 的简化版本，特别适合 目标非线性但约束线性 的问题。其基本思路如下： 在当前迭代点 \( \mathbf{x}_ k \)，构造目标函数 \( f \) 的一个 二次逼近模型 \( q_ k(\mathbf{d}) \)： \[ q_ k(\mathbf{d}) = f(\mathbf{x}_ k) + \nabla f(\mathbf{x}_ k)^T \mathbf{d} + \frac{1}{2} \mathbf{d}^T B_ k \mathbf{d} \] 其中 \( \mathbf{d} = \mathbf{x} - \mathbf{x}_ k \) 是步长，\( B_ k \) 是 \( \nabla^2 f(\mathbf{x}_ k) \) 的一个 对称近似矩阵 （例如 BFGS 拟牛顿更新）。 求解以下 二次规划子问题 得到步长 \( \mathbf{d} k \)： \[ \begin{aligned} \min {\mathbf{d} \in \mathbb{R}^n} \quad & q_ k(\mathbf{d}) \\ \text{s.t.} \quad & A(\mathbf{x}_ k + \mathbf{d}) \leq \mathbf{b} \end{aligned} \] 注意：由于约束是线性的，子问题是一个 凸二次规划（如果 \( B_ k \succeq 0 \)） 。 更新迭代点：\( \mathbf{x}_ {k+1} = \mathbf{x}_ k + \alpha_ k \mathbf{d}_ k \)，其中 \( \alpha_ k \in (0,1] \) 是步长，通常通过 线搜索 （例如 Armijo 条件）确定，以保证目标函数充分下降。 更新近似 Hessian \( B_ k \)（例如用 BFGS 公式），重复直到收敛。 4. 针对大规模线性约束的改进策略 为应对约束数量 \( m \) 很大的情况，可以采用以下两种互补的策略： 策略 A：积极集方法（Active Set Method） 在每次迭代中， 仅考虑可能起作用的约束 （即积极约束或接近积极的约束），大大减少 QP 子问题的约束数量。 步骤 ： 在当前点 \( \mathbf{x}_ k \)，计算约束违反度：\( \mathbf{c}_ k = A\mathbf{x}_ k - \mathbf{b} \)。 选择 积极集 \( \mathcal{A} k = \{ i \mid c {k,i} \geq -\epsilon \} \)，其中 \( \epsilon > 0 \) 是一个小阈值（例如 \( 10^{-6} \)）。 求解仅包含 \( \mathcal{A}_ k \) 中约束的 QP 子问题，得到步长 \( \mathbf{d}_ k \)。 若新步长导致某个不在 \( \mathcal{A}_ k \) 中的约束被违反，则将其加入积极集，重新求解 QP。 通过迭代更新积极集，最终得到子问题的精确解。 策略 B：梯度投影 + 截断共轭梯度法 当 \( B_ k \) 是 对角占优或简单结构 时，可以结合梯度投影和共轭梯度法来近似求解 QP。 步骤 ： 将 QP 子问题改写为： \[ \min_ {\mathbf{d}} \frac{1}{2} \mathbf{d}^T B_ k \mathbf{d} + \nabla f(\mathbf{x}_ k)^T \mathbf{d} \quad \text{s.t.} \quad A\mathbf{d} \leq \mathbf{b} - A\mathbf{x}_ k \] 使用 梯度投影法 ：迭代更新 \( \mathbf{d} \)： \[ \mathbf{d}^{(t+1)} = P_ \Omega \left( \mathbf{d}^{(t)} - \eta (B_ k \mathbf{d}^{(t)} + \nabla f(\mathbf{x} k)) \right) \] 其中 \( P \Omega \) 是到线性约束集 \( \Omega = \{ \mathbf{d} \mid A\mathbf{d} \leq \mathbf{b} - A\mathbf{x}_ k \} \) 的投影，可通过 稀疏矩阵投影算法 高效计算。 当投影迭代达到一定精度或最大迭代次数时停止，得到近似步长 \( \mathbf{d}_ k \)。 5. 完整算法流程（结合积极集与拟牛顿更新） 初始化 ：选择初始点 \( \mathbf{x}_ 0 \) 满足 \( A\mathbf{x}_ 0 \leq \mathbf{b} \)，初始正定矩阵 \( B_ 0 = I \)（单位阵），容忍误差 \( \epsilon > 0 \)，令 \( k = 0 \)。 主循环 （直到满足停止条件 \( \| \nabla f(\mathbf{x}_ k) + A^T \boldsymbol{\lambda} k \| \infty \leq \epsilon \) 且约束违反度足够小）： 步骤 1：梯度计算 ：计算 \( g_ k = \nabla f(\mathbf{x}_ k) \)。 步骤 2：积极集识别 ：计算 \( \mathbf{c} k = A\mathbf{x} k - \mathbf{b} \)，定义积极集 \( \mathcal{A} k = \{ i \mid c {k,i} \geq -\epsilon {act} \} \)，其中 \( \epsilon {act} = 10^{-6} \)。 步骤 3：构造并求解简化 QP ： \[ \begin{aligned} \min_ {\mathbf{d}} \quad & g_ k^T \mathbf{d} + \frac{1}{2} \mathbf{d}^T B_ k \mathbf{d} \\ \text{s.t.} \quad & A_ i \mathbf{d} \leq b_ i - A_ i \mathbf{x}_ k, \quad i \in \mathcal{A}_ k \end{aligned} \] 使用 稀疏 QP 求解器 （如基于内点法或有效集法）求解，得到步长 \( \mathbf{d}_ k \) 和对偶变量 \( \boldsymbol{\lambda}_ k^{(a)} \)（对应积极约束）。 步骤 4：步长接受与线搜索 ： 令 \( \alpha_ k = 1 \)。 回溯线搜索 ：当 \( f(\mathbf{x}_ k + \alpha_ k \mathbf{d}_ k) > f(\mathbf{x}_ k) + \beta \alpha_ k g_ k^T \mathbf{d}_ k \)（Armijo 条件，\( \beta \in (0,1) \)）或 \( A(\mathbf{x}_ k + \alpha_ k \mathbf{d}_ k) \nleq \mathbf{b} \) 时，令 \( \alpha_ k \leftarrow \tau \alpha_ k \)（\( \tau \in (0,1) \)）。 若 \( \alpha_ k \) 小于最小值（例如 \( 10^{-8} \)），则重启（例如减小积极集阈值或重置 \( B_ k = I \)）。 步骤 5：更新迭代点 ：\( \mathbf{x}_ {k+1} = \mathbf{x}_ k + \alpha_ k \mathbf{d}_ k \)。 步骤 6：更新拟牛顿矩阵 ： 计算梯度差 \( \mathbf{s} k = \mathbf{x} {k+1} - \mathbf{x}_ k \)，\( \mathbf{y} k = \nabla f(\mathbf{x} {k+1}) - \nabla f(\mathbf{x}_ k) \)。 使用 BFGS 公式更新 \( B_ {k+1} \)： \[ B_ {k+1} = B_ k - \frac{B_ k \mathbf{s}_ k \mathbf{s}_ k^T B_ k}{\mathbf{s}_ k^T B_ k \mathbf{s}_ k} + \frac{\mathbf{y}_ k \mathbf{y}_ k^T}{\mathbf{s}_ k^T \mathbf{y}_ k}, \quad \text{若 } \mathbf{s}_ k^T \mathbf{y}_ k > 0 \] 若 \( \mathbf{s}_ k^T \mathbf{y} k \leq 0 \)，则跳过更新（保持 \( B {k+1} = B_ k \)）或使用 Powell 修正。 步骤 7：检查收敛 ：计算 KKT 残差： \[ r_ k = \| \nabla f(\mathbf{x}_ k) + A^T \boldsymbol{\lambda} k \| \infty, \quad \text{其中 } \boldsymbol{\lambda}_ k \text{ 由 } \mathcal{A}_ k \text{ 对应的对偶变量扩展得到（非积极约束对应零）}. \] 若 \( r_ k \leq \epsilon \) 且 \( \max(0, A\mathbf{x}_ k - \mathbf{b}) \leq \epsilon \)，则停止；否则令 \( k \leftarrow k+1 \) 继续。 6. 收敛性分析要点 全局收敛 ：在适当假设下（如 \( f \) 连续可微且有下界，约束集有内点，BFGS 更新保持一致正定性），结合 Armijo 线搜索，算法生成的序列 \( \{ \mathbf{x}_ k \} \) 的任何极限点都是原问题的 KKT 点 。 局部超线性收敛 ：如果 \( B_ k \) 通过 BFGS 更新渐近逼近真实 Hessian，且积极集识别准确，则在极限点附近步长 \( \alpha_ k = 1 \) 最终被接受，算法呈现 超线性收敛速度 。 大规模计算复杂度 ：积极集策略将每次 QP 的约束数降至 \( O(|\mathcal{A}_ k|) \)，通常远小于 \( m \)。若使用稀疏 QP 求解器，每次迭代的复杂度为 \( O(n^{1.5} \sim n^2) \)（取决于稀疏结构），内存需求为 \( O(nnz(A) + n^2) \)，其中 \( nnz(A) \) 是 \( A \) 的非零元个数。 7. 举例说明 考虑问题： \[ \min_ {x_ 1,x_ 2} \quad f(x_ 1,x_ 2) = e^{x_ 1} + x_ 1 x_ 2 + \sin(x_ 2^2), \quad \text{s.t.} \quad x_ 1 + 2x_ 2 \leq 1, \; -x_ 1 \leq 0, \; -x_ 2 \leq 0 \] 初始化：\( \mathbf{x}_ 0 = (0.2, 0.2) \)，满足约束。 迭代 1：计算梯度 \( g_ 0 \)，识别积极集（可能为空），构造并求解 QP 得到步长 \( \mathbf{d}_ 0 \)，线搜索确定 \( \alpha_ 0 \)，更新点，BFGS 更新 \( B_ 1 \)。 迭代 k：重复直至梯度与约束满足收敛条件。 8. 总结 逐步二次逼近法（SQA） 通过 序列求解二次规划子问题 来处理非线性目标与线性约束的优化。针对大规模约束，结合 积极集策略 可以显著降低计算量。BFGS 拟牛顿更新避免了昂贵的 Hessian 计算，而 梯度投影 可作为备选方案来加速子问题求解。该算法在工程优化、机器学习参数调优等领域有广泛应用，尤其在目标函数复杂但约束相对简单的大规模问题中表现高效。