Augmented Lagrangian Method

augmented_Lagrangian_method(M, F, gradF, x=random_point(M); kwargs...)

perform the augmented Lagrangian method (ALM)^{[LiuBoumal2020]}. The aim of the ALM is to find the solution of the ConstrainedProblem

\[\begin{aligned} \min_{x ∈\mathcal{M}} &f(x)\\ \text{subject to } &g_i(x)\leq 0 \quad \text{ for } i= 1, …, m,\\ \quad &h_j(x)=0 \quad \text{ for } j=1,…,n, \end{aligned}\]

where M is a Riemannian manifold, and $f$, $\{g_i\}_{i=1}^m$ and $\{h_j\}_{j=1}^p$ are twice continuously differentiable functions from M to ℝ. For that, in every step $k$ of the algorithm, the AugmentedLagrangianCost $\mathcal{L}_{ρ^{(k-1)}}(x, μ^{(k-1)}, λ^{(k-1)})$ is minimized on $\mathcal{M}$, where $μ^{(k-1)} \in \mathbb R^n$ and $λ^{(k-1)} \in \mathbb R^m$ are the current iterates of the Lagrange multipliers and $ρ^{(k-1)}$ is the current penalty parameter.

The Lagrange multipliers are then updated by

\[λ_j^{(k)} =\operatorname{clip}_{[λ_{\min},λ_{\max}]} (λ_j^{(k-1)} + ρ^{(k-1)} h_j(x^{(k)})) \text{for all} j=1,…,p,\]

and

\[μ_i^{(k)} =\operatorname{clip}_{[0,μ_{\max}]} (μ_i^{(k-1)} + ρ^{(k-1)} g_i(x^{(k)})) \text{ for all } i=1,…,m,\]

where $λ_{\min} \leq λ_{\max}$ and $μ_{\max}$ are the multiplier boundaries.

Next, we update the accuracy tolerance $ϵ$ by setting

\[ϵ^{(k)}=\max\{ϵ_{\min}, θ_ϵ ϵ^{(k-1)}\},\]

where $ϵ_{\min}$ is the lowest value $ϵ$ is allowed to become and $θ_ϵ ∈ (0,1)$ is constant scaling factor.

Last, we update the penalty parameter $ρ$. For this, we define

\[σ^{(k)}=\max_{j=1,…,p, i=1,…,m} \{\|h_j(x^{(k)})\|, \|\max_{i=1,…,m}\{g_i(x^{(k)}), -\frac{μ_i^{(k-1)}}{ρ^{(k-1)}} \}\| \}.\]

Then, we update ρ according to

\[ρ^{(k)} = \begin{cases} ρ^{(k-1)}/θ_ρ, & \text{if } σ^{(k)}\leq θ_ρ σ^{(k-1)} ,\\ ρ^{(k-1)}, & \text{else,} \end{cases}\]

where $θ_ρ \in (0,1)$ is a constant scaling factor.

Input

• M – a manifold $\mathcal M$
• F – a cost function $F:\mathcal M→ℝ$ to minimize
• gradF – the gradient of the cost function

Optional

• G – the inequality constraints
• H – the equality constraints
• gradG – the gradient of the inequality constraints
• gradH – the gradient of the equality constraints
• ϵ – (1e-3) the accuracy tolerance
• ϵ_min – (1e-6) the lower bound for the accuracy tolerance
• ϵ_exponent – (1/100) exponent of the ϵ update factor; also 1/number of iterations until maximal accuracy is needed to end algorithm naturally
• θ_ϵ – ((ϵ_min / ϵ)^(ϵ_exponent)) the scaling factor of the exactness
• μ – (ones(size(G(M,x),1))) the Lagrange multiplier with respect to the inequality constraints
• μ_max – (20.0) an upper bound for the Lagrange multiplier belonging to the inequality constraints
• λ – (ones(size(H(M,x),1))) the Lagrange multiplier with respect to the equality constraints
• λ_max – (20.0) an upper bound for the Lagrange multiplier belonging to the equality constraints
• λ_min – (- λ_max) a lower bound for the Lagrange multiplier belonging to the equality constraints
• τ – (0.8) factor for the improvement of the evaluation of the penalty parameter
• ρ – (1.0) the penalty parameter
• θ_ρ – (0.3) the scaling factor of the penalty parameter
• sub_cost – (AugmentedLagrangianCost(problem, ρ, μ, λ)) use augmented Lagranian, expecially with the same numbers ρ,μ as in the options for the sub problem
• sub_grad – (AugmentedLagrangianGrad(problem, ρ, μ, λ)) use augmented Lagranian gradient, expecially with the same numbers ρ,μ as in the options for the sub problem
• sub_kwargs – keyword arguments to decorate the sub options, e.g. with debug.
• sub_stopping_criterion – (StopAfterIteration(200) |StopWhenGradientNormLess(ϵ) |StopWhenStepsizeLess(1e-8)) specify a stopping criterion for the subsolver.
• sub_problem – (GradientProblem(M, subcost, subgrad; evaluation=evaluation)) problem for the subsolver
• sub_options – (QuasiNewtonOptions) using QuasiNewtonLimitedMemoryDirectionUpdate with InverseBFGS and sub_stopping_criterion as a stopping criterion. See also sub_kwargs.
• stopping_criterion – (StopAfterIteration(300) | (StopWhenSmallerOrEqual(ϵ, ϵ_min) & StopWhenChangeLess(1e-10))) a functor inheriting from StoppingCriterion indicating when to stop.

