# A Randomized Algorithm for Optimal PID Controllers
## 4 The Suggested Algorithm  
Assume that \(\hat{K}^{\left(0\right)}\in int\left(\mathcal{S}_{\Omega}\right)^{q\times r}\) was found by the Ray-Shooting algorithm ([6]) or by any other method (see [21; 22; 23]). We assume that \(I-\hat{K}_{3}^{\left(0\right)}C_{2}B_{2}\) is invertible (and in addition, we assume that \(\hat{K}_{3}^{\left(0\right)}\) has the form (6) for some initial matrix \(Z^{\left(0\right)}\), when dealing with the \(H_{2}\)-norm minimization). Let \(h>0\) and let \(U^{\left(0\right)}\) be a unit vector w.r.t. the Frobenius norm, i.e., \(\left\|U^{\left(0\right)}\right\|_{F}=1\). Let \(L^{\left(0\right)}=\hat{K}^{\left(0\right)}+h\cdot U^{\left(0\right)}\) and let \(\mathcal{L}\) be the hyperplane defined by \(L^{\left(0\right)}+V\), where \(\left\langle V,U^{\left(0\right)}\right\rangle_{F}=0\). Let \(r_{\infty}>0\) and let \(\mathcal{R}_{\infty}\) denote the set of all \(F\in\mathcal{L}\), such that \(\left\|F-L^{\left(0\right)}\right\|_{F}\leq r_{\infty}\). Let \(\mathcal{R}_{\infty}\left(\epsilon\right)=\mathcal{R}_{\infty}+\overline{ \mathbb{B}\left(0,\epsilon\right)}\), where \(\overline{\mathbb{B}\left(0,\epsilon\right)}\) denotes the closed ball centered at \(0\) with radius \(\epsilon\)\(\left(0<\epsilon\leq\frac{1}{2}\right)\), with respect to the Frobenius norm on \(\mathbb{R}^{q\times r}\). Let \(\mathcal{D}^{\left(0\right)}=CH\left(K^{\left(0\right)},\mathcal{R}_{\infty} \left(\epsilon\right)\right)\) denote the convex-hull of the vertex \(\hat{K}^{\left(0\right)}\) with the basis \(\mathcal{R}_{\infty}\left(\epsilon\right)\). Let \(\mathcal{S}_{\Omega}^{\left(0\right)}=\mathcal{S}_{\Omega}\cap\mathcal{D}^{ \left(0\right)}\) and please note that \(\mathcal{S}_{\Omega}^{\left(0\right)}\) is compact (but generally not convex). We wish to minimize a continuous function \(f\left(\hat{K}\right)\) over the compact set \(\mathcal{S}_{\Omega}\cap\overline{\mathbb{B}\left(\hat{K}^{\left(0\right)},h \right)}\). Let \(\hat{K}_{*}\) denote a point in \(\mathcal{S}_{\Omega}\cap\overline{\mathbb{B}\left(\hat{K}^{\left(0\right)},h \right)}\) where a global minimum of \(f\left(\hat{K}\right)\) is accepted. Obviously, \(\hat{K}_{*}\in\mathcal{D}^{\left(0\right)}\), for some direction \(U^{\left(0\right)}\), as above. When dealing with the \(H_{2}\)-norm minimization, and if \(U^{\left(0\right)}=\left[ \begin{array}{cc}U_{1}^{\left(0\right)}&U_{2}^{ \left(0\right)}&U_{3}^{\left(0\right)}\end{array} \right]\) then, the directions will be constrained to have the form \(U_{3}^{\left(0\right)}=mat\left(L_{\left(C_{2}B_{1}\right)^{T}\otimes D_{1,2} }vec\left(Z\right)\right)\), in order that \(L^{\left(0\right)}\) would have the form (6). We will also restrict \(V\) as we have restricted \(U^{\left(0\right)}\), in order that any element of \(\mathcal{L}\) would have the structure (6). The suggested Algorithm 1 goes as follows:  
We start with a point \(\hat{K}^{\left(0\right)}\in int\left(\mathcal{S}_{\Omega}\right)\), found by the Ray-Shooting algorithm [6]. Assuming that \(\hat{K}_{*}\in\mathcal{D}^{\left(0\right)}\), the inner-loop (\(j=1,\ldots,n\)) uses the Ray-Shooting Method in order to find an approximation of the global minimum of the function \(f\left(\hat{K}\right)\) over \(\mathcal{S}_{\Omega}^{\left(0\right)}\) - the portion of \(\mathcal{S}_{\Omega}\) bounded in the cone \(\mathcal{D}^{\left(0\right)}\). The proof of convergence in probability of the inner-loop and its complexity can be found in [6] (see also [7]). In the inner-loop, we choose a search direction by choosing a point \(F\) in \(\mathcal{R}_{\infty}\left(\epsilon\right)\) - the base of the cone \(\mathcal{D}^{\left(0\right)}\). Next, in the most inner-loop (\(k=1,\ldots,s\)) we scan the ray \(\hat{K}\left(t\right):=\left(1-t\right)\hat{K}^{\left(0\right)}+tF\) and record the best controller on it. Repeating this sufficiently many times, we reach \(\hat{K}_{*}\) (or an \(\epsilon\)- neighborhood of it) with high probability, under the assumption that \(\hat{K}_{*}\in\mathcal{D}^{\left(0\right)}\).