## 3 Modified PROS with Local Search Mechanism
### Analysis of the Modified Algorithms
: _The probability of tame convergence is defined as the probability of an algorithm with sampling policy \(\pi\) to find a tame solution in its next iteration, given the current best solution vector. That is,_  
\[f(\mathbf{x}^{(t+1)})<f(\mathbf{x}^{(t)})\]1  
**Lemma 2**. : _The probability of tame convergence of PROS is \(\frac{l_{j}}{b_{j}-a_{j}}\)._Proof. : Let \(P_{j}^{U}\) be the probability that a _tame_ solution is found by sampling using uniform distribution on the \(j\)-th decision variable in the \((t+1)\)-th iteration, given the best solution vector in the \(t\)-th iteration. Then  
\[f(\mathbf{x}^{(t+1)})<f(\mathbf{x}^{(t)})\]2  
**Theorem 4**. : _The probability of tame convergence of TROS is \(\frac{l_{j}}{b_{j}-a_{j}}(\frac{l_{j}+2\
u_{j}}{a_{j}+l_{j}+\
u_{j}})\) when \(x_{j}^{(t)}<x_{j}^{*}\) and is \(\frac{l_{j}}{b_{j}-a_{j}}(\frac{l_{j}+2q_{j}}{q_{j}+l_{j}+\
u_{j}})\) when \(x_{j}^{(t)}>x_{j}^{*}\) where \(u_{j}=x_{j}^{l}-x_{j}^{(t)}\), \(v_{j}=b_{j}-x_{j}^{\prime}\), \(q_{j}=x_{j}^{l}-a_{j}\) and \(r_{j}=x_{j}^{(t)}-x_{j}^{\prime}\)._  
Proof. : Let \(P_{j}^{T}\) be the probability that a _tame_ solution is found by sampling using the triangular distribution on the \(j\)-th decision variable in the \((t+1)\)-th iteration, given the best solution vector in the \(t\)-th iteration. That is,  
\[f(\mathbf{x}^{(t+1)})<f(\mathbf{x}^{(t)})\]3  
For case 1, \(x_{j}^{(t)}<x_{j}^{*}\):  
\[f(\mathbf{x}^{(t+1)})<f(\mathbf{x}^{(t)})\]4  
\[f(\mathbf{x}^{(t+1)})<f(\mathbf{x}^{(t)})\]5  
Similarly, for case 2, \(x_{j}^{(t)}>x_{j}^{*}\):  
\[f(\mathbf{x}^{(t+1)})<f(\mathbf{x}^{(t)})\]6  
\[f(\mathbf{x}^{(t+1)})<f(\mathbf{x}^{(t)})\]7  
**Corollary 2**. : _The conditions that TROS has a higher probability of tame convergence than that of PROS, the same probability as that of PROS, and a lower probability than that of PROS are as follows, respectively._  
\[f(\mathbf{x}^{(t+1)})<f(\mathbf{x}^{(t)})\]8 **Left**: an example function where \(x^{(t)}<x_{j}^{*}\). **Right**: another example function where \(x^{(t)}>x_{j}^{*}\). The set of _tame_ solutions is denoted as \(S_{j}\). _For case 1, \(x_{j}^{(t)}<x_{j}^{*}\):_  
\[P_{j}^{T} \begin{cases}>P_{j}^{UI}&,\,v_{j}>u_{j}\\ =P_{j}^{UI}&,\,v_{j}=u_{j}\,.\\ <P_{j}^{UI}&,\,v_{j}<u_{j}\end{cases} \]  
_For case 2, \(x_{j}^{(t)}>x_{j}^{*}\):_  
\[P_{j}^{T} \begin{cases}>P_{j}^{UI}&,\,q_{j}>r_{j}\\ =P_{j}^{UI}&,\,q_{j}=r_{j}\,.\\ <P_{j}^{UI}&,\,q_{j}<r_{j}\end{cases} \]  
**Corollary 3**. : _The probability of tame convergence of TROS is higher than or equal to that of PROS for all convex functions._  
Proof. : For convex functions, \(u_{j}=0\) (for case 1) and \(r_{j}=0\) (for case 2). An example convex function is shown in Figure 3.  
For case 1, \(x_{j}^{(t)}<x_{j}^{*}\):  
\[P_{j}^{T} =\frac{l_{j}}{b_{j}-a_{j}}(\frac{l_{j}+2v_{j}}{u_{j}+l_{j}+v_{j}})\] \[=P_{j}^{UI}(1+\frac{v_{j}}{l_{j}+v_{j}})\] \[\therefore P_{j}^{T} \begin{cases}>P_{j}^{UI}&,\,v_{j}>0\\ =P_{j}^{UI}&,\,v_{j}=0\end{cases} .\]  
Similarly, for case 2, \(x_{j}^{(t)}>x_{j}^{*}\):  
\[P_{j}^{T} =\frac{l_{j}}{b_{j}-a_{j}}(\frac{l_{j}+2q_{j}}{q_{j}+l_{j}+r_{j}})\] \[=P_{j}^{UI}(1+\frac{q_{j}}{q_{j}+l_{j}})\] \[\therefore P_{j}^{T} \begin{cases}>P_{j}^{UI}&,\,q_{j}>0\\ =P_{j}^{UI}&,\,q_{j}=0\end{cases} .\]  
Therefore, for convex functions, \(P_{j}^{T}\) can never be less than \(P_{j}^{U}\). Figure 3: An example convex function. Left: for case 1, \(x_{j}^{(t)}<x_{j}^{*}\), \(u_{j}=0\). Right: case 2, \(x_{j}^{(t)}>x_{j}^{*}\), \(r_{j}=0\). **Theorem 5**. : _The probability of tame convergence of QROS is \(\frac{l_{j}}{b_{j}-a_{j}}\frac{(l_{j}+v_{j})(l_{j}+2v_{j})+v_{j}^{2}}{(u_{j}+l_{j} +v_{j})^{2}}\) when \(x_{j}^{(t)}<x_{j}^{*}\) and is \(\frac{l_{j}}{b_{j}-a_{j}}\frac{(q_{j}+l_{j})(2q_{j}+l_{j})+q_{j}^{2}}{(q_{j}+l_ {j}+r_{j})^{2}}\) when \(x_{j}^{(t)}>x_{j}^{*}\) where \(u_{j}=x_{j}^{l}-x_{j}^{(t)}\), \(v_{j}=b_{j}-x_{j}^{r}\), \(q_{j}=x_{j}^{l}-a_{j}\) and \(r_{j}=x_{j}^{(t)}-x_{j}^{r}\)._  
Proof.