🔢 mathematics

An augmented Lagrangian algorithm for constrained nonlinear least-squares

本文提出了一种用于求解带有混合线性与非线性约束的受限非线性最小二乘问题的全局收敛增广拉格朗日算法，该算法在子问题中采用了梯度投影法以及结构化海森矩阵近似。

原作者： Pierre Borie, Fabian Bastin, Stéphane Dellacherie

发布于 2026-07-14

📖 1 分钟阅读🧠 深度阅读

原作者： Pierre Borie, Fabian Bastin, Stéphane Dellacherie

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在寻找一个完美的地点来搭建一个巨大的、摇摇欲坠的帐篷。你希望帐篷符合特定的形状（即“最小二乘法”部分，意味着你希望最大限度地减少帐篷支柱与理想形状之间的间隙），但你也有严格的规则：帐篷必须留在围起来的院子里，且某些支柱必须接触到特定的树木或岩石（即“约束条件”）。

这正是 Pierre Borie、Fabian Bastin 和 Stéphane Dellacherie 在其论文中解决的问题。他们构建了一种名为 TRAULLS（置信域增强非线性最小二乘求解器）的新算法，用于解决这些棘手的“受约束非线性最小二乘”谜题。

以下是他们的方法是如何运作的，通过一个你可以想象出的故事进行拆解。

两部分策略：惩罚箱与围栏

大多数传统的解决方法试图同时解决形状问题和围栏问题，这就像是在走钢丝的同时还要玩杂耍。作者的方法更聪明。他们将工作分为两个层面：

围栏（线性约束）： 关于院子边界和树木的规则是“线性的”。把这些想象成一个坚硬、不可改变的围栏。算法直接处理这些规则，就像一个知道如何沿着墙壁滑动而不越界的机器人。
惩罚箱（非线性约束）： 难点在于帐篷“摇摆”的形状。如果帐篷不符合理想形状，算法并不会忽略它；而是会将帐篷放入一个“惩罚箱”中。每当帐篷形状不对时，算法都会在得分中增加一笔巨额“罚款”。这被称为增广拉格朗日法（Augmented Lagrangian）。

算法在玩一场“忽冷忽热”的游戏。它试图在围栏内寻找最佳位置，同时最小化罚款。如果帐篷仍然太摇摆（罚款太高），算法会在下一轮中增加罚款金额，迫使帐篷精准地卡入正确的形状。

“步法”之舞：Cauchy 与子空间

一旦算法决定向更好的位置迈出一步，它并不仅仅是靠猜测。它使用了一个两步走的舞蹈：

Cauchy 步： 首先，它向下坡方向快速、谨慎地迈出一步。这就像是观察坡度，并朝着感觉最陡峭的方向迈出安全的一步。这保证了算法永远不会陷入停滞或向后退步。
子空间最小化： 在完成那个安全步骤后，它会看得更深。它在一个由当前触及的规则所定义的特定“隧道”（子空间）中进行探索。它使用一种称为**投影共轭梯度法（Projected Conjugate Gradient）**的特殊工具，在那个隧道内精准定位最佳点。

秘诀所在：“结构化”海森矩阵（Hessian）

这是论文真正精妙之处。为了知道往哪个方向是“下坡”，算法需要一张地形图，称为海森矩阵（Hessian）。

旧方法： 一些方法使用粗略的地图（高斯-牛顿法），假设地面是平坦的。这很快，但如果地面凹凸不平，就会出错。
“完整”方法： 其他方法试图完美地绘制出整个凹凸不平的地面。这很精确，但会消耗大量的内存和时间，导致计算量过大时电脑崩溃。

作者的创新是一种**结构化拟牛顿（Structured Quasi-Newton）**更新。想象一下你有一张地形草图。与其每次都重画整张图，不如只更新发生变化的部分，并使用一种尊重该问题独特的“平方和”性质的特殊规则（SR1 更新）。

他们测试了一种“混合”策略：如果地面看起来很平坦，他们就使用快速草图；如果地面看起来凹凸不平，他们就切换到详细更新。
结果： 在对 79 个不同问题（变量范围从 2 到 1000 个）的测试中，这种混合 SR1 方法是最稳健的。它不仅有效，而且在处理“凹凸不平”的问题时比标准草图表现更好，并且比其他复杂的算法更可靠。

