# Delayed Star Subgradient Methods for Constrained Nondifferentiable Quasi-Convex Optimization
## 3 Algorithms and Convergence Results
### Delayed Star Subgradient Method I
By imposing either the coercivity of the objective function \(f\) or the compactness of the constraint \(X\), we can obtain an approximate convergence behavior and some nice convergence results in comparison to the one obtained in Theorem 1. Theorem 2: _Suppose that Assumptions 1 and 2 hold. Let \(\{\mathbf{x}_{k}\}_{k=0}^{\infty}\) be a sequence generated by DSSM-I, and let \(\{\mathbf{x}_{k}\}_{k=0}^{\infty}\) be a nonincreasing sequence with \(\lim_{k\to\infty}\alpha_{k}=0\) and \(\sum_{k=0}^{\infty}\alpha_{k}=\infty\). If the function \(f\) is coercive or the constrained set \(X\) is compact, then the following statements hold:_  
\((i)\) _For any_ \(\sigma>0\)_, there exists_ \(N_{\sigma}\in\mathbb{N}_{0}\) _such that_  
\[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}.\]8  
\[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}.\]9  
\((ii)\) _\(\lim_{k\to\infty}\operatorname{dist}(\mathbf{x}_{k},X^{*})=0\), and \(\lim_{k\to\infty}f(\mathbf{x}_{k})=f^{*}\)._  
Proof: Let \(\sigma>0\) be arbitrary and denote the notation  
\[\|\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}}.\]0  
Since the function \(f\) is coercive or the constrained set \(X\) is compact, we ensure that \(X^{*}\
eq\emptyset\) which together with \(X^{*}\subseteq X\cap S_{f,f^{*}+L\sigma}^{\leq}\) yield that \(X\cap S_{f,f^{*}+L\sigma}^{\leq}\
eq\emptyset\). Moreover, the continuity and quasi-convexity of \(f\), respectively, imply that \(S_{f,f^{*}+L\sigma}^{\leq}\) is closed and convex, and so the set \(X\cap S_{f,f^{*}+L\sigma}^{\leq}\) is also closed and convex. Again, with either the compactness of \(X\) or the coercivity of \(f\), the intersection \(X\cap S_{f,f^{*}+L\sigma}^{\leq}\) is bounded, and hence, \(X\cap S_{f,f^{*}+L\sigma}^{\leq}\) is a compact set, which ensures that \(\rho(\sigma)<\infty\). \((i)\) Let \(\mathbf{x}^{*}\in X^{*}\) be given. Since \(\lim_{k\to\infty}\alpha_{k}=0\), we also have \(\lim_{k\to\infty}\alpha_{k-\tau}=0\). Consequently, there exists \(k_{\sigma}\in\mathbb{N}_{0}\) such that \(k_{\sigma}\geq\tau\) and  
\[\|\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}}.\]1  
This together with the relation that \(\|\mathbf{x}_{k}-\mathbf{x}_{k-\tau_{k}}\|\leq(\tau+1)\alpha_{k-\tau}\) which is obtained in Lemma 4 yield that  
\[\|\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}}.\]2  
Now, we will show that  
\[\|\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}}.\]3  
Let \(k\geq k_{\sigma}\) be fixed. We divide the proof into two cases according to the behavior of \(f(\mathbf{x}_{k-\tau_{k}})\). **Case 1:** Suppose that \(f(\mathbf{x}_{k-\tau_{k}})>f^{*}+L\sigma\). Then we have \(\mathbf{x}_{k-\tau_{k}}\
ot\in X^{*}\).