## 2 Analysis of the Pure Random Orthogonal Search (PROS) Algorithm  
The PROS algorithm was originally proposed by [PERSON] et al. in [15]. We describe it with our revised notation as follows:  
Initially, a candidate solution vector \(\mathbf{x}^{(0)}\) is generated randomly from \(\Omega\) (lines 1 and 2). Then, for each iteration \(t\), \(j\) is chosen randomly from \(1\) to \(D\) (line 4) and a real number \(r\) is drawn randomly with uniform distribution within the search space of the \(j\)-th decision variable (line 5). A new candidate solution vector \(\mathbf{y}\) is obtained by replacing the value of the \(j\)-th decision variable of the current best solution vector \(\mathbf{x}^{(t)}\) with \(r\) (lines 6 and 7). The new candidate solution vector \(\mathbf{y}\) is evaluated and the new best solution vector \(\mathbf{x}^{(t+1)}\) is then updated based on the comparison result between \(f(\mathbf{y})\) and \(f(\mathbf{x}^{(t)})\). If \(f(\mathbf{y})\) is smaller, \(\mathbf{y}\) is accepted as the new best solution vector. Otherwise, \(\mathbf{y}\) is rejected (lines 8 to 12). The iteration counter \(t\) is updated and the search process is repeated until a termination criterion is met (lines 13 and 14). Finally, the best solution vector found by the algorithm is returned as the final result (line 15). In the following analysis, we assume the algorithm runs continuously until the global optimum is found (defined below of this section). It is because we are interested in analyzing its ultimate performance. In practice, it may take an infinitely long time to reach the global optimum. Therefore, other termination criteria are usually adopted. For example, the algorithm stops when no improvement is made after a certain number of iterations or when a pre-defined maximum number of iterations is reached. The error of the algorithm after running for \(t\) iterations is given by  
\[e_{t}=f(\mathbf{x}^{(t)})-f(\mathbf{x}^{*}).\]  
Here, \(\mathbf{x}^{(t)}\) is the solution vector found by the algorithm in the \(t\)-th iteration and is also the best solution vector found by the algorithm after \(t\) iterations. It is because the values of the solution vectors found by PROS is monotonically non-increasing. That is,  
\[f(\mathbf{x}^{(t)})\leq f(\mathbf{x}^{(t-1)})\leq\cdots\leq f(\mathbf{x}^{(0)}),\]  
Consider the pseudo code from line 8 to line 12 of Algorithm 1. In the \(t\)-th iteration, when a better solution \(\mathbf{y}\) is found, it will be assigned to \(\mathbf{x}^{(t+1)}\). In this case, \(f(\mathbf{x}^{(t+1)})<f(\mathbf{x}^{(t)})\). When no better solution is found in the \(t\)-th iteration, \(\mathbf{x}^{(t)}\) will be assigned to \(\mathbf{x}^{(t+1)}\). In this case, \(f(\mathbf{x}^{(t+1)})=f(\mathbf{x}^{(t)})\). Combining the two conditions, \(f(\mathbf{x}^{(t+1)})\leq f(\mathbf{x}^{(t)})\) and the inequalities then follow. ```
input :nil output : the best solution vector \(\mathbf{x}^{(t)}\) found by the algorithm \(t\gets 0\);  Initialize \(\mathbf{x}^{(t)}=(x_{1},x_{2},\ldots,x_{D})\) randomly from \(\Omega=[a_{1},b_{1}]\times[a_{2},b_{2}]\times\cdots\times[a_{D},b_{D}]\); repeat  Sample a random integer \(j\in\{1,\ldots,D\}\);  Sample a random real number \(r\sim\mathcal{U}(a_{j},b_{j})\); \(\mathbf{y}\leftarrow\mathbf{x}^{(t)}\); \(y_{j}\gets r\); if\(f(\mathbf{y})<f(\mathbf{x}^{(t)})\)then \(\mathbf{x}^{(t+1)}\leftarrow\mathbf{y}\); else \(\mathbf{x}^{(t+1)}\leftarrow\mathbf{x}^{(t)}\);  end if \(t\gets t+1\); until a termination criterion is met; return\(\mathbf{x}^{(t)}\)
```  
**Algorithm 1**Pure Random Orthogonal Search (PROS)  
**Definition 1** (Region of Global Optimum). : _It is said that a candidate solution vector \(\mathbf{x}\) is in the region of global optimum \(R_{e}\) if the error of \(\mathbf{x}\) is not larger than \(e\). That is,_  
\[R_{e}=\{\mathbf{x}:\mathbf{x}\in\Omega\text{ and }f(\mathbf{x})-f^{*}\leq e\},\]  
_where \(e\) is a small positive real number denoting the tolerance of error._  
**Definition 2** (Convergence Time).