# Delayed Star Subgradient Methods for Constrained Nondifferentiable Quasi-Convex Optimization
## 3 Algorithms and Convergence Results
### Delayed Star Subgradient Method I
Applying Lemma 3 and the nonincreasing property of the stepsize \(\{\alpha_{k}\}_{k=0}^{\infty}\), we get  
\[\|\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}}.\]4  
Substituting the inequalities (11) and (12) in (14) gives  
\[\|\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}}.\]5  
By putting \(\mathbf{x}^{*}=P_{X^{*}}(\mathbf{x}_{k})\), we obtain \(\text{dist}(\mathbf{x}_{k+1},X^{*})\leq\text{dist}(\mathbf{x}_{k},X^{*})\). **Case 2:** Suppose that \(f(\mathbf{x}_{k-\tau_{k}})\leq f^{*}+L\sigma\). Then we have \(\mathbf{x}_{k-\tau_{k}}\in X\cap S^{\leq}_{f,f^{*}+L\sigma}\) and \(\text{dist}(\mathbf{x}_{k-\tau_{k}},X^{*})\leq\rho(\sigma)\). We note from the definition of \(\mathbf{x}_{k+1}=P_{X}(\mathbf{x}_{k}-\alpha_{k}\mathbf{g}_{k-\tau_{k}})\) the nonexpansiveness of \(P_{X}\) and the nonincreasing property of \(\{\alpha_{k}\}_{k=0}^{\infty}\) 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}}.\]6  
which together with the inequality (11) and (12) yield  
\[\|\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}}.\]7  
By putting \(\mathbf{x}^{*}:=P_{X^{*}}(\mathbf{x}_{k-\tau_{k}})\) and invoking \(\text{dist}(\mathbf{x}_{k-\tau_{k}},X^{*})\leq\rho(\sigma)\), we obtain  
\[\|\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}}.\]8  
Thus, we proved the relation (13). By using the same analogy of Theorem 1, we obtain that \(\liminf_{k\to\infty}f(\mathbf{x}_{k-\tau_{k}})=f^{*}\). Consequently, there exists \(k^{\prime}_{\sigma}\) such that \(k^{\prime}_{\sigma}\geq k_{\sigma}\) and \(f(\mathbf{x}_{k^{\prime}_{\sigma}-\tau_{k^{\prime}_{\sigma}}})<f^{*}+L\sigma^ {\frac{1}{p}}\). Therefore, we obtain from **Case** 2 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}}.\]9Put \(N_{\sigma}:=k_{\sigma}^{\prime}+1\). Suppose that \(\operatorname{dist}(\mathbf{x}_{k},X^{*})\leq\rho(\sigma)+\frac{(\tau+2)\sigma^{ \frac{1}{p}}}{2\tau+3}\) for all \(k\geq N_{\sigma}\). Invoking (13), we obtain \(\operatorname{dist}(\mathbf{x}_{k+1},X^{*})\leq\rho(\sigma)+\frac{(\tau+2) \sigma^{\frac{1}{p}}}{2\tau+3}\). Hence, we conclude by the strong induction 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}\]0  
\((ii)\) For each \(r\in\mathbb{N}\), we denote \(X_{\frac{1}{r}}:=X\cap S_{f,f^{*}+L\big{(}\frac{1}{r}\big{)}}^{<}\). Observe that \(\Big{\{}X_{\frac{1}{r}}\Big{\}}_{r=1}^{\infty}\) is nonincreasing and \(\bigcap_{r\in\mathbb{N}}X_{\frac{1}{r}}=X\cap S_{f,f^{*}}^{<}=X^{*}\). Subsequently, \(\Big{\{}\rho\Big{(}\frac{1}{r}\Big{)}\Big{\}}_{r\in\mathbb{N}}\) is also nonincreasing and \(\inf_{r\in\mathbb{N}}\rho\Big{(}\frac{1}{r}\Big{)}=\inf_{r\in\mathbb{N}}\max _{\mathbf{x}\in X_{\frac{1}{r}}}\operatorname{dist}(\mathbf{x},X^{*})=\max_{ \mathbf{x}\in X^{*}}\operatorname{dist}(\mathbf{x},X^{*})=0\). Hence, we obtain that \(\lim_{r\to\infty}\rho\Big{(}\frac{1}{r}\Big{)}=0\). Now, let \(\varepsilon>0\) be arbitrary.