# Non-Stationary Stochastic Global Optimization Algorithms
## 2 Preliminaries
### Systematic Formalization Theory
#### 2.1.3 Kernel  
Stochastic processes can model the process of generating one population from another population. A transition kernel is used to characterize each iteration in a stochastic process given by:  
\[K(x,A)=P(x,A)=Pr[X_{t}\in A\ |\ X_{t-1}=x]. \tag{2}\]  
where \(x\) is the current population and \(A\) a subset of possible populations.  
**Definition 1**.: _(**Markov kernel**) Let \((\Omega_{1},\Sigma_{1})\) and \((\Omega_{2},\Sigma_{2})\) be measurable spaces. A function \(K:\Omega_{1}\times\Sigma_{2}\to[0,1]\) is called a (Markov) kernel if the following two conditions hold:_  
1. _Function_ \(K_{x,\bullet}:A\mapsto K(x,A)\) _is a probability measure for each fixed_ \(x\in\Omega_{1}\)__
2. _Function_ \(K_{x,\bullet}:x\mapsto K(x,A)\) _is a measurable function for each fixed_ \(A\in\Sigma_{2}\)The transition kernel of an existing transition density \(K\): \(\Omega_{1}\times\Omega_{2}\rightarrow[0,1]\) is defined by:  
\[K(x,A)=\int_{A}K(x,y)dy. \tag{3}\]  
Kernels linked with deterministic methods used by SGoals play a significant role in developing a systematic formal theory. Next, we review several characterizations of stochastic methods using transition kernels.  
Deterministic Kernel  
Let \((\Omega_{1},\Sigma_{1})\) and \((\Omega_{2},\Sigma_{2})\) be measurable spaces, and \(f:\Omega_{1}\rightarrow\Omega_{2}\) be \(\Sigma_{1}-\Sigma_{2}\) measurable. The function \(1_{f}:\Omega_{1}\times\Sigma_{2}\rightarrow[0,1]\) is a kernel defined by:  
\[1_{f}(x,A)=\left\{\begin{array}{ll}1&\text{if }f(x)\in A\\ 0&\text{otherwise.}\end{array}\right. \tag{4}\]  
Kernel Indicator  
Let \((\Omega,\Sigma)\) be a measurable space. The indicator function \(1:\Omega\times\Sigma\rightarrow[0,1]\) defined as \(1(x,A)=1_{id(x)}(A)\), with \(id(x)=x\) is a kernel.  
Random Scan (Mixing)  
The mixing update mechanism of a set of \(n\) Markov transition kernels \(K_{1},\,\ldots,\,K_{n}\), each of them with a probability of being picked \(p_{1},p_{2},\ldots,p_{n}\) (\(\sum p_{i}=1\)), is defined by:  
\[\left(\sum_{i=1}^{n}p_{i}K_{1}\right)(x,A)=\sum_{i=1}^{n}p_{i}\int_{A}K_{i}(x, y)dy. \tag{5}\]  
Composition  
The composition update mechanism is built using the kernel multiplication operator. It is built on the concept of applying one kernel after another. Kernel composition of \(K_{1}\), \(K_{2}\) is defined by:  
\[(K_{2}\circ K_{1})(x,A)=\int K_{2}(y,A)K_{1}(x,dy). \tag{6}\]  
The composition of update mechanisms that correspond to a set of \(n\) transition kernels \(K_{1},\,\ldots,\,K_{n}\) is defined as the product kernel \(K_{n}\circ K_{n-1}\circ\ldots\circ K_{1}\). Based on the fact that kernel multiplication is an associative operation.  
The transition probability of iteration t (application) of a Markovian kernel \(K\), describes the probability to transit to set \(A\in\Sigma\) within \(t\) steps when starting at state \(x\in\Omega\) as defined by:  
\[K^{(t)}(x,A)=\begin{cases}K(x,A)&,\,t=1\\ \int\limits_{\Omega}K^{(t-1)}(y,A)K(x,dy)&,\,t>1.\end{cases} \tag{7}\]  
Let \(\ p:\Sigma\rightarrow[0,1]\) be the initial distribution of subsets, in that case the probability that the Markov process is in set \(A\in\Sigma\) at step \(t\geq 0\) is given by:  
\[Pr\{X_{t}\in A\}=\begin{cases}p(A)&,\,t=0\\ \int\limits_{\Omega}K^{(t)}(x,A)p(dx)&,\,t>0.\end{cases} \tag{8}\]