# On Application of the Ray-Shooting Method for LQR via Static-Output-Feedback
## 2 The Practical Algorithm for the Problem of LQR via SOF
The convergence in probability of the Hide-And-Seek algorithm can be found in [25]. **Remark 1**. : _The volume of \(\overline{\mathbb{B}\left(K^{\left(0\right)},h\right)}\) is given by \(\frac{n^{\ell/2}}{\Gamma\left(\ell/2+1\right)}\cdot h^{\ell}\) where \(\ell:=qr\) and \(\Gamma\) is the known \(\Gamma\)-function. The volume of \(\mathcal{D}^{\left(0\right)}\) is given approximately (and exactly when \(\epsilon=0\)) by \(\frac{h}{\ell}\cdot\frac{\pi^{\left(\ell-1\right)/2}}{\Gamma\left(\ell-1 \right)/2+1}\cdot r_{\infty}^{\ell-1}\). Thus, by taking \(r_{\infty}=h\), the portion of \(\overline{\mathbb{B}\left(K^{\left(0\right)},h\right)}\) covered by \(\mathcal{D}^{\left(0\right)}\) (i.e., the probability that \(K_{*}\in\mathcal{D}^{\left(0\right)}\)) is given by \(\frac{\Gamma\left(\ell/2+1\right)}{\ell\cdot\sqrt{\pi}\cdot\Gamma\left(\left( \ell-1\right)/2+1\right)}\). Let \(\Theta\) denote the known relation between functions \(f,g:\mathbb{N}\to R\) defined by \(f\left(n\right)=\Theta\left(g\left(n\right)\right)\) if and only if \(\lim_{n\rightarrow\infty}\frac{f\left(n\right)}{g\left(n\right)}=1\). Since \(\Gamma\left(\ell/2+1\right)=\Theta\left(\sqrt{2\pi}e^{-\ell/2}\left(\frac{ \ell}{2}\right)^{\frac{\ell+1}{2}}\right)\) and since \(\left(\frac{\ell-1}{\ell}\right)^{\ell/2}\to e^{-1/2}\) when \(\ell\rightarrow+\infty\), it follows that_  
\[\frac{\Gamma\left(\ell/2+1\right)}{\ell\cdot\sqrt{\pi}\cdot\Gamma\left(\left( \ell-1\right)/2+1\right)}=\Theta\left(\frac{1}{e\cdot\sqrt{2\pi\ell}}\right).\]  
_Therefore, by taking \(m=\left\lceil e\cdot\sqrt{2\pi\ell}\right\rceil\) iterations in the outer-loop, we have \(K_{*}\in\mathcal{D}^{\left(0\right)}\) almost surely. Specifically, when \(\ell\geq 12\), we suggest taking \(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 complexity of the suggested practical algorithm measured as the number of its arithmetic operations is given as follows:  
* computing the matrix \(P\left(K\left(t\right)\right)\) as in (5) takes \(O\left(\left(p^{2}\right)^{3}\right)=O\left(p^{6}\right)\), since the dominant operation is the inversion of the \(p^{2}\times p^{2}\) matrix there. * checking \(K\left(t\right)\in\mathcal{S}_{\alpha}\) by checking the \(\alpha\)-stability of \(A_{cl}\left(K\left(t\right)\right)\) (as well as computing \(\sigma\left(K\left(t\right)\right)\)), takes \(O\left(p^{3}\right)\) for computing the characteristic polynomial of \(A_{cl}\left(K\left(t\right)\right)\) (of \(P\left(K\left(t\right)\right)\), respectively) and \(O\left(p\log_{2}^{2}\left(p\right)\left(\log_{2}^{2}\left(p\right)+\log_{2}^{ 2}\left(b\right)\right)\right)\) for computing approximations \(\tilde{\lambda}_{j}\) for all the eigenvalues \(\lambda_{j},j=1,\ldots,p\) of \(A_{cl}\left(K\left(t\right)\right)\) (of \(P\left(K\left(t\right)\right)\), respectively), with accuracy \(\left|\tilde{\lambda}_{j}-\lambda_{j}\right|<2^{2-\frac{b}{p}}\) where \(b\geq p\log_{2}\left(p\right)\). The approximated eigenvalues can be computed to the accuracy \(2^{2-\frac{b}{p}}=\epsilon\), with \(b=\left(2+\log_{2}\left(\frac{1}{\epsilon}\right)\right)p\), by the algorithm of [PERSON] (see [26]). We end up with \(O\left(p^{3}\right)\) for these operations. * computing uniformly distributed \(q\times r\) matrix takes \(O\left(\max\left(q,r\right)^{3}\right)\) operations. We therefore have a total complexity of \(O\left(mns\left(\max\left(q,r\right)^{3}+p^{6}\right)\right)\). Let a closed \(\epsilon\)-neighborhood of \(K_{*}\) in \(D^{\left(0\right)}\) be defined by \[\mathcal{S}_{\alpha}^{\left(0\right)}\left(\epsilon\right)=\left\{ \begin{array}{ ccc}K\in\mathcal{S}_{\alpha}^{\left(0\right)}&\left|\sigma\left(K\right)\leq \sigma\left(K_{*}\right)+\epsilon\end{array}