# On the Adaptive Penalty Parameter Selection in ADMM
## 2 Adaptive Penalty Parameter Selection in ADMM Method  
In this section, we describe the strategy for automatic selection of the penalty parameter in ADMM according to the procedure proposed in [7], in which the authors introduced an adaptive selection of \(\tau\) based on the spectral properties of the Douglas-Rachford (DR) splitting method applied to the dual problem of (1). Given a closed convex (proper) function \(f\) defined on \(\mathbb{R}^{n}\), the Fenchel conjugate of \(f\) is the closed convex (proper) function \(f^{*}\) defined by  
\[f^{*}(x^{*})=\sup_{x}\{x^{\top}x^{*}-f(x)\}=-\inf_{x}\{f(x)-x^{\top}x^{*}\},\]  
(see [14]). The dual problem of (1) is given by  
\[\max_{\xi\in\mathbb{R}^{p}}\xi^{\top}d-H^{*}(E^{\top}\xi)-G^{*}(F^{\top}\xi), \tag{5}\]  
where \(H^{*}\) and \(G^{*}\) denote, respectively, the Fenchel conjugate of \(H\) and \(G\). Problem (5) can be equivalently rewritten as  
\[\min_{\xi\in\mathbb{R}^{p}}H^{*}(E^{\top}\xi)-\xi^{\top}d+G^{*}(F^{\top}\xi). \tag{6}\]It can be proved that solving (1) by ADMM is equivalent to solving the dual problem (6) by means of the DR method [15], which, in turn, is equivalent to applying the DR scheme to  
\[0\in(E^{\top}\partial H^{*}(E^{\top}\xi)-d)+F^{\top}\partial G^{*}(F^{\top}\xi).\]  
In this way, two sequences \((\bar{\xi}^{k})_{k}\) and \((\xi^{k})_{k}\) are generated such that  
\[0 \in \frac{\bar{\xi}^{k+1}-\bar{\xi}^{k}}{\tau^{k}}+(E^{\top}\partial H ^{*}(E^{\top}\bar{\xi}^{k+1})-d)+F^{\top}\partial G^{*}(F^{\top}\bar{\xi}^{k}), \tag{7}\] \[0 \in \frac{\bar{\xi}^{k+1}-\bar{\xi}^{k}}{\tau^{k}}+(E^{\top}\partial H ^{*}(E^{\top}\bar{\xi}^{k+1})-d)+F^{\top}\partial G^{*}(F^{\top}\bar{\xi}^{k+1 }). \tag{8}\]  
Then, Proposition 1 in [7] proves that the choice of the parameter \(\tau^{k}\) that guarantees the minimal residual of \((E^{\top}\partial H^{*}(E^{\top}\bar{\xi}^{k+1})-d)+F^{\top}\partial G^{*}(F^{ \top}\bar{\xi}^{k+1})\) in DR steps is given by  
\[\tau^{k}=\sqrt{\alpha_{k}\beta_{k}} \tag{9}\]  
where \(\alpha_{k},\beta_{k}>0\) are BB stepsizes arising by imposing the following quasi-Newton conditions:  
\[\alpha_{k} = \underset{\alpha\in\mathbb{R}}{\operatorname{argmin}}\left\| \alpha^{-1}(\bar{\xi}^{k}-\bar{\xi}^{k-1})-(\phi^{k}-\phi^{k-1})\right\|, \tag{10}\] \[\beta_{k} = \underset{\beta\in\mathbb{R}}{\operatorname{argmin}}\left\| \beta^{-1}(\bar{\xi}^{k}-\bar{\xi}^{k-1})-(\psi^{k}-\psi^{k-1})\right\|, \tag{11}\]  
where \(\phi^{k}\in E^{\top}\partial H^{*}(E^{\top}\bar{\xi}^{k})-d\), \(\phi^{k-1}\in E^{\top}\partial H^{*}(E^{\top}\bar{\xi}^{k-1})-d\), \(\psi^{k}\in F^{\top}\partial G^{*}(F^{\top}\bar{\xi}^{k})\), and \(\psi^{k-1}\in F^{\top}\partial G^{*}(F^{\top}\bar{\xi}^{k-1})\). Note that \(1/\alpha_{k}\) and \(1/\beta_{k}\) can be interpreted as spectral gradient stepsizes of type BB1 for \(H^{*}(E^{\top}\bar{\xi}^{k})-(\bar{\xi}^{k})^{\top}d\) and \(G^{*}(F^{\top}\bar{\xi}^{k})\), respectively. Based on the equivalence between DR and ADMM, the optimal DR stepsize \(\tau^{k}\) defined in (9) corresponds to the optimal penalty parameter for the ADMM scheme. Moreover, to compute practical estimates of these optimal parameters for ADMM, the dual problem is not required to be supplied, thanks to the theoretical link between primal and dual variables. Indeed, the optimality condition for Problem (2) prescribes  
\[0\in\partial H(u^{k+1})-E^{\top}\Big{(}\bar{\xi}^{k}+\tau^{k}(d-Eu^{k+1}-Fv^{k })\Big{)},\]  
which is equivalent to  
\[\max_{\xi\in\mathbb{R}^{p}}\xi^{\top}d-H^{*}(E^{\top}\xi)-G^{*}(F^{\top}\xi), \tag{5}\]0  
Recalling that for a closed proper convex function \(f\), \(x\in\partial f^{*}(x^{*})\) if and only if \(x^{*}\in\partial f(x)\) (see [14], Corollary 23.5.1), from the previous relation, we obtain  
\[\max_{\xi\in\mathbb{R}^{p}}\xi^{\top}d-H^{*}(E^{\top}\xi)-G^{*}(F^{\top}\xi), \tag{5}\]1  
and, hence, it follows  
\[\max_{\xi\in\mathbb{R}^{p}}\xi^{\top}d-H^{*}(E^{\top}\xi)-G^{*}(F^{\top}\xi), \tag{5}\]2  
where \(\bar{\xi}^{k+1}:=\bar{\xi}^{k}+\tau^{k}(d-Eu^{k+1}-Fv^{k})\).