# On the Adaptive Penalty Parameter Selection in ADMM
## 1 Introduction  
The alternating direction method of multipliers [1] (ADMM) has been recognized as a simple but powerful algorithm to solve optimization problems of the form  
\[ \begin{array}{ll}\min_{u\in\mathbb{R}^{n},v\in\mathbb{R}^{m}}&H(u)+G(v)\\ \text{subject to}&Eu+Fv=d\end{array}  \tag{1}\]  
where \(H\colon\mathbb{R}^{n}\to\mathbb{R}\cup\{+\infty\}\) and \(G\colon\mathbb{R}^{m}\to\mathbb{R}\cup\{+\infty\}\) are closed, proper, and convex functions, \(E\in\mathbb{R}^{p\times n}\), \(F\in\mathbb{R}^{p\times m}\), \(d\in\mathbb{R}^{p}\). ADMM splits the problem into smaller pieces, each of which is then easier to handle, blending the benefits of dual decomposition and augmented Lagrangian methods [1]. Starting from an initialization \((u^{0},v^{0},\xi^{0})\) and \(\tau>0\), at each iteration, ADMM updates the primal and dual variables as  
\[u^{k+1} = \operatorname*{argmin}_{u}H(u)+\frac{\tau}{2}\left\|d-Eu-Fv^{k}+ \frac{\xi^{k}}{\tau}\right\|^{2} \tag{2}\] \[v^{k+1} = \operatorname*{argmin}_{v}G(v)+\frac{\tau}{2}\left\|d-Eu^{k+1}-Fv +\frac{\xi^{k}}{\tau}\right\|^{2}\] (3) \[\xi^{k+1} = \xi^{k}+\tau\Big{(}d-Eu^{k+1}-Fv^{k+1}\Big{)}. \tag{4}\]  
ADMM is guaranteed to converge under mild assumptions for any fixed value of the penalty parameter \(\tau\), even if the subproblems are solved inexactly [2]. Despite this, it is well-known that the choice of the parameter \(\tau\) is problem-dependent and can affect the practical performance of the algorithm, yielding a highly inefficient method when itis not properly selected. Some work has been done to develop suitable techniques for tuning the values of \(\tau\) at each iteration, with the aim of speeding up the convergence in practical applications [3; 4; 5; 6]. In [3], the authors proposed an adaptive strategy based on primal and dual residuals, with the idea that \(\tau^{k}\) forces both to have a similar magnitude. Such a scheme is not guaranteed to converge; nevertheless, the standard convergence theory (fixed values of \(\tau\)) still applies if one assumes that \(\tau^{k}\) becomes fixed after a finite number of iterations. A more general and reliable approach has been introduced in [7], where the authors proposed a strategy for automatic selection of the penalty parameter in ADMM, borrowing ideas from spectral stepsize selection strategies in gradient-based methods for unconstrained optimization [8; 9; 10; 11]. In particular, starting from the analysis of the dual unconstrained formulation of problem (1), in [7] an optimal penalty parameter at each iteration is defined as the reciprocal of the geometric mean of Barzilai-Borwein-like spectral stepsizes [8; 10], corresponding to a gradient step of the Fenchel conjugates of the functions \(H\) and \(G\), respectively. Relying on the procedure suggested in [7], this paper aims at investigating the practical efficiency of ADMM, employing adaptive selections of the penalty parameter based on different spectral stepsize rules. Indeed, spectral analysis of Barzilai-Borwein (BB) rules (and their variants) has shown how different choices can influence the practical acceleration of gradient-based methods for both constrained and unconstrained smooth optimization, due to the intrinsic different abilities of such stepsizes of capturing the spectral properties of the problem. Indeed, for strictly convex quadratic problems, the Barzilai-Borwein updating rules correspond to the inverses of the Rayleigh quotients of the Hessian, thus providing suitable approximations of the inverses of its eigenvalues. Such an ability has been exploited within ad hoc steplength selection strategies to obtain practical accelerations of gradient-based methods; moreover, this property is preserved in the case of general non-quadratic minimization problems [9; 11; 12; 13]. In this view, we combine the adaptive ADMM scheme with state-of-the-art stepsizes to compute reliable approximations of the penalty parameter \(\tau^{k}\) at each iteration.