他们的发现（以及没发现的）

作者在一部配备 M4 处理器的 Mac mini 上运行了他们的算法，并将其与另外两个著名的求解器进行了对比：IPOPT 和 Percival。

速度： 就原始时间而言，他们的新求解器（TRAULLS）紧随 IPOPT 之后。IPOPT 在处理简单问题时稍快，但随着问题变得复杂，两者的差距缩小了。
效率： IPOPT 是节省“残差评估”（检查帐篷形状）的冠军。这是因为 IPOPT 在每一步都使用精确、重型的数学运算。然而，TRAULLS 在许多指标上都比 Percival（另一种增广拉格朗日求解器）要好，并且在许多指标上与 IPOPT 相当。
赢家： 论文表明，对于这类特定问题，使用混合 SR1 更新是整体最佳策略。它在速度和精度之间取得了完美的平衡。

他们排除了什么

论文明确表达了反对在大型问题中使用“完整”海森矩阵（完美的地图）的观点。他们证明了计算完整的二阶项需要耗费过多的时间和存储空间，使得在变量极多的情况下是不切实际的。他们还表明，简单的“高斯-牛顿”草图（忽略凹凸不平）在“帐篷”远离理想形状时，其精度本身是不够的。

他们有多确定？

作者对自己的结果非常有信心，但也措辞谨慎。

他们通过数学证明了在满足某些标准假设的情况下，他们的方法最终会找到解（全局收敛性）。
他们通过对 79 个特定问题实例的数值实验测量了性能。
他们并不声称它是宇宙中最快的求解器。他们承认，对于大规模问题（即变量数量极其庞大的情况），他们的方法会遇到瓶颈，因为“结构化”地图仍需要存储一个稠密矩阵。他们建议，对于那些超大型案例，需要开发一个“有限内存”版本，但目前尚未构建。

简而言之，TRAULLS 是解决带有规则的复杂拟合问题的一种全新的、聪明的办法。它利用“惩罚箱”来处理硬性规则，并利用“智能草图”来导航地形，证明了在模拟实验中，它是解决这些数学谜题的一个强大且可靠的竞争者。

技术摘要：一种用于受约束非线性最小二乘问题的增广拉格朗日算法

问题表述
本文研究了受约束非线性最小二乘（NLS）问题，该问题定义为在满足非线性等式约束 $c(x)=0$ 和线性约束 $x \in \Omega$ 的条件下，最小化平方残差之和 $\frac{1}{2}\|r(x)\|^2$ 。集合 $\Omega$ 包含了线性等式（$Ax=b $）和边界约束（$ l \le x \le u $）。假设残差$ r(x) $和约束$ c(x)$ 是二次连续可微的。解决此类问题的核心挑战在于如何高效地处理 NLS 结构——即如何将目标函数的 Hessian 矩阵分解为一阶项 $J(x)^\top J(x)$ 和涉及单个残差 Hessian 的二阶项——同时还要强制执行一般性约束。

方法论
所提出的算法在 Julia 中实现为 TRAULLS，它将增广拉格朗日（AL）框架与结构化拟牛顿（SQN）近似以及梯度投影技术相结合。

