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 this
algorithm –
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 to 0.5.
params.gamma (double) – Controls the rate at which the upper curvature is updated (see \(\gamma\) from the original paper). Defaults to 0.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 to 1.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 to 0.3.
params.theta (double) – Determines the accuracy of the inner R-ACG call (see \(\theta\) from [2]). Defaults to 4.
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 to 1.25.
params.lambda (double) – The initial stepsize (see \(\lambda\) from [2]). Defaults to 1 / 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 to 10.
params.tau (double) – A parameter constant that determines the accuracy of the inner ACG call (see \(\tau\) from [2, 3]). Defaults to tau_mult * (lambda M + 1) where lambda is the initial stepsize and tau_mult is the constant in params.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/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 to params.M1.
params.lambda (double) – The initial stepsize \(\lambda\). Defaults to 1 / params.M1.
params.steptype (character vector) – Either 'adaptive' or 'constant'. If it is adaptive, 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) – If true, then the sequence of outer iterates forms a monotonically nonincreasing sequence with respect to the objective function. If false, then no such property is guaranteed. Defaults to true.

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 to params.M1.
params.lambda (double) – The initial stepsize \(\lambda\). Defaults to 1 / params.M1.
params.steptype (character vector) – Either 'adaptive' or 'constant'. If it is adaptive, 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.