Source-linked AI summary
An Efficient Inexact Symmetric Gauss-Seidel Based Majorized ADMM for High-Dimensional Convex Composite Conic Programming
Liang Chen, Defeng Sun, Kim-Chuan Toh
TL;DR
High-dimensional convex composite conic problems are costly when subproblems require exact or repeated inner solves. The paper proposes sGS-imsPADMM, combining inexact majorized semi-proximal ADMM with inexact symmetric Gauss-Seidel updates. Preliminary experiments report 2 to 3 times faster performance than a directly extended multi-block ADMM, while the method has convergence and non-ergodic complexity guarantees.
Problem
Exact or highly accurate ALM and BCD subproblem solves can be expensive in high-dimensional settings, motivating an efficient inexact method for moderate accuracy.
Method
sGS-imsPADMM combines an inexact 2-block majorized semi-proximal ADMM with inexact symmetric Gauss-Seidel iterations, using one inexact sGS cycle per subproblem.
Results
2 to 3 times faster than directly extended multi-block ADMM with step-length 1.618 on the average or for the vast majority of tested high-dimensional SDP problems.
Takeaways & Limitations
The method provides a simple implementable first-order approach with global convergence and non-ergodic iteration-complexity guarantees for moderate-accuracy high-dimensional conic optimization.
Takeaways & Limitations
The reported numerical experiments are preliminary, and extending the approach to high-accuracy solvers is left for future research.
Abstract
from arXiv · showhide
In this paper, we propose an inexact multi-block ADMM-type first-order method for solving a class of high-dimensional convex composite conic optimization problems to moderate accuracy. The design of this method combines an inexact 2-block majorized semi-proximal ADMM and the recent advances in the inexact symmetric Gauss-Seidel (sGS) technique for solving a multi-block convex composite quadratic programming whose objective contains a nonsmooth term involving only the first block-variable. One distinctive feature of our proposed method (the sGS-imsPADMM) is that it only needs one cycle of an inexact sGS method, instead of an unknown number of cycles, to solve each of the subproblems involved.With some simple and implementable error tolerance criteria, the cost for solving the subproblems can be greatly reduced, and many steps in the forward sweep of each sGS cycle can often be skipped, which further contributes to the efficiency of the proposed method. Global convergence as well as the iteration complexity in the non-ergodic sense is established.Preliminary numerical experiments on some high-dimensional linear and convex quadratic SDP problems with a large number of linear equality and inequality constraints are also provided. The results show that for the vast majority of the tested problems, the sGS-imsPADMM is 2 to 3 times faster than the directly extended multi-block ADMM with the aggressive step-length of 1.618, which is currently the benchmark among first-order methods for solving multi-block linear and quadratic SDP problems though its convergence is not guaranteed.
1 Introduction
The paper targets high-dimensional convex composite conic problems where exact augmented-Lagrangian subproblem solves are expensive. It proposes sGS-imsPADMM, an inexact multi-block ADMM-type method designed for moderate accuracy with convergence guarantees and favorable preliminary performance.
- Problem setting: High dimension means AA* and/or Q are too large for explicit storage or Cholesky factorization.
- Motivation: ALM subproblems can be expensive because coupled quadratic terms interact with two nonsmooth functions, while BCD may require many cycles.
- Motivation: Inexact subproblem solves are essential because large linear systems can be solved approximately with iterative methods such as conjugate gradients.
- Method: sGS-imsPADMM combines majorized semi-proximal ADMM with inexact symmetric Gauss-Seidel iterations and uses one inexact sGS cycle per subproblem.
- Method: Majorization allows the smooth functions f and g to be non-quadratic, extending the method beyond convex quadratic conic programming.
- Results: The method has global convergence and non-ergodic iteration-complexity guarantees, while preliminary tests report 2 to 3 times faster performance than directly extended multi-block ADMM.
2 Preliminaries
This section establishes the notation, optimality framework, and regularity assumptions used to analyze the convex composite model. It introduces KKT conditions under Slater’s constraint qualification and the operators supporting majorization and proximal analysis.
- Notation: The preliminaries define Euclidean-space adjoints, induced norms, positive semidefinite operators, operator square roots, weighted inner products, distances, and relative interiors.
- Convex analysis: The proximal mapping is defined for a closed proper convex function relative to a positive definite operator.
- Constraint qualification: Slater’s constraint qualification requires a feasible point with x and y in the relative interiors of the effective domains of p and q.
- Optimality conditions: Under Slater’s condition, primal and dual optimality is characterized by the KKT system involving subdifferentials, gradients, and the linear constraint.
3 An Inexact Majorized sPADMM
The imsPADMM majorizes the smooth terms and uses semi-proximal operators to construct an inexact two-block ADMM framework. Its subproblems are solved approximately under summable error tolerances.
- Majorized formulation: The method majorizes the smooth functions and defines a majorized augmented Lagrangian for the two-block problem.The construction permits nonquadratic smooth functions with Lipschitz-continuous gradients.
- Majorized formulation: Positive-definite operators M and N combine gradient majorants, proximal terms, and constraint operators to regularize the x- and y-subproblems.They are required to satisfy M ≻ 0 and N ≻ 0.
- Inexact updates: The imsPADMM computes x and y alternately, allowing each block subproblem to be solved inexactly.The algorithm uses a step-length τ and a summable sequence of nonnegative error tolerances.
- Inexact updates: The resulting approximate updates satisfy metric error bounds relative to corresponding exact subproblem solutions.Proposition 3.1 bounds the x-update error by ε_k and gives a related bound for the y-update.
4 An imsPADMM with Symmetric Gauss-Seidel Iteration
The sGS-imsPADMM embeds one inexact symmetric Gauss-Seidel cycle into the majorized semi-proximal ADMM. Blockwise operators and admissible error tests make the multi-block updates explicitly implementable while permitting skipped forward-sweep solves.
- sGS decomposition: The sGS decomposition solves a multi-block quadratic subproblem through backward and forward Gauss-Seidel sweeps.Its block operator is decomposed into diagonal, upper-triangular, and adjoint components.
- sGS decomposition: The decomposition requires the nonsmooth function to depend only on the first block variable.It does not apply when another block also contains a nonsmooth convex term.
- Inexact implementation: Forward-sweep subproblems may be skipped when backward-sweep estimates satisfy an admissible error condition.One stated criterion accepts an estimate when ∥δ_i∥ ≤ c∥eδ_i∥, with c suggested as 10.
- Algorithm construction: Block diagonal regularizers are selected so the block subproblems are positive definite and the nonsmooth first-block problems are tractable.The resulting majorized operators incorporate sGS corrections and diagonal proximal terms.
- Algorithm construction: The sGS-imsPADMM applies one inexact sGS cycle to each majorized ADMM subproblem.The algorithm performs backward and forward sweeps for both the x- and y-block groups.
- Inexact implementation: Under the stated definiteness assumptions, the generated sequences are well-defined and the sGS-imsPADMM can be viewed as an explicitly implementable imsPADMM.Choosing the constructed semi-proximal terms links the two algorithmic formulations.
5 Convergence Analysis
The convergence analysis establishes global convergence of the inexact majorized ADMM under nonempty KKT solutions, positive-definite metric conditions, and admissible step-length and error assumptions. The iterates converge to a primal-dual solution.
- Convergence framework: The analysis uses summable error tolerances and quasi-Fejér-type estimates to control the inexact iterates.These estimates support boundedness and convergence of auxiliary sequences.
- Assumptions: The convergence theorem applies to the inexact method with a step-length restricted to the stated admissible interval.The proof uses the associated positive constants determined by τ.
- Global convergence: If the KKT solution set is nonempty and the metric operators satisfy the stated positive-definiteness conditions, the sequence generated by imsPADMM converges to a KKT point.Theorem 5.1 requires Σ_f + S + σAA∗ ≻ 0 and Σ_g + T + σBB∗ ≻ 0.
- Global convergence: The convergence proof establishes boundedness of the iterates and vanishing residual and update differences.The analysis derives boundedness before identifying cluster points satisfying the KKT conditions.
- Global convergence: Every cluster point satisfies the primal and dual stationarity conditions together with feasibility.The limiting point solves the primal problem, while its multiplier solves the dual problem.
6 Non-Ergodic Iteration Complexity
The paper measures non-ergodic progress through a KKT-residual mapping that combines stationarity and feasibility. Under the convergence assumptions, an iterate with residual D(w) ≤ o(1/k) is available after k steps.
- Complexity result: The paper establishes a non-ergodic iteration-complexity result for the imsPADMM.The result is stated for the convergent sequence generated under the assumptions of the global convergence theorem.
- Residual measure: The residual measure D(w) combines distances of the two stationarity mappings from zero with the primal feasibility residual.An ε-approximate solution is defined by D(w) ≤ ε.
- Complexity result: o(1/k) residual accuracy is attained by at least one iterate among the first k steps.The complexity is expressed through a minimum over iterates rather than an averaged sequence.
- Complexity caveat: The residual sequence D(w^k) need not decrease monotonically, particularly because the method is inexact.This explains the use of a minimum over the first k iterates in the complexity statement.
7 Numerical Experiments
The experiments evaluate sGS-imsPADMM on high-dimensional SDP-BIQ and QSDP-BIQ instances, using approximate subproblem solves and specialized linear-system techniques. Across the reported tests, it generally outperforms the directly extended multi-block sPADMM.
- Test problems: The test suite contains one group of SDP-BIQ problems and three groups of QSDP-BIQ problems, with 80 instances per group and n ranging from 151 to 501.The methods are compared against directly extended multi-block sPADMM with step-length 1.618, whose convergence is not guaranteed.
- Implementation: The implementation solves large yI and W linear systems with preconditioned conjugate gradients and uses eigenvalue-based preconditioners for inexact subproblems.Equality-related systems can be handled through Cholesky factorization when cost and memory remain manageable.
- Numerical results: 2 to 3 times faster on about 80% of group 2 problems, and 2 to 4 times faster on more than 90% of group 3 instances.For group 3, the W subproblems admit closed-form solutions through eigenvalue decomposition.
- Interpretation: The overall advantage is attributed to allowing approximate subproblem solutions without adding proximal terms, whereas directly extended sPADMM solves subproblems exactly and may converge more slowly.The implementation uses summable-error-style tolerances and permits iterative linear-system solves.
8 Conclusions
The sGS-imsPADMM combines inexact majorized ADMM with inexact sGS updates for high-dimensional convex composite conic optimization. Experiments indicate substantial speedups over directly extended multi-block ADMM, while the paper identifies high-accuracy solver development as future work.
- Contributions: The method combines inexact 2-block majorized sPADMM with inexact sGS techniques for high-dimensional convex composite conic optimization.It is designed for moderate-accuracy solutions.
- Numerical results: Table 1 reports performance on one SDP-BIQ group and three QSDP-BIQ groups with n > 500 at accuracy 10^-6.The table compares sGS-isPADMM with directly extended multi-block ADMM using step-length τ = 1.618.
- Contributions: One cycle of inexact sGS solves each subproblem, avoiding an unknown number of cycles.This is a central implementation feature of the proposed method.
- Numerical results: 2 to 3 times faster was observed for the vast majority of 320 tested high-dimensional SDP problems than directly extended multi-block ADMM with step-length 1.618.The comparison method has no convergence guarantee but is described as a benchmark for multi-block linear and quadratic SDPs.
- Future direction: The proposed method is intended to provide a good initial point for warm-starting the augmented Lagrangian method.The stated goal is to benefit quickly from the augmented Lagrangian method’s fast local linear convergence.
- Future direction: Developing efficient high-accuracy solvers based on sGS-imsPADMM remains future research.The paper explicitly leaves this extension open.