Optimal control of discrete-time switched linear systems via continuous parameterization Jérémie Kreiss ∗ Laurent Bako ∗∗ Eric Blanco ∗∗ arXiv:1704.06985v1 [cs.SY] 23 Apr 2017 ∗ Laboratoire Ampère, INSA de Lyon, Université de Lyon 20, Avenue Albert Einstein, 69100 Villeurbanne, France E-mail: jeremie.kreiss@insa-lyon.fr ∗∗ Laboratoire Ampère – Ecole Centrale de Lyon – Université de Lyon 36, Avenue Guy de Collongue, 69134 Ecully, France Abstract: The paper presents a novel method for designing an optimal controller for discretetime switched linear systems. The problem is formulated as one of computing the discrete mode sequence and the continuous input sequence that jointly minimize a quadratic performance index. State-of- art methods for solving such a control problem suffer in general from a high computational requirement due to the fact that an exponential number of switching sequences must be explored. The method of this paper addresses the challenge of the switching law design by introducing auxiliary continuous input variables and then solving a non-smooth block-sparsity inducing optimization problem. Keywords: optimal control, switched linear systems, quadratic control, dynamic programming. 1. INTRODUCTION Switched systems constitute a class of dynamic systems consisting of a finite number of subsystems which are activated one after another over time by a switching signal [12], [8], [7]. In many cases, the switching signal is an external input which, together with the continuous input vector, can be used to control the behavior of the switched system. Examples of real processes that can be represented as switched systems with external discrete and/or continuous inputs are: autonomous vehicles, chemical processes, electrical circuits, etc. (see e.g., [12] and [8] for a background). The problem of controlling switched systems of this type therefore involves designing a continuous control law along with a switching sequence to achieve some performance specifications. We will be interested more specifically in optimal control design for discrete-time switched linear systems (SLS). The existing approaches to the problem of optimal control for switched systems can be classified into two groups: the ones addressing the continuous-time case [13, 5, 9, 10, 11] and those pertaining to the discrete-time case [14], [6]. Other classifications can be done with respect to the length of the control horizon (finite or infinite), the simplifying assumptions posed a priori on the structure of the discrete or the continuous input or the conceptual nature of the methods. One observation that can be made is the following. Considering the quadratic optimal control of SLS in continuous-time where no structure is imposed in advance on the discrete and continuous control policies, there is so far no exact solution for both finite and infinite control horizons. In discrete-time an exact solution has been derived in [14] for the case of finite control horizon. However direct numerical implementation proves to be so expensive that it is not affordable in practice. Therefore a relevant question of major importance is how to develop some suboptimal strategies that would be much less expensive while still being close to optimality. Some relaxations have been discussed in [14, 6] for this purpose. However the resulting control algorithms still suffer from an exponential demand in storage capacity. In this paper, we focus on the quadratic optimal control of switched linear systems. The discussion here is restricted to finite-horizon problems but the envisioned ultimate goal is to extend it to infinite horizon. We first observe that the origin of the huge complexity associated with computing the solution to this optimization problem is the presence of discrete variables. Therefore a key idea in our approach is to parameterize the discrete inputs by auxiliary control variables which are continuous. With this reformulation, the SLS optimal control problem becomes completely continuous but nonconvex. We then discuss some convex relaxation strategies. More precisely, we propose solving a sequence of convex problems in order to estimate the auxiliary control variables. The whole process yields an implementation which is shown in simulation to coincide statistically very often with the true optimal control. The advantage of the proposed computational scheme is that it has only a polynomial complexity. Moreover it requires the same storing capacity (for the sequence of positive semidefinite matrices generated by the Riccati recursion) as the solution to the simpler linear quadratic optimal problem. The structure of this paper is as follows. In Section 2, we formulate the switched quadratic control problem. We discuss the expression of the optimal solution and the associated complexity issue. In Section 3 we present the new continuous parameterization of the discrete control variable and develop a four-steps algorithm for solving it approximately. A numerical illustration is provided in Section 4. Finally, some concluding remarks are given in section 5. [4]. However a direct implementation of the optimal control suffers from an exponential complexity in both storing and computational resources. The goal of this paper is to discuss some alternative formulations and corresponding solutions of the quadratic optimal control problem for SLS so as to yield more efficient implementations. 2. PROBLEM FORMULATION Let us first characterize the solution to problem (3). For this purpose, let Jk (x, u(·), σ(·)) denote the performance index corresponding to the situation when the system starts in an arbitrary state x ∈ Rn at time k and evolves under the action of the inputs u(·) and σ(·). Introduce the function Jk∗ : Rn → R defined by Jk∗ (x) = min Jk (x, u(·), σ(·)) 2.1 Switched linear systems We consider a discrete-time switched linear system (SLS) described by x(k + 1) = Aσ(k) x(k) + Bσ(k) u(k), x(0) = x0 (1) where k ∈ Z+ is a time index, x(k) ∈ Rn and u(k) ∈ Rnu are respectively the state and the continuous input at time k, x0 is the initial state; σ(k) ∈ Ω , {1, . . . , q} refers to the value taken by the switching signal (also called here the discrete input) at time k. Ω is a finite set collecting the indices of the different subsystems of the SLS (1). For any i ∈ Ω, the pair (Ai , Bi ) ∈ Rn×n × Rn×nu of matrices is associated with the subsystem i. Throughout the paper, we use notations of the type u(·) to designate the entire sequence {u(k)}. It is important to note that the switching signal σ(·) , {σ(k)} is viewed here as an external input. For simplicity, we assume that σ(k) can be selected freely in Ω without any constraint. The control problem of interest is that of designing jointly a continuous control sequence u(·) and a discrete control sequence σ(·) so as to minimize a certain performance index over a finite time horizon. For this purpose it will be assumed throughout the paper that the SLS (1) is stabilizable. 2.2 Switched optimal quadratic problem We consider a quadratic performance index associated with system (1) in the form 1 J0 (x0 , u(·), σ(·)) = xT (N )Ψx(N ) 2 N −1 (2)  1 X T x (k)Q(k)x(k) + uT (k)R(k)u(k) + 2 k=0 N −1 where N denotes the control horizon, {R(k)}k=0 ⊂ Rnu ×nu is a given sequence of symmetric positive definite N matrices; {Q(k)}k=0 ⊂ Rn×n with Q(N ) = Ψ represents a sequence of positive semidefinite matrices. The problem of interest in this paper is stated as follows. Problem 1. Given the performance matrices {Q(k)}N k=0 N −1 and {R(k)}k=0 , find a continuous input sequence u(·) and a discrete input sequence σ(·) that minimize the performance index (2) subject to the switched system equation (1). In more formal terms, this is equivalent to solving the optimization problem
min J0 x0 , u(·), σ(·) u(·),σ(·) (3) s.t. Eq. (1). We start by observing that the solution to problem (3) can be mathematically characterized in a quite straightforward way using, for example, the Bellman optimality principle u(k),··· ,u(N −1) σ(k),··· ,σ(N −1) (4) s.t. x(t + 1) = Aσ(t) x(t) + Bσ(t) u(t), x(k) = x t = k, . . . , N − 1. ∗ Jk (x) is called the value function or the cost-to-go. It is ∗ interesting to note from (2) that JN (x) = xT Ψx for all n x ∈ R . Equipped with the notation (4), the Bellman principle of optimality [4] can be expressed as   ∗ ℓ(x, u, k) + Jk+1 (Ai x + Bi u) (5) Jk∗ (x) = min nu (u,i)∈R ×Ω  1 T where ℓ(x, u, k) = x Q(k)x + uT R(k)u is the running 2 cost. Theorem 1. Consider the control problem (3) and let the functions Jk∗ be defined as in (4). Denote with u∗ (·), σ ∗ (·), x∗ (·) respectively the optimal continuous input, discrete input and continuous state. Then the following statements hold. 1. The value function Jk∗ is quadratic and can be written as Jk∗ (x) = xT P ∗ (k)x ∀x ∈ Rn , ∀k ∈ {0, . . . , N } , (6) where {P ∗ (k)} is a sequence of matrices generated recursively backward in time according to the Ricatti recursion defined by P ∗ (k) = ρσ∗ (k),k (P ∗ (k + 1)), P ∗ (N ) = Ψ (7) with ρi,k (P ) =Q(k) + AT i P Ai
−1 T T Bi P Ai . − Ai P Bi R(k) + BiT P Bi (8) 2. The optimal continuous input is given by
u∗ (k) = −Kσ∗ (k),k P ∗ (k + 1) x∗ (k) (9)
−1 BiT P Ai . where Ki,k (P ) = R(k) + BiT P Bi ∗ 3. The optimal discrete input σ (·) is given by   σ ∗ (k) ∈ argmin x∗ (k)T ρi,k (P ∗ (k + 1))x∗ (k) . (10) i∈Ω Proof. The proof follows by a simple backward induction exploiting the Bellman optimality equation (5). It is therefore omitted. 2.3 Implementation of the optimal control In order to implement the control law (9)-(10), we need to fully compute offline the sequence {P ∗ (k)}N k=0 by the Ricatti recursion (7). Note that this recursion depends on the optimal switching signal σ ∗ (·) which in turn depends on the optimal continuous state x∗ (·) as can be seen from Eq. (10). Unfortunately the optimal state is not available offline. This is a source of a major difficulty. To cope with this challenge an elegant solution has been developed in [14]. The authors first showed that the value function given in (6) can be re-expressed as Jk∗ (x) • A nonsmooth block-sparsity-inducing optimization involving the auxiliary control variables. The purpose of this is to enforce their expected structure as will be described next. 3.1 Continuous parameterization of the discrete input T = min x P x P ∈Hk where {Hk } is a sequence of sets of symmetric positive semidefinite matrices defined by 1  HN = {Ψ}  Hk = ρi,k (P ) : P ∈ Hk+1 , i ∈ Ω , k = N − 1, . . . , 0. (11) The sets {Hk } collect indeed all the possible values of the Ricatti sequence (7) for all admissible switching signals. Since the definition of the sets {Hk } is now freed from the dependence on the continuous state, they can be computed offline and stored. Once this is done the optimal control law can be obtained online by applying σ ∗ (k) ∈ arg min x∗ (k)⊤ ρi,k (P )x∗ (k) (12) i∈Ω,P ∈Hk+1 along with (9). It turns out that the trick of [14] makes the optimal control (9)-(10) implementable. This is done however at the price of a huge complexity. In effect, the cardinality of the sets Hk grows exponentially fast with respect to the control horizon N . For example, the cardinality of Hk is about q N −k . Indeed the above implementation requires an exponential load in terms of both computational and storage resources. This complexity affects all the steps of the implementation: offline computation and storage of the sets {Hk } and online reading and search for the optimal discrete control by Eq. (12) over the sets {Hk }. To reduce the complexity, a suboptimal solution is discussed in [14]. But it is fair to observe that some shortcomings still persist. First, the proposed procedure does not alleviate the off-line computational load ; it only allows for a saving of the necessary storage capacity. Moreover the cardinality reduction algorithm has still to test all the elements in the sets Hk hence resulting in an exponential complexity. This complexity restricts the applicability of the solution of [14] to the control of switched systems with small number of subsystems and small control horizons. Noting that exponential complexity is generated by the presence of discrete variables in the optimization problem, we discuss here a new approach which relies on a continuous parameterization of the switching sequence. 3. PROPOSED SOLUTION The proposed design method relies on two main ideas: • A continuous parameterization of the discrete control variable σ(·). This consists in replacing the discrete input in the SLS (1) with continuous variables called auxiliary control variables. Consequently, problem (3) can be written as a constrained optimization problem in only continuous variables hence getting rid of its combinatorial feature. 1 Note that in the setting of [14] the weighting matrices Q and R depend on the subsystem index, not on time. As a consequence ρ is indexed there only by i. A starting point is to notice that the SLS dynamics in (1) can be written in the form x(k + 1) = Ai x(k) + Bi u(k) + fi (k), ∀i ∈ Ω (13) where fi (k) = (Aσ(k) − Ai )x(k) + (Bσ(k) − Bi )u(k). Each fi (k) can be interpreted as the difference between the state of the SLS at time k + 1 under σ(k) and the state that would have been obtained if σ(k) was set equal to i. It follows that for any time instant k, fσ(k) (k) = 0. From now on let us forget about the explicit expressions of the fi (k)’s and view them just as unknown control variables satisfying the following constraint: for all k, there exists j = j(k) ∈ Ω such that fj (k) = 0n,1 where 0n,1 denotes a n-dimensional vector with all entries equal to zero. By letting f¯(k) = [f1 (k)T · · · fq (k)T ]T ∈ Rqn , the above constraint can be written as f¯(k) ∈ S with S being a subset of Rqn defined by  S = v = (v1T , · · · , vqT )T ∈ Rqn , with vi ∈ Rn , i ∈ Ω : ∃j ∈ Ω : vj = 0n,1 . (14) There are many other equivalent ways of representing the set S. One of those which are smooth is the following n S = v = (v1T , · · · , vqT )T ∈ Rqn , with vi ∈ Rn , i ∈ Ω : q Y kvi k = 0 i=1 o for any vector norm k·k on Rn . The variable f¯(k) is then regarded as an auxiliary control variable to be computed along with the continuous input variable. Based on this parameterization we now restate the control problem as follows. N N −1 Problem 2. Given the matrices {Q(k)}k=0 and {R(k)}k=0 , find a continuous input sequence u(·) and an auxiliary input sequence f¯(·) that minimize the performance index N −1 X 1 T ℓ(x(k), u(k), k) x (N )Ψx(N ) + 2 k=0 (15) subject to system (13) written in expanded form as       B1 A1 x(k + 1)  .    ..   ..  =  .  x(k) +  ..  u(k) + f¯(k) (16)  . Bq x(k + 1) Aq and the constraint f¯(k) ∈ S. V (x0 ,u(·), f¯(·)) = To write this in a more compact form, define T    T T , B̄ = B1T · · · BqT , Ā = AT 1 · · · Aq T Ln,q = [In · · · In ] = 1q ⊗ In , where 1q = [1 · · · 1]T is a vector of q ones, In is the ndimensional identity matrix and ⊗ denotes the Kronecker product. Then problem (2) can be written as a constrained optimization problem as follows 
min V x0 , u(·), f¯(·) ¯ u(·),f(·) s.t. Ln,q x(k + 1) = Āx(k) + B̄u(k) + f¯(k) (17) f¯(k) ∈ S, k = 0, . . . , N − 1 x(0) = x0 . It is important to note that problems (3) and (17) are equivalent. But contrary to (3), problem (17) is an optimization problem in which all the decision variables are continuous. One can therefore hope for designing an algorithm that solves it in polynomial time. A remaining challenge to deal with is the non convexity of (17). 3.2 An algorithm in four stages We now ask the question of how to compute numerically the solution to problem (17). Because of the non-convex constraint f¯(k) ∈ S, the problem is not convex. For efficiency of solving we therefore need to find a convex relaxation. We will discuss a block-sparsity inducing optimization technique for that. The global computational procedure can be decomposed into four stages which are described next.  N −1 Stage (a) In this first stage, the sequence f¯(k) k=0 is considered as a (unknown) parameter. Hence the criterion V is minimized with respect to u(·) only, i.e., we solve
min V x0 , u(·), f¯(·) u(·) s.t. Ln,q x(k + 1) = Āx(k) + B̄u(k) + f¯(k), (18) k = 0, . . . , N − 1 x(0) = x0 ,  where the constraint on f¯(k) has been removed. This is a convex program. One difference with the classical linear quadratic control problem is that the dynamic matrix Ā in (18) is rectangular rather than square. Also the state x(k+ 1) is repeated here q times on left hand side of the dynamics equation. Denote with V1 (x0 , f¯(·)) the resulting optimal
functional, i.e., V1 (x0 , f¯(·)) = minu(·) V x0 , u(·), f¯(·) . Using the method of Lagrange multipliers, construct the Lagrangian V̄ by embedding the constraints of (18) in the cost functional. This yields
V̄ = V x0 , u(·), f¯(·) + N −1 X
λ̄T (k + 1) Āx(k) + B̄u(k) + f¯(k) − Ln,q x(k + 1) k=0 (19)  where λ̄(k) , with λ̄(k) = [λ1 (k)T · · · λq (k)T ]T , is a sequence of Lagrange multipliers. Introduce now the discrete time Hamiltonian H associated with the system (16) and the performance index (15) defined by Hk = H x(k), u(k), λ̄(k + 1), k)
= ℓ(x(k), u(k), k) + λT (k + 1) Āx(k) + B̄u(k) + f¯(k) (20) With this short-hand notation the extended cost (19) takes the form 1 V̄ = x(N )T Ψx(N ) − λ̄T (N )Ln,q x(N ) 2 N −1 (21) X
Hk − λ̄T (k)Ln,q x(k) + H0 . + k=1 Considering the minimization of V̄ with respect to u, let us look at the effect of an elementary variation du of u and of the induced change dx in the state. These together induce a variation dV̄ of V̄ , expressible by T  dx(N ) dV̄ = Ψx(N ) − LT n,q λ̄(N ) !   N −1 T X ∂Hk ∂Hk T + − Ln,q λ̄(k) dx(k) + du(k) ∂x(k) ∂u(k) k=1 + ∂H0 ∂H0 dx(0) + du(0). ∂x(0) ∂u(0) (22) Note that dx(0) = 0 since the initial state is fixed. At the optimal value of V̄ we must have dV̄ = 0 as a consequence of any variation du of the input and any subsequent variation dx of the state. This implies that all terms in the previous equation must be set to zero. Thus for all k = 1, . . . , N − 1, λ̄(k) must satisfy ∂Hk LT (23) , LT n,q λ̄(k) = n,q λ̄(N ) = Ψx(N ). ∂x(k) Similarly, we must impose ∂Hk = 0. ∂u(k) It follows that the optimal continuous input can be expressed as (24) u(k) = −R−1 B̄ T λ̄(k + 1). We can rewrite (16) and (23) respectively as follows Ln,q x(k + 1) = Āx(k) − B̄R−1 B̄ T λ̄(k + 1) + f¯(k) (25) with initial condition x(0) = x0 and T LT n,q λ̄(k) = Qx(k) + Ā λ̄(k + 1), with the final constraint LT n,q λ̄(N ) (26) = Ψx(N ). Eqs (25) and (26) form a system of linear equations that characterizes completely the solution to (18). Stage (b) Now, we seek the minimal value of V1 (x0 , f¯(·)) with respect to f¯(·). Since for any k the solution f¯(k) is expected to live in the set S defined in (14), the optimization problem is as follows
min V1 x0 , f¯(·) f¯(·) (27) s.t. f¯(k) ∈ S ∀k ∈ {0, · · · , N − 1}. As mentioned earlier, this problem is not convex. In order to keep polynomial complexity, we need to find a convex relaxation of it. To do so, let us denote with χS : Rnq → R ∪ {+∞} the indicator function of S defined from Rnq to real extended line by χS (z) = 0 if z ∈ S and χS (z) = +∞ otherwise. Then (27) is equivalent −1 i h
NX χS (f¯(k)) . min V1 x0 , f¯(·) + f¯(·) k=0 To find a convex relaxation of the terms χS (f¯(k)), we view each vector f¯(k) as being relatively block-sparse in the sense that it must admit at least one subvector fj (k) which ¯ is equal to zero. With this in mind we Pqreplace χS (f (k)) with a nonsmooth convex function, i=1 wi (k) kfi (k)k2 where the wi (k)’s denote some positive weights. As is suggested by a certain number of results (see e.g., [3, 2]), minimizing such a function enjoys the nice property that it is able to promote block sparsity hence yielding a vector f¯(k) with some of its subvectors fi (k) potentially equal or close to zero. The role of the weights {wi (k)} is to discriminate between the different subvectors of f¯(k). They can be selected, for example, iteratively as follows: solve the problem with all weights set to one and based on the resulting solution, retune the weights through a simple rule of the form wi (k) = 1/(kfˆi (k)k2 + ǫ) for some small number ǫ > 0. For better numerical stability, one can consider normalizing a posteriori the weights along the i dimension. Finally we formulate the following convex optimization problem: q N −1 X h i X
¯ (28) wi (k) kfi (k)k2 . min γ1 V1 x0 , f (·) + γ2 f¯(·) k=0 i=1 For writing simplicity, we have not given here the explicit expression of V1 (x0 , f (·)). The derivation of such an expression follows from straightforward algebraic calculations departing from the system of linear equations (25)(26).  ¯(k) = [fˆ⊤ (k) · · · fˆ⊤ (k)]⊤ Stage (c) Let fˆ¯(k) with fˆ 1 q denote a solution to problem (28). Since this is obtained under some relaxation of the initial problem, there is no guarantee that fˆ¯(k) will lie in the set S for all k. Hence, ¯(k) onto S in order to determine we need to project those fˆ the switching sequence. The projection we used consists in selecting the discrete input to be the index i ∈ Ω such that fˆi has the minimum norm among all, i.e., σ̂(k) ∈ argminkfˆi (k)k, k = 0, . . . , N − 1, (29) i∈Ω with k·k denoting the vector 2-norm. In some sense, this corresponds to forcing to zero the fˆi having the minimum norm. Stage (d) Once we have computed the switching se−1 quence {σ̂(k)}N k=0 offline, the SLS optimal control problem reduces to that of a linear time-varying system with matrices defined by (Aσ̂(k) , Bσ̂(k) ). The solution of such a problem with respect to the quadratic cost (2) can be determined as in the conventional case [1]. To obtain it, we can just apply (7)-(8) with σ ∗ (·) replaced by σ̂(·) to generate offline a sequence of matrices {P̂ (k)}. By storing this single Ricatti sequence, the final continuous and discrete inputs are then, similarly as in (9)-(10), selected online as û(k) = −Kσ̂(k),k (P̂ (k + 1))x̂(k)   σ̂(k) ∈ arg min x̂(k)T ρi,k (P̂ (k + 1))x̂(k) (30) (31) i∈Ω with x̂(·) denoting the associated state trajectory. This means that the discrete input is recalculated online. As it turns out, the implementation proposed in this paper has a polynomial complexity. Moreover it requires storing only a single sequence of matrices {P̂ (k)} just as in the solution of the linear quadratic problem (single linear subsystem). In comparison with [14], the gain on the memory demand is significant. However in its current version, the proposed implementation is not guaranteed to yield the optimal control. In view of the applied control policy (30)(31), the sole objective of the procedure described above for solving Problem 2 is the computation of the Ricatti sequence {P̂ (k)}. 4. RESULTS Note that for all the following tests, the weights γ1 and γ2 are taken equals to 1. 4.1 A statistical test In this section we challenge the capability of the proposed method to obtain the solution to the optimal quadratic control problem for switched systems of the form (1). For this purpose 100 examples of two-dimensional switched systems, with each composed of q = 2 subsystems, are generated at random using the MATLAB function drss. The initial state is also sampled from a Gaussian distribution N (0, 20I2 ). For each of these examples, the optimal control problem is that of finding the discrete and continuous inputs to minimize a finite horizon performance index of the form (2) with N = 15 and with Q(k) = I2 and R(k) = 1 for all k. For the sake of comparison, we also implement the optimal control law as described in [14] and recalled above in Eqs (11)-(12). This is possible here since the number of subsystems and the control horizon are small. As a matter of fact the cardinality of H0 in (11) for the current experiment is about 215 = 32768, which is computationally affordable on a standard computer. Let Jiopt and Jio , i = 1, . . . , 100, denote respectively the optimal index and the value yielded by our method. For each of the 100 examples, define the following relative error as an empirical measure of the distance to optimality J o − J opt εi = i opti . Ji The table below displays the distribution of εi in terms of probabilities of the type Prob(ε  i ≤ α) with α being a threshold taking values in 10−10 , 10−8 , 10−7 , 10−5 . It turns out that the solution achieved by the proposed method either coincides with the optimal index or lies generally in a small neighborhood of it. This suggests that for generic systems, the implemented strategy discussed in this paper has the potential of recovering the optimal control and this, at a much affordable price. Threshold on εi 10−5 10−7 10−8 10−10 0 % examples 100% 98% 97% 96% 83% Table 1. Distribution of the relative error εi for the 100 examples of switched systems: (n, q) = (2, 2). Repeating a similar experiment as above with this time examples of switched systems with state dimension n = 3 and number of modes q = 3 yield the results reported in Table 2. Note that for this last experiment the control horizon has been reduced to N = 10 in order to alleviate the computational load associated with the computation of the exact optimal solution. A little degradation of the results can be observed in Table 2 in comparison Threshold 10−2 10−5 10−7 10−8 10−10 0 % examples 100% 96% 93% 92% 90% 81% 2 σ with the results given in Table 1. This may be due to numerical artefacts as a result of increased number of decision variables. The approximate performance index is still very close to the optimal one. 1 0 1 2 3 4 5 Table 2. Distribution of the relative error εi for the 100 examples of switched systems: (n, q) = (3, 3). 5. CONCLUSION In this paper, we studied the discrete-time quadratic optimal control problem for switched systems on a finite time horizon. Based on a continuous parameterization of the discrete input, we proposed an approach that is able to yield the optimal solution in polynomial time with respect to the length of control horizon. Moreover the proposed algorithm appears to be cheaper than most existing methods in terms of computational load and storage resources. Future research will focus on analyzing the properties of this method. REFERENCES [1] Anderson, B. and Moore, J. (1990). Optimal Control : Linear Quadratic Methods. Prentice-Hall International. [2] Bako, L. and Lecoeuche, S. (2013). A sparse optimization approach to state observer design for switched linear systems. Systems & Control Letters, 62, 143– 151. [3] Bako, L. and Ohlsson, H. (2016). Analysis of a nonsmooth optimization approach to robust estimation. Automatica, 66, 132–145. 7 8 9 10 11 12 13 14 time (a) Discrete input: optimal σ∗ (·) (red stars) and approximate one σ̂(·) (blue circles). 4.2 Illustration of performance on a single example x∗∗1 x x̂1 2 x̂2 2 1 State For illustration purpose, let us now focus on a single switched system. The considered example is in the form (1) and consists of two linear subsystems with matrices defined by     2 0.9 0 , , B1 = A1 = 1 0.5 1.5     (32) 0 1.1 1 . , B2 = A2 = 1 0 0.8 It can be observed that none of the individual subsystems is stable. In this experiment, the control horizon is set to N = 15; the initial state is x0 = [1 2]⊤ and the weighting matrices of the performance index are defined as in Section 4.1. Applying the proposed method on this example yields the results presented in Figure 1. It turns out that the obtained discrete input is equal to the optimal one except at the two time instants t = 10 and t = 14. However the impact of this difference is negligible on the performance index J0 since we still get a relative error of 4.03 × 10−9 . This is because the errors occur at a time when the state has almost already converged to zero as shown by Figure 1-(b). We can even conjecture that small amplitude of the state makes it difficult to recover the optimal discrete input by (31). 6 0 -1 -2 0 5 10 15 time (b) Continuous states x∗ (·) and x̂(·). Fig. 1. Results obtained on the switched system defined by (32). [4] Bertsekas, D.P. (2012). Dynamic Programming and Optimal Control. Athena Scientific. [5] Deaecto, G.S., Geromel, J.C., and Daafouz, J. (2011). Dynamic output feedback hinf control of switched linear systems. Automatica, 47, 1713–1720. [6] Görges, D., Izák, M., and Liu, S. (2011). Optimal control and scheduling of switched systems. IEEE Transactions on Automatic Control. [7] Lemmon, M.D., He, K.X., and Markovsky, I. (1999). Supervisory hybrid systems. IEEE Control Systems, 19, 42–55. [8] Lunze, J. and Lamnabhi-Lagarrigue, F. (eds.) (2009). Handbook of Hybrid Systems Control, Theory, Tools, Application. Cambridge University Press. [9] Riedinger, P. (2013). A switched LQ regulator design in continuous time. IEEE Transactions on Automatic Control, 59, 1322–1328. [10] Riedinger, P. and Vivalda, J.C. (2015). Dynamic output feedback for switched linear systems based on a LQG design. Automatica, 54, 235–245. [11] Senger, G.A. and Trofino, A. (2015). Switching rule design for affine switched systems with guaranteed cost and uncertain equilibrium condition. IEEE Transactions on Automatic Control, (To appear). [12] Van Der Shaft, A. and Schumacher, H. (1999). An Introduction to Hybrid Dynamical Systems. SpringerVerlag London. [13] Xu, X. and Antsaklis, P.J. (2004). Optimal control of switched systems based on parameterization of the switching instants. IEEE Transactions on automatic control, 49, 2–16. [14] Zhang, W., Abate, A., Hu, J., and Vitus, M. (2009). Exponential stabilization of discrete-time switched linear systems. Automatica, 45, 2526–2536.