## 3 Nelder-Mead Algorithm for the Optimal Completion of Incomplete PCMs
### Nelder-Mead Algorithm
To solve the constrained eigenvalue minimization problem (4), we first transform the coordinates \(x_{i}\) for all \(i=1,2,\ldots,k\) using transformation (6) and then we apply the standard Nelder-Mead algorithm for the unconstrained problem \(\min f(\mathbf{x})\), \(\mathbf{x}\in\mathbb{R}_{+}^{k}\). Here, we use the standard Nelder-Mead algorithm implementation, where the standard values are \(\rho=1,\ \chi=2,\ \gamma=1/2\), and \(\sigma=1/2\), which are often suggested in the literature [33; 39; 44; 56; 57]. The algorithm starts with an initial simplex with \(k+1\) non-degenerate vertices \(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{k+1}\) around a given initial point \(\mathbf{x}_{0}\). Vertex \(\mathbf{x}_{1}\) can be chosen arbitrarily. However, the most common choice of \(\mathbf{x}_{1}\) in implementation is \(\mathbf{x}_{1}=\mathbf{x}_{0}\) in order to make proper restarts of the algorithm [41]. The remaining \(k\) vertices are then generated on the basis of step-size 0.05 in the direction of the unit vector \(\mathbf{e}_{j}=(0,0,\ldots,1,\ldots,0)\in\mathbb{R}^{k}\)[44]:  
\[\mathbf{x}_{j+1}=\mathbf{x}_{0}+0.05\mathbf{e}_{j}\,\forall j=1,\ldots,k. \tag{9}\]  
The initial simplex \(S_{0}\) is a convex hull of \(k+1\) vertices \(\mathbf{x}_{1},\ldots,\mathbf{x}_{k},\mathbf{x}_{k+1}\in\mathbb{R}_{+}^{k}\). The ordering of the vertices \(S_{0}\) should satisfy the increasing function values of the form:  
\[f(\mathbf{x}_{1})\leq f(\mathbf{x}_{2})\leq\ldots\leq f(\mathbf{x}_{k})\leq f (\mathbf{x}_{k+1}). \tag{10}\]  
We consider \(\mathbf{x}_{1}\) as the best vertex (vertex that results in the minimum function value) and \(\mathbf{x}_{k+1}\) as the worst vertex (a vertex which results in the maximum function value). The centroid \(\overline{\mathbf{x}}\) is calculated as \(\overline{\mathbf{x}}=\frac{1}{k}\sum_{j=1}^{k}\mathbf{x}_{j}\), which is the average of the non-worst \(k\) vertices, i.e., all vertices (points) except for \(\mathbf{x}_{k+1}\). According to [39; 56], the description of one simplex iteration of the standard Nelder-Mead algorithm is presented in Algorithm 1. At each iteration, the simplex vertices are ordered as \(\mathbf{x}_{1},\ldots,\mathbf{x}_{k},\mathbf{x}_{k+1}\) according to the increasing values of the objective function. Note that the new working simplex in a _nonshrink_ iteration of the algorithm has only one new vertex. In this case, the new vertex replaces the worst vertex \(\mathbf{x}_{k+1}\) in the former simplex S. In the case of a _shrink_ step, the new simplex S contains \(k\) new vertices: \(\mathbf{x}_{2},\mathbf{x}_{3}\ldots,\mathbf{x}_{k+1}\). In this situation, vertex \(\mathbf{x}_{1}\) will be the old vertex from the former simplex S.  
Now we can solve the constrained eigenvalue minimization problem (4) using the standard Nelder-Mead Algorithm 1, equivalent to MATLAB's fminsearch algorithm, in connection with _coordinate transformation_ (6) for each simplex iteration; henceforth, we shall simply call it _Nelder-Mead algorithm_. For the respective given values to TolX, TolFun, MaxIter, and MaxFunEvals, the _Nelder-Mead algorithm_ terminates when one of the following three conditions is satisfied:  
(C1) \(\max_{2\leq j\leq k+1}||\mathbf{x}_{j}-\mathbf{x}_{1}||_{\infty}\leq\) TolX and \(\max_{2\leq j\leq k+1}|f(\mathbf{x}_{j})-f(\mathbf{x}_{1})|\leq\) TolFun;  
(C2) The number of iterations reaches MaxIter;  
(C3) The number of function evaluations reaches MaxFunEvals. It is important to note that problem (4) is a non-convex problem, but this can be transformed into a convex minimization problem by using exponential parameterization [15]. From now on, we consider that our optimization problem is convex and constrained with scalar bounds. ```
Compute an initial simplex \(S_{0}\). Compute \(f_{j}=f(\mathbf{x}_{j})\), \(j=1,2,\ldots,k+1\). Sort the vertices \(S_{0}\) so that (10) holds. \(S\gets S_{0}\)\(\triangleright\) A simplex \(S=\{\mathbf{x}_{j}\}_{j=1,\ldots,k+1}\) is updated iteratively.