Augmented Lagrangian Method

Manopt.augmented_Lagrangian_methodFunction
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

source

Options

Manopt.AugmentedLagrangianMethodOptionsType
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/ϵ)^(1/num_outer_itertgn)) 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

source

Helping Functions

Manopt.AugmentedLagrangianCostType
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
source
Manopt.AugmentedLagrangianGradType
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_{ρ}(q, μ, λ)$, see also AugmentedLagrangianCost.

source

Literature