Struct optimization_engine::alm::AlmOptimizer

pub struct AlmOptimizer<'life, MappingAlm, MappingPm, ParametricGradientType, ParametricCostType, ConstraintsType, AlmSetC, LagrangeSetY>
where
    MappingAlm: Fn(&[f64], &mut [f64]) -> FunctionCallResult,
    MappingPm: Fn(&[f64], &mut [f64]) -> FunctionCallResult,
    ParametricGradientType: Fn(&[f64], &[f64], &mut [f64]) -> FunctionCallResult,
    ParametricCostType: Fn(&[f64], &[f64], &mut f64) -> FunctionCallResult,
    ConstraintsType: Constraint,
    AlmSetC: Constraint,
    LagrangeSetY: Constraint,
{ /* private fields */ }

Implements the ALM/PM method

AlmOptimizer solves the problem

$$ \begin{aligned} \mathrm{Minimize}\ f(u) \\ u \in U \\ F_1(u) \in C \\ F_2(u) = 0 \end{aligned}$$

where $u\in\mathbb{R}^{n_u}$, $f:\mathbb{R}^n\to\mathbb{R}$ is a $C^{1,1}$-smooth cost function, $U$ is a (not necessarily convex) closed subset of $\mathbb{R}^{n_u}$ on which we can easily compute projections (e.g., a rectangle, a ball, a second-order cone, a finite set, etc), $F_1:\mathbb{R}^{n_u}\to\mathbb{R}^{n_1}$ and $F_2:\mathbb{R}^{n_u} \to\mathbb{R}^{n_2}$ are mappings with smooth partial derivatives, and $C\subseteq\mathbb{R}^{n_1}$ is a convex closed set on which we can easily compute projections.

Numerical algorithm

Input:

• $\epsilon, \delta > 0$ (tolerance),
• $\nu_{\max}$ (maximum number of iterations),
• $c_0 > 0$ (initial penalty parameter),
• $\epsilon_0 > \epsilon$ (initial tolerance),
• $\rho > 1$ (update factor for the penalty parameter)
• $\beta \in (0, 1)$ (decrease factor for the inner tolerance)
• $\theta \in (0, 1)$ (sufficient decrease coefficient)
• $u^0 \in \mathbb{R}^n$ (initial guess)
• $y^0 \in \mathbb{R}^{n_1}$ (initial guess for the Lagrange multipliers)
• $Y \subseteq C^*$ (compact set)

The ALM/PM algorithm performs the following iterations:

• $\bar{\epsilon} = \epsilon_0$, $y\gets{}y^0$, $u\gets{}u^0$, $t,z\gets{}0$
• For $\nu=0,\ldots, \nu_{\max}$
  • $y \gets \Pi_Y(y)$
  • $u \gets \arg\min_{u\in U} \psi(u, \xi)$, where $\psi(u, \xi)$ is a given function: this problem is solved with tolerance $\bar\epsilon$ (see AlmFactory regarding how this is constructed)
  • $y^+ \gets y + c(F_1(u) - \Pi_C(F_1(u) + y/c))$
  • Define $z^+ \gets \Vert y^+ - y \Vert$ and $t^+ = \Vert F_2(u) \Vert$
  • If $z^+ \leq c\delta$, $t^+ \leq \delta$ and $\epsilon_\nu \leq \epsilon$, return $(u, y^+)$
  • else if not ($\nu=0$ or ($z^+ \leq \theta z$ and $t^+ \leq \theta t$)), $c \gets \rho{}c$
  • $\bar\epsilon \gets \max\{\epsilon, \beta\bar{\epsilon}\}$

Theoretical solution guarantees

The solver determines an $(\epsilon, \delta)$-approximate KKT point for the problem, that is, a pair $(u^\star, y^\star)$ which satisfies

$$ \begin{aligned} v {}\in{}& \partial_u L(u^\star, y^\star), \text{ with } \Vert v \Vert \leq \epsilon, \\ w {}\in{}& \partial_y [-L](u^\star, y^\star), \text{ with } \Vert w \Vert \leq \delta, \\ \Vert F_2(u^\star) \Vert {}\leq{}& \delta \end{aligned} $$

