🔢 mathematics

An augmented Lagrangian algorithm for constrained nonlinear least-squares

This paper presents a globally convergent augmented Lagrangian algorithm for solving constrained nonlinear least-squares problems with mixed linear and nonlinear constraints, which employs gradient projection for subproblems and structured Hessian approximations.

Original authors: Pierre Borie, Fabian Bastin, Stéphane Dellacherie

Published 2026-07-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Pierre Borie, Fabian Bastin, Stéphane Dellacherie

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the perfect spot to set up a giant, wobbly tent. You want the tent to fit a specific shape (the "least-squares" part, meaning you want to minimize the gaps between your tent poles and the ideal shape), but you also have strict rules: the tent must stay within a fenced-in yard, and certain poles must touch specific trees or rocks (the "constraints").

This is exactly the problem Pierre Borie, Fabian Bastin, and Stéphane Dellacherie tackled in their paper. They built a new algorithm called TRAULLS (Trust Region Augmented nonLinear Least-squares Solver) to solve these tricky "constrained nonlinear least-squares" puzzles.

Here is how their method works, broken down into a story you can picture.

The Two-Part Strategy: The Penalty Box and the Fence

Most old-school methods try to solve the shape problem and the fence problem at the same time, which is like trying to juggle while walking a tightrope. The authors' approach is smarter. They split the job into two layers:

The Fence (Linear Constraints): The rules about the yard boundaries and the trees are "linear." Think of these as a rigid, unchangeable fence. The algorithm handles these directly, like a robot that knows exactly how to slide along a wall without crossing it.
The Penalty Box (Nonlinear Constraints): The tricky part is the "wobbly" shape of the tent. If the tent doesn't match the ideal shape, the algorithm doesn't just ignore it; it puts the tent in a "penalty box." Every time the tent is the wrong shape, the algorithm adds a huge "fine" to the score. This is called the Augmented Lagrangian.

The algorithm plays a game of "hot and cold." It tries to find the best spot inside the fence while minimizing the fines. If the tent is still too wobbly (the fine is too high), the algorithm increases the size of the fine for the next round, forcing the tent to snap into the right shape.

The "Step" Dance: Cauchy and the Subspace

Once the algorithm decides to take a step toward a better spot, it doesn't just guess. It uses a two-step dance:

The Cauchy Step: First, it takes a quick, cautious step downhill. It's like looking at the slope and taking a safe step in the direction that feels steepest. This guarantees the algorithm never gets stuck or goes backward.
The Subspace Minimization: After that safe step, it looks deeper. It explores a specific "tunnel" (a subspace) defined by the rules it's currently touching. It uses a special tool called Projected Conjugate Gradient to zoom in on the best spot within that tunnel.

The Secret Sauce: The "Structured" Hessian

Here is where the paper gets really clever. To know which way is "down," the algorithm needs a map of the terrain, called the Hessian.

The Old Way: Some methods use a rough map (Gauss-Newton) that assumes the ground is flat. This is fast but can be wrong if the ground is bumpy.
The "Full" Way: Other methods try to draw the entire bumpy ground perfectly. This is accurate but takes so much memory and time that it crashes computers with too many variables.

The authors' innovation is a Structured Quasi-Newton update. Imagine you have a sketch of the ground. Instead of redrawing the whole thing every time, you only update the parts that changed, using a special rule (the SR1 update) that respects the unique "sum-of-squares" nature of the problem.

They tested a "Hybrid" strategy: If the ground looks flat, they use the fast sketch. If it looks bumpy, they switch to the detailed update.
The Result: In their tests on 79 different problems (ranging from 2 to 1000 variables), this Hybrid SR1 approach was the most robust. It didn't just work; it handled the "bumpy" problems better than the standard sketch and was more reliable than other complex methods.

