Exact Penalty Method
Manopt.exact_penalty_method
— Functionexact_penalty_method(M, F, gradF, p=rand(M); kwargs...)
exact_penalty_method(M, cmo::ConstrainedManifoldObjective, p=rand(M); kwargs...)
perform the exact penalty method (EPM) Liu, Boumal, 2019, Appl. Math. Optim The aim of the EPM is to find a solution of the constrained optimisation task
\[\begin{aligned} \min_{p ∈\mathcal{M}} &f(p)\\ \text{subject to } &g_i(p)\leq 0 \quad \text{ for } i= 1, …, m,\\ \quad &h_j(p)=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}^n$ 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}^n \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 minimizegrad_f
– the gradient of the cost function
Optional (if not called with the ConstrainedManifoldObjective
cmo
)
g
– (nothing
) the inequality constraintsh
– (nothing
) the equality constraintsgrad_g
– (nothing
) the gradient of the inequality constraintsgrad_h
– (nothing
) the gradient of the equality constraints
Note that one of the pairs (g
, grad_g
) or (h
, grad_h
) has to be proviede. Otherwise the problem is not constrained and you can also call e.g. quasi_Newton
Optional
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 toleranceu
– (1e–1
) the smoothing parameter and threshold for violation of the constraintsu_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 parametermin_stepsize
– (1e-10
) the minimal step sizesub_cost
– (ExactPenaltyCost
(problem, ρ, u; smoothing=smoothing)
) use this exact penality cost, expecially with the same numbersρ,u
as in the options for the sub problemsub_grad
– (ExactPenaltyGrad
(problem, ρ, u; smoothing=smoothing)
) use this exact penality gradient, expecially with the same numbersρ,u
as in the options for the sub problemsub_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
– (DefaultManoptProblem
(M,
ManifoldGradientObjective
(sub_cost, sub_grad; evaluation=evaluation)
– ` problem for the subsolversub_state
– (QuasiNewtonState
) usingQuasiNewtonLimitedMemoryDirectionUpdate
withInverseBFGS
andsub_stopping_criterion
as a stopping criterion. See alsosub_kwargs
.stopping_criterion
– (StopAfterIteration
(300)
| (StopWhenSmallerOrEqual
(ϵ, ϵ_min)
&StopWhenChangeLess
(1e-10)
) a functor inheriting fromStoppingCriterion
indicating when to stop.
Output
the obtained (approximate) minimizer $p^*$, see get_solver_return
for details
Manopt.exact_penalty_method!
— Functionexact_penalty_method!(M, f, grad_f, p; kwargs...)
exact_penalty_method!(M, cmo::ConstrainedManifoldObjective, p; kwargs...)
perform the exact penalty method (EPM) performed in place of p
.
For all options, see exact_penalty_method
.
State
Manopt.ExactPenaltyMethodState
— TypeExactPenaltyMethodState{P,T} <: AbstractManoptSolverState
Describes the exact penalty method, with
Fields
a default value is given in brackets if a parameter can be left out in initialization.
p
– a set point on a manifold as starting pointsub_problem
– anAbstractManoptProblem
problem for the subsolversub_state
– anAbstractManoptSolverState
for the subsolverϵ
– (1e–3
) the accuracy toleranceϵ_min
– (1e-6
) the lower bound for the accuracy toleranceu
– (1e–1
) the smoothing parameter and threshold for violation of the constraintsu_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 parameterstopping_criterion
– (StopWhenAny
(
StopAfterIteration
(300),
StopWhenAll
(
StopWhenSmallerOrEqual
(ϵ, ϵ_min),
StopWhenChangeLess
(min_stepsize)))
) a functor inheriting fromStoppingCriterion
indicating when to stop.
Constructor
ExactPenaltyMethodState(M::AbstractManifold, p, sub_problem, sub_state; kwargs...)
construct an exact penalty options with the fields and defaults as above, where the manifold M
is used for defaults in the keyword arguments.
See also
Helping Functions
Manopt.ExactPenaltyCost
— TypeExactPenaltyCost{S, Pr, R}
Represent the cost of the exact penalty method based on a ConstrainedManifoldObjective
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(co::ConstrainedManifoldObjective, ρ, u; smoothing=LinearQuadraticHuber())
Manopt.ExactPenaltyGrad
— TypeExactPenaltyGrad{S, CO, R}
Represent the gradient of the ExactPenaltyCost
based on a ConstrainedManifoldObjective
co
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(co::ConstrainedManifoldObjective, ρ, u; smoothing=LinearQuadraticHuber())
Manopt.SmoothingTechnique
— Typeabstract type SmoothingTechnique
Specify a smoothing technique, e.g. for the ExactPenaltyCost
and ExactPenaltyGrad
.
Manopt.LinearQuadraticHuber
— TypeLinearQuadraticHuber <: 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}\]
Manopt.LogarithmicSumOfExponentials
— TypeLogarithmicSumOfExponentials <: SmoothingTechnique
Specify a smoothing based on $\max\{a,b\} ≈ u \log(\mathrm{e}^{\frac{a}{u}}+\mathrm{e}^{\frac{b}{u}})$ for some $u$.
Literature
- [LB19]