Switched-mode systems: gradient-descent algorithms with Armijo step sizes

This paper concerns optimal mode-scheduling in autonomous switched-mode hybrid dynamical systems, where the objective is to minimize a cost-performance functional defined on the state trajectory as a function of the schedule of modes. The controlled variable, namely the modes’ schedule, consists of the sequence of modes and the switchover times between them. We propose a gradient-descent algorithm that adjusts a given mode-schedule by changing multiple modes over time-sets of positive Lebesgue measures, thereby avoiding the inefficiencies inherent in existing techniques that change the modes one at a time. The algorithm is based on steepest descent with Armijo step sizes along Gâteaux differentials of the performance functional with respect to schedule-variations, which yields effective descent at each iteration. Since the space of mode-schedules is infinite dimensional and incomplete, the algorithm’s convergence is proved in the sense of Polak’s framework of optimality functions and minimizing sequences. Simulation results are presented, and possible extensions to problems with dwell-time lower-bound constraints are discussed.

1. Note that the argument for proving Eq. 46 requires the assumption that \(v\in \mathcal {V}\), and may break down without it. Also, observe that it is possible that, for arbitrarily-large j, a mode present in v _k(j) at a time s may not be present in v _σ at any time near s; consequently a sharp inequality in Eq. 46 is possible, namely \(\lim _{j\rightarrow \infty }D_{\sigma _{k(j)}}<D_{\sigma }\).

Authors and Affiliations

1. School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA, 30332, USA

   Y. Wardi, M. Egerstedt & M. Hale

Corresponding author

Correspondence to Y. Wardi.

Research supported in part by the National Science Foundation under Grant CNS-1239225

Appendix

Proof of Lemma 2.

The proof follows from Proposition 5.6.8 and Proposition 5.6.10 in Polak (1997), which are stated in a more general context. For detailed arguments, consider the following setting. Let f ₁:R ⁿ → R ⁿ, f ₂:R ⁿ → R ⁿ, and L : R ⁿ → R be C ² functions, and fix T > 0 and x ₀ ∈ R ⁿ. Given γ ∈ [0, T], define the vector field

and consider the differential equation \(\dot {x}(t))=F(x(t), t;\gamma )\) on the interval t ∈ [0, T], with the initial condition x(0) = x ₀. Since the equation depends on γ, we denote its solution by x(t;γ). Define the performance function J(γ) by \(J(\gamma ):={{\int }_{0}^{T}}L(x(t;\gamma )dt\). Define the costate variable p(t;γ) by the equation \(\dot {p}(t;\gamma )=-\left (\frac {\partial F}{\partial x}(x, t;\gamma )\right )^{\top }p(t;\gamma )-\left (\frac {\partial L}{\partial t}(x;\gamma )\right )^{\top }\), dot denoting derivative with respect to t, with the boundary condition p(T;γ) = 0.

In the context of this paper, Lemma 2 amounts to the assertion that J(γ) is C ². Reference Egerstedt et al. (2006) proved (in a more general context) that J(γ) is C ¹ and the first derivative is given by

(see Proposition 2 2 and Proposition 3.1 there). Now the partial derivatives \(\frac {\partial x}{\partial t}(\gamma ;\gamma )\) and \(\frac {\partial x}{\partial \gamma }(\gamma ;\gamma )\) generally do not exist, but the total derivative \(\frac {dx}{d\gamma }(\gamma ;\gamma )\) exists and it is continuous. To see this note that for all t ∈ [0, γ] x(t;γ) satisfies the equation \(\dot {z}(t)=f_{1}(z(t))\), and hence \(\frac {dx}{d\gamma }(\gamma ;\gamma )=\dot {z}(\gamma )=f_{1}(x(\gamma ;\gamma )\), and the latter term is continuous by the assumption that f ₁(x) is C ². In a similar way, the total derivative \(\frac {dp}{d\gamma }(\gamma ;\gamma )\) exists and it is continuous. To see this, (Polak 1997) (Corollary 5.6.9) proves that for every t ∈ (γ, t] the derivative term \(\frac {\partial x}{\partial t}x(t;\gamma )\) is continuously differentiable in γ. Furthermore, by the costate equation the evolution of p(t;γ) backwards in time depends only on the vector field f ₂ but not on f ₁, and therefore \(\frac {dp}{d\gamma }(\gamma ;\gamma )=\left (-\left (\frac {\partial F}{\partial x}(x, \gamma ;\gamma )\right )^{\top }p(\gamma ;\gamma )-\left (\frac {\partial L}{\partial t}(x;\gamma )\right )^{\top }\right )^{\prime }\), “prime” denoting derivative with respect to γ; continuity follows by standard variational arguments on differentiability of differential equations (e.g., Corollary 5.6.9 in Polak (1997)) and the C ² assumptions on f ₁, f ₂, and L. All of this implies that term in the the RHS of Eq. 59 is continuously differentiable thereby ascertaining that J(γ) is twice continuously differentiable. □

Proof of Lemma 3.

Consider a set S ⊂ [0, T) and schedules σ ₁ and σ ₂ as in the statement of the lemma. For i = 1, 2, let x _i (⋅) and p _i (⋅) denote the state trajectory and costate trajectory, respectively, associated with \(v_{\sigma _{i}}\). By Eqs. 1 and 5, and by Lemma 5.6.7 in Polak (1997) concerning Lipschitz continuity of solutions of differential equations, there exists K ₁ > 0 such that, for all S ⊂ [0, T), σ ₁ ∈ Σ, and σ ₂ ∈ Σ as above,

and

For every s ∈ [0, T)∖S, \(v_{\sigma _{1}}(s)=v_{\sigma _{2}}(s)\), and therefore, and by Eq. 6, for every w ∈ V,

Consequently, and by Eqs. 60 and 61, there exists K ₂ > 0 such that, for every S ⊂ [0, T), σ ₁ ∈ Σ, and σ ₂ ∈ Σ as above, and for every w ∈ V,

Since V is a finite set, and since \(v_{\sigma _{1}}(\tau )=v_{\sigma _{2}}(\tau )\) ∀τ ∈ [0, T)∖S, there exists K ₃ > 0 such that for all S ⊂ [0, T) and σ ₁ ∈ Σ and σ ₂ ∈ Σ as above, \(||v_{\sigma _{1}}-v_{\sigma _{2}}||_{L^{2}}\leq K_{3}\mu (S)\). This, together with Eq. 63, implies Eq. 22 with K := K ₂ K ₃. □

Reprints and permissions