ADMM#

class cuqi.solver.ADMM(A, b, penalty_terms, x0, penalty_parameter=10, maxit=100, inner_max_it=10, adaptive=True)#

Alternating Direction Method of Multipliers for solving regularized linear least squares problems of the form: Minimize ||Ax-b||^2 + sum_i f_i(L_i x), where the sum ranges from 1 to an arbitrary n. See definition of the parameter penalty_terms below for more details about f_i and L_i

Reference: [1] Boyd et al. “Distributed optimization and statistical learning via the alternating direction method of multipliers.”Foundations and Trends® in Machine learning, 2011.

Parameters:

  • A (ndarray or callable) – Represents a matrix or a function that performs matrix-vector multiplications. When A is a callable, it accepts arguments (x, flag) where: - flag=1 indicates multiplication of A with vector x, that is A @ x. - flag=2 indicates multiplication of the transpose of A with vector x, that is A.T @ x.

  • b (ndarray.)

  • penalty_terms (List of tuples (callable proximal operator of f_i, linear operator L_i)) – Each callable proximal operator of f_i accepts two arguments (x, p) and should return the minimizer of p/2||x-z||^2 + f(x) over z for some f.

  • x0 (ndarray. Initial guess.)

  • penalty_parameter (Trade-off between linear least squares and regularization term in the solver iterates. Denoted as "rho" in [1].)

  • maxit (The maximum number of iterations.)

  • adaptive (Whether to adaptively update the penalty_parameter each iteration such that the primal and dual residual norms are of the same order of magnitude. Based on [1], Subsection 3.4.1)

Example

from cuqi.solver import ADMM, ProximalL1, ProjectNonnegative
import numpy as np

rng = np.random.default_rng()

m, n, k = 10, 5, 4
A = rng.standard_normal((m, n))
b = rng.standard_normal(m)
L = rng.standard_normal((k, n))

x0 = np.zeros(n)
admm = ADMM(A, b, x0, penalty_terms = [(ProximalL1, L), (lambda z, _ : ProjectNonnegative(z), np.eye(n))], tradeoff = 10)
sol, _ = admm.solve()
__init__(A, b, penalty_terms, x0, penalty_parameter=10, maxit=100, inner_max_it=10, adaptive=True)#

Methods

__init__(A, b, penalty_terms, x0[, ...])

solve()

Solves the regularized linear least squares problem using ADMM in scaled form.