where $L:\mathbb{R}^{n_u}\times\mathbb{R}^{n_1}{}\to{}\mathbb{R}$ is the associated Lagrangian function which is given by

$$ L(u, y) {}={} f(u) + y^\top F_1(u) + \delta_U(u) + \delta_{C^{\ast}}(y), $$

for $u\in\mathbb{R}^{n_u}$, $y\in\mathbb{R}^{n_1}$, $C^{\ast}$ is the convex conjugate set of $C$ and $\delta_{U}$, $\delta_{C^{\ast}}$ are the indicator functions of $U$ and $C^{\ast}$ respectively.

Implementations

impl<'life, MappingAlm, MappingPm, ParametricGradientType, ParametricCostType, ConstraintsType, AlmSetC, LagrangeSetY> AlmOptimizer<'life, MappingAlm, MappingPm, ParametricGradientType, ParametricCostType, ConstraintsType, AlmSetC, LagrangeSetY>

where MappingAlm: Fn(&[f64], &mut [f64]) -> FunctionCallResult, MappingPm: Fn(&[f64], &mut [f64]) -> FunctionCallResult, ParametricGradientType: Fn(&[f64], &[f64], &mut [f64]) -> FunctionCallResult, ParametricCostType: Fn(&[f64], &[f64], &mut f64) -> FunctionCallResult, ConstraintsType: Constraint, AlmSetC: Constraint, LagrangeSetY: Constraint,