Output

the obtained (approximate) minimizer $x^*$, see get_solver_return for details

augmented_Lagrangian_method!(M, F, gradF x=random_point(M); kwargs...)

perform the augmented Lagrangian method (ALM) in-place of x.

For all options, see augmented_Lagrangian_method.

AugmentedLagrangianMethodOptions{P,T} <: Options

Describes the augmented Lagrangian method, with

Fields

a default value is given in brackets if a parameter can be left out in initialization.

• x – a set point on a manifold as starting point
• sub_problem – problem for the subsolver
• sub_options – options of the subproblem
• ϵ – (1e–3) the accuracy tolerance
• ϵ_min – (1e-6) the lower bound for the accuracy tolerance
• λ – (ones(len(get_equality_constraints(p,x))) the Lagrange multiplier with respect to the equality constraints
• λ_max – (20.0) an upper bound for the Lagrange multiplier belonging to the equality constraints
• λ_min – (- λ_max) a lower bound for the Lagrange multiplier belonging to the equality constraints
• μ – (ones(len(get_inequality_constraints(p,x))) the Lagrange multiplier with respect to the inequality constraints
• μ_max – (20.0) an upper bound for the Lagrange multiplier belonging to the inequality constraints
• ρ – (1.0) the penalty parameter
• τ – (0.8) factor for the improvement of the evaluation of the penalty parameter
• θ_ρ – (0.3) the scaling factor of the penalty parameter
• θ_ϵ – ((ϵ_min/ϵ)^(ϵ_exponent)) the scaling factor of the accuracy tolerance
• penalty – evaluation of the current penalty term, initialized to Inf.
• stopping_criterion – ((StopAfterIteration(300) | (StopWhenSmallerOrEqual(ϵ, ϵ_min) &StopWhenChangeLess(1e-10))) a functor inheriting from StoppingCriterion indicating when to stop.

Constructor

AugmentedLagrangianMethodOptions(M::AbstractManifold, P::ConstrainedProblem, x; kwargs...)

construct an augmented Lagrangian method options with the fields and defaults as above, where the manifold M and the ConstrainedProblem P are used for defaults in the keyword arguments.

See also

augmented_Lagrangian_method

AugmentedLagrangianCost{Pr,R,T}

Stores the parameters $ρ ∈ \mathbb R$, $μ ∈ \mathbb R^m$, $λ ∈ \mathbb R^n$ of the augmented Lagrangian associated to the ConstrainedProblem P.

This struct is also a functor (M,p) -> v that can be used as a cost function within a solver, based on the internal ConstrainedProblem we can compute

\[\mathcal L_\rho(p, μ, λ) = f(x) + \frac{ρ}{2} \biggl( \sum_{j=1}^n \Bigl( h_j(p) + \frac{λ_j}{ρ} \Bigr)^2 + \sum_{i=1}^m \max\Bigl\{ 0, \frac{μ_i}{ρ} + g_i(p) \Bigr\}^2 \Bigr)\]

Fields

• P::Pr, ρ::R, μ::T, λ::T as mentioned above

AugmentedLagrangianGrad{Pr,R,T}

Stores the parameters $ρ ∈ \mathbb R$, $μ ∈ \mathbb R^m$, $λ ∈ \mathbb R^n$ of the augmented Lagrangian associated to the ConstrainedProblem P.

This struct is also a functor in both formats

• (M, p) -> X to compute the gradient in allocating fashion.
• (M, X, p) to compute the gradient in in-place fashion.

based on the internal ConstrainedProblem and computes the gradient $\operatorname{grad} \mathcal L_{ρ}(p, μ, λ)$, see also AugmentedLagrangianCost.