PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems

Euhanna Ghadimi, André Teixeira, Iman Shames, Mikael Johansson

arXiv:1306.2454v2math.OCmath.DS

TL;DR

The paper addresses how ADMM parameter choices affect convergence time, an issue that remains insufficiently quantified despite established convergence results. It derives optimal parameters for two quadratic problem classes, proves linear convergence with minimized convergence factors, and validates the tuned algorithms numerically against existing alternatives.

  • Problem

    ADMM convergence time is heavily affected by the algorithm parameter, and poor selection can result in arbitrarily large convergence times.

  • Method

    The paper derives and jointly optimizes ADMM step-size and over-relaxation parameters for ℓ2-regularized quadratic minimization and quadratic programming with linear inequality constraints.

  • Results

    For both problem classes, the authors establish global linear convergence and explicit parameters achieving the smallest possible convergence factors, then validate the results numerically.

  • Takeaways & Limitations

    The resulting parameter-selection rules provide tuned ADMM algorithms with superior performance in the reported numerical comparisons.

Abstract

from arXiv · show

The alternating direction method of multipliers (ADMM) has emerged as a powerful technique for large-scale structured optimization. Despite many recent results on the convergence properties of ADMM, a quantitative characterization of the impact of the algorithm parameters on the convergence times of the method is still lacking. In this paper we find the optimal algorithm parameters that minimize the convergence factor of the ADMM iterates in the context of l2-regularized minimization and constrained quadratic programming. Numerical examples show that our parameter selection rules significantly outperform existing alternatives in the literature.

I. INTRODUCTION

ADMM is a robust method for structured optimization, but its parameter still strongly affects convergence time. This paper derives optimal parameters and convergence factors for two quadratic problem classes and studies over-relaxation.

  • ADMM supports large-scale structured optimization and has applications including compressed sensing, estimation, image processing, machine learning, and resource allocation.
  • Unlike gradient methods, ADMM converges under mild conditions for every positive parameter value, although poor tuning can make convergence arbitrarily slow.
  • The paper derives parameters minimizing ADMM convergence factors for ℓ2-regularized quadratic minimization and quadratic programming with linear inequality constraints.
  • For both quadratic classes, the authors establish linear convergence and provide explicit optimal parameters and associated convergence factors.
  • The analysis also jointly selects the ADMM and over-relaxation parameters, with numerical examples evaluating the resulting rules in an extensive MPC case study.

II. BACKGROUND AND PRELIMINARIES

The section introduces fixed-point convergence results and the ADMM framework, including its residuals, relaxation, and parameter-tuning objective. It motivates selecting step-size and relaxation parameters to minimize convergence factors.

  • Fixed-point iterations: Proposition 1 characterizes when the iterations converge to a fixed point in Im(V), extending prior work to a higher-dimensional 1-eigenspace.
  • Fixed-point iterations: The convergence factor of the fixed-point iteration is the modulus of T's largest non-unit eigenvalue.
  • ADMM: ADMM uses a single parameter, ρ, and can converge for all parameter values under mild conditions, but poor tuning can make it slow.
  • ADMM: ADMM convergence is commonly described using primal and dual residuals, while relaxation incorporates past iterates into subsequent updates.
  • ADMM: The relaxation parameter α_k lies in (0, 2); α_k = 1 recovers standard ADMM, whereas α_k > 1 is over-relaxation often supported by empirical studies.
  • Paper objective: For quadratic problem classes, the paper derives explicit ρ and α values that minimize convergence factors.

III. OPTIMAL CONVERGENCE FACTOR FOR ℓ2-REGULARIZED QUADRATIC MINIMIZATION

This section analyzes ADMM for ℓ2-regularized quadratic minimization, characterizing convergence for positive step-sizes and deriving optimal and over-relaxed parameter choices.

  • Problem setting: ℓ2-regularized estimation problems motivate ADMM step-size analysis and comparison with direct alternatives.The section focuses on quadratic objectives with regularization parameter δ > 0.
  • Standard ADMM: ADMM iterates converge to the solution at a linear rate for every ρ > 0 and δ > 0.The result applies to both x^k and z^k, with z^{k+1} − z⋆ converging linearly.
  • Standard ADMM: For ρ = δ, the error-dynamics convergence factor is independent of Q.The convergence-factor guarantee holds for all initial values, although particular initializations may converge faster.
  • Over-relaxed ADMM: Over-relaxed ADMM can achieve a strictly smaller convergence factor than classical ADMM for a supported range of α.The iterates remain convergent for positive ρ and admissible α, and α ∈ (1, 2] is guaranteed to improve convergence.
  • Over-relaxed ADMM: With the optimal over-relaxed parameters, ADMM iterations converge in one iteration.The section also notes that the useful upper bound on α depends on eigenvalues of Q, which may be unknown.

IV. OPTIMAL CONVERGENCE FACTOR FOR QUADRATIC PROGRAMMING

