非线性规划中的序列二次规划-积极集-信赖域混合算法进阶题：处理带非凸不等式约束的大规模稀疏优化
题目描述
考虑以下大规模稀疏非线性规划问题：
\[\min_{x \in \mathbb{R}^n} f(x) \]
\[\text{s.t. } c_i(x) \leq 0, \quad i = 1, \dots, m \]
其中：
- \(f: \mathbb{R}^n \to \mathbb{R}\) 是二阶连续可微、可能非凸的目标函数；
- \(c_i: \mathbb{R}^n \to \mathbb{R}\) 是二阶连续可微、可能非凸的约束函数；
- 变量维度 \(n\) 很大（例如 \(n \geq 10^4\)），且目标函数和约束的Hessian矩阵具有稀疏结构；
- 约束数量 \(m\) 可以很大，但每个约束仅依赖于少数变量（局部性），使得约束Jacobian矩阵也是稀疏的。
要求设计一种序列二次规划-积极集-信赖域混合算法，有效利用稀疏性，并能处理非凸约束可能导致的不可行子问题。需要详细说明算法框架、关键步骤、稀疏性利用策略以及全局收敛性保证。
解题过程
1. 算法总体框架
该算法将序列二次规划（SQP）、积极集法（Active Set）和信赖域法（Trust Region）结合，并特别针对大规模稀疏问题设计。基本迭代步骤如下：
- 在当前迭代点 \(x_k\)，构建一个带信赖域约束的二次规划子问题。
- 利用积极集策略识别可能起作用的约束，减少子问题规模。
- 求解该二次规划子问题，得到试探步 \(p_k\)。
- 计算实际下降量与预测下降量的比值，决定是否接受该步，并更新信赖域半径。
- 更新迭代点，并调整积极集。
下面我们逐步展开。
2. 构建二次规划子问题（带信赖域）
在点 \(x_k\) 处，我们对目标函数和约束进行二阶近似（或拟牛顿近似），得到子问题：
\[\min_{p \in \mathbb{R}^n} \nabla f(x_k)^T p + \frac{1}{2} p^T B_k p \]
\[ \text{s.t. } c_i(x_k) + \nabla c_i(x_k)^T p \leq 0, \quad i = 1, \dots, m \]
\[ \| p \| \leq \Delta_k \]
其中：
- \(B_k\) 是目标函数Hessian \(\nabla^2 f(x_k)\) 或其拟牛顿近似（例如BFGS更新），利用稀疏性存储；
- \(\nabla c_i(x_k)\) 是约束梯度，构成稀疏Jacobian矩阵；
- \(\Delta_k > 0\) 是当前信赖域半径；
- \(\| \cdot \|\) 通常取 \(\ell_2\) 范数，但对于稀疏问题，也可用加权范数以适配问题尺度。
3. 积极集策略缩减问题规模
由于 \(m\) 可能很大，直接求解以上子问题代价高。我们采用积极集法的思想：
- 积极集 \(\mathcal{A}_k\) ：在当前点 \(x_k\)，定义 \(\mathcal{A}_k = \{ i \mid c_i(x_k) \geq -\epsilon \}\)，即那些值接近零（可能起作用）的约束索引，\(\epsilon > 0\) 为一小阈值。
- 忽略非积极约束：对于 \(i \notin \mathcal{A}_k\)，约束 \(c_i(x_k) + \nabla c_i(x_k)^T p \leq 0\) 在 \(x_k\) 处远离边界，在当前信赖域步长内很可能保持满足，故暂时忽略它们。
- 缩减后的子问题：只保留积极集约束：
\[\min_{p} \nabla f(x_k)^T p + \frac{1}{2} p^T B_k p \]
\[ \text{s.t. } c_i(x_k) + \nabla c_i(x_k)^T p \leq 0, \quad i \in \mathcal{A}_k \]
\[ \| p \| \leq \Delta_k \]
这样，约束数量从 \(m\) 减少到 \(|\mathcal{A}_k|\)，通常远小于 \(m\)。
4. 稀疏性利用与子问题求解
(a) 稀疏数据结构
- \(B_k\) 以稀疏矩阵格式（如CSR）存储，仅非零元素参与运算。
- Jacobian矩阵 \(J_k = [\nabla c_i(x_k)^T]_{i \in \mathcal{A}_k}\) 同样稀疏存储，每行对应一个积极约束的梯度。
(b) 子问题求解算法
子问题是带信赖域约束的二次规划（可能非凸，因 \(B_k\) 不一定正定）。常用方法：
- 截断共轭梯度法（Steihaug-Toint方法）：适用于大规模稀疏问题，可处理不定Hessian，并在遇到负曲率或触及信赖域边界时停止。
- 由于还有线性不等式约束，可结合积极集迭代：在每次积极集变更后，用截断共轭梯度法求解等式约束子问题。
具体步骤：
- 设当前积极集为 \(\mathcal{A}_k^+ \subseteq \mathcal{A}_k\)（等式约束子集）。
- 求解等式约束子问题：
\[ \min_p \nabla f(x_k)^T p + \frac{1}{2} p^T B_k p \]
\[ \text{s.t. } c_i(x_k) + \nabla c_i(x_k)^T p = 0, \; i \in \mathcal{A}_k^+ \]
\[ \| p \| \leq \Delta_k \]
用拉格朗日乘子法转化为线性系统，并利用共轭梯度法迭代求解（因为系统大规模稀疏）。
3. 检查新解是否满足所有不等式约束；若不满足，将最违反的约束加入 \(\mathcal{A}_k^+\)，重复步骤2。
4. 若在积极集上乘子非负（满足KKT条件），则停止；否则移除对应约束，重复。
5. 接受试探步与更新信赖域半径
计算实际下降量 \(\text{ared}_k = f(x_k) - f(x_k + p_k)\) 和预测下降量 \(\text{pred}_k = -(\nabla f(x_k)^T p_k + \frac{1}{2} p_k^T B_k p_k)\)。定义比值：
\[\rho_k = \frac{\text{ared}_k}{\text{pred}_k} \]
更新规则：
- 若 \(\rho_k \geq \eta_1\)（例如 \(\eta_1 = 0.01\)），接受步长：\(x_{k+1} = x_k + p_k\)。
- 否则拒绝步长：\(x_{k+1} = x_k\)。
- 调整信赖域半径：
\[ \Delta_{k+1} = \begin{cases} \gamma_1 \Delta_k, & \text{if } \rho_k < \eta_1 \\ \Delta_k, & \text{if } \eta_1 \leq \rho_k < \eta_2 \\ \min(\gamma_2 \Delta_k, \Delta_{\max}), & \text{if } \rho_k \geq \eta_2 \end{cases} \]
其中 \(0 < \eta_1 < \eta_2 < 1\)，\(0 < \gamma_1 < 1 < \gamma_2\)，典型值 \(\eta_1=0.01, \eta_2=0.75, \gamma_1=0.5, \gamma_2=2\)。
6. 处理非凸约束导致的不可行子问题
当约束非凸时，二次约束近似可能在信赖域内不可行。对策：
- 松弛法：引入松弛变量 \(s \geq 0\)，将约束改为 \(c_i(x_k) + \nabla c_i(x_k)^T p \leq s\)，并最小化 \(s\) 作为目标的一部分，确保子问题总是可行。
- 调整信赖域：若子问题不可行，缩小信赖域半径 \(\Delta_k\) 直到可行（因为约束近似在足够小邻域内更精确）。
7. 算法流程总结
- 初始化：给定初始点 \(x_0\)，初始信赖域半径 \(\Delta_0 > 0\)，初始Hessian近似 \(B_0\)（可为单位阵），容忍阈值 \(\epsilon > 0\)，\(k=0\)。
- 循环直到收敛（满足KKT条件）：
a. 计算 \(f(x_k)\)、\(\nabla f(x_k)\)、\(c_i(x_k)\)、\(\nabla c_i(x_k)\)。
b. 确定积极集 \(\mathcal{A}_k = \{ i \mid c_i(x_k) \geq -\epsilon \}\)。
c. 构建并求解缩减后的二次规划子问题（带信赖域），得试探步 \(p_k\)。
d. 计算比值 \(\rho_k\)。
e. 根据 \(\rho_k\) 决定是否接受 \(p_k\)，并更新信赖域半径。
f. 若接受步长，用BFGS等稀疏拟牛顿公式更新 \(B_{k+1}\)。
g. \(k \leftarrow k+1\)。 - 输出解 \(x_k\)。
8. 全局收敛性保证
- 在标准假设下（函数有下界、Hessian近似一致有界、约束梯度线性独立），该算法能保证每个极限点满足一阶必要最优条件（KKT条件）。
- 关键点：信赖域机制确保全局收敛，即使子问题Hessian非正定；积极集策略仅减少计算量，不影响收敛性，因为最终积极集会稳定在最优积极集。
- 稀疏性利用不影响理论性质，但大幅提升大规模问题下的计算效率。
9. 实际应用建议
- 可使用稀疏线性代数库（如SuiteSparse）加速子问题求解。
- 对于高度非凸问题，可结合过滤线搜索（Filter Line Search）替代信赖域，以更好平衡可行性与最优性。
- 并行计算：可并行计算目标/约束的函数值和梯度，进一步提升大规模问题性能。
通过以上设计，该混合算法能有效求解大规模稀疏非凸约束优化问题，兼具SQP的快速局部收敛、积极集法的约束处理效率、信赖域的全局收敛保证，以及稀疏计算的可扩展性。