AugmentedLagrangianOptimizer

Overview¶

AugmentedLagrangianOptimizer combines penalty terms with Lagrange multipliers to improve convergence and conditioning on constrained nonlinear problems. It uses the BCL update policy inspired by Conn, Gould, and Toint by default, while retaining the earlier Aggressive policy as an explicit option.

Authors: Frank Dellaert, et al. (see THANKS for the full author list)

See LICENSE for the license information

try:
    import google.colab
    %pip install --quiet gtsam-develop
except ImportError:
    pass

Key Concepts¶

AugmentedLagrangianState stores equality and nonnegative inequality multipliers plus stationarity, generalized-feasibility, primal-feasibility, and complementarity diagnostics.
augmentedLagrangianFunction builds a fixed-multiplier subproblem with exact Powell--Hestenes--Rockafellar (PHR) terms for scalar inequalities.
BCL is the default. It accepts a multiplier update only when generalized feasibility meets its current target; otherwise it increases the common direct penalty.
Aggressive remains available as an explicit option and updates multipliers after every solved subproblem.

Mathematical Formulation¶

For whitened equalities $h(x)=0$ , whitened scalar inequalities $g_i(x)\leq0$ , direct penalties $\rho_e,\rho_i>0$ , and nonnegative inequality multipliers, the fixed-parameter objective is:

\mathcal{L}_A(x,\lambda)=\frac{1}{2}\|f(x)\|^2 +\lambda_e^T h(x)+\frac{\rho_e}{2}\|h(x)\|^2 +\sum_i\frac{\max(0,\lambda_i+\rho_i g_i(x))^2-\lambda_i^2}{2\rho_i}.

(1)

The projected inequality residual $q_i=\max(g_i,-\lambda_i/\rho_i)$ gives $\lambda_i^+=\max(0,\lambda_i+\rho_i g_i)=\lambda_i+\rho_i q_i$ . BCL uses the full augmented-Lagrangian gradient infinity norm for inner stationarity and $\max(\|h\|_\infty,\|q\|_\infty)$ for generalized feasibility.

The BCL policy follows the update schedule of Conn, Gould, and Toint Algorithm 1 as closely as possible, but it is not entirely faithful: unconstrained LM replaces their projected bound-constrained inner solver, and direct PHR inequalities replace their bounded slack formulation. Their convergence proof therefore does not apply here.

Key User API¶

AugmentedLagrangianOptimizer(problem, initialValues, params)
optimize()
progress()
augmentedLagrangianFunction(state, epsilon) (advanced inspection; epsilon is retained for source compatibility)
AugmentedLagrangianParams: updatePolicy, Aggressive controls, and flat BCL schedule parameters

Concise C++ Example¶

#include <gtsam/constrained/AugmentedLagrangianOptimizer.h>

using namespace gtsam;

auto params = std::make_shared<AugmentedLagrangianParams>();
// BCL is the default update policy.
params->verbose = true;

AugmentedLagrangianOptimizer optimizer(problem, init_values, params);
Values results = optimizer.optimize();

References¶

Examples¶

Algorithm reference¶

A. R. Conn, N. I. M. Gould, and Ph. L. Toint, A Globally Convergent Augmented Lagrangian Algorithm for Optimization with General Constraints and Simple Bounds, SIAM Journal on Numerical Analysis 28(2), 1991.