AdmmParams

Parameters to the ADMM algorithm.

The fields represent:

• P: A sparse nxn positive semidefinite matrix
• q: an n-vector
• A: an mxn matrix
• b: an m-vector
• g: a vector of PiecewiseQuadratic functions

Settings

Settings for the ADMM algorithm.

The fields represent:

• ρ: Augmented Lagrangian parameter for constraints (must be positive)
• σ: Augmented Lagrangian parameter for variables (must be positive)
• α: Over-relaxation parameter (must be ∈ [0, 2], typically ∈ [1.0, 1.8])
• max_iters: Maximum allowed ADMM iterations (must be positive)
• ϵ: Threshold for determining convergence (must be nonnegative)
• term_cond_freq: Frequency in iterations with which to check for termination
• compute_stats: Whether to compute objectives and residuals on every iteration
• term_cond_type:
  • 1 uses the ConvergeTermCache
  • 2 uses the FirstVarsTermCache
• obj_tol: Minimum amount by which the objective needs to improve to be considered and improvement
• res_tol: Maximum allowable residual for an iterate to be considered an improvement
• non_improvement_iters: Maximum allowed non-improvement iterations before termination

Stats

Stats from the ADMM algorithm per iteration

The fields represent:

• obj: Objective values
• res: Residuals
• iters: Number of iterations completed

Vars

Store variables that need to be updated on each iteration of ADMM.

The fields represent:

• x: Previous value of x
• z: Previous value of z
• w: Previous value of w
• y: Previous value of y
• xt: Auxiliary variable
• zt: Auxiliary variable

Notes:

