# Exact Penalty Method

Manopt.exact_penalty_methodFunction
exact_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 minimize
• grad_f – the gradient of the cost function

Optional (if not called with the ConstrainedManifoldObjective cmo)

• g – (nothing) the inequality constraints
• h – (nothing) the equality constraints
• grad_g – (nothing) the gradient of the inequality constraints
• grad_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

Output

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

source

## State

Manopt.ExactPenaltyMethodStateType
ExactPenaltyMethodState{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.

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.

exact_penalty_method

source

## Helping Functions

Manopt.ExactPenaltyCostType
ExactPenaltyCost{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())
source
Manopt.ExactPenaltyGradType
ExactPenaltyGrad{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())
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

[LB19]