# Knowledge-Based Perturbation LaF-CMA-ES for Multimodal Optimization
## 3 The KbP-LaF-CMAES Algorithm
### Convergence Analysis of Kbp-LaF-CMAES
\(\Phi\) is defined by \(\Phi(x_{0})(x,\sigma)=(x+x_{0},\sigma)\) for all \(x_{0},x,\sigma\). Then, as the homomorphism definition,  
\[\mathcal{G}(\Phi(x_{0})(x,\sigma),y)=\Phi(x_{0})\mathcal{G}((x,\sigma),y) \tag{17}\]  
\[\mathcal{G}\Big{(}\Phi(x_{0})(x,\sigma),\mathcal{S}_{\Phi(x_{0})(x,\sigma)}^{f (x-x_{0})}*u\Big{)}=\Phi(x_{0})\mathcal{G}\Big{(}(x,\sigma),\mathcal{S}_{(x, \sigma)}^{f(x)}*u\Big{)} \tag{18}\]  
CMA-ES algorithm is translation invariance. \(\square\)  
**Proof 3. ** Invariance to Scaling of \(f\). \(\varphi\) is defined by \(\varphi(\alpha)(x,\sigma)=(x/\alpha,\sigma/\alpha)\) for all \(x_{0},x,\sigma\). \[f\big{(}\mathcal{S}ol\big{(}(x,\sigma),u^{i}\big{)}\big{)}=f\big{(}\alpha \mathcal{S}ol\big{(}\big{(}\tfrac{x}{\alpha},\tfrac{\sigma}{\alpha}\big{)},u^{i} \big{)}\big{)}\]  
) implies that the same permutation \(\mathcal{S}\) is obtained by the \((x,\sigma)\) of \(f\) and \(\big{(}\tfrac{x}{\alpha},\tfrac{\sigma}{\alpha}\big{)}\) of \(f(\alpha x)\), denoted as \(\mathcal{S}^{f(x)}_{(x,\sigma)}=\mathcal{S}^{f(\alpha x)}_{(\tfrac{x}{\alpha}, \tfrac{\sigma}{\alpha})}\). \[\mathcal{F}^{f(x)}\big{(}(x,\sigma),u\big{)}=\mathcal{G}\big{(}(x,\sigma), \mathcal{S}^{f(x)}_{(x,\sigma)}\ast u\big{)} \tag{19}\]  
\[X_{t}^{i}=\mathcal{Sol}\Big{(}(X_{t},\sigma_{t}),U_{t}^{i}\Big{)},i=1,\cdots,p \tag{12}\]0  
Then,  
\[X_{t}^{i}=\mathcal{Sol}\Big{(}(X_{t},\sigma_{t}),U_{t}^{i}\Big{)},i=1,\cdots,p \tag{12}\]1  
Hence, the property of scaling-invariance of CMA-ES is held. 2. Linear Convergence of CMA-ES In this part, \(Z_{t}\) is defined as \(\frac{X_{t}}{\alpha_{t}}\). The log-progress \(\ln\|X_{t+1}\|/\|X_{t}\|\) is investigated in the following for the analysis of linear convergence. \[X_{t}^{i}=\mathcal{Sol}\Big{(}(X_{t},\sigma_{t}),U_{t}^{i}\Big{)},i=1,\cdots,p \tag{12}\]2 (22)  
\(\eta^{\ast}\) is the multiplicative step-size update. \(Y(Z_{t},U_{t})\) is the ordered vector \(\mathcal{S}_{(Z_{t},1)}\ast U_{t}\). According to the property of logarithm, \(\frac{1}{t}\ln\frac{\|X_{t}\|}{\|X_{0}\|}\) is expressed as follows. \[ \begin{array}{l}\frac{1}{t}\ln\frac{\|X_{t}\|}{\|X_{0}\|}=\frac{1}{t}\ln \prod\limits_{k=0}^{t-1}\frac{\|X_{k+1}\|}{\|X_{k}\|}=\frac{1}{t}\sum\limits_ {k=0}^{t-1}\ln\frac{\|Z_{k+1}\|}{\|Z_{k}\|}\eta^{\ast}(Y(Z_{k},U_{k}))\\ \qquad\qquad\qquad\qquad\qquad=\frac{1}{t}\sum\limits_{k=0}^{t-1}\ln\|Z_{k+1 }\|-\frac{1}{t}\sum\limits_{k=0}^{t-1}\ln\|Z_{k}\|+\frac{1}{t}\sum\limits_{k= 0}^{t-1}\ln\eta^{\ast}(Y(Z_{k},U_{k}))\end{array}  \tag{23}\]  
\(\mathcal{R}(z)\) is defined as the expectation of the logarithm of \(\eta^{\ast}(Y(z,U))\). \(P^{t}(z,A)\) is the transition probabilities of the Markov chain. The \(\sigma\)-finite measure \(\pi\) is invariant if it satisfies  
\[\pi(A)=\int\pi(dz)P(z,A) \tag{24}\]  
\[E_{\pi}\bigg{[}\ln\frac{\|X_{t+1}\|}{\|X_{t}\|}\bigg{]}=\int E_{U\sim p_{U}}[ \ln(\eta^{\ast}(Y(z,U)))]\pi(dz)=\int\mathcal{R}(z)\pi(dz) \tag{25}\]  
CR is the convergence rate as the opposite of RHS of the previous equation. \[CR=-\!\int E_{U\sim p_{U}}[\ln(\eta^{\ast}(Y(z,U)))]\pi(dz)=-\!\int\mathcal{R }(z)\pi(dz) \tag{26}\]  
Then,  
\[\lim\limits_{t\to\infty}\!\frac{1}{t}\ln\frac{\|X_{t}\|}{\|X_{0}\|}=\int\ln\! \|z\|\pi(dz)-\int\ln\!\|z\|\pi(dz)+\int E[\ln(\eta^{\ast}(Y(z,U)))]\pi(dz)=-CR \tag{27}\]  
The linear convergence can be proven by exploiting the application of a Law of Large Numbers (LLN). \(\Delta\) is the drift operation defined as follows. \[\Delta V(z)=\int P(z,dy)V(y)-V(z)=E_{Z}[V(Z_{1})-V(Z_{0})] \tag{28}\]  
Then,  
\[\big{\|}P^{t}(z,.)-\pi\big{\|}_{h}\underset{t\to\infty}{\to}0 \tag{29}\]  
KbP-LaF-CMAES can reach the global optimum in probability.