GitHub

Method of moving asymptotes in pure Julia

Description

There are 2 versions of the method of moving asymptotes (MMA) that are available in NonconvexMMA.jl:

  1. The original MMA algorithm from the 1987 paper.
  2. The globally convergent MMA (GCMMA) algorithm from the 2002 paper.

The MMA algorithm only supports inequality constraints. However, the original algorithm was slightly generalized to handle infinite variable bounds.

Quick start

Given a model model and an initial solution x0, the following can be used to optimize the model using MMA.

using Nonconvex
Nonconvex.@load MMA

alg = MMA87() # or MMA02()
options = MMAOptions()
result = optimize(model, alg, x0, options = options, convcriteria = KKTCriteria())

Construct an instance

To construct an instance of the original MMA algorithm, use:

alg = MMA87()

or alternatively:

alg = MMA()

To construct an instance of the globally convergent MMA algorithm, use:

alg = MMA02()

or alternatively:

alg = GCMMA()

Options

To specify options for the MMA algorithm, you can construct an instance of MMAOptions and use keyword arguments.

NonconvexMMA.MMAOptions — Type
MMAOptions

A struct that stores all the options of the MMA algorithms. Th following are the fields of MMAOptions:

  • maxiter: the maximum number of inner iterations. For MMA87, there is 1 inner iteration per outer iteration.
  • outer_maxiter: the maximum number of outer iterations.
  • maxinner: the maximum number of inner iterations per outer iteration of MMA02. Not applicable for MMA87.
  • tol: a tolerance struct of type Tolerance.
  • s_init: defined in the original MMA02 paper.
  • s_incr: defined in the original MMA02 paper.
  • s_decr: defined in the original MMA02 paper.
  • store_trace: if true, a trace will be stored.
  • dual_options: the options passed to the dual optimizer from Optim.jl.
  • convcriteria: an instance of ConvergenceCriteria that specifies the convergence criteria of the MMA algorithm.
  • verbose: true/false, when true prints convergence statistics.
source

The tol option in MMA can be set to an instance of the Tolerance struct:

NonconvexCore.Tolerance — Type
Tolerance

A struct specifying the different tolerances used to assess the convergence of the algorithms. The following are the fields of Tolerance:

  • x: the tolerance for Δx in ConvergenceState. x_converged will be true if Δx is less than the x tolerance in Tolerance. This is used to assess convergence when the GenericCriteria is used as the convergence criteria.
  • fabs: the tolerance for Δf in ConvergenceState. f_converged will be true if Δf is less than the fabs tolerance in Tolerance. This is used to assess convergence when the GenericCriteria is used as the convergence criteria.
  • frel: the tolerance for relΔf in ConvergenceState. f_converged will be true if relΔf is less than the frel tolerance in Tolerance. This is used to assess convergence when the GenericCriteria is used as the convergence criteria.
  • kkt: the KKT tolerance. kkt_converged in ConvergenceState will be true if the kkt_residual is less than the KKT tolerance. And ipopt_converged in ConvergenceState will be true if ipopt_residual is less than the KKT tolerance. This is used to assess convergence when the KKTCriteria, the ScaledKKTCriteria or IpoptCriteria criteria is used as the convergence criteria.
  • infeas: the maximum infeasibility tolerance. infeas_converged in ConvergenceState will be true if the maximum infeasibility is less than the infeasibility tolerance. This is used to assess convergence regardless of the convergence criteria used.

For more on convergence criteria, see GenericCriteria, KKTCriteria, ScaledKKTCriteria and IpoptCriteria.

source
NonconvexCore.ConvergenceState — Type
ConvergenceState

A struct that summarizes the convergence state of a solution. The fields in this struct are:

  • Δx: the infinity norm of the change in the solution x.
  • Δf: the change in the objective value f.
  • relΔf: the ratio of change in the objective value f.
  • kkt_residual: the Karush-Kuhn-Tucker (KKT) residual of the solution. If ScaledKKTCriteria is used instead of KKTCriteria, the kkt_residual will be divided by a factor.
  • ipopt_residual: the modified KKT residual used in the IPOPT solver.
  • infeas: maximum infeasibility amount. This is 0 if the solution is feasible.
  • x_converged: true if Δx is less than the x tolerance in MMAOptions.
  • fabs_converged: true if Δf is less than the f tolerance in MMAOptions.
  • frel_converged: true if relΔf is less than the f tolerance in MMAOptions.
  • kkt_converged: true if the kkt_residual is less than the KKT tolerance in MMAOptions.
  • ipopt_converged: true if the ipopt_residual is less than the KKT tolerance in MMAOptions.
  • infeas_converged: true if infeas is less than the infeasibility tolerance in MMAOptions.
  • f_increased: true if the objective value of the current solution is higher than that of the previous solution.
  • converged: true if the solution satisfies the convergence criteria of choice. See ConvergenceCriteria for more on the different convergence criteria available.
source

Convergence criteria

There are 4 convergence criteria available for the MMA algorithm:

  • GenericCriteria
  • KKTCriteria
  • ScaledKKTCriteria
  • IpoptCriteria
NonconvexCore.GenericCriteria — Type
GenericCriteria

This is a generic convergence criteria that uses:

  1. The maximum change in the solution, Δx,
  2. The change in the objective value, Δf, and
  3. The change percentage in the objective value, Δf, and
  4. The maximum infeasibility infeas.

to assess convergence. More details are given in assess_convergence!.

source
NonconvexCore.ScaledKKTCriteria — Type
ScaledKKTCriteria

This convergence criteria uses another scaled version of the Karush-Kuhn-Tucker (KKT) residual and maximum infeasibility to assess convergence. In particular if the objective was scaled by a factor m, the KKT residual will be scaled down by a factor max(m, 1/m). This scaling was found to make the convergence criteria less sensitive to scale compared to using the traditional KKT residual. More details are given in assess_convergence!.

source
NonconvexCore.IpoptCriteria — Type
IpoptCriteria

This convergence criteria uses a scaled version of the Karush-Kuhn-Tucker (KKT) residual and maximum infeasibility to assess convergence. This scaled KKT residual is used in the IPOPT nonlinear programming solver as explained in this paper. More details are given in assess_convergence!.

source
NonconvexCore.assess_convergence! — Function
assess_convergence!(
    solution::Solution,
    model::AbstractModel,
    tol::Tolerance,
    criteria::ConvergenceCriteria,
    verbose::Bool,
    iter::Int
)

Evaluates the convergence state solution.convstate given the current solution, solution, the tolerance, tol, and the convergence criteria criteria. solution.convstate.converged is then updated.

If criteria is an instance of GenericCriteria, converged = (x_converged || f_converged) && infeas_converged. x_converged, f_converged and infeas_converged are explained in Tolerance. If criteria is an instance of KKTCriteria or ScaledKKTCriteria, converged = kkt_converged && infeas_converged. kkt_converged and infeas_converged are explained in Tolerance. If criteria is an instance of IpoptCriteria, converged = ipopt_converged && infeas_converged. ipopt_converged and infeas_converged are explained in Tolerance.

source

To specify the convergence criteria, use:

converiteria = GenericCriteria()

replacing GenericCriteria() by KKTCriteria(), ScaledKKTCriteria() or IpoptCriteria().