• We keep the previous values of x, w, z, y in order to check for convergence.
• The actual problem we are solving here is detailed in SeparableOptimization.factorize_kkt
• w and y are used when minimizing the augmented Lagrangian of the original problem (and consequently in ADMM's update rules)

get_num_vars(params::AdmmParams)

Return the number of variables in the problem that params was initialized with.

get_num_vars(settings::Settings)

Return the number of variables in the problem that settings was initialized with.

get_num_vars(vars::Vars)

Return the number of variables in the problem that vars was initialized with.

get_num_constrs(params::AdmmParams)

Return the number of constraints in the problem that params was initialized with.

get_num_constrs(settings::Settings)

Return the number of constraints in the problem that settings was initialized with.

get_num_constrs(vars::Vars)

Return the number of constraints in the problem that vars was initialized with.

assert_valid(params::AdmmParams, settings::Settings, vars::Vars)

Assert that the number of variables and constraints are consistent across a params-settings-vars combination

optimize(params::AdmmParams[, settings::Settings[, vars::Vars]])

Carries out the ADMM algorithm by calling admm_step until termination conditions are met.

factorize_kkt(params::AdmmParams, settings::Settings)

Factorize the KKT matrix representing the optimzality equations of the provided problem.

Extended help

Factorize the coefficient matrix of that KKT system representing the optimality equations that will be used (and reused) for the constrained least squares problem:

\[\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^T P x + q^T x + \sum_{i=1}^n g_i(x_i) \\ \text{subject to} & Ax = b. \end{array}\]

We can formulate this equivalently as

\[\begin{array}{ll} \text{minimize} & \displaystyle \frac12 \tilde x^T P \tilde x + q^T \tilde x + \mathcal{I}_\mathcal{A}(\tilde x, \tilde z) + g(x) + \mathcal{I}_{\mathcal B}(z) \\ \text{subject to} & \tilde x = x \\ & \tilde z = z. \end{array}\]

where $\mathcal I_{\mathcal A}$ is the indicator function over the affine constraints of the original form, i.e.,

\[\mathcal{I_{\mathcal A}}(x, z) = \begin{cases} 0 & Ax = z \\ \infty & {\rm otherwise}. \end{cases}\]

and $\mathcal I_{\mathcal B}$ is the indicator function over the singleton set of vectors equal to $b$, i.e.,

\[\mathcal{I_{\mathcal B}}(x) = \begin{cases} 0 & x = b \\ \infty & {\rm otherwise}. \end{cases}\]

We will denote the objective in this forumulation as $f(x, \tilde x, z, \tilde z)$.

The augmented Lagrangian for this problem is

\[L_{S,R} (x, \tilde x, z, \tilde z, w, y) = f(x, \tilde x, z, \tilde z) + \frac12 \| \tilde x - x + S^{-1} w \|_S^2 + \frac12 \| \tilde z - z + R^{-1} y \|_R^2,\]

where $f$ is the previously mentioned objective function. The diagonal, positive definite matrices $S\in \bf S{++}^l$ and $R\in \bf S_{++}^m$ are algorithm parameters. We define $\|\cdot \|_S$ is the $S$-norm, i.e., $\|x\|_S = \sqrt{x^T S x}$.

Solving for the optimality conditions, we can find optimal $\tilde x$ and $\tilde z$ by solving the linear system

\[\begin{bmatrix} P + S & A^T \\ A & -R^{-1} \end{bmatrix} \begin{bmatrix} \tilde x \\ \nu \end{bmatrix} = \begin{bmatrix} Sx - q - w \\ z - R^{-1} y \end{bmatrix}.\]

where $\tilde z$ can be recovered as $\tilde z = z + R^{-1}(\nu - y)$

In this function, we factor the coefficient matrix on the left hand side so that we repeatedly solve the linear system efficiently.

solve_kkt!(vars::Vars, kkt::KKT, params::AdmmParams, settings::Settings)

Solve the KKT system set up in the description of factorize_kkt for a particular right hand side.

admm_step!(vars::Vars, params::AdmmParams, kkt::KKT, pc::ProxCache, settings::Settings, iter::Int64; polish::Bool=false)

Carry out a single ADMM iteration.

Steps:

1. Solve the KKT system to carry out the xt and zt updates.
2. Use a mixture of the result of (1) and the previous x iterate to solve n univariate subproblems by minimizing the Lagrangian in the description of factorize_kkt w.r.t. x. (Requires evaluation of a proximal operator.)
3. Update w and y using the residuals associated with the constraints x = xt and z = zt.

Note:

• Note that for the entire run of the algorithm, the z update is just z = b, so we don't need

to do anything here.

compute_stats(vars::Vars, params::AdmmParams, stats::Stats, iter::Int64)

Update the objective, residual, and iteration fields of the Stats object.

ProxCache

Store the proximal operators corresponding to each element of a vector of PiecewiseQuadratics

Note

The proximal operator of $f$, $\rho$, denoted

\[\text{prox}_{f,\rho}(u) = \argmin_{x \in \text{dom}(f)} f(x) + \frac{\rho}{2} \|x - u \|_2^2\]

prox_step(pc::ProxCache, params::AdmmParams, settings::Settings, u::Vector{Float64})

Return the next x by using the proximal operators of the separable function pieces

get_term_cond_cache(params::AdmmParams, settings::Settings)

Return the TermCache corresponding to the term_cond_type specification in the ADMM Settings settings

check_term_conds!(tc::ConvergeTermCache, vars::Vars, params::AdmmParams, settings::Settings, iter::Int)

Check termination conditions

check_term_conds!(tc::FirstVarsTermCache, vars::Vars, params::AdmmParams, settings::Settings, iter::Int)

Check termination conditions

ConvergeTermCache

Cache state to helps determine whether or not to terminate

The fields represent:

• x_last: Previous x
• z_last: Previous z
• w_last: Previous w
• y_last: Previous y

FirstVarsTermCache

Cache state to helps determine whether or not to terminate

The fields represent:

• obj_best: The best encountered objective value
• res_best: The best encountered residual value
• x_best: The best encountered x iterate
• z_best: The best encountered z iterate
• w_best: The best encountered w (dual) iterate
• y_best: The best encountered y (dual) iterate
• n1: n - m
• lb: Lower bound
• ub: Upper bound
• A1: first n1 columns of A
• A2: remaining columns of A
• not_improved_count: The number of iterations without improvement seeing improvement
• not_improved_count_req: The max allowed iterations without improvement

get_obj_and_res_from_first_vars(tc::FirstVarsTermCache, vars::Vars, params::AdmmParams)

Get objective and residual from the FirstVarsTermCache tc