Hamilton-Jacobi Conditions for an Impulsive Control Problem

HAMILTON-JACOBI CONDITIONS FOR AN IMPULSIVE CONTROL PROBLEM Fernando L. Pereira ∗,1An´ıbal C. Matos ∗,1 Geraldo N. Silva ∗∗,2 ∗Instituto de Sistemas e Robotica Faculdade de Engenharia da Universidade do Porto R. Dr. Roberto Frias, 4200-465 Porto, Portugal e-mail:{flp,anibal}@fe.up.pt ∗∗ Computer Science and Statistics Dept. Universidade Estadual Paulista C. P. 136, S. J. Rio Preto-SP, Brasil e-mail:[email protected] Abstract: A vector-valued impulsive control problem is considered whose dynamics, defined by a differential inclusion, are such that the vector fields associated with the singular term do not satisfy the so called Frobenius condition. A concept of proper solution based on a reparametrization procedure is adopted which enables the derivation of optimality conditions of the Hamilton-Jacobi type. These conditions are obtained by taking a limit of those for an appropriate sequence of auxiliary “standard” optimal control problems approximating the original one. Copyright c 2001 IFAC Keywords: optimal control, Hamilton-Jacobi conditions, impulsive control. 1. INTRODUCTION Dynamic optimization problems arising in a variety of application areas such as finance, mechanics, resources management, and space navigation, (see, for example, (Brogliato, 1996), (Clark, Clarke, Munro, 1979), (DalMaso, Rampazzo, 1991), (Lawden, 1963), and (Marec, 1979)) whose solutions might involve discontinuous trajectories have been, over the years, motivating a significant research effort on the so-called Impulsive Control Problem (for a selected set of references see (Pereira, Silva, 2000) and references therein). 1The authors are indebted to FCT support under the grants to fund the research projects COSH and CorDyAL. 2The author is indebted to FAPESP and CNPq of Brazil. In this article, we address a class of impulsive control problems previously treated by (Silva, Vinter, 1997), in which the dynamics are defined by a measure differential equation. However, now, we consider vector valued measures without assuming commutativity of the singular vector field, similarly to the problem addressed in (Pereira, Silva, 2000). In this new context, the concept of proper solution is presented. Besides providing a meaning to the dynamic optimization problem, is also endowed with a robustness property allowing the extension of conditions of optimality of the Hamilton-Jacobi type for the considered class of impulsive control problems. The conditions presented here can be regarded as an extension to the impulsive optimal control problem of the standard ones for conventional dynamic optimization problems. Impulsive control problems have been addressed in a number of publications, namely, (Bressan, Rampazzo, 1991), (Dykhta, Sumsonuk, 1997), and (Kolokolnikova, 1997), (Rishel, 1965), (Rockafellar, 1976), Rockafellar, 1981) and (Warga, 1966). In the first four, closer in spirit to this article, impulsive control problems with vector valued control measures were addressed by imposing the Frobenius condition on the vector fields associated with the singular term. This very strict assumption ensures an unique jump endpoint, x(t+), once specified the value of the state variable at t−and the measure dµ(t). In (Bressan, Rampazzo, 1994), this commutativity assumption is lifted by noting that a certain quotient control system, obtained by an appropriate nonlinear local change of coordinates in the state space, is an impulsive one satisfying the above mentioned commutative hypothesis. In (Mota, Rampazzo, 1996), a dynamic programming approach for nonlinear systems driven by ordinary and impulsive controls is considered whose solution is given by a value function that depends on the time variable and on the variation of the control measure. A maximum principle is also proved and the relations between the adjoint variable and the value function are established. The problem formulated in this article is quite different from the ones above and, instead, falls into the control context of (Pereira, Silva, 2000). It adheres to important classes of problems involving the coordinated control of multiple dynamic systems. Basically, the idea is to control a dynamical system with several viable configurations in such a way that a given performance criterion is maximized during the execution of the given activities. Transitions between different configurations are not, in practice, instantaneous, although ideally might be considered so. Therefore, it is of interest to incorporate its management in the global optimization problem. This can be regarded as choosing the best path between the jump endpoints. This article is organized as follows: In the next section, we will state the optimal control problem in detail and present the required assumptions. In the third section, we explain the adopted solution concept and, in the fourth section, we present an auxiliary result that is used in the derivation of Hamilton-Jacobi type optimality conditions. These conditions are stated in the fifth section and a brief outline of the proof is given. 2. STATEMENT OF THE PROBLEM We will consider the following optimal control problem: (P) Minimize h(x(1)) (1) subject to dx(t)∈F(t, x(t))dt + G(t, x(t))µ(dt)∀t(2) µ(dt)∈K, (3) x(0) = x0.(4) Here, h:Rn→Ris the cost functional, F: [0,1]× Rn⇒Rn, and G: [0,1]×Rn⇒Rn×qare given set valued functions describing the dynamics, Kis a positive convex pointed cone in Rq, and x0∈Rn. By (3) it is meant that µ∈C∗([0,1]; K), i.e., µ(A)∈Kfor any Borel set A⊂[0,1], denoting C∗([0,1]; K) the set in the dual space of continuous functions from [0,1] to Rqwith values in K. The short notation used in (2) to express the dynamics (which are a significant extension of the one in (Silva, Vinter, 1997)), requires a careful explanation on how the interaction between the evolving state variable and the impulsive integrating control measure at times when the trajectory is discontinuous, is taken into account. This problem is a complementary formulation of the one in (Vinter, Pereira, 1988) in the sense that in this reference the singular dynamics depends on the ordinary control variable instead of the state variable. Let us denote by xac and by xs, respectively the absolutely continuous and the singular components of the trajectory, x, and consider a given initial condition x0. Then, x(t) = xac(t) + xs(t)∀t∈ [0,1] with x(0) = x0 ˙xac(t)∈F(t, x(t)) + G(t, x(t)) ·wac(t),L-a.e. xs(t) = Z[0,t] g(τ)¯µs(dτ)∀t∈[0,1]. Here ¯µis the total variation measure associated with the vector-valued measure µ(which, in this case, is given by Pq i=1 µi), µsand µac are, respectively, the singular and the absolutely continuous components of µ,wac is the time derivative of µac, and g(·) is a ¯µs-a.e. measurable selection of a certain set valued function ˜ G(t, x(t−); µ({t})) : [0,1] ×Rn×K⇒Rn. Defined in the next section, this set valued function is such that a concept of control process will fulfill the requirements underlying the wellposedness of the optimization control problem as well as the derivation of conditions of optimality. Remark that the fact that ˜ Gis set valued accounts for the nonuniquess of the solutions to (2) for a given initial state and control function. As can be seen in (Pereira, Silva, 2000), each one of these solutions can be regarded as the limit of a convergent (in a certain sense) subsequence of conventional control processes. A solution to (P) is a feasible control process (x, µ), in the sense that satisfies the constraints (2)-(4) as explained above, that minimizes h. The following hypothesis were assumed on the data of (P): (H1) his Lipschitz continuous with constant Kh. (H2) Fis continuous, and for each tis Lipschitz continuous with respect to xwith constant Kf. (H3) Fis a nonempty, convex and compact valued set-valued function. (H4) There are constants K1and K2, such that, ∀(t, x); ∀v∈F(t, x)|v| ≤ K1+K2|x|. (H5) Gis bounded and Lipschitz continuous with respect to (t, x) with constant KG. (H6) Fand Ghave closed graphs. Although a set of weaker assumptions could have been adopted, we preferred to preserve clarity at the cost of sacrificing additional technicalities. In the quest of dropping the commutativity assumption, two main goals were considered. One is to overcome the technical difficulty associated with the nonuniquenes of the trajectory. The second consists in providing useful practical information in the sense that the obtained conditions should support the approximation to the optimal control process, possibly involving a trajectory of bounded variation, by a sequence of conventional ones. 3. SOLUTION CONCEPT The definition of Proper Solution to (P) requires the auxiliary definitions of reparametrization and graph completion which can be readily adapted from (Pereira, Silva 2000). For the sake of completeness, they will be restated here. In what follows, AC([0,1]; Rn) and BV +([0,1]; Rn) denote, respectively, the space of absolutely continuous Rn-valued functions, and the space of Rn-valued functions of bounded variation which are right continuous on (0,1], and L × B is the product σfield where Lare the Lebesgue subsets of [0,1] and Bthe Borel sets in Rq. Definition 1. Aµ-graph completion (where µ∈ C∗(0,1; K)) is a pair (θ, γ) : [0, α]→R+×K where: •θ: [0, α]→[0,1] is the “inverse” of ¯η(i.e., θ(s) = t, ∀s∈¯η(t)) and •γ: ¯η(t)→Rqgiven by γ(s) :=    M(θ(s)) if ¯µ({t}) = 0 M(t−) + Zs η(t−) v(σ)dσ if ¯µ({t})>0, where α= 1 + ¯µ([0,1]), v(·)∈Vt, a set of functions v: ¯η(t)→Rq, with v(s)∈Kand Pq i=1 vi(s) = 1 ∀s∈¯η(t), and R¯η(t)v(s)ds = µ({t})}. Here, M:= col(M1, ..., Mq), with Mi(0) = 0 and, ∀t > 0, Mi(t) = R[0,t]µi(ds), ¯µ(dt) := Pq i=1 µi(dt), and the set valued function ¯η(t) is given by [η(t−), η(t)] if ¯µ({t})>0 and by {η(t)} otherwise, being the time reparametrization η(·) defined by η(t) := t+ q X i=1 Mi(t). Proposition 1 in (Silva, Vinter, 1998) concerning the relevant properties of graph completions can be easily extended in a straightforward manner to the case of vector valued control measures when the above reparametrization procedure is adopted. In opposition to the scalar valued control measure case, we have to deal with a set valued reparametrization. More specifically, when more than one component of the control measure is supported at the same point in time, multiple conventional trajectories can be associated with the given generalized control process. This is a consequence of the noncommutativity of the semigroup composition of the vector fields associated with the columns of the matrix G. In order to single out one conventional reparametrized control process, we adopted the definition of h-graph completion presented below. For a given feasible measure µand an initial state x0, consider the family of reparametrized trajectories Fx0,µ defined by {y∈AC([0, α]; Rn) : ˙y(s)∈˜ F(s, y(s)) ˙ θ(s) + ˜ G(s, y(s))˙γ(s),(˙ θ(s),˙γ(s)) ∈K1, [0, α]-a.e., y(0) = x0} where •α= 1 + ¯µ([0,1]) •˜ F(s, y(s)) = F(θ(s), y(s)), •˜ G(s, y(s)) = G(θ(s), y(s)), •γ(0) = 0, and γ(η(t)) = µ([0, t]) ∀t∈[0,1], •K1={w∈[0,1] ×K:Pq i=0 wi= 1}. Definition 2. A given pair of functions (θ, γ) is a h-graph completion related to (x0, µ) if it minimizes h(y(1)) over all y(·) in Fx0,µ. The set of h-standard processes Phis the set of all triples (y, θ, γ) s.t. y∈ Fx0,µ,∀h-graph completion (θ, γ). Definition 3. A function x∈BV +([0,1]; Rn) is aProper solution to (2) relative to the objective functional (1) if there exists a L-integrable function f, f(t)∈F(t, x(t)) L-a.e.,and a h-graph completion yielding a ¯µ-integrable function g, g(t) ∈˜ G(t, x(t−); µ({t})) ¯µ-a.e., such that ∀t∈(0,1] x(t) = x(0) + Zt 0 f(τ)dτ +Z[0,t] g(τ)¯µ(dτ). Here, the set valued function ˜ G: [0,1] ×Rn× K⇒Rnis given by                    {G(t, z)w(t)}if |α|= 0 {[ξ(η(t)) −ξ(η(t−))] |α|: ˙ ξ(s)∈G(t, ξ(s)) ˙γ(s),¯η(t)-a.e., ξ(η(t−)) = z, γ(η(t)) −γ(η(t−)) = α} otherwise where |α|=Pq i=1 αi,w(·) is the Radon-Nicodym derivative of µw.r.t. ¯µ, (ξ, γ) is an element of AC([0,1]; Rn+q), and the pair (θ, γ) is a µ-graph completion with ˙ θ(s)≡0 on ¯η(t). Note that the definition of a solution to (2) for a given (x0, µ), includes the specification of a path joining the endpoints of every discontinuity. This path corresponds to an arc which satisfies the singular dynamics, i.e., ˙ ξt(s)∈G(t, ξt(s))v(s), for ξt(η(t−)) = x(t−) and for some v∈K. The good definition of the solution is guaranteed by selecting the additional control vin such a way that resulting trajectory is the one obtained as the limit over all minimizing sequences of conventional control processes for problem (P). This definition provides not only a framework for the derivation of optimality conditions, but also to support the design of computational algorithms. By only requiring that Fbe L-measurable, G be B-measurable and both take closed values, for a given measure µ, there is an equivalence between the set of solutions of (2) and the set of standard processes Phin the sense that for each solution to (2) there corresponds one and only one h-standard process (y, θ, γ) such that x(t) = y(η(t)) for all t∈[0,1]. This statement is a straightforward extension of Theorem 4.1 in (Silva, Vinter, 1997). Furthermore, it can also be shown that kxkT V ≤ kykT V . Given a sequence of measures µiand a sequence of initial values xi 0we denote the associated sequence of h-standard processes by Pi h. Solutions to (2) (as defined above) are “robust” in the sense that the set of solutions has desirable “closure” properties with respect to perturbations of the driving measure µand the initial state. The following result is a direct generalization of Proposition 5.1, (Silva, Vinter, 1996) which concerns the approximation of measure differential equations. Proposition 1. Let the hypotheses (H1)-(H6), stated above, be in force. Take a sequence {xi 0} in Rnand a sequence {µi}in C∗([0,1]; K),and x0∈Rnand µ∈C∗([0,1]; K) such that xi 0→x0 and µi→µweakly∗, as i→ ∞. Take also a sequence {xi}in BV +([0,1]; Rn) such that xiis a robust solution to (2) for each iand assume the existence of β(t)∈L1and c > 0 such that F(t, xi(t)) ⊂β(t)Ba.e. and |G(t, xi(t))| ≤ cfor all tand i. Then, there exist: (a) a sequence of h-standard processes (yi, θi, γi) in Pi h, (b) (y, θ, γ)∈Phand (c) a solution xto (2) , such that xi(t) = yi(ηi(t)) ∀t∈(0,1] and x(t) = y(η(t)) ∀t∈(0,1]. Along a subsequence, we have dxi→dx weakly∗ and xi(t)→x(t) for all t∈[0,1] \ Mµ∪ {0,1} (where Mµdenotes the atoms of µ) and yi→y strongly in C([0,1]; Rn). 4. PRELIMINARY RESULTS In this section we present a result concerning the approximation of arcs by reparametrized trajectories for the impulsive control system. This result resembles the Fillipov approximation theorem, derived for absolutely continuous control systems, see (Aubin, Cellina 1984). Theorem 1. Let F:R×Rn⇒Rnand G:R× Rn⇒Rn×qbe such that F(·, x) and G(·, x) are Lebesgue measurable ∀x∈Rn, and F(t, ·) and G(t, ·) are Lipschitz continuous of rank k for all t∈R. Take a > 0 and consider two Lipschitz continuous functions θ: [0, a]→Rand γ: [0, a]→Rq, satisfying (˙ θ(s),˙γ(s)) ∈K1, s ∈[0, a]−a.e.. Take also z∈AC([0, a]; Rn) such that ˙z(s) = φ(s)˙ θ(s) + ψ(s)˙γ(s), s ∈[0, a]−a.e. where φ∈L1([0, a]; Rn) and ψ∈L1([0, a]; Rn×q). Let p∈L1([0, a]; R) be such that dF(θ(s),z(s))(φ(s)) ≤p(s)˙ θ(s)6= 0 −a.e. dG(θ(s),z(s))(ψ(s)) ≤p(s) ˙γ(s)6= 0 −a.e. and take x0∈Rn. Let λ: [0, a]→Rbe defined as λ(s) = |z(a)−x0|ek(s−a)+Zs a ek(s−σ)p(σ)dσ. Then there exist x∈AC([0, a]; Rn), fand g, measurable selections of F(θ(s), x(s)) and G(θ(s), x(s)), respectively, satisfying ˙x(s) = f(s)˙ θ(s) + g(s)˙γ(s), s ∈[0, a]−a.e., x(0) = x0, and such that |x(s)−z(s)| ≤ λ(s)∀s∈[0, a] |f(s)−φ(s)| ≤ kλ(s) + p(s)s∈[0, a]−a.e. |g(s)−ψ(s)| ≤ kλ(s) + p(s)s∈[0, a]−a.e. 5. OPTIMALITY CONDITIONS The statement of the derived optimality conditions governing minimizers for (P) over state trajectories which are interpreted as proper solutions to (2) requires the introduction of some notation and a few concepts from nonsmooth analysis. Let f:Rn→Rbe a lower semicontinuous function. The lower Dini derivative, or subderivative, of fw.r.t. xin the direction vis given by Df(x;v) := lim inf w→v δ↓0 f(x+δw)−f(x) δ. ∂Df(x) denotes the D-subdifferential of fat xand is the set {ζ∈Rn:Df(x;v)≥ hζ, vi,∀v∈Rn}. Elements of this set are called D-subgradients. Properties and calculus rules of subderivatives, as well as their relations with generalized gradients in the sense of Clarke or of proximality are addressed more in detail in (Clarke 1983), (Clarke, Ledyaev, Stern, Wolenski 1998), (Aubin, Ekeland 1984) and (Mordukhovich, 1985). Consider also X(τ, ξ) to be the set of feasible trajectories, in the sense of Definition 3 , for (P) starting at (τ, ξ), i.e., X(τ, ξ) := {(x(·), µ) : (x, µ) is solution to (2) and (3) with x(τ) = ξ}, the Reachable set from (τ, ξ) by R(τ, ξ) := {x(1) ∈Rn: (x, µ)∈X(τ, ξ)}, and the value function V(τ, ξ) := min{h(z) : z∈R(τ, ξ)}. Definition 4. W: [0,1] ×Rn→Ris a solution to the Generalized Hamilton-Jacobi Equation on a certain tube Tin the phase space if, for all t∈(0,1), all x∈Rn, with (t, x)∈T, min (w0,w)∈K1 f∈F(t,x) g∈G(t,x) DW ((t, x); (w0, fw0+gw)) ≥0,(5) and for all t∈[0,1], all x∈Rn, with (t, x)∈T min (0,w)∈K1 g∈G(t,x) DW(t)(x;gw)≥0,(6) where, for each t∈[0,1], W(t):Rn→Ris the function defined as W(t)(x) = W(t, x), for all x∈Rn. Conditions (5) and (6) characterize the monotonicity of solutions of the generalized HamiltonJacobi equation when evaluated along feasible trajectories. While (5) has to be satisfied along the continuous component of the trajectory, (6) has to hold along the path joining the jump endpoints. If x(·) is a trajectory solution to (2), this path is in fact an arc satisfying the singular dynamics as defined in the solution in the sense of Definition 3, i.e., it has to be parametrized by an hreparametrization pair (θ, γ). We define the notion of verification function along the lines of (Vinter, Wolenski 1990). Definition 5. Wis a verification function for (P) if •It is locally Lipschitz.. •For all x∈Rn,W(1, x)≤h(x). •It is a solution to the Generalized HamiltonJacobi Equation as defined above. Now, we are ready to state the main results of this article which can be regarded as extensions of the corresponding ones in (Vinter, Wolenski 1990) to impulsive control problems. It is assumed that the data of (P) satisfies hypotheses (H1)-(H6) and also ∀r > 0,∃ko,∀(s, y)∈[0,1] ×Rn,∀(x, µ)∈ X(s, y),|y| ≤ r⇒ kµk ≤ ko. Theorem 2. For each (τ, ξ)∈[0,1] ×Rn, the value function Vis a verification function which is maximal, i.e., V(τ, ξ) = max{W(τ, ξ) : Wis a verification function}. Furthermore, Vis such that (5) holds with equality and, for all x∈Rn, min{h(x)−V(1, x),min (0,w)∈K1 g∈G(1,x) DV(1)(x;gw)}= 0. The next result concerns the Hamilton-Jacobi verification theorem. Theorem 3. (x, µ)∈X(0, x0) is an optimal solution to (P) if and only if there exists a verification function Wsatisfying W(0, x0) = g(x(1)). The general idea behind the proof of the above results involves the concept of reparametrized trajectories defined above. The monotonicity of veri- fication functions evaluated along reparametrized trajectories results from the the absolute continuity of such trajectories as well as the properties of the lower Dini derivatives. The Lipschitz continuity of the valued function can be shown to follow from a simple application of theorem 1, under the assumed hypotheses. To show the other properties of the value function, one can proceed as in in (Vinter, Wolenski, 1990), once more working with reparametrized trajectories. REFERENCES Aubin, J.-P. and I. Ekeland (1984). Applied Nonlinear Analysis, John Wiley & Sons, New York. Aubin, J.-P. and A. Cellina (1984). Differential Inclusions, Springer-Verlag, Berlin. F. Clarke (1983) Optimization and Nonsmooth Analysis, John Wiley & Sons, New York. F. Clarke, Yu. Ledyaev, R.Stern and P. Wolenski (1998) Nonsmooth analysis and control theory, Graduate Texts in Mathematics, 178, Springer-Verlag, New York. A. Bressan and F. Rampazzo (1991), Impulsive Control Systems with Commutative Vector Fields, J. of Optimization Theory and Applications,71, No. 1, pp. 67-83. A. Bressan and F. Rampazzo (1994), Impulsive Control Systems without Commutativity Assumptions, J. of Optimization Theory and Applications,81, No. 3, pp. 435-457. B. Brogliato (1996), Nonsmooth Impact Mechanics: Models, Dynamics and Control, Lect. Notes in Control and Inform. Sci., 220, Springer-Verlag. C. Clark, F. Clarke, G. Munro (1979), The Optimal Exploitation of Renewable Stocks, Econometrica,47, pp. 25-47. G. DalMaso and F. Rampazzo (1991), On systems of ordinary differential equations with measures as controls, Differential and Integral Equations,4, pp. 739-765. V. Dykhta and O. Sumsonuk (1997), A Maximum Principle for Optimal Impulsive Processes and Its Applications, Proc. European Control Conference, V.2-FR-A-D-3, Brussels, Belgium. G. Kolokolnikova (1997), A Variational Maximum Principle for Discontinuous Trajectories of Unbounded Asymptotically Linear Control Systems, Diff. Equations,33, pp.1633-1640. D. Lawden (1963), Optimal Trajectories for Space Navigation, Butterworth, London. J.-P. Marec (1979), Optimal Space Trajectories, Elsevier. B. Mordukhovich (1985), On necessary conditions for an extremum in nonsmooth optimization, Soviety Math. Dokl.,32, pp. 215-220. B. Mota, F. Rampazzo (1996), Dynamic Programming for Nonlinear Systems by Ordinary and Impulse Controls, SIAM J. Control and Optim.,34, pp.199-225. F. Pereira, G. Silva and R. Vinter (1998), Necessary Conditions of Optimality for Impulsive Differential Inclusions, Proc. Conf. Decision and Control’98, Tampa, FL, pp.16-18. F. Pereira, and G. Silva (2000), Necessary conditions of optimality for vector-valued impulsive control problems, Systems & Control Letters, 40, 205-215. R. Rishel (1965), An Extended Pontryagin Principle for Control Systems whose Control Laws Contain Measures, SIAM J. Control,3, pp.191-205. R. Rockafellar (1976), Dual Problems for Arcs of Bounded Variation, in : Calculus of Variations and Control Theory, D.L. Russell ed., Academic Press, New York, pp.155-192. R. Rockafellar (1981), Optimality Conditions for Convex Control Problems with Nonnegative States and the Possibility of Jumps, in : Game Theory and Mathematical Economics, O. Moeschlin, D. Pallaschke eds., North Holland, Amsterdam, pp.339 -349. G. Silva and R. Vinter (1996), Measure Differential Inclusions, J. of Mathematical Analysis and Applications,202, pp. 727-746. G. Silva and R. Vinter (1997), Necessary Conditions For Optimal Impulsive Control Problems, SIAM J.Control and Optim.,35, pp. 1829-1846. R. Vinter and F. Pereira (1988), A maximum principle for optimal processes with discontinuous trajectories, SIAM J. Control and Optim.,26, pp. 205-229. R. Vinter and P. Wolenski (1990), HamiltonJacobi Theory for Optimal Control Problems with Data Measurable in Time, SIAM J. Control and Optim.,28, pp. 1404-1419. J. Warga (1966), Variational Problems with Unbounded Controls, SIAM J. Control,3, pp. 424-438.