What They Found (and What They Didn't)

The authors ran their algorithm on a computer (a Mac mini with an M4 processor) and compared it to two other famous solvers: IPOPT and Percival.

The Speed: In terms of raw time, their new solver (TRAULLS) was a close second to IPOPT. IPOPT was slightly faster on the easiest problems, but as the problems got harder, the gap closed.
The Efficiency: IPOPT was the champion at saving "residual evaluations" (checking the tent shape). This is because IPOPT uses exact, heavy-duty math for every step. TRAULLS, however, was much better than Percival (another Augmented Lagrangian solver) and comparable to IPOPT on many metrics.
The Winner: The paper suggests that for this specific type of problem, using the Hybrid SR1 update is the best overall strategy. It strikes a perfect balance between speed and accuracy.

What They Ruled Out

The paper explicitly argues against using the "full" Hessian (the perfect map) for large problems. They show that calculating the full second-order terms takes too much time and storage, making it impractical for problems with many variables. They also showed that the simple "Gauss-Newton" sketch (ignoring the bumps) isn't accurate enough on its own for problems where the "tent" is far from the ideal shape.

How Sure Are They?

The authors are very confident in their results, but they are careful with their words.

They proved mathematically that their method will eventually find a solution (global convergence) under certain standard assumptions.
They measured the performance through numerical experiments on 79 specific problem instances.
They do not claim it is the fastest solver in the entire universe. They admit that for massive problems (where the number of variables is huge), their method hits a wall because the "structured" map still requires storing a dense matrix. They suggest that a "limited-memory" version would be needed for those giant cases, but they didn't build that yet.

In short, TRAULLS is a new, clever way to solve complex fitting problems with rules. It uses a "penalty box" to handle the hard rules and a "smart sketch" to navigate the terrain, proving in simulations that it's a strong, reliable contender for solving these mathematical puzzles.

Technical Summary: An Augmented Lagrangian Algorithm for Constrained Nonlinear Least-Squares

Problem Formulation
The paper addresses the constrained nonlinear least-squares (NLS) problem, defined as minimizing the sum of squared residuals $\frac{1}{2}\|r(x)\|^2$ subject to a mix of nonlinear equality constraints $c(x)=0$ and linear constraints $x \in \Omega$ . The set $\Omega$ encompasses linear equalities ($Ax=b$) and bound constraints ( $l \le x \le u$ ). The residuals $r(x)$ and constraints $c(x)$ are assumed to be twice continuously differentiable. The primary challenge in solving such problems lies in efficiently handling the NLS structure—specifically, the decomposition of the objective Hessian into a first-order term $J(x)^\top J(x)$ and a second-order term involving the Hessians of individual residuals—while simultaneously enforcing general constraints.

Methodology
The proposed algorithm, implemented in Julia as TRAULLS, integrates the Augmented Lagrangian (AL) framework with structured quasi-Newton (SQN) approximations and gradient projection techniques.

Augmented Lagrangian Framework:
The nonlinear constraints are incorporated into the objective function via an AL penalty term, transforming the original problem into a sequence of linearly constrained subproblems. At each outer iteration $K$ , the algorithm minimizes the AL function $\Phi(x, \lambda, \mu)$ over the polyhedral set $\Omega$ .
- Multiplier and Penalty Updates: If the nonlinear feasibility is sufficiently improved, Lagrange multipliers are updated via dual ascent ( $\lambda_{K+1} = \lambda_K + \mu_K c(x_K)$ ). If feasibility is not improved, the penalty parameter $\mu_K$ is increased to enforce constraints more strictly in the next iteration.
- Inner Minimization: The subproblem (minimizing $\Phi$ over $\Omega$ ) is solved using a trust-region method. The algorithm employs a nested structure where each outer iteration triggers a sequence of inner iterations ( $k$ ), which are further composed of minor iterations ( $j$ ).
Inner Minimization and Step Computation:
The inner loop utilizes a gradient projection technique adapted for polyhedral sets.
- Cauchy Step: A Cauchy step is computed by finding the first local minimizer of a quadratic model along the projected gradient path. This ensures global convergence.
- Subspace Minimization: To accelerate convergence, the algorithm performs a sequence of minor iterations within the subspace defined by the active constraints at the Cauchy point. These steps are computed using a Projected Conjugate Gradient (PCG) method.
- Trust Region: A trust-region strategy controls step quality, with the region defined by an $\ell_\infty$ norm to maintain the polyhedral structure of the constraints.
Structured Hessian Approximation:
A key contribution is the approximation of the AL Hessian. Instead of computing the full second-order terms (which is computationally expensive), the method approximates the Hessian as $H_k = B^{GN}_k + B_k$ , where:
- $B^{GN}_k = J_k^\top J_k + \mu C_k^\top C_k$ is the Gauss-Newton approximation.
- $B_k$ is a structured correction approximating the second-order terms of the residuals and constraints.
- Update Rule: The paper employs a Symmetric Rank-1 (SR1) update derived from a structured secant equation tailored to the NLS structure. This equation relates the change in gradients to the change in variables via the Jacobians of residuals and constraints.
- Hybrid Strategy: The algorithm dynamically switches between the pure Gauss-Newton model and the structured SQN model based on the magnitude of the residuals (using a switching criterion $\zeta_k$ ). If residuals are small, the GN model is used; otherwise, the structured correction is applied to improve accuracy.

Key Contributions

Algorithmic Integration: The paper presents a solver that unifies the Augmented Lagrangian framework with structured quasi-Newton updates specifically designed for the sum-of-squares structure of both the objective and the penalty term.
Handling General Constraints: Unlike many existing NLS solvers that focus on bound constraints, this method directly handles a mix of linear equalities, bounds, and nonlinear equalities without converting all constraints to bounds.
Structured Secant Equation: The derivation of a secant equation (Eq. 2.26) that respects the NLS structure allows for the efficient approximation of the Hessian without computing full second derivatives.
Global Convergence: The authors provide a rigorous proof of global convergence to a first-order critical point, establishing that the method converges under standard assumptions (twice differentiability, linear independence of active constraints).

Numerical Results
The authors evaluated TRAULLS on 79 problem instances ranging from 2 to 1000 variables, including problems from standard collections and specific benchmarks.

Hessian Approximation Comparison: Experiments comparing Gauss-Newton (GN), plain SR1, plain BFGS, and their hybrid variants showed that the Hybrid SR1 approach offered the best balance of robustness and efficiency. While GN was fastest per iteration, the hybrid approach required fewer inner iterations and demonstrated superior robustness on problems with larger residuals.
Comparison with State-of-the-Art: TRAULLS was compared against IPOPT (a general-purpose interior-point solver) and Percival (another AL-based solver).
- Performance: TRAULLS achieved computation times comparable to IPOPT, though IPOPT generally required fewer function evaluations due to its use of exact Hessians.
- Robustness: TRAULLS outperformed Percival significantly, demonstrating that exploiting the specific least-squares structure yields better performance even within the same algorithmic framework (AL).
- Limitations: The dense storage required for the structured Hessian correction limits scalability for very large numbers of variables, a point the authors acknowledge.

Significance and Claims
The paper claims to present a solver specifically designed for constrained NLS problems that effectively balances the exploitation of the least-squares structure with the flexibility to handle general constraints. The authors emphasize that their approach avoids the high cost of computing full second-order derivatives while maintaining robustness through structured updates. The significance lies in providing a specialized tool for data-fitting and parameter estimation problems where physical consistency (enforced by constraints) is required, offering a competitive alternative to general-purpose solvers like IPOPT and existing AL methods like Percival. The authors modestly note that while the current implementation shows promising performance, future work should address scalability through limited-memory variants and adaptive sampling for large residual sets.