An overview of nondegenerate necessary conditions of optimality for optimal control problems with higher index state constraints

AN OVERVIEW OF NONDEGENERATE NECESSARY CONDITIONS OF OPTIMALITY APPLIED TO OPTIMAL CONTROL PROBLEMS WITH HIGHER INDEX STATE CONSTRAINTS S. O. Lopes ∗F. A. C. C. Fontes ∗∗ ∗Departamento de Matem´ atica para a Ciˆ encia e Tecnologia and Officina Mathematica, Universidade do Minho, 4800-058 Guimar˜ aes, Portugal. [email protected] ∗∗ Departamento de Matem´ atica para a Ciˆ encia e Tecnologia and ISR-Porto, Universidade do Minho, 4800-058 Guimar˜ aes, Portugal. [email protected] Abstract: The main purpose of necessary conditions of optimality (NCO) is, given an optimization problem, to select a set of candidates to minimizer. However, for some optimization problems with constraints — in particular for optimal control problems —, it may happen that the NCO are unable to provide any useful information; that is, the set of candidates to minimizers that satisfy certain NCO coincides with the set of all admissible solutions. When this happens, we say that the degeneracy phenomenon occurs. To avoid this phenomenon, stronger forms of NCO are developed. These stronger forms can be applied when the problem satisfies additional hypotheses, known as constraint qualifications. In the case of optimal control problems with state constraints that have higher index (i.e. the first derivative of the state constraint with respect to time does not depend on the control), most constraint qualifications described in literature are not adequate. We note that control problems with higher index state constraints arise frequently in practice. An example, explored here, is a common mechanical systems for which there is a constraint on the position (an obstacle in the path, for example) and the control acts as a second derivative of the position (a force or acceleration) which is a typical case arising in the area of mobile robotics. So, there is a need to develop new constraint qualifications, involving higher derivatives of the state constraint. In this paper, we make an overview of recent constraint qualifications that allow strengthened forms of the NCO for optimal control with higher index state-constraints. Keywords: optimal control; maximum principle; degeneracy phenomenon; higher order state constraints. 1. INTRODUCTION Necessary Conditions of Optimality (NCO) play an important role in the characterization of and search for solutions to Optimization Problems. They enable us to identify a small set of candidates to local minimizers among the overall set of admissible solutions. The simplest and best known example is the well known Fermat’s rule fx(¯x) = 0, that provides a necessary condition of optimality for unconstrained and differentiable problems. (fxdenotes the derivative of fwith respect to x) In order to reduce further the set of candidates to minimizers, we can use a well-known stronger form of NCO fx(¯x) = 0 and H(¯x)is positive semi-definite. (Here, fis twice differentiable and His the Hessian matrix whose elements are the second partial derivatives of f). In constrained optimization problems it may happen that even when there are admissible solutions leading to different costs, the set of candidates to minimizers that satisfy certain NCO coincides with the set of all admissible solutions. When this is the case we say that the NCO is degenerate. Strong forms of NCO are developed to avoid this phenomenon. In next section, we study the degeneracy in optimal control problems with state constraints and we introduce some strong forms of NCO for this kind of problems. We start by introducing an optimal control in Mayer form, in which the initial state is fixed and the trajectory is subject to inequality constraints. Consider the following optimal control problem: (P)Minimize g(x(1)) subject to ˙x(t) = f(x(t), u(t)) a.e. t ∈[0,1] x(0) = x0 u(t)∈Ω(t)a.e. t ∈[0,1] h(x(t)) ≤0∀t∈[0,1], for which the functions g: IRn→IR,f: IRn× IRm→IRn,h: IRn→IR, an initial state x0∈IRn and a multifunction Ω : [0,1] ⇒IRmare given. The set of control functions for (P), denoted U, is the set of measurable functions u: [0,1] →IRmsuch that u(t)∈Ω(t)a.e. t∈[0,1]. A state trajectory is an absolutely continuous function which satisfies the differential equation in the constraints for some control function u. The domain of the above optimization problem is the set of admissible processes, namely pairs (x, u)comprising a control function u and a corresponding state trajectory xwhich satisfy the constraints of (P). We shall seek strong local minimizers, that is, admissible processes (¯x, ¯u)such that g(¯x(1)) ≤g(x(1)) for admissible processes (x, u) satisfying maxt∈[0,1] |x(t)−¯x(t)| ≤ δfor some δ > 0. It is well-known that the necessary conditions of optimality for optimal control problems may appear in the form of Maximum Principle (MP). Here, we introduce a nonsmooth version of the MP, a version that allows the data be non-differentiable. We assume that the problem (P) satisfies the following set of hypothesis: There exists a δ0>0, such that H1 x→f(x, u)is Lipschitz continuous with a Lipschitz constant Kf, for all u∈Ω(t); H2 f(x, Ω(t)) is a compact set for all x∈¯x+δ0B; H3 gis locally Lipschitz continuous; H4 Gr Ωis a Borel set; H5 x→h(x)is continuously differentiable; Define the Hamiltonian H(x(t), p(t), u(t)) = p(t)·f(x(t), u(t)). The MP for problem (P) (see (Vinter, 2000)) asserts the existence of an absolutely continuous function p: [0,1] →IRn, a nonnegative measure µ∈ C∗([0,1]; IR) and a scalar λ≥0such that µ{[0,1]}+λ > 0,(1) −˙p(t)∈co ∂x(q(t)·f(¯x(t),¯u(t))) a.e. t, (2) q(1) ∈λ∂g(¯x(1)) (3) supp{µ} ⊂ {t∈[0,1] : h(¯x(t)) = 0},(4) and for almost every t∈[0,1],¯u(t)maximizes over Ω(t) u7→ q(t)·f(¯x(t), u)(5) where q(t) =                p(t) + Z [0,t) hx(¯x(s))µ(ds)t∈[0,1) p(1) + Z [0,1] hx(¯x(s))µ(ds)t= 1. Remark 1.1. co Sdenotes the convex hull of a set S and ∂g(¯x(1)) is the limiting subdiferential of g.( See next section) 2. PRELIMINARES Definition 2.1. The convex hull of a set C, denoted by co C, is the smallest convex set that contains C. Definition 2.2. The limiting normal cone of a closed set C⊂IRnat ¯x∈C, denoted by NC(¯x), is the set NC(¯x) = {η∈IRn:∃sequences {Mi} ∈ IR+, xi→¯x, ηi→ηsuch that xi∈C and ηi·(y−xi)≤Miky−xik2 for all y∈IRn, i = 1,2, ...}. Definition 2.3. Take a lower semicontinuous function g: IRn→IR and a point x∈dom g. The limiting subdifferential of gat x, written ∂g(x), is the set ∂g(¯x) = {η∈IRn: (η, −1) ∈Nepi g(¯x, g(¯x))}. where epi g={(x, α)∈IRn+1 :α≥g(x)}denotes the epigraph of a function g. If gis continuously differentiable, then ∂g(¯x(1)) = gx(¯x(1)). We define also the hybrid partial subdifferential of h in the x-variable ∂> xh(t, x)to be the following ∂> xh(t, x) := co{ξ:there exist (ti, xi)→(t, x)s.t. h(ti, xi)>0, h(ti, xi)→h(t, x), and ∇xh(ti, xi)→ξ} See (Vinter, 2000) for a review of Nonsmooth Analysis and related concepts using a similar notation. 3. DEGENERACY IN OPTIMAL CONTROL PROBLEMS The main purpose of MP consists in selecting a set of candidates to minimizer. However, it can happen that the set of candidates is equal to the set of admissible processes. In this case, the MP does not give any useful information about the minimizers. If the trajectory starts on the boundary of the admissible region, i.e. h(x0) = 0, then the set of multipliers, degenerate multipliers λ= 0, µ ≡δt=0, p ≡ −hx(x0)(6) satisfies the (MP) for all admissible processes (x, u). (Here, δ{0}denotes the Dirac unit measure concentrated at t= 0.) In this case, the necessary conditions of optimality are said to degenerate. There is a growing literature where the MP is strengthened with additional conditions, typically a stronger form of the nontriviality condition. In (Ferreira and Vinter, 1994), (Ferreira et al., 1999) and (Rampazzo and Vinter, 2000), the nontriviality condition is replaced by µ{(0,1]}+λ > 0.(7) Remark 3.1. We are assuming that the optimal control problem is like (P), where the final state is free. This last condition eliminates degenerate multipliers like the ones in (6) and therefore guarantees that degeneracy does not occur. However these strengthened forms of the MP have to be satisfied for all local minimizers, to guarantee that the MP is still a necessary condition. So, additional hypotheses, known as Constraint Qualifications, are needed to identify the problems under which we can strengthen the MP. An overview of the recent results in this area is done in (Lopes and Fontes, 2007), where we can see that Constraint Qualification are typically of two types: CQ1 ∃˜u(t)∈Ω(t)such that for a.e. t∈[0, ) hx(x0)·[f(x0,˜u(t)) −f(x0,¯u(t)] <−δ Loosely speaking, CQ1 is the requirement that there exists a control function pulling the state away from Fig. 1. CQ1type constraint qualification. Fig. 2. CQ2type constraint qualification. the boundary of the state constraint set faster than the optimal control. Constraint qualifications of this type can be found in (Ferreira and Vinter, 1994; Ferreira et al., 1999). CQ2 ∃˜u(t)∈Ω(t)such that for all t∈[0, ) hx(x0)·f(x0,˜u(t)) <−δ This CQ2 requires the existence of a control functions pushing the state away from the state constraint boundary at the initial time. Constraint qualifications of this type can be found, for example, in (Rampazzo and Vinter, 2000; Arutyunov and Aseev, 1997). There are, however, some problems with interest in practice for which the constraint qualification CQ1 and CQ2 are useless to select a set of problems in which the Maximum Principle can be fortified. These problems are known as optimal control problems with higher index of the state constraint. Fig. 3. A higher index constrained system. 4. HIGHER INDEX STATE CONSTRAINED PROBLEMS We define the index of a state constraint as a measure of how many times we have to differentiate the state constraint to have an explicit dependence on the control. Definition 4.1. (Index of the State Constraint) Let h(i)(x(t)) = d dti h(x(t)). The state constraint is said to have index k, if kis a non-negative integer such that ∂ ∂uh(j)(x) = 0, j = 0,1, ..., k −1 ∂ ∂uh(k)(x)6= 0. If ∂ ∂u h(j)(x) = 0 for all j≥0, the state constraint is said to have index k=∞. We note that control problems with higher index state constraints arise frequently in mechanical systems, when there is a constraint on the position (an obstacle in the path, for example) and the control acts as a second derivative of the position (a force or acceleration). This is illustrated in the following example: Example 4.1. Consider a second order linear system modelling a mass (1/b) moving along a line by action of a force (u)and in which the position (x1) is constrained to a certain half-space (≤d/c1). (see Figure 3). ˙x(t) = 0 1 0 0 x(t) + 0 bu(t),(8) [c1,0]x(t)−d≤0. We note that the quantity h(1)(x(t)) = hx(x(t)) ·[f(x(t), u(t))] = [0, c1]x(t) does not depend explicitly on the control. Therefore, the index is greater than one. If the index is greater than one, then CQ1 and CQ2 are useless to identify problems in which the Maximum Principle can be fortified. Assume that k > 1. By definition of index of the State Constraint, CQ1 is never satisfied. Now, suppose that CQ2 is satisfied. By definition of index, we have hx(x0)·f(x0,˜u(t)) = hx(x0)·f(x0,¯u(t)) <−δ for each t∈[0, ). On the other hand, by continuity of hx(·)and f(·, u), we conclude that there exists τ0sufficient near of 0 and τ0≤τsuch that for each t∈[0, τ0] hx(¯x(t)) ·f(¯x(t)¯u(t)) <−δ0, Therefore h(1)(¯x(t)) <−δ0(9) for each t∈[0, τ0]. That means that the initial part of the optimal trajectory leaves the boundary for a period of time. We can conclude that, if the problem has index greater than one, CQ2 is satisfied only for a particular kind of problems. As we do not know in advance the behavior of the minimizer trajectory, we would have to assume that all admissible trajectories satisfy inequality (9). However, for this kind of problems, the nontriviality condition can be directly replaced by (7) as is shown in (Ferreira and Vinter, 1994). Therefore, the constraint qualification CQ2 looses its interest for higher index problems. In order to remedy this problem, new constraint qualifications dependent on the index of the state constraint were developed. In next section, we make an overview of recent results in this area. 5. AN OVERVIEW OF NONDEGENERATE NECESSARY CONDITIONS OF OPTIMALITY APPLIED TO OPTIMAL CONTROL PROBLEMS WITH HIGHER INDEX STATE CONSTRAINTS In this section, we are assuming that the problems have index k. New Constraints Qualifications dependent of kwere developed in (Fontes, 2005), (Lopes and Fontes, 2008a) and (Lopes and Fontes, 2008b). In (Fontes, 2005), linear optimal control problems like (PL) were considered: (PL)Minimize 1 Z 0 L(x(t), u(t))dt +W(x(1)) subject to ˙x(t) = Ax(t) + Bu(t)a.e.t ∈[0,1] x(0) = x0 u(t)∈Ω(t)a.e.t ∈[0,1] cTx(t)≤d∀t∈[0,1]. Note that, for this particular case, the state constraint is said to have index kif kis a non-negative integer such that cTAjB= 0, j = 0,1, ..., k −1 cTAkB6= 0. The constraint qualification that guarantees the nondegeneracy is the following: CQ0(Fon05) ∃δ > 0,  > 0and a control ˜u∈Ω(t) such that cTAkB(˜u(t)−¯u(t)) <−δ for all t∈[0, ). A generalization of this result allowing nonlinear optimal control problems can be found in (Lopes and Fontes, 2008a). In this case, the constraint qualification is CQ0(LopFon08a) ∃δ > 0,  > 0and a control ˜u∈Ω(t)such that h(k) x(x0)·[f(x0,˜u(t)) −f(x0,¯u(t))] <−δ for all t∈[0, ). Remark 5.1. Note that, for linear problems like (PL) CQ0(LopFon08a) reduces to CQ0(Fon05). However, these Constraint Qualifications involve the minimizing ¯uwhich we do not know in advance, and consequently the conditions are, in general not easily verifiable, except in special cases, such as problems in the Calculus of Variations (see (Lopes and Fontes, 2003) and (Ferreira and Vinter, 1994)). In (Lopes and Fontes, 2008b), the nondegenerate NCO are valid under a constraint qualification that no longer involves the minimizing ¯u. CQ0(LopFon08b) ∃δ > 0,  > 0and a control ˜u∈Ω(t)such that h(k) x(x0)·f(x0,˜u(t)) <−δ. for all t∈[0, ). All theses Constraint Qualifications allow to strengthen the MP with the inequality (7). For technical reasons, they assume that an initial part of the optimal trajectory does not enter and leave the boundary of the state constraint an infinite number of times. That is, the initial part of the optimal trajectory either stays on the boundary of the state constraint for some time or leaves the boundary immediately. Assumption 1: Either (A) ∃τ∈(0,1) such that h(¯x(t)) = 0 for all t∈[0, τ] or (B) ∃τ∈(0,1) such that h(¯x(t)) <0for all t∈(0, τ]. The proof of these results is based on transformation of the initial problem on a problem with the following new state constraint ˜ h(t, x) = max{h(x), h(k)(x)}if t= 0 h(x)if t > 0. As the new state constraint satisfy the following Constraint Qualification: CQ If h(0, x0)=0, then there exist positive constants ,1,δ, and a control ˜u∈Ω(t)such that for a.e. t∈[0, ) ζ·[f(t, x0,˜u(t)) −f(t, x0,¯u(t))] <−δ for all ζ∈∂> xh(s, x), s ∈[0, ), x ∈ {x0}+1B, then applying the main theorem in (Ferreira et al., 1999) the results holds. 6. ACKNOWLEDGEMENTS The financial support from FEDER/POSC under Project FCT POSC/EEA-SRI/61831/2004 is gratefully acknowledged. 7. REFERENCES Arutyunov, A. V. and S. M. Aseev (1997). Investigation of the degeneracy phenomenon of the maximum principle for optimal control problems with state constraints. SIAM Journal of Control and Optimization 35, 930–952. Ferreira, M. M. A. and R. B. Vinter (1994). When is the maximum principle for state constrained problems nondegenerate?. Journal of Mathematical Analysis and Applications 187(2), 438–467. Ferreira, M. M. A., F. A. C. C. Fontes and R. B. Vinter (1999). Nondegenerate necessary conditions for nonconvex optimal control problems with state constraints. Journal of Mathematical Analysis and Applications 233, 116–129. Fontes, F. A. C. C. (2005). Nondegenerate necessary conditions for linear optimal problems with higher index state constraints,. In: Proceedings ECC-CDC’05 European Control Conference and Conference on Decision and Control 2005,. Seville, Spain. pp. 2149–2151. Lopes, S. O. and F. A. C. C. Fontes (2003). Normality in necessary conditions for dynamic optimization problems. In: Third Junior European Meeting on Control, Optimization and Computation. Aveiro, Portugal. Lopes, S. O. and F. A. C. C. Fontes (2007). On the degeneracy phenomenon in optimization problems with inequality constraints. In: ORP3 conference. Guimaraes, Portugal. Lopes, S. O. and F. A. C. C. Fontes (2008a). Nondegenerate necessary conditions for nonlinear optimal problems with higher-index state constraints,. In: Proceedings in Applied Mathematics and Mechanics 2008, (ICIAM 20076th International Congress on Industrial and Applied Mathematics). Zurich, Switzerland. Lopes, S. O. and F. A. C. C. Fontes (2008b). On the degeneracy phenomenon for nonlinear optimal control problems with higher index state constraints. Technical report. Officina Mathematica, University of Minho. Guimaraes, Portugal, http://repositorium.sdum.uminho.pt/. Rampazzo, F. and R. B. Vinter (2000). Degenerate optimal control problems with state constraints. SIAM Journal of Control and Optimization 39, 989–1007. Vinter, R. (2000). Optimal control. Birkhauser. Boston.