# On the Adaptive Penalty Parameter Selection in ADMM
## 2 Adaptive Penalty Parameter Selection in ADMM Method
Similarly, from the optimality condition for the subproblem (3), one can obtain  
\[\max_{\xi\in\mathbb{R}^{p}}\xi^{\top}d-H^{*}(E^{\top}\xi)-G^{*}(F^{\top}\xi), \tag{5}\]3From (12) and (13), we have  
\[\max_{\xi\in\mathbb{R}^{p}}\xi^{\top}d-H^{*}(E^{\top}\xi)-G^{*}(F^{\top}\xi), \tag{5}\]4 \[\max_{\xi\in\mathbb{R}^{p}}\xi^{\top}d-H^{*}(E^{\top}\xi)-G^{*}(F^{\top}\xi), \tag{5}\]5  
Finally, one can define \(\Delta\xi^{k-1}=\xi^{k}-\xi^{k-1}\) and \(\Delta H^{k-1}=\partial H(\xi^{k})-\partial H(\xi^{k-1})\), where \(\bar{H}(\xi):=H^{*}(E^{\top}\xi)-\xi^{\top}d\), and the set subtraction is given by the Minkowski-Pontryagin difference [16; 17]. In particular, a practical computation of an element of \(\Delta\bar{H}^{k-1}\) can be provided through quantities available at the current ADMM iteration by exploiting (12); thus, with a slight abuse of notation, we may write  
\[\max_{\xi\in\mathbb{R}^{p}}\xi^{\top}d-H^{*}(E^{\top}\xi)-G^{*}(F^{\top}\xi), \tag{5}\]6  
Then, the two BB-based rules can be recovered as  
\[\max_{\xi\in\mathbb{R}^{p}}\xi^{\top}d-H^{*}(E^{\top}\xi)-G^{*}(F^{\top}\xi), \tag{5}\]7 \[\max_{\xi\in\mathbb{R}^{p}}\xi^{\top}d-H^{*}(E^{\top}\xi)-G^{*}(F^{\top}\xi), \tag{5}\]8  
With a similar argument, the curvature estimates of \(\bar{G}(\xi):=G^{*}(F^{\top}\xi)\) are provided by the following stepsizes:  
\[\max_{\xi\in\mathbb{R}^{p}}\xi^{\top}d-H^{*}(E^{\top}\xi)-G^{*}(F^{\top}\xi), \tag{5}\]9 \[\min_{\xi\in\mathbb{R}^{p}}H^{*}(E^{\top}\xi)-\xi^{\top}d+G^{*}(F^{\top}\xi). \tag{6}\]0  
where \(\Delta\xi^{k-1}=\xi^{k}-\xi^{k-1}\) and \(\Delta\bar{G}^{k-1}=F(v^{k}-v^{k-1})\). The previous quasi-Newton conditions express a local property of linearity of the dual subgradients with respect to the dual variables. The validity of this assumption can be checked during the iterative procedure to test the reliability of the spectral BB-based parameters. In particular, the stepsizes (16)-(19) can be considered reliable when, respectively, the ratios  
\[\min_{\xi\in\mathbb{R}^{p}}H^{*}(E^{\top}\xi)-\xi^{\top}d+G^{*}(F^{\top}\xi). \tag{6}\]1  
are bounded away from zero. Then, as safeguarding condition, the update of the penalty parameter is realized in accordance with (9) when both the ratios in (20) are greater than a prefixed threshold \(\bar{\epsilon}\in(0,1)\) expressing the required level of reliability provided by the estimates (10) and (11). If only one of the ratios satisfies the safeguarding condition, the corresponding stepsize is used to estimate \(\tau^{k}\), which eventually is set equal to the last updated value when both stepsizes are considered inaccurate, i.e., when \(\alpha_{cor}\leq\bar{\epsilon}\) and \(\beta_{cor}\leq\bar{\epsilon}\). A general ADMM scheme with adaptive selection of the penalty parameter based on the described procedure is outlined in Algorithm 1. We remark that different versions of Algorithm 1 arise depending on the different rules selected for computing the spectral stepsizes \(\alpha_{k}\) and \(\beta_{k}\) in STEP 4. In particular, in the scheme originally proposed in [7], \(\alpha_{k}\) and \(\beta_{k}\) are provided by a generalization of the _adaptive steepest descent_ (ASD) strategy introduced in [10], which performs a proper alternation of larger and smaller stepsizes. In the next section, we will compare this procedure with other updating rules based on both single and alternating BB-based strategies. As final remark, we recall that a proof of the convergence of ADMM with variable penalty parameter was provided in [3] under suitable assumptions on the increase and decrease in the sequence \(\{\tau^{k}\}_{k}\) (see Section 4--Theorem 4.1 in [3]). Although this convergence analysis cannot straightforwardly be applied to our case, as observed in [7], this issue may be bypassed in practice by turning off the adaptivity after a finite number of steps. ```
Initialize \(u^{0},v^{0},\tilde{g}^{0}\), \(\tau_{0}>0,\ \tilde{\varepsilon}\in(0,1)\), \(n\geq 1\) For\(k=0,1,2,...\)  Step 1  Compute \(u^{k+1}\) by solving (2). Step 2  Compute \(v^{k+1}\) by solving (3).