## 3 Modified PROS with Local Search Mechanism
### Analysis of the Modified Algorithms  
In this subsection, we are going to explain the motivation and analyze the performance of the two algorithms. Sampling using uniform distribution can be considered as performing global search on a decision variable, while sampling using the triangular distribution and the quadratic distribution can be considered as performing local search on a decision variable. **Definition 6** (Improved Solution). : _The candidate solution vector \(\mathbf{x}^{(t+1)}\) found by the algorithm is said to be improved if its error is less than the error of the current best solution. That is,_  
\[f(\mathbf{x}^{(t+1)})-f(\mathbf{x}^{*})<f(\mathbf{x}^{(t)})-f(\mathbf{x}^{*})\]  
_or simply_  
\[f(\mathbf{x}^{(t+1)})<f(\mathbf{x}^{(t)})\]  
_where \(t\) denotes the current iteration._  
For continuous (or Lipschitz) unimodal functions defined on a bounded domain, finding an improved solution vector always lead to the convergence to the global optimum. However, it may not be true for multimodal functions. Therefore, we are not interested in simply finding an improved solution vector. Here, we define a restrictive subset of improved solution vectors. **Definition 7** (_Tame_ Solution). : _The candidate solution vector \(\mathbf{x}^{(t+1)}\) found by the algorithm is said to be a tame solution if the errors of all points in between the line containing the candidate solution and the optimum solution are all less than the error of the current best solution. That is,_  
\[f(\mathbf{ax}^{(t+1)}+(1-\alpha)\mathbf{x}^{*})<f(\mathbf{x}^{(t)}),\forall \alpha\in[0,1]\]  
_where \(t\) denotes the current iteration._A local optimum in a multimodal function is not considered as a _tame_ solution if there exists a high hill in between the local optimum and the global optimum. The purpose of defining _tame_ solution is when a _tame_ solution is found, it does not only mean the solution is improved but also implies one could apply some simple techniques to converge to the global optimum. Therefore, we are interested in knowing the probability of finding a _tame_ solution by each of the algorithms. We define following terms for the analysis of the performance of the proposed algorithms. Let \(\mathbf{x}^{(t)}=(x_{1}^{(t)},x_{2}^{(t)},\ldots,x_{D}^{(t)})\) be the current best solution vector, and \(j\in\{1,\ldots,D\}\) be the chosen decision variable of the current iteration. Given \(\mathbf{x}_{-j}^{(t)}=(x_{1}^{(t)},\ldots,x_{j-1}^{(t)},x_{j+1}^{(t)},\ldots,\)\(x_{D}^{(t)})\), assume \(f(\mathbf{x}_{-j}^{(t)},x_{j})\) has a unique global minimum and is denoted as \(x_{j}^{*}\). That is,  
\[f(\mathbf{x}_{-j}^{(t)},x_{j}^{*})\leq f(\mathbf{x}_{-j}^{(t)},x_{j}),\forall x _{j}\in[a_{j},b_{j}].\]  
Let \(R_{j}\) be the set of values of the \(j\)-th decision variable that belong to improved solution vectors. That is,  
\[R_{j}=\{x_{j}|f(\mathbf{x}_{-j}^{(t)},x_{j})<f(\mathbf{x}_{-j}^{(t)},x_{j}^{(t )}),x_{j}\in[a_{j},b_{j}]\}.\]  
Let \(S_{j}\) be the set of values of the \(j\)-th decision variable that belong to _tame_ solution vectors. That is,  
\[S_{j}=\{x_{j}|(ax_{j}+(1-\alpha)x_{j}^{*})\in R_{j},\forall\alpha\in[0,1],x_{j} \in[a_{j},b_{j}]\}.\]  
Let \(x_{j}^{l}\) be the smallest \(x_{j}\) value and \(x_{j}^{r}\) be the largest \(x_{j}\) value of the _tame_ solutions, respectively. That is,  
\[x_{j}^{l}=\inf S_{j}\]  
and  
\[x_{j}^{r}=\sup S_{j}.\]  
Let \(l_{j}\) be the length of the interval \(S_{j}\). That is,  
\[l_{j}=x_{j}^{r}-x_{j}^{l}.\]  
By Lemma 1, \(l_{j}\) is non-negative and is bounded below by  
\[l_{j}\geq\frac{e}{L}\]  
where \(e\) is the error of \(f(\mathbf{x}_{-j}^{(t)},x_{j}^{(t)})\) with respect to \(f(\mathbf{x}_{-j}^{(t)},x_{j}^{*})\). That is,  
\[f(\mathbf{x}^{(t+1)})<f(\mathbf{x}^{(t)})\]0  
Figure 2 shows two examples of multimodal functions with the corresponding set of _tame_ solutions denoted by \(S_{j}\). **Definition 8** (Probability of _Tame_ Convergence).