# On Application of the Ray-Shooting Method for LQR via Static-Output-Feedback
## 2 The Practical Algorithm for the Problem of LQR via SOF
\right.\right\}.\] Let the idealized algorithm be the algorithm that samples the search space \(D^{\left(0\right)}\) until hitting \(\mathcal{S}_{\alpha}^{\left(0\right)}\left(\epsilon\right)\), where the sampling is according to a general p.d.f. \(g\) and a related generator \(G\). For \(0<\beta<1\), the number of iterations needed to guarantee a probability of at least \(1-\beta\) to hit \(\mathcal{S}_{\alpha}^{\left(0\right)}\left(\epsilon\right)\) is given by \[\left\lceil\frac{M_{g}Vo\ell\left(D^{\left(0\right)}\right)}{m_{g}Vo\ell\left( \mathcal{S}_{\alpha}^{\left(0\right)}\left(\epsilon\right)\right)}\left| \ln\left(\beta\right)\right|\right\rceil,\] (7)where Vo\(\ell\) denotes the volume of the related set and \(M_{g},m_{g}\) are the essential-supremum and essential-infimum of \(g\) over \(D^{(0)}\), respectively (see [16]). Similarly to what is done in [16], one can show that the last is \(O\left(\frac{|\ln(\beta)|hM_{g}}{\varepsilon m_{g}}\left(\frac{r_{\infty}}{r_{ \varepsilon}}\right)^{qt}\right)\), where \(r_{\varepsilon}\) is a radius of a ball of a basis of a cone with height \(\epsilon\) and vertex \(K_{*}\) that has a volume that equals to \(V\circ\ell\left(\mathcal{S}_{\alpha}^{(0)}\left(\epsilon\right)\right)\). This results in an exponential number of iterations, but if we restrict the input of the algorithm to systems with \(q,r\) satisfying \(q\leq q_{0},r\leq r_{0}\) when \(q_{0},r_{0}\) are fixed, then, the number of iterations would be \(O\left(\frac{|\ln(\beta)|hM_{g}}{\varepsilon m_{g}}\left(\frac{r_{\infty}}{r_ {\varepsilon}}\right)^{q_{0}r_{0}}\right)\), i.e., polynomial in \(\left(\frac{r_{\infty}}{r_{\varepsilon}}\right)\)--which can be considered as the true size of the problem (for a fixed \(p,q,r\)). In this sense we can say that the algorithm is efficient. The total number of arithmetic operations of the idealized algorithm that guarantees a probability at least \(1-\beta\) to hit \(\mathcal{S}_{\alpha}^{(0)}\left(\epsilon\right)\) is therefore given by \(O\left(\frac{|\ln(\beta)|h}{\epsilon}\left(\frac{r_{\infty}}{r_{\varepsilon}} \right)^{q_{0}r_{0}}\left(\max\left(q,r\right)^{3}+p^{6}\right)\right)\), since sampling points according to the uniform distribution \(g\) (and therefore \(m_{g}=M_{g}=1\)) and the related generator \(G\), takes \(O\left(\max\left(q,r\right)^{3}\right)\). For the sake of comparison, which will be presented in the next section, we bring here, in Algorithm 2, the algorithm of [PERSON] and [PERSON] (see [5]) adjusted to our formulation of the problem, which we call: the MC Algorithm. To the best of our knowledge, this is the best algorithm for LQR via SOF published so far. ```
Input:\(0<\epsilon\leq\frac{1}{2},\alpha,h,r_{\infty}>0\), integers: \(m,n,s>0\), \(\text{controllable pairs }(A,B)\) and \(\left(A^{T},C^{T}\right)\), \(\text{matrices }Q>0,R\geq 0\) and \(K^{(0)}\in int\left(


```
Input:\(0<\epsilon,\alpha\), integers: \(m,s>0\),  controllable pairs \(\left(A,B\right)\) and \(\left(A^{\mathrm{T}},C^{\mathrm{T}}\right)\),  matrices \(Q>0,R>0\) and \(K_{0}\in int\left(\mathcal{S}_{\alpha}\right)\). Output:\(K\in\mathcal{S}_{\alpha}\) close as possible to \(K_{*}\). 1. \(j\gets 0\)
2. \(A_{0}\gets A-BK_{0}C\)
3. \(P_{0}\leftarrow-mat\left( \begin{array}{c}\left(I_{p}\otimes A_{0}^{T}+A_{0 }^{T}\otimes I_{p}\right)^{-1}\cdot\\ vec\left(Q+C^{\mathrm{T}}K_{0}^{T}\,RK_{0}C\right)\end{array} \right)\)
4. \(S_{0}\leftarrow-mat\left(\left(I_{p}\otimes A_{0}+A_{0}\otimes I_{p}\right)^{- 1}\cdot vec\left(I_{p}\right)\right)\)
5. \(\sigma_{max}\left(K_{0}\right)\leftarrow\max\left(\sigma\left(P_{0}\right)\right)\)
6. \(\Delta K_{0}\gets R^{-1}B^{\mathrm{T}}P_{0}S_{0}C^{\mathrm{T}}\left(CS_{0} C\right)^{-1}-K_{0}\)
7. \(flag\gets 0\)
8. for \(k=1\) to \(s\) do
8.1. \(t\leftarrow\frac{k}{s}\)
8.2. \(K\left(t\right)\leftarrow\left(1-t\right)K_{0}+t\Delta K_{0}\)
8.3. if \(K\left(t\right)\in\mathcal{S}_{\alpha}\) then
8.3. \(A\left(t\right)\gets A-BK\left(t\right)C\)
8.3. \(P\left(t\right)\leftarrow-mat\left(