# Non-Stationary Stochastic Global Optimization Algorithms
## 3 Materials and Methods
### Generalization to Non-Stationary Algorithms  
For a non-stationary (or non-homogeneous) Markov process, the transition probabilities (kernel) may change over time ([26]). Suppose that \(K_{t}\) is the transition kernel applied at time \(t>0\) of a non-stationary Markov process. Then, the transition kernel of such non-stationary Markov process at time \(t\) is defined as \(K^{(t)}=K_{t}\circ K_{t-1}\circ\ldots\circ K_{1}\). Clearly, we can rewrite Equation (7). The transition kernel of a non-stationary Markov process is given by:  
\[K^{(t)}(x,A)=\begin{cases}K^{1}(x,A)&\text{if }t=1\\ \int\limits_{\Omega}K^{(t-1)}(y,A)K^{t}(x,dy)&\text{if }t>1.\end{cases} \tag{15}\]  
Now we are in the position of generalizing Lemma 71 in [11] to non-stationary Markov processes.  
Lemma 3: _If \(\exists\delta>0\), such that for all \(x\in\Omega_{e}^{c}\), \(K_{t}(x,\Omega_{e})\geq\delta>0\) and, for all \(x\in\Omega_{e}\), \(K_{t}(x,\Omega_{e})=1\), then \(K^{(t)}(x,\Omega_{e})\geq 1-(1-\delta)^{t}\) holds for \(t\geq 1\)._  
Proof: We just rewrite the proof of Lemma 71 in [11] ([PERSON] uses induction on \(t\)) but taking care of the non-stationary property of the [PERSON] process. For \(t=1\) we have that \(K^{(t)}(x,\Omega_{e})=K_{t}(x,\Omega_{e})\) (Equation (7)), so \(K^{(t)}(x,\Omega_{e})\geq\delta\) (condition lemma), therefore \(K^{(t)}(x,\Omega_{e})\geq 1-(1-\delta)^{t}\) (\(t=1\) and numeric operations). Here, we will use the notation (as [PERSON] did) \(K^{(t)}(y,\Omega_{e})=K^{(t)}_{y}(\Omega_{e})\) to reduce the visual length of the equations.  
\(K^{(t+1)}_{x}(\Omega_{e})\)  
\(=\int\limits_{\Omega}K^{(t)}_{y}(\Omega_{e})K_{t}(x,dy)\) (Equation (7))  
\(=\int\limits_{\Omega_{e}}K^{(t)}_{y}(\Omega_{e})K_{t}(x,dy)+\int\limits_{\Omega _{e}^{c}}K^{(t)}_{y}(\Omega_{e})K_{t}(x,dy)\) (\(\Omega=\Omega_{e}\bigcup\Omega_{e}^{c}\))  
\(=\int\limits_{\Omega_{e}}K_{t}(x,dy)+\int\limits_{\Omega_{e}^{c}}K^{(t)}_{y}( \Omega_{e})K_{t}(x,dy)\) (If \(y\in\Omega_{e}\), \(K^{(t)}_{y}(\Omega_{e})=1\))  
\(=K_{t}(x,\Omega_{e})+\int\limits_{\Omega_{e}^{c}}K^{(t)}_{y}(\Omega_{e})K_{t}(x,dy)\) (def kernel)  
\(\geq K_{t}(x,\Omega_{e})+\left[1-(1-\delta)^{t}\right]\int\limits_{\Omega_{e}^ {c}}K_{t}(x,dy)\) (Induction hypothesis)  
\(\geq K_{t}(x,\Omega_{e})+\left[1-(1-\delta)^{t}\right]K_{t}(x,\Omega_{e}^{c})\) (def kernel)  
\(\geq K_{t}(x,\Omega_{e})+K_{t}(x,\Omega_{e}^{c})-(1-\delta)^{t}K_{t}(x, \Omega_{e}^{c})\)  
\(\geq 1-(1-\delta)^{t}(1-K_{t}(x,\Omega_{e}))\) (Probability)  
\(\geq 1-(1-\delta)^{t}(1-\delta)\) (condition lemma)  
\(\geq 1-(1-\delta)^{t+1}\).  
Finally, Theorem 72 in [11] also holds for non-stationary Markov processes. So, in order to show convergence of a non-stationary SGoal it is sufficient to prove that the SGoal satisfies the condition of Lemma 3.  
Theorem 3.2: _(Theorem 72 in [11]--a corrected version of Theorem 1 in [24]) A SGoal whose stochastic kernel satisfies \(K^{(t)}(x,\Omega_{e})\geq 1-(1-\delta)^{t}\) for all \(t\geq 1\) will converge to the global optimum (\(f^{*}\)) of a well-defined real-valued function \(f:\Phi\to\mathbb{R}\), defined in an arbitrary space \(\Omega\subseteq\Phi\), regardless of the initial distribution \(p(\cdot)\)._  
Proof.: See proof of Theorem 72 in [11].