Research map / Learning theory and algorithms / Prediction and decision losses
Optimizing ADMM and Over-Relaxed ADMM Parameters for Linear Quadratic Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives a fixed-point/spectral-radius analysis of ADMM and over-relaxed ADMM for linear quadratic problems, giving a numerical gradient-descent rule for the penalty parameter and a closed-form optimal relaxation parameter alpha* = -2/(λ1(Q)+λn(Q)).
Problem
Choosing optimal penalty and relaxation parameters for ADMM and over-relaxed ADMM when solving linear quadratic problems in imaging, where empirical choices often slow convergence.
Approach
Recasts ADMM iterations as a fixed-point system whose iteration matrix has spectral radius at most 1 for any penalty; minimizes the spectral radius via numerical gradient descent over the penalty, and gives a closed-form relaxation parameter that equalizes the extreme eigenvalue contributions.
Key results
- Closed-form relaxation alpha*=-2/(λ1(Q)+λn(Q)) yields faster convergence than the empirical range [1.5,1.8] in random instantiations (50 trials).
- For image deblurring, closed-form optimum is theta*=1 and alpha*=2, with oADMM converging in essentially one step (superlinear, near-zero spectral radius).
- Theory shows the ADMM iteration matrix spectral radius is bounded by 1 for any penalty, so ADMM for LQPs converges unconditionally.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| select the penalty parameter by minimizing the iteration-matrix spectral radius | ADMM and over-relaxed ADMM · 50 random instantiations | convergence rate | Helped |
| use the optimized penalty parameter and closed-form optimal relaxation parameter | over-relaxed ADMM · diffeomorphic image registration | convergence rate | Helped |
| use the optimal penalty and relaxation parameters | over-relaxed ADMM · image deblurring | iterations to convergence | Helped |
| use the proposed parameter selection methods | ADMM and over-relaxed ADMM · MRI reconstruction | convergence efficiency | Helped |
Surprising findings
- The optimal relaxation parameter for the tested problems (alpha*=2 in deblurring) falls outside the widely used range [1.5, 1.8].
Limitations
- Analysis restricted to linear quadratic problems; extension to non-quadratic (e.g., L1) problems is only suggested.
- Closed-form penalty solutions exist only for specific structures (deblurring, MRI); registration requires numerical gradient descent.
- The regularization parameter mu is fixed and not optimized.
Experimental setup
Datasets: random instantiations of A and L (200x50) phantom test image cardiac MR image (k-space, 50% Cartesian undersampling) image pair for diffeomorphic registration
Benchmarks: random instantiations of linear quadratic problems image deblurring phantom MRI reconstruction cardiac image diffeomorphic image registration
Metrics: spectral radius / convergence factor iteration count to convergence Jacobian determinant positivity
Baselines: gradient descent GD-N GD-NR conjugate gradient ADMM with alpha=1 (unrelaxed)
Builds on: ADMM over-relaxed ADMM Nesterov accelerated gradient
Closest papers by meaning
- Adaptive Relaxed ADMM: Convergence Theory and Practical Implementation (CVPR 2017 · similarity 0.90)
- ADMM without a Fixed Penalty Parameter: Faster Convergence with New Adaptive Penalization (NeurIPS 2017 · similarity 0.90)
- ADMM for Nonconvex Optimization under Minimal Continuity Assumption (ICLR 2025 · similarity 0.87)
- Decoupling Training-Free Guided Diffusion by ADMM (CVPR 2025 · similarity 0.87)
- How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization (ICLR 2024 · similarity 0.84)
- Prior Mismatch and Adaptation in PnP-ADMM with a Nonconvex Convergence Analysis (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.