# Delayed Star Subgradient Methods for Constrained Nondifferentiable Quasi-Convex Optimization
## 3 Algorithms and Convergence Results
### Delayed Star Subgradient Method I
For any \(\mathbf{x}^{*}\in X^{*}\) and \(k\in\mathbb{N}_{0}\), if \(\mathbf{x}_{k}\
otin X^{*}\), then_  
\[f(\mathbf{x}_{k})-f^{*}\leq L\langle\mathbf{g}_{k},\mathbf{x}_{k}-\mathbf{x}^ {*}\rangle^{p}\qquad\text{ for all }\mathbf{g}_{k}\in\partial^{*}f(\mathbf{x}_{k})\cap \mathcal{S}.\]  
Next, we will provide some lemma, which are important tools for proving the convergence results of DSSM-I. We first provide the basic inequality relating to the sufficient decreasing property of the generated sequence. Lemma 3: _Suppose that Assumption 2 holds. Let \(\{\mathbf{x}_{k}\}_{k=0}^{\infty}\) be a sequence generated by DSSM-I. For any \(\mathbf{x}^{*}\in X^{*}\) and \(k\in\mathbb{N}_{0}\), if \(\mathbf{x}_{k-\tau_{k}}\
otin X^{*}\), then_  
\[\|\mathbf{x}_{k+1}-\mathbf{x}^{*}\|^{2}\leq\|\mathbf{x}_{k}-\mathbf{x}^{*}\|^ {2}+\alpha_{k}^{2}+2\alpha_{k}\|\mathbf{x}_{k}-\mathbf{x}_{k-\tau_{k}}\|-2 \alpha_{k}L^{-\frac{1}{p}}\big{(}f(\mathbf{x}_{k-\tau_{k}})-f^{*}\big{)}^{ \frac{1}{p}}.\]  
Proof. : Let \(\mathbf{x}^{*}\in X^{*}\) and \(k\in\mathbb{N}_{0}\) be fixed. Suppose that \(\mathbf{x}_{k-\tau_{k}}\
otin X^{*}\). We note from the definition \(\mathbf{x}_{k}\) in DSSM-I that  
\[\|\mathbf{x}_{k+1}-\mathbf{x}^{*}\|^{2} = \|P_{X}(\mathbf{x}_{k}-\alpha_{k}\mathbf{g}_{k-\tau_{k}})-P_{X}( \mathbf{x}^{*})\|^{2}\] \[\leq \|\mathbf{x}_{k}-\alpha_{k}\mathbf{g}_{k-\tau_{k}}-\mathbf{x}^{*}\| ^{2}\] \[= \|\mathbf{x}_{k}-\mathbf{x}^{*}\|^{2}+\alpha_{k}^{2}-2\alpha_{k} \langle\mathbf{g}_{k-\tau_{k}},\mathbf{x}_{k}-\mathbf{x}^{*}\rangle\] \[\leq \|\mathbf{x}_{k}-\mathbf{x}^{*}\|^{2}+\alpha_{k}^{2}+2\alpha_{k} \|\mathbf{x}_{k}-\mathbf{x}_{k-\tau_{k}}\|-2\alpha_{k}\langle\mathbf{g}_{k- \tau_{k}},\mathbf{x}_{k-\tau_{k}}-\mathbf{x}^{*}\rangle\] \[\leq \|\mathbf{x}_{k}-\mathbf{x}^{*}\|^{2}+\alpha_{k}^{2}+2\alpha_{k} \|\mathbf{x}_{k}-\mathbf{x}_{k-\tau_{k}}\|-2\alpha_{k}L^{-\frac{1}{p}}\big{(} f(\mathbf{x}_{k-\tau_{k}})-f^{*}\big{)}^{\frac{1}{p}},\]  
where the first inequality follows from the nonexpansiveness of metric projection, and the second one follows from the Cauchy-Schwarz inequality and the fact that \(\|\mathbf{g}_{k-\tau_{k}}\|=1\) for all \(k\in\mathbb{N}_{0}\), and the last one follows from Lemma 2. This completes the proof. Lemma 4: _Suppose that Assumption 1 holds. Let \(\{\mathbf{x}_{k}\}_{k=0}^{\infty}\) be a sequence generated by DSSM-I, and let \(\{\alpha_{k}\}_{k=0}^{\infty}\subset(0,\infty)\) be a nonincreasing sequence with \(\lim_{k\to\infty}\alpha_{k}=0\) and \(\sum_{k=0}^{\infty}\alpha_{k}=\infty\). Then \(\|\  
Let \(k\in\mathbb{N}_{0}\) be such that \(k\geq\tau\). Combining (3) and (4) together with the nonincreasing of \(\{\alpha_{k}\}_{k=0}^{\infty}\) yields  
\[\|\mathbf{x}_{k}-\mathbf{x}_{k-\tau_{k}}\|\leq\sum_{i=0}^{\tau}\| \mathbf{x}_{k-i+1}-\mathbf{x}_{k-i}\|\leq\sum_{i=0}^{\tau}\alpha_{k-i}\leq\sum_ {i=0}^{\tau}\alpha_{k-\tau}=(\tau+1)\alpha_{k-\tau}. \tag{5}\]  
Furthermore, since \(\lim_{k\to\infty}\alpha_{k}=0\), we conclude that \(\lim_{k\to\infty}\|\mathbf{x}_{k}-\mathbf{x}_{k-\tau_{k}}\|=0\). The proof is complete. Now, we are ready to prove the first convergence result in the sense of the inferior limit of the function values of the generated sequence is equal to the optimal value \(f^{*}\). Theorem 3.1: _Suppose that Assumptions 1 and 2 hold. Let \(\{\mathbf{x}_{k}\}_{k=0}^{\infty}\) be a sequence generated by DSSM-I and \(\{\alpha_{k}\}_{k=0}^{\infty}\) be a nonincreasing sequence with \(\lim_{k\to\infty}\alpha_{k}=0\) and \(\sum_{k=0}^{\infty}\alpha_{k}=\infty\). Then, we have \(\liminf_{k\to\infty}f(\mathbf{x}_{k})=f^{*}\)._  
Proof: It is obvious that \(\liminf_{k\to\infty}f(\mathbf{x}_{k})\geq f^{*}\) since \(f(\mathbf{x}_{k})\geq f^{*}\) for all \(k\in\mathbb{N}_{0}\), so that it is sufficient to prove that \(\liminf_{k\to\infty}f(\mathbf{x}_{k})\leq f^{*}\). Now, assume to the contrary that \(\liminf_{k\to\infty}f(\mathbf{x}_{k})>f^{*}\). Then there exists \(\epsilon>0\) and \(k_{1}\in\mathbb{N}_{0}\) such that \(f(\mathbf{x}_{k})>f^{*}+\epsilon\) for all \(k\geq k_{1}\).