Non-Negative Conjugate Gradients

技术摘要：非负共轭梯度法 (Non-Negative Conjugate Gradients)

问题陈述
本文研究的是严格凸非负二次规划 (NNQP) 问题：
$$\min_{x \in \mathbb{R}^n} f(x) = \frac{1}{2}x^\top A x - b^\top x \quad \text{subject to} \quad x \ge 0,$$
其中 $A$ 是对称正定 (SPD) 矩阵。作者还考虑了带有线性约束 $Bx = c$ 的等式增广变体。虽然共轭梯度 (CG) 方法是求解无约束 SPD 系统 $Ax=b$的标准求解器，但它本身并不具备处理非负约束$x \ge 0$ 的能力。现有的可行点方法（例如投影梯度法、MPRGP）通常面临收敛速率较慢（$O(\kappa)$）的问题，或者在处理一般等式约束时，难以在不引入外部增广拉格朗日循环的情况下进行处理。其目标是在不牺牲 CG 的 $O(\sqrt{\kappa})$ 收敛速率或其无矩阵 (matrix-free) 特性的前提下解决该问题。

方法论
所提出的方法——非负共轭梯度法 (NNCG)——将 CG 求解器封装在一个原对偶活跃集 (primal-dual active-set) 外部循环中。其核心策略包括：

1. 活跃集缩减 (Active-Set Reduction)： 算法维护一个由索引组成的“自由集” $F$，其中满足 $x_i > 0$。在该集合上，边界约束是不活跃的，从而将问题简化为无约束 SPD 系统 $A_F x_F = b_F$（对于等式增项情况，则为鞍点系统）。
2. 无矩阵内层求解 (Matrix-Free Inner Solve)： 内层系统使用 CG 进行求解。至关重要的一点是，该方法是无矩阵的：如果 $A = M^\top M$，则算子 $v \mapsto A_F v$ 通过计算 $M_F^\top (M_F v)$ 实现，仅需两次与 $M$ 的矩阵-向量乘积，从而避免了 $O(n^2)$ 的 $A$ 矩阵存储开销。
3. 原对偶切换 (Primal-Dual Toggling)：
   • 原变量步骤 (Primal Step)： 任何变为负值的自由变量 $x_i$ 都会从 $F$ 中剔除（设为 0）。
   • 对偶变量步骤 (Dual Step)： 任何满足 $x_i = 0$ 且还原梯度 $s_i = (Ax)_i - b_i$ 为负值的变量将被引入 $F$。
   • 这些切换对应于线性互补问题 (LCP) $(A, -b)$ 的主轴旋转 (principal pivots)。
4. 终止策略： 为了确保即使在退化情况下也能有限终止，该方法采用了由 Bland 最小索引回退机制 (least-index Bland fallback) 保护的 块主轴旋转路径 (block-principal-pivoting path)（快速批量交换）。这种基于 J´udice 和 Pires [21] 以及 Murty [25] 的构造，保证了向唯一全局极小值的收敛。
5. 处理不精确性 (Handling Inexactness)： 本文的一个关键理论贡献是证明了：如果 CG 内层残差相对于“决策间距”（即在精确轨迹中遇到的最小非零原变量或对偶变量值）足够小，则不精确循环会做出与精确循环完全相同的符号决策。这使得有限终止保证可以转移到无矩阵、不精确的计算范式中。
6. 正则化与预处理： 使用岭/Tikhonov 分解 $A_\alpha = (1-\alpha)A + \alpha R^\top R$ 来压缩条件数 $\kappa$，并确保即使在原始 $A$ 是秩亏缺的情况下，$A_\alpha$ 仍保持为 P-矩阵（严格正定主子矩阵）。预处理（如 Jacobi、Nyström）被用于进一步加速内层 CG 求解。

核心贡献

• 不精确求解的有限终止性： 本文将块主轴旋转的有限终止保证（此前仅适用于精确求解）扩展到了不精确、无矩阵的 CG 范式中。引理 4.1 表明，一旦内层残差与决策间距挂钩，近似循环将遵循精确的自由集轨迹。
• 直接处理等式约束： 不同于需要通过外部增广拉格朗日循环来处理一般等式 $Bx=c$ 的可行点方法，本方法通过舒尔补 (Schur complement) 在解析上消除了乘子，直接在活跃集框架内求解等式增广问题。
• 无矩阵高效性： 求解器无需组装 $A$，仅需 $O(n)$ 的工作内存和每个外部步骤 $O(\sqrt{\kappa})$ 的内层迭代。
• 热启动 (Warm-Starting)： 该方法支持在参数族（例如有效前沿）中的热启动，其中前一步的自由集和解可作为初始猜测，在支持集稳定的情况下大幅减少外部迭代次数。

结果

• 合成性能： 在具有植入最优解的合成 SPD 问题上，算法最多在 6 个外部步骤内达到最优。总 CG 内层迭代次数随条件数 $\kappa$ 呈亚线性增长（在对数-对数坐标系下斜率 $\approx 0.35$），证实了 $O(\sqrt{\kappa})$ 的行为。
• 退化与循环： 在旨在导致无保护批量旋转发生循环的对抗性相关设计族中，所提出的回退机制成功终止了循环，而无保护路径则陷入了循环。
• 秩亏缺： 在秩亏缺情形下 ($m < n$)，未正则化的求解器无法收敛或无法认证最优性。引入微小的正则化参数 $\alpha > 0$ 可恢复 P-矩阵属性，确保收敛并提供 KKT 认证。
• 基准对比：
  • 对比投影梯度法： 在病态问题上，NNCG 的表现优于投影梯度法 $\sqrt{\kappa}$ 倍。
  • 对比 Lawson-Hanson 与 内部点法： 在稠密、已组装的问题上，由于块旋转能在个位数次的外部步骤内达到最优支持集，NNCG（配合直接内层求解）显著更快（例如在 $n=2000$ 时比 Lawson-Hanson 快 48 倍）。
  • 大规模下的稠密求解器对比： 在无矩阵去模糊应用（$n=65,536$）中，稠密求解器（Lawson-Hanson, Clarabel）因内存限制（$O(n^2)$ 存储）而失效。NNCG 以 $O(n)$ 内存和秒级时间解决此类问题，而稠密求解器甚至无法实例化算子。
• 实际应用： 在高光谱解混问题（Cuprite 场景，$n=498$ 个特征）中，通过热启动，该方法比冷启动运行实现了 672 倍的加速，并提供了精确的 KKT 证书（识别出单一矿物支持集），而可行点方法返回的是需要阈值处理的近似解。

意义与主张
本文声称 NNCG 为非负二次规划提供了无条件的有限终止保证，即使在存在退化和不精确内层求解的情况下也是如此。它弥合了 Krylov 子空间方法（CG）的高效性与活跃集方法（Active-set methods）的组合优化保证之间的鸿沟。

作者强调，该方法是应用无关的，能够处理边界约束和一般线性等式，而无需外部循环。虽然该方法仅针对非负象限（而非一般的箱式约束），但它通过提供精确的 KKT 证书并原生处理等式约束，展现出优于可行点方法（如 MPRGP）的独特优势。这项工作确立了“决策对决策”的转移在精确求解与不精确求解之间是可行的，从而将主轴旋转的鲁棒性与矩阵自由 Krylov 求解器的可扩展性结合在一起。