Exact Penalty Method

Manopt.exact_penalty_methodFunction
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
  • u_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 ϵ 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

source

Options

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

source

Helping Functions

Manopt.ExactPenaltyCostType
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) -> vof the costv`.

Fields

  • P, ρ, u as mentioned above.

Constructor

ExactPenaltyCost(P::ConstrainedProblem, ρ, u; smoothing=LinearQuadraticHuber())
source
Manopt.ExactPenaltyGradType
ExactPenaltyGrad{S<:SmoothingTechnique, Pr<:ConstrainedProblem, R}

Represent the gradient of the ExactPenaltyCost based on a ConstrainedProblem P and a parameter $ρ$ and a smoothing parameyterwhere we use 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())
source
Manopt.LinearQuadraticHuberType
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}\]

source
Manopt.LogarithmicSumOfExponentialsType
LogarithmicSumOfExponentials <: SmoothingTechnique

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

source

Literature