6. Solvers¶
This section documents the solvers that available for solving unconstrained composite optimization problems. For simplicity, we only list the parameter inputs that affect the behavior of the method for a fixed optimization problem. All other inputs should be passed from the model object that is calling the solver.
Note
All solvers have a parameter i_logging
that, when set to true
, will log the function value, (inner) iteration number, and time at each (outer) iteration. These values are then added to the history
struct that is output by each solver.
6.1. Auxiliary Solvers¶
These solvers are used as (possible) subroutines for the other solvers of this section.
- src.solvers.ACG(oracle, params)¶
An accelerated composite gradient (ACG) algorithm for use inside of the accelerated inexact proximal point (AIPP) method.
See also
src/solvers/AIPP.m
Note
Its iterates are generated according the paper:
Monteiro, R. D., Ortiz, C., & Svaiter, B. F. (2016). An adaptive accelerated first-order method for convex optimization. Computational Optimization and Applications, 64(1), 31-73.
- Parameters
oracle (
Oracle
) – The oracle underlying the optimization problem.params (
struct
) – Contains instructions on how to call the algorithm. This should ideally be customized from by caller of thisalgorithm –
user. (
rather than the
) –
- Returns
A pair of structs containing model and history related outputs of the solved problem associated with the oracle and input parameters.
6.2. NCO Solvers¶
These solvers are used for nonconvex composite optimization problems.
- src.solvers.AC_ACG(oracle, params)¶
The average curvature accelerated composite gradient (AC-ACG) method.
Note
Based on the paper:
Liang, J., & Monteiro, R. D. (2019). An average curvature accelerated composite gradient method for nonconvex smooth composite optimization problems. arXiv preprint arXiv:1909.04248.
- Parameters
oracle (
Oracle
) – The oracle underlying the optimization problem.params.alpha (
double
) – Controls the rate at which the upper curvature is updated (see \(\alpha\) from the original paper). Defaults to0.5
.params.gamma (
double
) – Controls the rate at which the upper curvature is updated (see \(\gamma\) from the original paper). Defaults to0.01
.
- Returns
A pair of structs containing model and history related outputs of the solved problem associated with the oracle and input parameters.
- src.solvers.ADAP_FISTA(oracle, params)¶
The adaptive nonconvex fast iterative soft theresholding (ADAP-NC-FISTA) method.
See also
src/solvers/NC_FISTA.m
Note
Based on the paper (see the ADAP-NC-FISTA method):
Liang, J., Monteiro, R. D., & Sim, C. K. (2019). A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems. arXiv preprint arXiv:1905.07010.
- Parameters
oracle (
Oracle
) – The oracle underlying the optimization problem.params.theta (
double
) – Controls how the stepsize is updated (see \(\theta\) from the original paper). Defaults to1.25
.
- Returns
A pair of structs containing model and history related outputs of the solved problem associated with the oracle and input parameters.
- src.solvers.AG(oracle, params)¶
The accelerated gradient (AG) method.
See also
src/solvers/UPFAG.m
Note
A variant of Algorithm 2 (with the upper curvature \(M\) replacing the Lipschitz constant \(L_f\)) from the paper:
Ghadimi, S., & Lan, G. (2016). Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1-2), 59-99.
- Parameters
oracle (
Oracle
) – The oracle underlying the optimization problem.params (
struct
) – Contains instructions on how to call the algorithm.
- Returns
A pair of structs containing model and history related outputs of the solved problem associated with the oracle and input parameters.
- src.solvers.AIPP(oracle, params)¶
Variants of the accelerated inexact proximal point (AIPP) method
See also
src/solvers/ACG.m
Note
Based on the papers:
[1] Kong, W., Melo, J. G., & Monteiro, R. D. (2019). Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. SIAM Journal on Optimization, 29(4), 2566-2593.
[2] Kong, W., Melo, J. G., & Monteiro, R. D. (2020). An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems. Computational Optimization and Applications, 76(2), 305-346.
[3] Kong, W., & Monteiro, R. D. (2019). An accelerated inexact proximal point method for solving nonconvex-concave min-max problems. arXiv preprint arXiv:1905.13433.
In particular, \(\tau\) is updated using the rule in [3].
- Parameters
oracle (
Oracle
) – The oracle underlying the optimization problem.params.aipp_type (
character vector
) – Specifies which AIPP variant to use. More specifically, ‘aipp’ is the AIPP method from [1], while ‘aipp_c’, ‘aipp_v1’, and ‘aipp_v2’ are the R-AIPPc, R-AIPPv1, and R-AIPPv2 methods from [2]. Defaults to'aipp_v2'
.params.sigma (
double
) – Determines the accuracy of the inner ACG call (see \(\sigma\) from [1]). Defaults to0.3
.params.theta (
double
) – Determines the accuracy of the inner R-ACG call (see \(\theta\) from [2]). Defaults to4
.params.acg_steptype (
character vector
) – Is either “variable” or “constant”. If it is “variable”, then the ACG call employs a line search subroutine to look for the appropriate upper curvature, with a starting estimate of \(L_0 = \lambda (M / 100) + 1\). If “constant”, then no subroutine is employed and the upper curvature remains fixed at \(L_0 = \lambda M + 1\). Defaults to'variable'
.params.acg_ls_multiplier (
double
) – Determines how quickly the line search subroutine of the ACG call (multiplicatively) increases its estimate. Defaults to1.25
.params.lambda (
double
) – The initial stepsize (see \(\lambda\) from [2]). Defaults to1 / m
.params.mu_fn (
function handle
) – Determines the strong convexity parameter \(\mu\) given to the ACG call as a function of lambda, the stepsize. Defaults to@(lambda) 1
.params.tau_mult (
double
) – An auxiliary parameter constant used to determine the first value of \(\tau\). Defaults to10
.params.tau (
double
) – A parameter constant that determines the accuracy of the inner ACG call (see \(\tau\) from [2, 3]). Defaults totau_mult * (lambda M + 1)
wherelambda
is the initial stepsize andtau_mult
is the constant inparams.tau_mult
.
- Returns
A pair of structs containing model and history related outputs of the solved problem associated with the oracle and input parameters.
- src.solvers.ECG(oracle, params)¶
The well-known exact composite gradient (ECG) method with constant stepsize.
Note
For reference, see the paper:
Nesterov, Y. (2013). Gradient methods for minimizing composite functions. Mathematical Programming, 140(1), 125-161.
- Parameters
oracle (
Oracle
) – The oracle underlying the optimization problem.params (
struct
) – Contains instructions on how to call the algorithm.
- Returns
A pair of structs containing model and history related outputs of the solved problem associated with the oracle and input parameters.
- src.solvers.NC_FISTA(oracle, params)¶
The nonconvex fast iterative soft theresholding (ADAP-NC-FISTA) method.
See Also:
src/solvers/ADAP_FISTA.m
Note
Based on the paper (see the NC-FISTA method):
Liang, J., Monteiro, R. D., & Sim, C. K. (2019). A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems. arXiv preprint arXiv:1905.07010.
- Parameters
oracle (
Oracle
) – The oracle underlying the optimization problem.params.lambda (
double
) – The first stepsize used by the method (see \(\lambda\) from the original paper). Defaults to0.99 / L
.params.xi (
double
) – Determines \(A_0\) from the original paper (see \(\xi\) from the original paper). Defaults to1.05 * m
.
- Returns
A pair of structs containing model and history related outputs of the solved problem associated with the oracle and input parameters.
- src.solvers.UPFAG(oracle, params)¶
The unified problem-parameter free accelerated gradient (UPFAG) method.
See also
src/solvers/AG.m
Note
A version of the file provided by Ghadimi, Lan, and Zhang, which was heavily edited to conform with the CompModel framework. Based on the paper (see the UPFAG-fullBB method):
Ghadimi, S., Lan, G., & Zhang, H. (2019). Generalized uniformly optimal methods for nonlinear programming. Journal of Scientific Computing, 79(3), 1854-1881.
- Parameters
oracle (
Oracle
) – The oracle underlying the optimization problem.params (
struct
) – Contains instructions on how to call the algorithm.
- Returns
A pair of structs containing model and history related outputs of the solved problem associated with the oracle and input parameters.
6.3. Spectral NCO Solvers¶
These solvers are used for spectral nonconvex composite optimization problems.
- src.solvers.DA_ICG(spectral_oracle, params)¶
The doubly-accelerated inexact composite gradient (DA-ICG) method.
See also
src/solvers/IA_ICG.m
Note
Based on the paper:
[1] Kong, W., & Monteiro, R. D. (2020). Accelerated Inexact Composite Gradient Methods for Nonconvex Spectral Optimization Problems. arXiv preprint arXiv:2007.11772.
- Parameters
spectral_oracle (
SpectralOracle
) – The spectral oracle underlying the optimization problem.params.xi (
double
) – Controls the amount of curvature that is initially redistributed from \(f_1\) to \(f_2\). Defaults toparams.M1
.params.lambda (
double
) – The initial stepsize \(\lambda\). Defaults to1 / params.M1
.params.steptype (
character vector
) – Either'adaptive'
or'constant'
. If it isadaptive
, then the stepsize is chosen adaptively. If it is constant, then the stepsize is constant. Defaults to'adaptive'
.params.sigma (
double
) – Controls the accuracy of the inner subroutine. Defaults to(1 / 2 - max([params.lambda * (params.M1 - params.xi), 0]))
.params.acg_steptype (
character vector
) – Is either “variable” or “constant”. If it is “variable”, then the ACG call employs a line search subroutine to look for the appropriate upper curvature, with a starting estimate of \(L_0 = \lambda (M / 100) + 1\). If “constant”, then no subroutine is employed and the upper curvature remains fixed at \(L_0 = \lambda M + 1\). Defaults to'variable'
.params.Omega_projection (
function handle
) – A one argument function, which when evaluated at \(x\), computes \({\rm Proj}_\Omega(x)\). For details see the definition of \(\Omega\) in [1]. Defaults to@(X) X
.params.is_monotone (
bool
) – Iftrue
, then the sequence of outer iterates forms a monotonically nonincreasing sequence with respect to the objective function. Iffalse
, then no such property is guaranteed. Defaults totrue
.
- Returns
A pair of structs containing model and history related outputs of the solved problem associated with the oracle and input parameters.
- src.solvers.IA_ICG(spectral_oracle, params)¶
The accelerated inexact composite gradient (AICG) method. The inner-accelerated inexact composite gradient (IA-ICG) method.
See also
src/solvers/DA_ICG.m
Note
Based on the paper:
Kong, W., & Monteiro, R. D. (2020). Accelerated Inexact Composite Gradient Methods for Nonconvex Spectral Optimization Problems. arXiv preprint arXiv:2007.11772.
- Parameters
spectral_oracle (
SpectralOracle
) – The spectral oracle underlying the optimization problem.params.xi (
double
) – Controls the amount of curvature that is initially redistributed from \(f_1\) to \(f_2\). Defaults toparams.M1
.params.lambda (
double
) – The initial stepsize \(\lambda\). Defaults to1 / params.M1
.params.steptype (
character vector
) – Either'adaptive'
or'constant'
. If it isadaptive
, then the stepsize is chosen adaptively. If it is constant, then the stepsize is constant. Defaults to'adaptive'
.params.sigma (
double
) – Controls the accuracy of the inner subroutine. Defaults to(9 / 10 - max([params.lambda * (params.M1 - params.xi), 0]))
.params.acg_steptype (
character vector
) – Is either “variable” or “constant”. If it is “variable”, then the ACG call employs a line search subroutine to look for the appropriate upper curvature, with a starting estimate of \(L_0 = \lambda (M / 100) + 1\). If “constant”, then no subroutine is employed and the upper curvature remains fixed at \(L_0 = \lambda M + 1\). Defaults to'variable'
.
- Returns
A pair of structs containing model and history related outputs of the solved problem associated with the oracle and input parameters.