增广拉格朗日框架：
非线性约束通过 AL 惩罚项合并到目标函数中，从而将原始问题转化为一系列线性约束子问题。在每个外部迭代 $K$ ，算法在多面体集 $\Omega$ 上最小化 AL 函数 $\Phi(x, \lambda, \mu)$ 。
- 乘子与惩罚参数更新： 如果非线性可行性得到充分改善，则通过对偶上升更新拉格朗日乘子（ $\lambda_{K+1} = \lambda_K + \mu_K c(x_K)$ ）。如果可行性未得到改善，则增加惩罚参数 $\mu_K$ ，以便在下次迭代中更严格地执行约束。
- 内部最小化： 子问题（在 $\Omega$ 上最小化 $\Phi$ ）使用信赖域方法求解。算法采用嵌套结构，其中每个外部迭代触发一系列内部迭代（ $k$ ），而内部迭代又进一步由次级迭代（ $j$ ）组成。
内部最小化与步长计算：
内部循环利用了一种适用于多面体集的梯度投影技术。
- Cauchy 步： 通过沿投影梯度路径寻找二次模型的第一个局部极小值来计算 Cauchy 步。这确保了全局收敛性。
- 子空间最小化： 为了加速收敛，算法在 Cauchy 点处的活跃约束所定义的子空间内执行一系列次级迭代。这些步骤使用**投影共轭梯度法（PCG）**进行计算。
- 信赖域： 信赖域策略控制步长质量，其区域由 $\ell_\infty$ 范数定义，以保持约束的多面体结构。
结构化 Hessian 近似：
其核心贡献之一是对 AL Hessian 的近似。该方法并非计算完整的二阶项（这在计算上非常昂贵），而是将 Hessian 近似为 $H_k = B^{GN}_k + B_k$ ，其中：
- $B^{GN}_k = J_k^\top J_k + \mu C_k^\top C_k$ 是高斯-牛顿（Gauss-Newton）近似。
- $B_k$ 是近似残差和约束二阶项的结构化修正项。
- 更新规则： 本文采用了从针对 NLS 结构定制的结构化割线方程导出的**对称秩-1（SR1）**更新。该方程通过残差和约束的雅可比矩阵将梯度的变化与变量的变化联系起来。
- 混合策略： 算法根据残差的大小（使用切换准则 $\zeta_k$ ）在纯高斯-牛顿模型和结构化 SQN 模型之间进行动态切换。当残差较小时使用 GN 模型；否则应用结构化修正以提高精度。

核心贡献

算法集成： 本文提出了一种求解器，它将增广拉格朗日框架与专门为目标函数和惩罚项的平方和结构设计的结构化拟牛顿更新相统一。
处理一般约束： 与许多专注于边界约束的现有 NLS 求解器不同，该方法直接处理线性等式、边界和非线性等式的混合问题，而无需将所有约束转换为边界约束。
结构化割线方程： 推导出的尊重 NLS 结构的割线方程（方程 2.26）允许在不计算完整二阶导数的情况下实现高效的 Hessian 近似。
全局收敛性： 作者提供了收敛至一阶临界点的全局收敛性严格证明，并确立了该方法在标准假设（二次可微、活跃约束线性无关）下具有收敛性。

数值结果
作者在 79 个问题实例上评估了 TRAULLS，涵盖了从 2 到 1000 个变量的问题，包括来自标准集合和特定基准测试的问题。

Hessian 近似对比： 对高斯-牛顿（GN）、普通 SR1、普通 BFGS 及其混合变体进行的实验表明，混合 SR1 方法在鲁棒性和效率之间达到了最佳平衡。虽然 GN 每次迭代的速度最快，但混合方法所需的内部迭代次数更少，并在处理较大残差的问题时表现出更优越的鲁棒性。
与最先进技术的比较： 将 TRAULLS 与 IPOPT（通用内点求解器）和 Percival（另一种基于 AL 的求解器）进行了比较。
- 性能： TRAULLS 实现了与 IPOPT 相当的计算时间，尽管由于 IPOPT 使用精确 Hessian，其函数调用次数通常更少。
- 鲁棒性： TRAULLS 显著优于 Percival，证明了即使在相同的算法框架（AL）内，利用特定的最小二乘结构也能获得更好的性能。
- 局限性： 结构化 Hessian 修正所需的密集存储限制了其在大规模变量下的扩展性，作者也承认了这一点。

意义与主张
本文声称提出了一种专门为受约束 NLS 问题设计的求解器，该求解器有效地平衡了对最小二乘结构的利用与处理一般约束的灵活性。作者强调，其方法在避免计算完整二阶导数的高昂成本的同时，通过结构化更新保持了鲁棒性。其意义在于提供了一个专门用于数据拟合和参数估计问题的工具，在这些问题中需要通过约束来保证物理一致性，并为像 IPOPT 这样的通用求解器以及像 Percival 这样的现有 AL 方法提供了一个具有竞争力的替代方案。作者谦逊地指出，虽然目前的实现显示出良好的性能，但未来的工作应通过有限内存变体和针对大残差集的自适应采样来解决扩展性问题。