Solvers#

Solvers are algorithms that find solutions to optimization problems. rlaopt provides several solvers, each suited for different types of problems.

Available Solvers#

Alternating Direction Method of Multipliers (ADMM)#

The ADMM solver is designed for problems of the form

\[\operatorname{minimize}_x f(x) + \sum_{i = 1}^k g_i(A_i x - b_i),\]

where \(f\) is smooth (differentiable) and \(g\) is proxable.

Our implementation internally decomposes the problem into the form

\[\begin{split}\operatorname{minimize}_{x, z_1, \ldots, z_k} f(x) + \sum_{i = 1}^k g_i(z_i) \\ \text{subject to } A_i x - z_i - b_i = 0, \quad i = 1, \ldots, k\end{split}\]

before applying the ADMM algorithm.

Our implementation is based on the implementation from Diamandis et al. [DFZ+23].

from rlaopt.solvers import ADMM, ADMMConfig

config = ADMMConfig(
    rho=1.0,               # Augmented Lagrangian parameter
)
solver = ADMM(objective, config)
result = solver.solve()

Features:

Supports multiple proxable terms for the same variable
Allows for over-relaxation and primal-dual residual balancing [BPC+11]

Proximal Gradient (ProxGrad)#

The ProxGrad solver is designed for problems of the form:

\[\operatorname{minimize}_x f(x) + g(x)\]

where \(f\) is smooth (differentiable) and \(g\) is proxable (has an efficient proximal operator).

from rlaopt.solvers import ProxGrad, ProxGradConfig

config = ProxGradConfig(
    eta=0.01,              # Step size
    use_linesearch=True,   # Use line search
    use_acceleration=False # Use Nesterov acceleration
)
solver = ProxGrad(objective, config)
result = solver.solve()

Features:

Supports backtracking line search
Optional Nesterov acceleration

Preconditioned Conjugate Gradient (PCG)#

The PCG solver is a preconditioned conjugate gradient method for solving linear systems.

from rlaopt.solvers import PCG, PCGConfig

config = PCGConfig(max_iters=1000, tol=1e-6)
solver = PCG(linear_system, config)
result = solver.solve()

Choosing a Solver#

Use ADMM when:

Your objective can be written in the form \(f(x) + \sum_{i = 1}^k g_i(A_i x - b_i)\) where \(f\) is smooth and \(g_i\) are proxable
If there are only smooth components, use ProxGrad instead

Use ProxGrad when:

Your objective can be written in the form \(f(x) + g(x)\) where \(f\) is smooth and \(g\) is proxable
Examples include Lasso regression, Elastic Net, and other regularized regression problems

Use PCG when:

You need to solve large positive-definite linear systems

Solver Configuration#

Each solver has a configuration class that controls its behavior:

ADMMConfig: Augmented Lagrangian parameter, over-relaxation, residual balancing, etc.
ProxGradConfig: Step size, line search, acceleration
PCGConfig: Iteration limits, tolerance, preconditioner

Stopping Criteria#

All solvers support stopping criteria:

ADMMStoppingCriteria: Maximum iterations, primal and dual residual tolerance
ProxGradStoppingCriteria: Maximum iterations, convergence tolerance
PCGStoppingCriteria: Maximum iterations, convergence tolerance

The solver will stop when either criterion is met.

[BPC+11]

Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine Learning, 3(1):1–122, 2011.

[DFZ+23]

Theo Diamandis, Zachary Frangella, Shipu Zhao, Bartolomeo Stellato, and Madeleine Udell. GeNIOS: an (almost) second-order operator-splitting solver for large-scale convex optimization. In revision at Math Programming Computation, 2023. URL: https://arxiv.org/abs/2310.08333, arXiv:2310.08333.

Solvers

Contents