Closed-Form Parameter Selection for ADMM and Over-Relaxed ADMM via Spectral Upper-Envelope Analysis

The Alternating Direction Method of Multipliers (ADMM) and its over-relaxed variant (oADMM) are among the most effective optimization solvers in modern machine learning. However, their convergence performance depends critically on penalty and relaxation parameters that are challenging to tune properly. In practice, these parameters are typically selected through manual tuning, iterative procedures such as gradient-based search, or adaptive schemes such as residual balancing. Such approaches incur substantial computational overhead while offering limited theoretical guidance. To address this issue, we introduce a spectral upper-envelope framework, supported by strong theoretical guarantees, that provides analytical parameter-selection rules for ADMM and oADMM over a broad class of linear quadratic problems (LQPs). By formulating these algorithms as fixed-point iterations, we relate their convergence behavior to the spectral radius of the corresponding iteration matrix. This viewpoint leads to a tight and tractable upper bound, from which closed-form parameter choices can be derived, thereby eliminating the need for manual or iterative tuning. Extensive stochastic experiments show that the proposed parameters closely match optimal values obtained via gradient-descent search. In addition, experiments on two application domains, namely heterogeneous parabolic partial differential equations (PDEs) and diffeomorphic image registration, demonstrate that the proposed framework enables ADMM and oADMM to achieve faster convergence than state-of-the-art iterative solvers. Overall, our spectral upper-envelope framework provides a practical and theoretically grounded approach to parameter selection for ADMM and oADMM.