This section develops a linear-convergence analysis for ADMM applied to constrained quadratic programs and derives optimal step-size results under rank conditions on the constraint matrix.

  • QP formulation: The QP is converted to standard ADMM form by introducing a slack vector z.The analysis rewrites the iterations using auxiliary variables and time-varying matrix operators.
  • Optimal parameters: The optimal step-size and smallest achievable convergence factor are characterized when A is full row-rank or invertible.The optimality result is restricted to these constraint-matrix conditions.
  • Convergence: For every positive step-size, the auxiliary residual converges linearly to zero, and the primal and dual residuals converge R-linearly to zero.These guarantees apply to all QPs of the stated form.
  • Rank dependence: When A has linearly dependent rows, the convergence factor can be arbitrarily close to 1.The result establishes that slow local convergence can occur for any ρ when the nullity of A is nonzero.
  • Heuristic extension: A heuristic using the smallest nonzero eigenvalue can reduce convergence time when A is nonzero and ξ is small.Numerical results show this heuristic performs well across different problem setups.

B. Over-relaxed ADMM iterations

The over-relaxed ADMM analysis derives convergence and jointly optimal parameter choices, showing smaller convergence factors than standard ADMM under rank conditions.

  • Iteration form: Over-relaxation replaces Ax^{k+1} in the z- and u-updates with αAx^{k+1} − (1 − α)z^k.The resulting iterations are analyzed through an equivalent fixed-point formulation.
  • Iteration form: Any fixed point of the relaxed iterations corresponds to a global optimum of the quadratic program.This connects the fixed-point analysis to optimization solutions.
  • Convergence: The relaxed fixed-point iteration converges linearly in the auxiliary residual, while primal and dual residuals converge R-linearly to zero.The convergence theorem applies under its stated parameter conditions.
  • Optimal parameters: For full row-rank or invertible A, the paper derives jointly optimal step-size, relaxation parameter, and convergence factor.The derivation is restricted to these constraint-matrix cases.
  • Speedup and scaling: For α ∈ (1, 2], over-relaxed iterates have a smaller convergence factor than the corresponding standard iterations.The convergence factors increase with the eigenvalue ratio, motivating constraint scaling to reduce that ratio without changing complexity.

D. Special cases of quadratic programming

Special active-set cases yield explicit limiting behavior, while numerical examples compare ADMM parameter rules with gradient, heavy-ball, and accelerated alternatives.

  • Special cases: When constraints are never active, relaxed and standard ADMM coincide and their convergence factors satisfy ζ = ζ_R → 0.The same limiting result is stated for the corresponding inactive-constraint extreme.
  • Special cases: The active-set extreme also admits parameters minimizing the relaxed ADMM convergence factor.The result is formulated under F^{k+1} = F^k = I.
  • Special cases: When constraints are active or inactive, the corresponding dual or primal residual remains zero for all k ≥ 2 updates.This observation concerns the residual associated with the inactive side of the constraint behavior.
  • Numerical evaluation: ADMM converges faster than gradient methods for some regularization parameters δ and slower for others.The experiments compare optimal and alternative step-size rules across regularized quadratic problems.
  • Numerical evaluation: ADMM outperforms gradient and heavy-ball methods for small δ but performs worse as δ becomes large.Small δ corresponds to an ill-conditioned problem, whereas large δ makes the overall problem well-conditioned.

B. Quadratic programming via ADMM

The paper evaluates ADMM parameter rules for quadratic programming, including accelerated variants and model predictive control problems. Its numerical studies compare convergence using residuals and iteration counts across algorithmic choices, showing advantages for the proposed tuning rules.

  • Accelerated ADMM: The study compares proposed ADMM step-size and over-relaxation rules with accelerated ADMM alternatives for quadratic programming.The comparisons include fast-ADMM and variants with and without over-relaxation.
  • Accelerated ADMM: The four quadratic-programming algorithms are evaluated by the sum of primal and dual residuals.The experiments use n decision variables and m inequality constraints.
  • Accelerated ADMM: The proposed tuning rules show significant improvement over fast-ADMM in residual convergence.The comparison includes fast-ADMM with both its proposed ρ = 1 and the paper’s ρ = ρ⋆.
  • Model Predictive Control: For 170 feasible MPC quadratic programs, the heuristic step-size ρ⋆ produces iteration counts close to the empirical minimum.The problems use n = 10 decision variables and m = 40 inequality constraints, with varying feasible initial states.
  • Model Predictive Control: Performance on the MPC problems improves further with the scaling matrix L = L⋆ and optimal over-relaxation α = 2.The iteration threshold is max{∥r^k∥, ∥s^k∥} ≤ 10^-5.
  • Model Predictive Control: With L = I and α = 2, ADMM uniformly outperforms fast-ADMM across the tested MPC initial states.The comparison is based on the number of iterations required to reach the stated residual threshold.

3) Local convergence factor:

