## 3 The Generalized Alternating Linearization Bundle Method
Choose \(\tilde{f}_{k}:\mathbb{R}^{n}\rightarrow\mathbb{R}\) closed convex and such that  
\[\max\{\tilde{f}_{k-1},f_{k}\}\leq\tilde{f}_{k}\leq f.\]  
**Step 2** (Solve \(f\)-subproblem). Set  
\[y^{k+1}:=\arg\min\left\{\phi_{f}^{k}(\cdot):=\tilde{f}_{k}(\cdot)+\tilde{h}_{ k-1}(\cdot)+\frac{1}{2t_{k}}\|\cdot-\hat{x}^{k}\|^{2}\right\}, \tag{11}\]  
\[\tilde{f}_{k}(\cdot):=\tilde{f}_{k}(y^{k+1})+\langle p_{f^{\prime}}^{k},-y^{k +1}\rangle\;\;\text{with}\;\;p_{f}^{k}:=\frac{1}{t_{k}}(\hat{x}^{k}-y^{k+1})-p _{h}^{k-1}. \tag{12}\]  
**Step 3** (Solve \(h\)-subproblem). Set  
\[x^{k+1}:=\arg\min\left\{\phi_{h}^{k}(\cdot):=\tilde{f}_{k}(\cdot)+h(\cdot)+ \frac{1}{2t_{k}}\|\cdot-\hat{x}^{k}\|^{2}\right\}, \tag{13}\]  
\[f_{j}(\cdot):=f^{j}_{x}+\langle g^{j}_{x^{j}},-x^{j}\rangle,\;\;j\in J^{k}.\]0  
**Step 4** (Stopping criterion). Compute  
\[f_{j}(\cdot):=f^{j}_{x}+\langle g^{j}_{x^{j}},-x^{j}\rangle,\;\;j\in J^{k}.\]1  
If \(\max\{\|p^{k}\|,\epsilon_{k}\}=0\), stop. **Step 5** (Noise attenuation). If \(v_{k}<-\epsilon_{k}\), set \(t_{k}:=10t_{k}\), \(\hat{u}^{k}:=k\), and go back to Step 2. **Step 6** (Call oracle). Select a new error bound \(e_{x}^{k+1}\geq 0\) and a new descent target \(\gamma_{x}^{k+1}\in\mathbb{R}\cup\{+\infty\}\). Call the oracle (6) to compute \(\tilde{f}_{x}^{k+1}\) and \(\tilde{g}_{x}^{k+1}\). **Step 7** (Descent test). If the descent condition  
\[f_{j}(\cdot):=f^{j}_{x}+\langle g^{j}_{x^{j}},-x^{j}\rangle,\;\;j\in J^{k}.\]2  
holds, set \(\hat{x}^{k+1}:=x^{k+1}\), \(F_{\hat{x}}^{k+1}:=F_{x}^{k+1}\), \(\hat{t}^{k+1}:=0\), \(k(l+1):=k+1\), and \(l:=l+1\) (_descent step_); otherwise, set \(\hat{x}^{k+1}:=\hat{x}^{k}\), \(F_{\hat{x}}^{k+1}:=F_{\hat{x}}^{k}\), \(\hat{t}^{k+1}:=\hat{i}^{k}_{t}\), and \(k(l+1)=k(l)\) (_null step_). **Step 8** (Stepsize updating). For a descent step, select \(t_{k+1}\geq t_{k}\). For a null step, either set \(t_{k+1}:=t_{k}\) or choose \(t_{k+1}\in[t_{\min},t_{k}]\) if \(t_{k}^{k+1}=0\). **Step 9** (Loop). Let \(k:=k+1\), and go to Step 1. **Remark 1**. : _(i) Theoretically speaking, the model function \(\tilde{f}_{k}\) can be the simplest form \(\max\{\tilde{f}_{k-1},f_{k}\}\), but in order to keep numerical stability, it may additionally consist of some active linearizations.__(ii) Alternately solving subproblems (11) and (13) can be regarded as the proximal alternating linearization method (e.g., Reference [21]) being applied to the function \(\tilde{f}_{k}+h\)._  
_(iii) If \(\tilde{f}_{k}\) is a polyhedral function, then subproblem (11) is equivalent to a convex quadratic programming and thus can be solved efficiently. In addition, if \(h\) is simple, subproblem (13) can also be solved easily, or even has a closed-form solution (say \(h(x)=\frac{1}{2}\|x\|^{2}\))._  
_(iv) The role of Step 5 is to reduce the impact of inexactness. The algorithm loops between steps 2-5 by increasing the step size \(t_{k}\) until \(v_{k}\geq-\epsilon_{k}\)._  
_(v) The stability center, descent target and error bound keep unchanged in the loop between Steps 2 and 5_  
_(vi) In order to establish global convergence of the algorithm, the descent target and error bound at Step 6 should be suitably updated. Some detailed rules are presented in the next section._  
The following lemma summarizes some fundamental properties of Algorithm 1, whose proof is a slight modification of that in [22], Lemma 2.2. **Lemma 1**.