# A Direct Search Algorithm for Global Optimization
## 3 A Direct Search Algorithm for Global Optimization
### Review of the Basic Geometric Results about \(n\)-Simplices  
Let \(\mathcal{V}=\{\mathbf{x}_{i}:i\in\mathbb{Z}_{[0,n]}\}\) be a set of \(n+1\) affinely-independent points in \(\mathbb{R}^{n}\), then the closed convex hull of \(\mathcal{V}\) is an \(n\)-simplex \(\Sigma\) with vertex set \(\mathcal{V}\), and it is denoted as follows:  
\[\Sigma=\mathbf{Co}(\mathcal{V}) \tag{6}\]  
Next, we introduce certain specific types of \(n\)-simplices that are non-standard in the literature. **Definition 1** (Right \(n\)-simplex). : A right \(n\)-simplex has a vertex, such that the \(n\) edges intersecting at it are pairwise orthogonal. This vertex is called the right vertex. **Definition 2** (Isosceles right \(n\)-simplex). : A right \(n\)-simplex, such that every edge intersecting at the right vertex has the same length \(\Delta\), is an isosceles right \(n\)-simplex of length \(\Delta\). **Definition 3** (Standard \(n\)-simplex). : The standard \(n\)-simplex is an isosceles right \(n\)-simplex of unit length. By locating the zero of \(\mathbb{R}^{n}\) in the right vertex, the standard \(n\)-simplex \(\Sigma^{0}_{n}\) is the \(n\)-dimensional polytope with vertex set \(\mathcal{V}=\{\mathbf{b}_{i}\in\mathbb{R}^{n}:i\in\mathbb{Z}_{[0,n]}\}\) where \(\mathbf{b}_{0}\) is the zero vector, and \(\mathbf{b}_{i}\) is the \(i\)-th element of the standard basis of \(\mathbb{R}^{n}\). Alternatively, the standard \(n\)-simplex can be defined as the intersection of the closed unit ball in the one-norm of \(\mathbb{R}^{n}\) and the non-negative orthant, _i.e._, \(\Sigma^{0}_{n}=\{\mathbf{x}\in[0,1]^{n}:\|\mathbf{x}\|_{1}\leq 1\}\). The content of an \(n\)-dimensional object is the measure of the amount of space inside its boundary: For instance, the content of a two-simplex is its area, and the content of a three-simplex is its volume. It can be proven by induction that the content of a standard \(n\)-simplex is \(\frac{1}{n!}\). A regular \(n\)-box is an \(n\)-dimensional box with edges of equal length. If the content of an \(n\)-simplex is not zero, then a geometric object of nonzero content can fit in its interior. The following lemma provides the edge length of the maximum regular \(n\)-box that can fit in the interior of a standard \(n\)-simplex. The regular \(n\)-box of maximum size that can be contained inside a standard \(n\)-simplex has edge length \(\frac{1}{n}\) and content \(\left(\frac{1}{n}\right)^{n}\). Proof. : The standard \(n\)-simplex is given as \(\Sigma_{n}^{0}=\{\mathbf{x}\in[0,1]^{n}:\|\mathbf{x}\|_{1}\leq 1\}\). The maximum \(n\)-box that can be allocated inside the standard \(n\)-simplex has a vertex in the origin, and it is oriented along the coordinate directions. The opposite vertex to the origin of this regular \(n\)-box has coordinates \(x_{i}=\frac{1}{n}\) for \(i\in\mathbb{Z}_{[1,n]}\); therefore, its edge length is \(\frac{1}{n}\), and its content is \(\left(\frac{1}{n}\right)^{n}\). The edges that intersect at the right vertex of a standard \(n\)-simplex are oriented along the coordinate directions, so these edge directions define a nonnegative orthant. Any direction inside this orthant can be expressed by a nonnegative \(n\)-dimensional vector of unit norm,, \(\langle\mathbf{d},\mathbf{d}\rangle=1\). A direction \(\mathbf{d}\) forms angles \(\theta_{i}\) with the coordinate directions whose cosines are called the directional cosines and are given by \(\cos\theta_{i}=\langle\mathbf{d},\mathbf{b}_{i}\rangle\). The following lemma proves that any direction \(\mathbf{d}\) contained in the nonnegative orthant has at least one directional cosine that never is less than \(\frac{1}{\sqrt{n}}\). The smallest directional cosine of any direction contained in the orthant formed by the edges intersecting at the right vertex of a standard \(n\)-simplex is never less than \(\frac{1}{\sqrt{n}}\). Proof.