The section evaluates ADMM parameter-selection rules through local convergence factors and numerical examples. Tuned parameters yield linear convergence guarantees and outperform existing methods in numerical tests.

  • Numerical evaluation: The numerical example evaluates ADMM with α = 1 and L = I using primal, dual, and auxiliary residuals.The step-size is selected heuristically as ρ⋆ = 1/28.6 using the smallest nonzero eigenvalue of AQ−1A⊤.
  • Numerical evaluation: The residual F k+1vk+1 − F kvk decreases monotonically, as predicted by Theorem 3.
  • Numerical evaluation: The convergence factor remains close to 1 over several time-steps in the slow-convergence example.The figure compares the residuals with the lower bound on the convergence factor ζ and reports iteration counts over ρ ∈ [0.1ρ⋆, 10ρ⋆].
  • Numerical evaluation: The heuristic step-size rule performs reasonably well in the right subplot of Fig. 5.
  • Main results: The paper establishes linear convergence and explicit optimal parameters for ℓ2-regularized minimization and quadratic programming with linear inequality constraints.It also derives jointly optimal step-size and over-relaxation parameters and validates the analytical results numerically.
  • Main results: The tuned ADMM algorithms demonstrate superior performance compared to existing methods from the literature, while the analysis is limited to two classes of quadratic problems.The authors identify extension to more general problems as future work.

A. Proof of Theorem 1

The proof characterizes ADMM convergence through the spectral radius of a linear error matrix. It identifies the convergence factor as the maximum eigenvalue-dependent factor and analyzes how over-relaxation changes it.

  • Classical ADMM: ADMM iterates converge when the spectral radius of the error matrix E is less than one.
  • Classical ADMM: For fixed ρ, the convergence factor is ζ(ρ) = max_k ||e_k+1||/||e_k|| and equals the spectral radius of E.
  • Classical ADMM: The optimal pair (ρ⋆, ζ⋆) minimizes the maximum eigenvalue-dependent convergence factor over the step-size parameter.
  • Classical ADMM: The proof treats separate regimes according to the relative values of ρ and δ, with endpoint cases determined by eigenvalues of Q.
  • Over-relaxed ADMM: The over-relaxed iterations can have a smaller convergence factor and smaller ε-solution time than classical ADMM.The proof compares the relaxed and classical factors through an affine transformation with the same maximizing eigenvalue index.
  • Over-relaxed ADMM: The jointly optimal parameters are (ρ⋆, α⋆) = (δ, 2), for which the algorithm converges in one iteration.At this pair, the relaxed error matrix is a matrix of zeros.

E. Proof of Theorem 3

The proof establishes linear convergence by analyzing the eigenvalues of a matrix M and separating full-rank from rank-deficient cases. It then derives the parameter-dependent convergence factor and its lower bound.

  • Convergence analysis: If ||2M − I|| < 1, the iterations converge to zero at a linear rate.
  • Convergence analysis: For ρ > 0, the eigenvalues of M lie in [0, 1), so ||2M − I|| ≤ 1 is guaranteed.
  • Rank conditions: When A is invertible or full row-rank, M is invertible and ||2M − I|| < 1, guaranteeing linear convergence.
  • Rank conditions: When A is tall and A⊤ is rank deficient, M has zero eigenvalues and ||2M − I|| = 1.The zero-eigenspace is then disregarded because it corresponds to stationary algorithm points.
  • Residual convergence: The R-linear convergence of the primal and dual residuals follows from the linear convergence of F k+1vk+1 − F kvk and established residual bounds.
  • Optimal parameter: The convergence factor is determined by the maximum over eigenvalue-dependent terms, whose minimizing ρ occurs at the intersection point in equation (29).
  • Lower bound: The convergence factor is defined as the maximum over k of the relevant residual ratio, yielding a lower-bound argument for slow convergence.

H. Proof of Lemma 1

The proof shows that fixed points of the over-relaxed iterations satisfy the optimization problem’s KKT conditions. It then establishes global linear convergence for the allowed relaxation range.

  • Fixed-point optimality: The fixed point (x⋆, z⋆, u⋆) satisfies the KKT conditions with µ⋆ = 1/ρu⋆.The argument derives feasibility, nonnegativity, stationarity, and the multiplier relation from the fixed-point updates.
  • Linear convergence: For ρ ∈ R++ and α ∈ (0, 2], the relaxed convergence factor satisfies ζR < 1.
  • Linear convergence: The relaxed iterations converge linearly to a fixed point, which is also a global optimum of the objective.
  • Residual convergence: The R-linear convergence of the primal and dual residuals follows from the linear convergence rate of the auxiliary iteration and residual bounds.

J. Proof of Theorem 7

The proof analyzes how relaxation affects the convergence factor and establishes that α > 1 improves it over the unrelaxed algorithm. It also reformulates the parameter optimization as a convex problem.

  • ζR(ρ, α, λi(AQ−1A⊤)) decreases monotonically with α.
  • For fixed A, Q, and ρ, the proof identifies α values producing a smaller convergence factor than (20).The relevant condition is ζR − ζ < 0.
  • α > 1 yields a smaller convergence factor for the relaxed algorithm than for algorithm (20).The comparison is expressed as ζR − ζ < 0.
  • The analysis uses eigenvalue properties of LAQ−1A⊤L and restricts attention to the subspace orthogonal to the relevant nullspace.It also assumes W = diag(w), with w > 0.
  • The optimization reduces to minimizing ¯λ subject to the constraints in (37), which form a convex problem.The proof shows equivalence between optimization problem (60) and (37).
Loading 1306.2454v2…