# Delayed Star Subgradient Methods for Constrained Nondifferentiable Quasi-Convex Optimization
## 3 Algorithms and Convergence Results
### Delayed Star Subgradient Method I  
Now, we are ready to propose the delayed star subgradient method of the first kind which is defined as the following Algorithm 1. ```
Initialization: Given a stepsize \(\{\alpha_{k}\}_{k=0}^{\infty}\subset(0,\infty)\), the delays \(\{\tau_{k}\}_{k=0}^{\infty}\subset\mathbb{N}_{0}\), and initial points \(\mathbf{x}_{0},\mathbf{x}_{-1},\mathbf{x}_{-2},\ldots,\mathbf{x}_{-\tau}\in X\). Iterative Step: For a current point \(\mathbf{x}_{k}\in X\), we compute \[\mathbf{x}_{k+1}:=P_{X}(\mathbf{x}_{k}-\alpha_{k}\mathbf{g}_{k-\tau_{k}}),\] where \(\mathbf{g}_{k-\tau_{k}}\in\partial^{\star}f(\mathbf{x}_{k-\tau_{k}})\cap \mathcal{S}\) is a unit star subgradient of \(f\) at \(\mathbf{x}_{k-\tau_{k}}\). Update \(k:=k+1\). ```  
**Algorithm 1** Delayed Star Subgradient Method I (DSSM-I)  
Throughout this work, to simplify the analysis, we denote \(\mathbf{x}_{0}=\mathbf{x}_{-1}=\mathbf{x}_{-2}=\cdots=\mathbf{x}_{-\tau}\). **Remark 1**. :
1. _Since the function_ \(f\) _is quasi-convex, we note that DSSM-I is well defined. In fact, using Fact_ 1_, we have for any_ \(k\in\mathbb{N}_{0}\)_,_ \(\partial^{\star}f(\mathbf{x}_{k})\setminus\{\mathbf{0}\}\
eq\emptyset\)_. Hence, we are able to select any point_ \(\widehat{\
abla}^{\star}f(\mathbf{x}_{k})\in\partial^{\star}f(\mathbf{x}_{k}) \setminus\{\mathbf{0}\}\) _and subsequently set_ \(\mathbf{g}_{k}:=\frac{\widehat{\
abla}^{\star}f(\mathbf{x}_{k})}{\|\
abla^{ \star}f(\mathbf{x}_{k})\|}\in\partial^{\star}f(\mathbf{x}_{k})\cap\mathcal{S}\)_. Moreover, since_ \(\{\mathbf{x}_{k}\}_{k=0}^{\infty}\subset X\)_, it is clear that_ \(f(\mathbf{x}_{k})\geq f^{\star}\) _for all_ \(k\in\mathbb{N}_{0}\)_._
2. _If_ \(\tau_{k}=0\) _for all_ \(k\in\mathbb{N}_{0}\)_, DSSM-I coincides with the star subgradient method (SSM), which was proposed by [PERSON]_ _[_1_]__._  
**Remark 2**. : _Note that methods with time-varying delays allow us to use stale information, which is very helpful when the star subgradients are not easily computed. Assumption 1 is typically assumed for analyzing the convergence results of the delayed-type methods, see [18; 20; 24; 25; 26] and references therein. The presence of the delayed bound \(\tau\) ensures that we need to update the unit star subgradient of \(f\) at \(\mathbf{x}_{k-\tau_{k}}\) in at least every \(\tau\) iteration. Some examples of the delayed sequences are as follows:_  
1. _Constant delay_ _[_18_]__, that is,_ \(\tau_{k}:=\tau\) _for all_ \(k\in\mathbb{N}_{0}\)_._
2. _Cyclic delay_ _[_19; 20; 24; 26_]_ _and references therein. The typical form of this type is_ \(\tau_{k}:=k\mod(\tau+1)\) _for all_ \(k\in\mathbb{N}_{0}\)_. In this case, the delays_ \(\tau_{k}\) _(_\(k\in\mathbb{N}_{0}\)_) are chosen with deterministic order from the set_ \(\{0,1,2,\ldots,\tau\}\)_. This means that we will use stale information over a consistent period of length_ \(\tau+1\) _and update the new star subgradient at every_ \(\tau+1\) _iteration._
3. _Random delay_ _[_25_]__, that is, the delays_ \(\tau_{k}\) _(_\(k\in\mathbb{N}_{0}\)_) are randomly chosen in the set_ \(\{0,1,2,\ldots,\tau\}\)_._  
**Assumption 2**. : _The function \(f\) satisfies the Holder condition with order \(p>0\) and modulus \(L>0\) on \(X\), i.e., \(f(\mathbf{x})-f^{\star}\leq L\mathrm{dist}(\mathbf{x},X^{\star})^{p}\) for all \(\mathbf{x}\in X\)._The Holder condition assumption is typically assumed when investigating the convergence results of methods for solving quasi-convex optimization problems [6; 7; 9; 10; 11]. Note that, for the special case of \(p=1\), the Holder condition is nothing else than the Lipschitz condition. The following lemma provides a useful property of the star subgradient and will play an important role in the convergence analysis. The formal proof is due to [PERSON] [10] (Proposition 2.1). Lemma 2: _Suppose that Assumption 2 holds. Let \(\{\mathbf{x}_{k}\}_{k=0}^{\infty}\) be a sequence generated by DSSM-I.