其中 $\epsilon_k > 0$ 是一个小阈值（可能随迭代减小）。只有 $j \in \mathcal{A}_k$ 的不等式约束被纳入当前的二次规划子问题中。这大幅减少了约束数量，利用了约束的稀疏性。

其中 $0 < \eta_1 < \eta_2 < 1$， $0 < \gamma_1 < 1 < \gamma_2$， $\Delta_{\min}$ 和 $\Delta_{\max}$ 是半径上下界。

非线性规划中的序列二次规划-积极集-乘子法-过滤器-信赖域混合算法进阶题：求解具有非凸不等式约束和线性等式约束的大规模稀疏优化问题 这是一个结合了序列二次规划、积极集策略、乘子法、过滤器技术和信赖域框架的混合算法进阶题目。我们将从一个具体实例出发，逐步讲解其原理、构建和求解过程。 题目描述 考虑如下大规模稀疏非线性规划问题： \[ \begin{aligned} & \min_ {x \in \mathbb{R}^n} \quad f(x) \\ & \text{s.t.} \quad c_ i(x) = 0, \quad i \in \mathcal{E}, \\ & \qquad g_ j(x) \le 0, \quad j \in \mathcal{I}, \end{aligned} \] 其中： 决策变量 \(x \in \mathbb{R}^n\)，维度 \(n\) 很大（例如 \(n \ge 10^4\)），但目标函数 \(f(x)\) 和约束函数的梯度/Hessian矩阵是 稀疏的 。 目标函数 \(f(x)\) 是 非凸的、二次连续可微 的。 等式约束 \(c_ i(x)\) 是 线性的 （这在实际工程问题中常见，例如平衡方程、资源分配等式）。 不等式约束 \(g_ j(x)\) 是 非凸的、二次连续可微 的，且约束数量 \(|\mathcal{I}|\) 可能很大，但每个约束函数本身或其在当前迭代点的积极集是 稀疏的 。 问题是大规模的，但具有稀疏结构，因此算法需能利用稀疏性以提高效率。 我们的目标是：设计一个高效的混合算法，能够稳定、快速地找到满足一阶必要优化条件（KKT条件）的局部最优解。 解题过程 第一步：算法框架选择与动机 对于大规模、稀疏、非凸约束优化问题，直接使用标准的SQP（序列二次规划）可能面临子问题非凸、迭代点不可行、Maratos效应（目标函数不下降）等问题。因此，我们组合多种技术： 序列二次规划 ：在每一步迭代，用二阶近似构建一个二次规划子问题，快速逼近原问题。 积极集策略 ：仅处理可能起作用的约束，减少子问题的规模，这对大规模稀疏问题至关重要。 乘子法 ：将拉格朗日乘子估计引入子问题，改善收敛性和约束违反度的控制。 过滤器方法 ：代替传统的罚函数，同时考虑目标函数下降和约束违反度，避免惩罚参数难以选取的问题。 信赖域框架 ：为SQP子问题的求解提供全局收敛性保证，控制步长的可靠性。 混合算法核心思想是：在每一步迭代，基于当前点 \(x_ k\) 和乘子估计 \((\lambda_ k, \mu_ k)\)，构建一个带信赖域约束的二次规划子问题，用积极集策略识别有效约束，求解该子问题得到试探步，然后用过滤器判断是否接受该步长，并更新乘子和信赖域半径。 第二步：构建拉格朗日函数与KKT条件 首先定义增广拉格朗日函数（这里“增广”主要指乘子法的思想，实际子问题构造中可能不显式使用增广项，而是通过乘子估计）： \[ \mathcal{L}(x, \lambda, \mu) = f(x) + \sum_ {i \in \mathcal{E}} \lambda_ i c_ i(x) + \sum_ {j \in \mathcal{I}} \mu_ j g_ j(x), \] 其中 \(\lambda_ i\) 和 \(\mu_ j \ge 0\) 是拉格朗日乘子。 问题的一阶必要性条件（KKT条件）为： \[ \begin{aligned} \nabla_ x \mathcal{L}(x^ , \lambda^ , \mu^ ) &= 0, \\ c_ i(x^ ) &= 0, \quad i \in \mathcal{E}, \\ g_ j(x^ ) &\le 0, \quad j \in \mathcal{I}, \\ \mu_ j^ &\ge 0, \quad j \in \mathcal{I}, \\ \mu_ j^* g_ j(x^* ) &= 0, \quad j \in \mathcal{I}. \end{aligned} \] 第三步：序列二次规划子问题的构建 在第 \(k\) 次迭代，当前点为 \(x_ k\)，乘子估计为 \(\lambda_ k\) 和 \(\mu_ k\)。我们构建如下二次规划子问题： \[ \begin{aligned} \min_ {d \in \mathbb{R}^n} \quad & \nabla f(x_ k)^T d + \frac{1}{2} d^T B_ k d \\ \text{s.t.} \quad & c_ i(x_ k) + \nabla c_ i(x_ k)^T d = 0, \quad i \in \mathcal{E}, \\ & g_ j(x_ k) + \nabla g_ j(x_ k)^T d \le 0, \quad j \in \mathcal{I}, \\ & \|d\|_ {\infty} \le \Delta_ k, \end{aligned} \] 其中： \(d = x - x_ k\) 是试探步。 \(B_ k\) 是拉格朗日函数 Hessian \(\nabla_ {xx}^2 \mathcal{L}(x_ k, \lambda_ k, \mu_ k)\) 或其 稀疏拟牛顿近似 （如有限内存BFGS，L-BFGS）。利用稀疏性可高效存储和计算。 \(\|d\|_ {\infty} \le \Delta_ k\) 是信赖域约束，\(\Delta_ k > 0\) 是信赖域半径，控制步长大小，保证模型在局部足够准确。 注意 ：由于等式约束是线性的，其线性化是精确的，即 \(c_ i(x_ k + d) = c_ i(x_ k) + \nabla c_ i(x_ k)^T d\)。这简化了子问题的可行性处理。 第四步：积极集策略的应用 由于不等式约束数量可能很大，但许多在解处是不起作用的（严格小于0），我们采用 积极集策略 来缩减子问题的规模： 预测积极集 ：在当前点 \(x_ k\)，定义近似积极集 \(\mathcal{A}_ k \subseteq \mathcal{I}\)，例如： \[ \mathcal{A}_ k = \{ j \in \mathcal{I} : g_ j(x_ k) \ge -\epsilon_ k \}, \] 其中 \(\epsilon_ k > 0\) 是一个小阈值（可能随迭代减小）。只有 \(j \in \mathcal{A}_ k\) 的不等式约束被纳入当前的二次规划子问题中。这大幅减少了约束数量，利用了约束的稀疏性。 求解缩减子问题 ：只考虑 \(\mathcal{A}_ k\) 中的不等式约束，求解带信赖域约束的二次规划。由于问题规模缩减且具有稀疏结构，可采用专门求解大规模稀疏二次规划的方法（如内点法、有效集法的稀疏实现）。 更新积极集 ：求解子问题得到试探步 \(d_ k\) 和对应的乘子估计 \(\mu_ {k,j}\) 对于 \(j \in \mathcal{A}_ k\)。根据新的乘子符号和约束违反度，在下一步迭代调整积极集。 第五步：过滤器接受条件与迭代更新 得到试探步 \(d_ k\) 后，我们需要决定是否接受该步长，并更新迭代点。这里使用 过滤器 代替传统的罚函数。 定义过滤器 ：过滤器 \(\mathcal{F}_ k\) 是一个被禁止的 \((\theta, f)\) 对的集合，其中 \(\theta(x) = \|c(x)\| 2^2 + \sum {j \in \mathcal{I}} [ \max(0, g_ j(x)) ]^2\) 是约束违反度的度量。如果一点 \((f(x), \theta(x))\) 不被任何过滤器中的点占优（即同时有更小的 \(f\) 和更小的 \(\theta\)），则它是可接受的。 接受试探步的条件 ： 计算实际下降量：\(Ared_ k = f(x_ k) - f(x_ k + d_ k)\)。 计算预测下降量：\(Pred_ k = -\left( \nabla f(x_ k)^T d_ k + \frac{1}{2} d_ k^T B_ k d_ k \right)\)。 计算比值 \(r_ k = Ared_ k / Pred_ k\)。 如果 \(r_ k \ge \eta_ 1 > 0\)（例如 \(\eta_ 1 = 0.01\)） 且 点 \((f(x_ k + d_ k), \theta(x_ k + d_ k))\) 不被当前过滤器 \(\mathcal{F} k\) 占优，则接受该步：\(x {k+1} = x_ k + d_ k\)。 否则 ，拒绝该步：\(x_ {k+1} = x_ k\)，并将点 \((f(x_ k), \theta(x_ k))\) 加入过滤器（防止循环）。 更新信赖域半径 ： \[ \Delta_ {k+1} = \begin{cases} \max(\gamma_ 1 \Delta_ k, \Delta_ {\min}) & \text{if } r_ k < \eta_ 1, \\ \Delta_ k & \text{if } r_ k \in [ \eta_ 1, \eta_ 2), \\ \min(\gamma_ 2 \Delta_ k, \Delta_ {\max}) & \text{if } r_ k \ge \eta_ 2, \end{cases} \] 其中 \(0 < \eta_ 1 < \eta_ 2 < 1\)， \(0 < \gamma_ 1 < 1 < \gamma_ 2\)， \(\Delta_ {\min}\) 和 \(\Delta_ {\max}\) 是半径上下界。 第六步：乘子更新 如果试探步被接受，我们更新拉格朗日乘子： 对于等式约束乘子 \(\lambda\)，可直接取为二次规划子问题求解得到的乘子值 \(\lambda_ {k+1}\)。 对于不等式约束乘子 \(\mu\)，对积极集中的约束，同样取子问题解得的乘子 \(\mu_ {j,k+1} \ge 0\)；对非积极约束 (\(g_ j(x_ {k+1}) < 0\))，设 \(\mu_ {j,k+1} = 0\)。 这种更新方式本质上是 乘子法 的思想，在每一步通过求解子问题获得对最优乘子的估计，并用于构建下一步的Hessian近似 \(B_ {k+1}\)。 第七步：算法流程总结 初始化 ：给定初始点 \(x_ 0\)，初始乘子 \(\lambda_ 0, \mu_ 0 \ge 0\)，初始信赖域半径 \(\Delta_ 0 > 0\)，初始积极集 \(\mathcal{A}_ 0\)，初始空过滤器 \(\mathcal{F}_ 0 = \emptyset\)，对称正定矩阵 \(B_ 0\)（例如单位阵），设定参数 \(\eta_ 1, \eta_ 2, \gamma_ 1, \gamma_ 2, \epsilon_ 0\)，令 \(k=0\)。 主循环 （直到收敛条件满足，如KKT残差小于容差）： a. 构建并求解子问题 ：基于 \(x_ k, \lambda_ k, \mu_ k, B_ k, \Delta_ k\) 和当前积极集 \(\mathcal{A}_ k\)，构建并求解稀疏二次规划子问题，得到试探步 \(d_ k\) 和乘子 \((\lambda^q_ k, \mu^q_ k)\)。 b. 过滤器判断 ：计算实际下降 \(Ared_ k\) 和预测下降 \(Pred_ k\)，计算比值 \(r_ k = Ared_ k / Pred_ k\)。判断点 \((f(x_ k+d_ k), \theta(x_ k+d_ k))\) 是否被当前过滤器占优。 c. 步长接受与更新 ： 如果 \(r_ k \ge \eta_ 1\) 且点不被占优，则接受步长：\(x_ {k+1} = x_ k + d_ k\)，更新乘子 \(\lambda_ {k+1} = \lambda^q_ k\)， \(\mu_ {j,k+1} = \mu^q_ {j,k}\) for \(j \in \mathcal{A} k\)，否则 \(\mu {j,k+1}=0\)。 否则，拒绝步长：\(x_ {k+1} = x_ k\)，将 \((f(x_ k), \theta(x_ k))\) 加入过滤器 \(\mathcal{F} {k+1} = \mathcal{F} k \cup \{(f(x_ k), \theta(x_ k))\}\)。 d. 更新信赖域半径 ：根据 \(r_ k\) 按上述规则更新 \(\Delta {k+1}\)。 e. 更新积极集 ：基于新点 \(x {k+1}\) 和新的乘子，用阈值 \(\epsilon_ {k+1}\) 更新积极集 \(\mathcal{A} {k+1}\)。阈值 \(\epsilon_ k\) 可随迭代减小到零。 f. 更新Hessian近似 ：利用新点的梯度信息，通过拟牛顿公式（如BFGS）更新 \(B {k+1}\)，注意保持稀疏性。 g. \(k := k+1\)，进入下一轮迭代。 第八步：收敛性说明 该混合算法的收敛性分析通常包括： 在合理假设下（如目标和约束函数连续可微，迭代点有界，子问题一致可行，\(B_ k\) 一致有界正定），算法产生的迭代点至少有一个聚点满足KKT条件。 过滤器机制保证算法不会无限循环在不可行点。 信赖域机制和比值 \(r_ k\) 控制保证模型足够精确时才接受大步长，最终允许步长充分大以实现快速局部收敛（在解附近，若 \(B_ k\) 逼近真实Hessian，且积极集稳定，算法可达到二阶收敛速率）。 总结 本题展示的混合算法，通过 序列二次规划 提供局部二阶模型，用 积极集策略 处理大规模稀疏约束，用 乘子法 改善乘子估计，用 过滤器 管理目标下降与可行性，并在 信赖域 框架下保证全局收敛。它特别适合求解目标非凸、约束非线性但具有一定稀疏结构的大规模优化问题，是当前非线性规划中处理复杂实际工程问题的有效高级策略。