# A Randomized Algorithm for Optimal PID Controllers
## 4 The Suggested Algorithm
In [8] it was shown that by taking \(h=r_{\infty}\) and \(m=\left\lceil e\cdot\sqrt{2\pi\ell}\right\rceil\) iterations in the outer-loop (where \(\ell:=qr\)), we have \(\hat{K}_{*}\in\mathcal{D}^{\left(0\right)}\) almost surely. Specifically, when \(\ell\geq 12\), it was suggested to take \(m=2\ell\) and \(\ell\times\ell\) orthogonal matrix \(U=\left[ \begin{array}{cccc}u_{1}&u_{2}&\cdots&u_{\ell}\end{array} \right]\), and to take the directions \(U_{j}^{\left(0\right)}=\pm mat\left(u_{j}\right),j=1,\ldots,\ell\) in the outer-loop. The outer-loop (\(i=1,\ldots,m\)) is used instead of executing the Ray-Shooting algorithm again and again, by taking \(\hat{K}^{\left(\mathrm{best}\right)}\) as the new vertex of the search cone instead of \(\hat{K}^{\left(0\right)}\). The replacement of \(\hat{K}^{\left(0\right)}\) can be avoided if \(r_{\infty}\) is chosen sufficiently large. The replacement of \(\hat{K}^{\left(0\right)}\) by \(\hat{K}^{\left(\mathrm{best}\right)}\) can be considered as a heuristic step, which is made instead of running the Ray-Shooting algorithm many times in order to generate \"the best starting point\", which is relevant only if we actually evaluate \(f\left(\hat{K}\right)\) on each such point and take the point with the best value as the best starting point. Since in any case, we evaluate \(f\left(\hat{K}\right)\) in the main algorithm, we could avoid the repeated execution of the Ray-Shooting algorithm. The outer-loop is similar to what is done in the Hide-And-Seek algorithm (see [24; 25]). The convergence in probability of the Hide-And-Seek algorithm can be found in [26]. ```
0: An algorithm for deciding \(\Omega\)-stability and an algorithm for computing \(f\left(\hat{K}\right)\). Input:\(\hat{K}^{(0)}\) such that \(\hat{A}_{\epsilon t}\left(\hat{K}^{(0)}\right)\) is \(\Omega\)-stable and \(1-\hat{K}^{(0)}_{3}C_{2}B_{2}\) is invertible (with the needed structure (6) if \(H_{2}\)-norm minimization is sought), \(\epsilon>0,r_{\infty}>0,h>0\) and integers \(m,n,s\). Output:\(\hat{K}_{s}\) that globally minimize \(f\left(\hat{K}\right)\) (or within \(\epsilon\) distance from a global minimum of \(f\left(\hat{K}\right)\) ) in \(h\)-radius closed-ball centered at \(\hat{K}^{(0)}\). 1. \(\hat{K}^{(best)}\leftarrow\hat{K}^{(0)}\)
2. \(f^{(best)}\gets f\left(\hat{K}^{(0)}\right)\)
3. \(i\gets 0\)
4. \(k\gets 1\)
5. **while**\(i\leq m\)**do
6. \(i\gets i+1\)
7. choose \(U^{(0)}\) such that \(\left\|U^{(0)}\right\|_{F}=1\), uniformly at random
8. set \(L^{(0)}\leftarrow\ \hat{K}^{(0)}+h\cdot U^{(0)}\)
9. **for**\(j=1\) to \(n\)**do
10. choose \(F\in\mathcal{R}_{\infty}\left(\epsilon\right)\) uniformly at random
11. **for**\(k=1\) to \(s\)**do
12. \(t\leftarrow\frac{k}{s}\)
13. \(\hat{K}\left(t\right)\leftarrow\left(1-t\right)\hat{K}^{(0)}+tF\)
14. **if**\(\hat{K}\left(t\right)\in\mathcal{S}_{\Omega}\)**then
15. **if**\(f\left(\hat{K}\left(t\right)\right)<f^{(best)}\)**then
16. \(\hat{K}^{(best)}\leftarrow\hat{K}\left(t\right)\)
17. \(f^{(best)}\gets f\left(\hat{K}\left(t\right)\right)\)
18. **endif**
19. **end if**
20. **end for**
21. **end for**
22. **if**\(i\geq k\left\lceil e\cdot\sqrt{2\pi\ell}\right\rceil\)**then**
23. \(\hat{K}^{(0)}\leftarrow\hat{K}^{(best)}\)
24. \(k\gets k+1\)
25. **end if**
26. **end while**
27. **if**\(l-\hat{K}^{(best)}_{3}C_{2}B_{2}\) is invertible then**
28. **return**\(\hat{K}^{(best)},f^{(best)}\)
29. **else**
30. **return** failure
31. **end if**
```  
**Algorithm 1** **Optimal PID controller randomized algorithm**  
Remark 3: _Please note that \(\hat{K}^{(0)}\) should satisfy the feasibility condition that \(I-\hat{K}^{(0)}_{3}C_{2}B_{2}\) is invertible, in order to raise the probability that \(I-\hat{K}^{(best)}_{3}C_{2}B_{2}\) would be invertible.