General information of the systems and initial values.
Randomized and deterministic algorithms for the problem of LQR optimal control via static-output-feedback (SOF) for discrete-time systems are suggested in this chapter. The randomized algorithm is based on a recently introduced randomized optimization method named the Ray-Shooting Method that efficiently solves the global minimization problem of continuous functions over compact non-convex unconnected regions. The randomized algorithm presented here has a proof of convergence in probability to the global optimum. The suggested deterministic algorithm is based on the gradient method and thus can be proved to converge to local optimum only. A comparison between the algorithms is provided as well as the performance of the hybrid algorithm.
- control systems
- optimal control
- discrete-time systems
- state-space models
- NP-hard control problems
- randomized algorithms
- deterministic algorithms
The application of static-output-feedbacks (SOFs) for linear-quadratic regulators (LQR) is very attractive, since they are cheap and reliable and their implementation is simple and direct, because their components has direct physical interpretation in terms of sensors amplification rates and actuator activation power. Moreover, the long-term memory of dynamic feedbacks is useless for systems subject to random disturbances, to fast dynamic loadings or to random bursts and impulses, and the application of state feedbacks is not always possible due to unavailability of full-state measurements (see, e.g., ). Also, the use of SOF avoids the need to reconstruct the state by Kalman filter or by any other state reconstructor.
On the other hand, in practical applications, the entries of the needed SOFs are bounded, and since the problem of SOFs with interval constrained entries is NP-hard (see [2, 3]), one cannot expect the existence of a deterministic efficient (i.e., polynomial-time) algorithm to solve the problem. Randomized algorithms are thus natural solutions to the problem. The probabilistic and randomized methods for the constrained SOF problem and robust stabilization via SOFs (among other hard problems) are discussed in [4, 5, 6, 7]. For a survey of the SOF problem see , and for a recent survey of the robust SOF problem see .
The Ray-Shooting Method was recently introduced in , where it was used to derive the Ray-Shooting (RS) randomized algorithm for the minimal-gain SOF problem, with regional pole assignment, where the region can be non-convex and unconnected. The Ray-Shooting Method was successfully applied recently also to the following hard complexity control problems for continuous-time systems:
Structured and structured-sparse SOFs (see )
LQR via SOF for continuous-time LTI systems (see )
LQR optimal, -optimal, and -optimal proportional-integral-differential (PID) controllers (see )
Robust control via SOF (see )
The contribution of the research presented in the current chapter is as follows:
The randomized algorithm presented here (which we call the RS algorithm) is based on the Ray-Shooting Method (see ), which opposed to smooth optimization methods, and has the potential of finding a global optimum of continuous functions over compact non-convex and unconnected regions.
The RS algorithm has a proof of convergence in probability and explicit complexity.
Experience with the algorithm shows good quality of controllers (in terms of reduction of the LQR functional value with relatively small controller norms), high percent of success, and good run-time, for real-life systems. Thus, the suggested practical algorithm efficiently solves the problem of LQR via SOF for discrete-time systems.
The RS algorithm does not need to solve any Riccati or quadratic matrix equations (QMES) and thus can be applied to large systems.
The RS algorithm is one of the few, dealing with the problem of LQR via SOF for discrete-time systems.
A deterministic algorithm for the problem that generalizes the algorithm of Moerder and Calise , for discrete-time systems, is given (we call it the MC algorithm). The MC algorithm has a proof of convergence to a local optimum only, and it needs other algorithms for computing initial stabilizing SOF.
A comparison between the RS and the MC algorithms, as well as the performance of the hybrid algorithm, for real-life systems, is provided.
The reminder of the chapter is organized as follows:
In Section 2 we formulate the problem and give some useful lemmas (without a proof). In Section 3, we introduce the randomized algorithm for the problem of LQR via SOF for discrete-time LTI systems. Section 4 is devoted to the deterministic algorithm for the problem. In Section 5, we give the results of the algorithms for some real-life systems. Finally, in Section 6 we conclude with some remarks.
Let a discrete-time system be given by
where , , and . Let the LQR cost functional be defined by
where and . Let be the SOF, and let denote the closed-loop matrix. Let denote the open unit disk, let , and let denote the set of all with (where is the absolute value of ). For a square matrix , we denote by its spectrum. For any rectangular matrix , we denote by its Moore-Penrose pseudo-inverse. By we denote the Frobenius norm of , and by we denote the spectral norm of . By and , we denote the (left and right) orthogonal projections and on the spaces and , respectively. For a topological space and a subset , we denote by the interior of , i.e., the largest open set included in . By we denote the closure of , i.e., the smallest closed set containing , and by we denote the boundary of . Let denote the set of all matrices such that (i.e., stable in the discrete-time sense), and let denote the set of all matrices such that . If the last is nonempty, we say that is -stable and we call the degree of stability. Let be given. Substitution of the SOF into (2) yields:
Since and is stable, it follows that the Stein equation
has a unique solution , given by
Thus, when is known, we search for that minimizes the functional
Now, since for any , with equality in the worst case, therefore
Thus, when is unknown, we search for , such that is minimal. Note that if is an eigenvalue of and is a corresponding eigenvector, then (4) yields . Therefore, , and thus, minimizing results in eigenvalues that are getting closer to the boundary of . Since , the degree of stability, is important to get satisfactory decay rate of the state to , and for disturbance rejection, we allow the user of the algorithms to determine . Note that too high value of might result in nonexistence of any SOF for the system or in complicating the search for a starting SOF. Higher values of result in higher values of the optimal value of the LQR functional, i.e., higher energy consumption for decaying the disturbance to .
The functionals and are generally not convex since their domain of definition (and therefore ) is generally non-convex. Necessary conditions for optimality for continuous-time systems were given as three QMEs in [15, 16, 17, 18]. Necessary and sufficient conditions for optimality for continuous-time systems, based on linear matrix inequalities (LMI), were given in [19, 20, 21]. However, algorithms based on these formulations are generally not guaranteed to converge, seemingly because of the non-convexity of the coupled matrix equations or inequalities, and when they converge, it is to a local optimum only.
In the sequel, we will use the following lemmas, given here without proofs.
Lemma 2.1. We have:
The equation has solutions if and only if or equivalently, if and only if . In this case, the set of all solutions is given by
where is arbitrary.
The equation has solutions if and only if or equivalently, if and only if . In this case, the set of all solutions is given by
where is arbitrary.
Lemma 2.2. We have:
Let be matrices with sizes , respectively. Then
Let be matrices with sizes , respectively. Then
3. The randomized Ray-Shooting Method-based algorithm
The Ray-Shooting Method works as follows, for general function minimization: let be a continuous function defined over some compact set . Let be given and assume that we want to compute such that up to , i.e., to find in the set . Let be given, let and let denote the search space, which is a subset of the epigraph of . Let denote the cylinder enclosed between and the level . Let . Let and note that . Then, we choose in randomly, according to some distribution, and we define the ray as . We scan the ray and choose the largest such that (actually, we scan the ray from in equal-spaced points and take the first for which this happens). We define and update sets , , and by replacing with , where . Let , , and denote the updated sets. We continue the process similarly from , and we define a sequence . Note that for any , unless we have for some (in which the process is ceased). One can show that the sequence converges (in probability) to a point in . Note that shooting rays from the points of local minimum have positive probability to hit (under the following mild assumption), because any global minimum is visible from any local minimum. Moreover, for a given level of certainty, we hit in a finite number of iterations (see Remark 3.1 below). Practically, we may stop the algorithm if no improvement is detected within a window of of the allowed number of iterations. The function need not be smooth or even continuous. It only needs to be well defined and measurable over the compact domain , and should have non-negligible measure (i.e., should have some positive volume). Obviously, global minimum points belong to the boundary of the search space , and actually such points are where the distance between the compact sets and in is accepted. This is essential for the efficiency of the Ray-Shooting Method, although we raised the search space dimension from to .
In order to apply the Ray-Shooting Method for the LQR via SOF problem, we need the following definitions: assume that was found by the RS algorithm (see ) or by any other method (see [22, 23, 24]). Let and let be a unit vector (actually a matrix, but we consider here the space of matrices as a normed vector space) with respect to the Frobenius norm, i.e., . Let and let be the hyperplane defined by , where . Here is the tangent space at to the closed ball centered at with radius , with respect to the Frobenius norm on . Let and let denote the set of all , such that . Let , where denotes the closed ball centered at with radius (). Let denote the convex hull of the vertex with the basis . Let and note that is compact (but generally not convex). We wish to minimize the continuous function (or the continuous function , when is known) over the compact set . Let denote a point in where the minimum of is accepted. Obviously, , for some direction from .
The Ray-Shooting Algorithm 1 for the LQR via SOF problem, works as follows: we start with a point , found by the RS algorithm (see ). Assuming that , the inner loop () uses the Ray-Shooting Method in order to find an approximation of the global minimum of the function over —the portion of bounded in the cone . The proof of convergence in probability of the inner loop and its complexity (under the above-mentioned assumption) can be found in  (see also ). In the inner loop, we choose a search direction by choosing a point in —the base of the cone . Next, in the most inner loop (), we scan the ray and record the best controller on it. Repeating this sufficiently many times, we reach (or an neighborhood of it) with high probability, under the assumption that (see Remark 3.1).
The reasoning of the Ray-Shooting Method is that sampling the whole search space will lead to the probabilistic method that is doomed to the “curse of dimensionality,” which the method tries to avoid. This is achieved by slicing the search space into covering cones (is the number of cones allowed), because any point in the cone is visible from its vertex. At each cone we shoot rays (is the number of rays per cone) from its node toward its basis, where each ray is sampled from its head toward its tail, while updating the best point found so far. Note that the global minimum of over any compact subset of is achieved on the boundary of the related portion of the epigraph of . Therefore, we can break the most inner loop; in the first moment, we find an improvement in . This bypasses the need to sample the whole search space (although we raise by the search space dimension) and explains the efficiency of the Ray-Shooting Method in finding global optimum. Another advantage of the Ray-Shooting Method which is specific to the problem of LQR via SOF is that the search is concentrated to the parameter space (the -dimension space where the rests) and not to the certificate space (the -dimension space where the Lyapunov matrices rests). Thus, the method avoids the need to solve any Riccati, LMI, and BMI equations, which might make crucial difference for large-scale systems (i.e., where ).
1. compute as in (5)
6. choose such that , uniformly at random
9. choose , uniformly at random
14. compute as in (5)
Remark 3.1. In  it is shown that by taking iterations in the outer loop, we have , for some direction , almost surely. Let denote the set . Then, the total number of arithmetic operations of the RS algorithm that guarantees a probability of at least to hit is given by , for systems with for fixed , where is the radius of the basis of a cone with height that has the same volume as of ; see [10, 11, 12]. This is a polynomial-time algorithm by restricting the input and by regarding as the size of the problem.
4. The deterministic algorithm
The deterministic algorithm we introduce here as Algorithm 2 (which we call the MC algorithm) generalizes the algorithm of Daniel D. Moerder and Anthony A. Calise (see ) to the case of discrete-time systems. To the best of our knowledge, this is the best algorithm for LQR via SOF published so far, in terms of rate of convergence (to local minimum).
Here, we wish to minimize the LQR functional
under the constraints
under the constraint , where are the Lagrange multipliers. We have
where . Note that . Let the Lagrangian be defined by
for any any and any such that . The necessary conditions for optimality are , , and .
Now, using Lemma 2.2, we have
where the last passage is affordable because . Note that the last with the stability of implies that .
We also have
Thus, if is invertible, then
which is equivalent to
where is arbitrary matrix (and we may take , unless some other constraints on are needed). Note that if condition (12) does not happen, then . We conclude with the following theorem:
Theorem 4.1. Assume that given by (10) is minimized locally at some point , , and such that . Then
Since is minimal in some neighborhood of , it follows that , , and .
The condition is just
which with and implies that is stable. Now, since , it follows that is invertible, and therefore,
Since is invertible, implies that
Finally, implies that , which in view of Lemma 2.1 implies and
where is some matrix.
Note that the equations are coupled tightly, in the sense that and need , while needs and . Note also the cubic dependencies (that can be made quadratic by introducing new variables). These make the related QMEs non-convex and, therefore, hard to compute.
Remark 4.1. When is unknown, it is customary to assume that is uniformly distributed on the unit sphere, which implies that , where is the expectation operator. Thus, changing the problem to that of minimizing amounts to replacing with
Therefore, there is change in Algorithm 2.
Remark 4.2. The convergence of Algorithm 2 to local minimum can be proved similarly to the proof appearing in , under the assumptions that is nonempty and that is detectable (here, we do not need this condition because of the assumption that ). The convergence can actually be proved for the more general problem that adds to the LQR functional, thus minimizing also the Frobenius norm of . In this context, note that by adding to the LQR functional will lose the argument, and there will be a need to more general proof, because in the proof appearing in , the demand is for smooth function of , while is continuous but not Lipschitz continuous. The RS algorithm can use any continuous function of and can deal also with sparse SOFs for LQR and with regional pole-placement SOFs for LQR.
Example 4.1. In the following simple example, we illustrate the notions appearing in the definition of the RS algorithm, and we demonstrate the operation of the RS algorithm. Consider the unstable system
where we look for SOF stabilizing the system while reducing the LQR functional (2) with . Let then
with characteristic polynomial . Applying the Y. Bistritz stability criterion (see ), we have
where is the number of sign variations in the set. According to the Bistritz criterion, the system is stable if and only if . We conclude that is the set of all such that or , where the last branch is empty (which could have make the set non-convex). The set appears in Figure 1 as the blue region, where the golden star is the analytic global optimal solution (computed by the related discrete algebraic Riccati equation).
In Figure 1, we can see how the RS algorithm works: we fix , and we set for a single iteration, where the single cone is sampled along rays and each ray is sampled times. The sampled points are circled, where red circles indicate infeasible or non-improving points and the black circles indicate improving points. The green star point is the initial point found by the Ray-Shooting algorithm for minimal-norm SOF. The bold black circle is the boundary of the closed circle . We choose randomly to define the search direction, and we set to be the point where the direction meets the boundary of the circle. is the tangent line at to the circle, and is the width segment on the line, inflated by . The search cone is the related black triangle. Here is just the portion of the blue region inside the triangle, and we can see that the assumption that is in force. For the current problem , and therefore, by making iterations, will be inside some triangle almost surely.
The algorithm chooses in the basis of the triangle and defines to be the ray from to . The ray is sampled at equally spaced points, and the best feasible point is recorded.
In Figure 2, we can see that iterations suffice to include in some triangle and to find improving points very close to . In Figure 3, we can see that when we allow iterations, after iterations, the center is switched to the best point found so far (see lines in Algorithm 1). This is done in order to raise the probability to hit or its -neighborhood, and as we can see, the final best point (green star) is very close to (Figure 4).
The results of the algorithm for and iterations are the following. Note that , and note the “huge variations” the function has.
For we had
Note that in this case, the algorithm makes no improvement, while the RS and RS + MC have very close values to the global optimal value, with slightly better value for the RS + MC, over the RS algorithm.
For we had
For we had
In Figure 5, the initial condition response of the open-loop system is given. One can see the unstable mode related to the unstable eigenvalue . In Figures 6
In the following experiments, we applied Algorithms 1 and 2, for systems taken from the libraries [26, 27, 28]. The systems given in these libraries are real-life continuous-time systems. In order to get related discrete-time systems, we sampled the systems using the Tustin method with sampling rate . We took only the systems for which the RS algorithm succeeded in finding SOFs for the continuous-time systems (see , Table 8, p. 231). In order to initialize the MC Algorithm, we also used the RS algorithm to find a starting -stabilizing SOF. In all the experiments, we used ; , for the RS algorithm; and , for the MC Algorithm, in order to get the same number of total iterations and the same number of iterations for the local search. We took in all the cases.
The stability margin column of Table 1 relates to for which the absolute value of any eigenvalue of the closed loop is less than . The values of in Table 1 relates to the largest for which the RS algorithm succeeded in finding a starting SOF . As we saw above, it is worth searching for a starting point that maximizes . This can be achieved efficiently by running a binary search on the and using the RS algorithm as an oracle. Note that the RS CPU time appearing in the fourth column of Table 1 relates to running the RS algorithm for known optimal value of . The RS algorithm is sufficiently fast also for this purpose, but other algorithms such as the HIFOO (see ) and HINFSTRUCT (see ) can be applied in order to get a starting SOF. The advantage of the use of the RS is of finding starting SOF with relatively small norm.
Let denote the functional (7) for the system , where is stable, i.e., . Let denote the Lyapunov matrix (5) for the system with as above. Let denote the functional (7) for the system with and related Lyapunov matrix given by (5). Now, if is stable for some , then is stable for (but there might exist such that is stable, which cannot be defined as for some matrix ). Therefore,
where is an optimal LQR state-feedback (SF) controller for the system . We conclude that . Thus, is a lower bound for and can serve as a good estimator for it, in order to quantify the convergence of the algorithm to the global minimum (as is evidently seen from Table 1 in many cases) and in order to stop the algorithm earlier, since can be calculated in advance. The lower bound appears in the last column of Table 1.
For all the systems, we had controllable, except for ROC1 and ROC2. All the systems are unstable, except for AC6, AC15, and NN16 which are stable, but not -stable, for given in the stability margin column.
The experiments were executed on:
Computer: LAPTOP-GULIHG OV, ASUSeK COMPUTER, INC.
TUF GAMING FX504GM-FX80GM.
Processor: Intel(R) Core(TM) i7-8750H CPU@2.20GHz.
Platform: MATLAB, Version R2018b Win 64.
5.1 Conclusions from the experiments
Regarding the experimental results in Table 2 and the comparison between the RS algorithm and the MC algorithm, we conclude:
The RS algorithm performs in magnitude better than the MC algorithm for the systems: AC1, AC11, HE1, HE4, ROC1, ROC4, TF1, and NN5.
The MC algorithm performs in magnitude better than the RS algorithm for the systems AC5 and DIS5.
The MC algorithm performs slightly better than the RS algorithm for systems HE3 and NN16.
Regarding the experimental results in Table 2 and the performance of the RS + MC algorithm, we conclude:
The RS + MC algorithm performs better than each algorithm separately, for systems AC6, HE4, TF1, NN13, NN16, and NN17.
The RS + MC algorithm performs better than the RS algorithm for systems AC5, HE3, and DIS5.
The RS + MC algorithm performs exactly as the RS algorithm for systems AC1, AC11, DIS4, HE1, ROC1, ROC4, and NN5. This observation assesses the claim for convergence of the RS algorithm to global optimum.
The RS + MC algorithm performs exactly as the MC algorithm for systems AC5 and DIS5.
Regarding improvements over the starting point, we had:
The RS algorithm failed in finding any improvement over for systems AC5 and DIS5.
The MC algorithm failed in finding any improvement over for systems AC1, AC11, ROC1, and ROC4. This observation assesses the heuristic that it is better to start with a SOF that brings the poles of the closed loop as close as possible to the boundary of the disk .
The RS + MC algorithm improved in any case.
Regarding the assessment of convergence to a global minimum, we had the following results:
The RS algorithm and the RS + MC algorithm had very close values of (or exactly the same value) which is very close to the lower bound, for systems AC1, AC6, HE1, HE3, HE4, ROC1, DIS4, NN5, and NN16.
The MC algorithm achieved a very close value of to the lower bound, for the systems AC6, HE3, DIS5, NN5, and NN16.
As was expected, the MC algorithm seems to perform better locally, while the RS algorithm seems to perform better globally. Thus, practically, the best approach is to apply the RS algorithm in order to find a close neighborhood of a global minimum and then to apply the MC algorithm on the result, for the local optimization, as is evidently seen from the performance of the RS + MC algorithm.
5.2 Some specific results
Example 5.1. For the HE4 system with
we had the following results:
by the RS algorithm for minimal-gain SOF (see )
by the RS Algorithm1
by the MC Algorithm 2
and by RS + MC Algorithms 1 and 2:
6. Concluding remarks
The Ray-Shooting Method is a powerful tool, since it practically solves the problem of LQR via SOF, for real-life discrete-time LTI systems. The proposed hybrid algorithm RS + MC has good performance in terms of run-time, in terms of the quality of controllers (by reducing the starting point LQR functional value and by reducing the controller norm) and in terms of the success rate in finding a starting point feasible with respect to the needed -stability. The RS + MC algorithm has a proof of convergence in probability to a global minimum (as is evidently seen from the experiments). This enlarges the practicality and scope of the Ray-Shooting Method in solving hard complexity control problems, and we expect to receive more results in this direction.