pub fn new( alm_cache: &'life mut AlmCache, alm_problem: AlmProblem<MappingAlm, MappingPm, ParametricGradientType, ParametricCostType, ConstraintsType, AlmSetC, LagrangeSetY> ) -> Self

Create new instance of AlmOptimizer

Arguments

• alm_cache: a reuseable instance of AlmCache, which is borrowed by AlmOptimizer
• alm_problem: the problem specification (data for $\psi(u, \xi)$, $\nabla_u \psi(u, \xi)$, $F_1(u)$ (if any), $F_2(u)$ (if any), and sets $C$, $U$ and $Y$)

Example

use optimization_engine::{alm::*, FunctionCallResult, core::{panoc::*, constraints}};

let tolerance = 1e-8;
let nx = 10;
let n1 = 5;
let n2 = 0;
let lbfgs_mem = 3;
let panoc_cache = PANOCCache::new(nx, tolerance, lbfgs_mem);
let mut alm_cache = AlmCache::new(panoc_cache, n1, n2);

let psi =  |_u: &[f64], _param: &[f64], _cost: &mut f64| -> FunctionCallResult { Ok(()) };
let d_psi =|_u: &[f64], _param: &[f64], _grad: &mut [f64]| -> FunctionCallResult { Ok(()) };
let f1 = |_u: &[f64], _result: &mut [f64]| -> FunctionCallResult { Ok(()) };
let set_c = constraints::Ball2::new(None, 1.50);

// Construct an instance of AlmProblem without any PM-type data
let bounds = constraints::Ball2::new(None, 10.0);
let set_y = constraints::Ball2::new(None, 1.0);
let alm_problem = AlmProblem::new(
    bounds,
    Some(set_c),
    Some(set_y),
    psi,
    d_psi,
    Some(f1),
    NO_MAPPING,
    n1,
    n2,
);

let mut alm_optimizer = AlmOptimizer::new(&mut alm_cache, alm_problem)
    .with_delta_tolerance(1e-4)
    .with_max_outer_iterations(10);

pub fn with_max_outer_iterations(self, max_outer_iterations: usize) -> Self

Setter method for the maximum number of outer iterations

Arguments

• max_outer_iterations: maximum number of outer iterations

Returns

Returns the current mutable and updated instance of the provided object

Panics

The method panics if the specified number of outer iterations is zero

pub fn with_max_inner_iterations(self, max_inner_iterations: usize) -> Self

Setter method for the maximum number of iterations for the inner problems which are solved with PANOC (see PANOCOptimizer).

Arguments

• max_inner_iterations: maximum number of inner iterations

Returns

Returns the current mutable and updated instance of the provided object

Panics

The method panics if the specified number of inner iterations is zero

pub fn with_max_duration(self, max_duration: Duration) -> Self

Setter methods for the maximum duration

If the maximum duration is not set, there is no upper bound on the time allowed for the ALM/PM optimizer to run

Arguments

• max_duration: maximum allowed execution duration

Returns

Returns the current mutable and updated instance of the provided object

pub fn with_delta_tolerance(self, delta_tolerance: f64) -> Self

Set the delta tolerance

Arguments

• delta_tolerance: tolerance $\delta > 0$

Returns

Returns the current mutable and updated instance of the provided object

Panics

The method panics if the specified tolerance is not positive

pub fn with_epsilon_tolerance(self, epsilon_tolerance: f64) -> Self

Set the epsilon tolerance

Arguments

• epsilon_tolerance: tolerance $\epsilon > 0$

Returns

Returns the current mutable and updated instance of the provided object

Panics

The method panics if the specified tolerance is not positive

pub fn with_penalty_update_factor(self, penalty_update_factor: f64) -> Self

Setter method for the penalty update factor.

At every iteration of the ALM/PM algorithm, the penalty parameter, $c_\nu$, may be updated by multiplying it by a constant factor. This can be specified with this setter method. The default value is 5.0.

Arguments

• penalty_update_factor: the penalty update factor

Returns

Returns the current mutable and updated instance of the provided object

Panics

The method panics if the update factor is not larger than 1.0 + f64::EPSILON

pub fn with_inner_tolerance_update_factor( self, inner_tolerance_update_factor: f64 ) -> Self

Setter method for the update factor for the epsilon tolerance

The $\epsilon$-tolerance, which is the tolerance passed on to the inner problem, starts at an initial value $\epsilon_0$, and is updated at every (outer) iteration of the algorithm by being multiplied with this update factor, which must be in the interval $(0, 1)$.

Arguments

• inner_tolerance_update_factor: the tolerance update factor

Returns

Returns the current mutable and updated instance of the provided object

Panics

The method panics if the specified tolerance update factor is not in the interval from f64::EPSILON to 1.0 - f64::EPSILON.

pub fn with_initial_inner_tolerance(self, initial_inner_tolerance: f64) -> Self

Setter method for the sufficient decrease coefficient

The first inner problem is solved at an accuracy $\epsilon_0$. Subsequent problems are solved at an accuracy $\epsilon_{\nu+1} = \max{\epsilon, \beta \epsilon_{\nu}}$, where $\beta$ is the tolerance update factor and $\epsilon$ is the target tolerance for the inner problem.

Arguments

• initial_inner_tolerance: the initial value of the inner tolerance, that is, the value $\espilon_0$

Returns

Returns the current mutable and updated instance of the provided object

Panics

The method panics if the specified initial inner tolerance is less than the target tolerance. If you need to decrease the target tolerance, please use with_inner_tolerance to do so before invoking with_initial_inner_tolerance.

pub fn with_sufficient_decrease_coefficient( self, sufficient_decrease_coefficient: f64 ) -> Self

Setter method for the sufficient decrease coefficient

At every (outer) iteration, the ALM/PM may decide not to update the penalty parameter if the progress has been sufficiently good with respect to the previous iteration.

Arguments

• sufficient_decrease_coefficient: the sufficient decrease coefficient

Returns

Returns the current mutable and updated instance of the provided object

Panics

The method panics if the specified sufficient decrease coefficient is not in the range (f64::EPSILON, 1.0 - f64::EPSILON)

pub fn with_initial_lagrange_multipliers(self, y_init: &[f64]) -> Self

Setter method for the initial vector of Lagrange multipliers, $y^0$

Arguments

• y_init: initial vector of Lagrange multipliers (type: &[f64]) of length equal to n1

Returns

Returns the current mutable and updated instance of the provided object

Panics

The method will panic if the length of y_init is not equal to n1

pub fn with_initial_penalty(self, c0: f64) -> Self

Setter method for the initial penalty parameter

Arguments

• c0: initial value of the penalty parameter

Returns

Returns the current mutable and updated instance of the provided object

Panics

The method panics if the specified initial penalty parameter is not larger than f64::EPSILON

pub fn solve( &mut self, u: &mut [f64] ) -> Result<AlmOptimizerStatus, SolverError>

Solve the specified ALM problem