Exact Penalty Method

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

perform the exact penalty method (EPM)^{[LiuBoumal2020]}. The aim of the EPM 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,…,p, \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 a weighted $L_1$-penalty term for the violation of the constraints is added to the objective

\[f(x) + ρ (\sum_{i=1}^m \max\left\{0, g_i(x)\right\} + \sum_{j=1}^p \vert h_j(x)\vert),\]

where $ρ>0$ is the penalty parameter. Since this is non-smooth, a SmoothingTechnique with parameter u is applied, see the ExactPenaltyCost.

In every step $k$ of the exact penalty method, the smoothed objective is then minimized over all $x ∈\mathcal{M}$. Then, the accuracy tolerance $ϵ$ and the smoothing parameter $u$ are updated by setting

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

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

\[u^{(k)} = \max \{u_{\min}, \theta_u u^{(k-1)} \},\]

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

Last, we update the penalty parameter $ρ$ according to

\[ρ^{(k)} = \begin{cases} ρ^{(k-1)}/θ_ρ, & \text{if } \displaystyle \max_{j \in \mathcal{E},i \in \mathcal{I}} \Bigl\{ \vert h_j(x^{(k)}) \vert, g_i(x^{(k)})\Bigr\} \geq u^{(k-1)} \Bigr) ,\\ ρ^{(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
• x – initial point
• smoothing – (LogarithmicSumOfExponentials) SmoothingTechnique to use
• ϵ – (1e–3) the accuracy tolerance
• ϵ_exponent – (1/100) exponent of the ϵ update factor;
• ϵ_min – (1e-6) the lower bound for the accuracy tolerance
• u – (1e–1) the smoothing parameter and threshold for violation of the constraints
• u_exponent – (1/100) exponent of the u update factor;
• u_min – (1e-6) the lower bound for the smoothing parameter and threshold for violation of the constraints
• ρ – (1.0) the penalty parameter
• min_stepsize – (1e-10) the minimal step size
• sub_cost – (ExactPenaltyCost(problem, ρ, u; smoothing=smoothing)) use this exact penality cost, expecially with the same numbers ρ,u as in the options for the sub problem
• sub_grad – (ExactPenaltyGrad(problem, ρ, u; smoothing=smoothing)) use this exact penality gradient, expecially with the same numbers ρ,u 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-10)) 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

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

perform the exact penalty method (EPM)^{[LiuBoumal2020]} in place of x.

For all options, especially x for the initial point and smoothing_technique for the smoothing technique, see exact_penalty_method.

ExactPenaltyMethodOptions{P,T} <: Options

Describes the exact penalty 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
• u – (1e–1) the smoothing parameter and threshold for violation of the constraints
• u_min – (1e-6) the lower bound for the smoothing parameter and threshold for violation of the constraints
• ρ – (1.0) the penalty parameter
• θ_ρ – (0.3) the scaling factor of the penalty parameter
• stopping_criterion – (StopWhenAny(StopAfterIteration(300),StopWhenAll(StopWhenSmallerOrEqual(ϵ, ϵ_min),StopWhenChangeLess(min_stepsize)))) a functor inheriting from StoppingCriterion indicating when to stop.

Constructor

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

construct an exact penalty 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

exact_penalty_method

ExactPenaltyCost{S, Pr, R}

Represent the cost of the exact penalty method based on a ConstrainedProblem P and a parameter $ρ$ given by

\[f(p) + ρ\Bigl( \sum_{i=0}^m \max\{0,g_i(p)\} + \sum_{j=0}^n \lvert h_j(p)\rvert \Bigr),\]

where we use an additional parameter $u$ and a smoothing technique, e.g. LogarithmicSumOfExponentials or LinearQuadraticHuber to obtain a smooth cost function. This struct is also a functor (M,p) -> v of the cost $v$.

Fields

• P, ρ, u as mentioned above.

Constructor

ExactPenaltyCost(P::ConstrainedProblem, ρ, u; smoothing=LinearQuadraticHuber())

ExactPenaltyGrad{S<:SmoothingTechnique, Pr<:ConstrainedProblem, R}

Represent the gradient of the ExactPenaltyCost based on a ConstrainedProblem P and a parameter $ρ$ and a smoothing technique, which uses an additional parameter $u$.

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.

Fields

• P, ρ, u as mentioned above.

Constructor

ExactPenaltyGradient(P::ConstrainedProblem, ρ, u; smoothing=LinearQuadraticHuber())

abstract type SmoothingTechnique

Specify a smoothing technique, e.g. for the ExactPenaltyCost and ExactPenaltyGrad.

LinearQuadraticHuber <: SmoothingTechnique

Specify a smoothing based on $\max\{0,x\} ≈ \mathcal P(x,u)$ for some $u$, where

\[\mathcal P(x, u) = \begin{cases} 0 & \text{ if } x \leq 0,\\ \frac{x^2}{2u} & \text{ if } 0 \leq x \leq u,\\ x-\frac{u}{2} & \text{ if } x \geq u. \end{cases}\]

LogarithmicSumOfExponentials <: SmoothingTechnique

Specify a smoothing based on $\max\{a,b\} ≈ u \log(\mathrm{e}^{\frac{a}{u}}+\mathrm{e}^{\frac{b}{u}})$ for some $u$.