AugmentedLagrangianSolver<T>

Models & Types · AiDotNet.Solvers.Constrained

Solves general nonlinear constrained problems by the method of multipliers, minimizing a sequence of unconstrained augmented Lagrangians.

For Beginners

Two mechanisms push the answer into the allowed region. The penalty is a fine for breaking a rule, and it gets steeper if you keep breaking it. The multiplier is a price on that rule, learned from how much you have been breaking it. Fines alone would have to become infinite to work; prices converge to a finite right answer, and then the fine can stay small.

How It Works

Implements the augmented Lagrangian method of M. R. Hestenes, “Multiplier and Gradient Methods”, Journal of Optimization Theory and Applications 4(5), 1969, pp. 303-320, and M. J. D. Powell, “A Method for Nonlinear Constraints in Minimization Problems” (1969), with the inequality treatment of R. T. Rockafellar, “A Dual Approach to Solving Nonlinear Programming Problems by Unconstrained Optimization”, Mathematical Programming 5, 1973, pp. 354-373. The outer loop follows Framework 17.3 and Algorithm 17.4 of J. Nocedal and S. J. Wright, Numerical Optimization (2nd ed., Springer 2006).

Why not just a penalty. The obvious way to handle a constraint is to add a large multiple of its violation to the objective. It works, but only in the limit: the penalty must go to infinity for the answer to become exactly feasible, and long before it gets there the subproblem is too ill-conditioned to solve. The augmented Lagrangian adds an explicit multiplier term alongside the penalty and updates the multiplier after each subproblem. Those multipliers converge to the true Lagrange multipliers, at which point the constraints are satisfied exactly with the penalty still at a moderate value — the ill-conditioning never arrives.

The inequality form. Inequalities enter through (1/2ρ)·Σ max(0, μ_j + ρ·g_j(x))² − μ_j², which is Rockafellar’s. The max is what makes it correct: a constraint with room to spare contributes nothing and does not distort the objective, while one that is binding or violated contributes exactly as an equality would. The expression is continuously differentiable despite the max, because the two branches meet where the argument is zero and so does the derivative — which is why an ordinary smooth unconstrained solver can minimize it.

Example

// minimize x² + y² subject to x + y = 1; the answer is (0.5, 0.5).
var problem = new ConstrainedProblem<double>(
    objective: p => (p[0] * p[0] + p[1] * p[1],
                     new Vector<double>(new[] { 2 * p[0], 2 * p[1] })),
    equalityConstraints: p =>
    {
        var jacobian = new Matrix<double>(1, 2);
        jacobian[0, 0] = 1.0;
        jacobian[0, 1] = 1.0;
        return (new Vector<double>(new[] { p[0] + p[1] - 1.0 }), jacobian);
    });
            
var solution = new AugmentedLagrangianSolver<double>()
    .Solve(problem, new Vector<double>(new[] { 0.0, 0.0 }));

Constructors

Constructor Summary
AugmentedLagrangianSolver() Creates an augmented Lagrangian solver with the default options and inner optimizer.
AugmentedLagrangianSolver(AugmentedLagrangianSolverOptions options) Creates an augmented Lagrangian solver with the given options and the default inner optimizer.
AugmentedLagrangianSolver(AugmentedLagrangianSolverOptions options, IFunctionOptimizer<T> innerOptimizer) Creates an augmented Lagrangian solver.

Methods

Method Summary
ConstrainedSolution<T> Solve(ConstrainedProblem<T> problem, Vector<T> initialPoint) Solves a constrained problem.