M240C 1 EE240C06-C2 - Lecture notes 2 PDF

Preview

Summary

Prof Wang...

Description

CHAPTER 2 MATHEMATICAL PRELIMINARIES In this Chapter, we begin with an abstract general optimization problem. Then, attention will be directed to deriving necessary and sufficient conditions for optimality. Let D be a nonempty set, and C be a real-valued function defined on D. A general optimization or extremum problem is to find an element v ∗ ∈ D such that C(v ∗ ) ≤ C (v) (resp. ≥ C (v)) for all v ∈ D,

(2.1)

where v ∗ is called an optimal element, an absolute minimum (resp. maximum) point of C, or simply a solution to the optimization problem. The word extremum refers to either minimum or maximum. Note that the problem of maximizing a function J over D is equivalent to that of minimizing a function C = −J over D. Therefore, without loss of generality, only minimization problems need to be considered. We observe that in the foregoing problem statement, D could be any nonempty set of admissible objects. There may not be any algebraic structure on the set D at all, i.e. operations between the elements of D may not be defined. The optimization problem makes sense as long as a value for C can be assigned to each element in D. In the standard optimal control problems discussed in Chapter 1, it is convenient to embed D in a normed linear space V so that the addition of any two elements in D, multiplication of an element in D by a scalar, and the closeness between any two elements in D are defined. Simple Optimal Control Problem: To fix ideas, we consider a simple optimal control problem with fixed finite control time interval Ic = [to , t1 ]. Let the system be described by the following scalar differential equation: dx = f (t, x) + u, dt

(2.2)

with specified initial state x(to ) = xo , and singleton target set G(t1 ) = {x1 }. Let the set Uad of all admissible controls u = u(t) be real-valued functions defined on Ic having the following properties: (i) u(·) ∈ Co (Ic; R), the linear space of all real-valued continuous functions defined on Ic endowed with the norm ku(·)k = maxt∈Ic |u(t)|; (ii) the solution of (2.2) corresponding to initial state xo and control u(·) satisfies: xu (t1 ; xo , to ) = x1 . Let the cost functional be defined by Z t1 fo (t, xu (t; xo , to ), u(t))dt, C(u) = to

7

(2.3)

where fo is a specified real-valued continuous function of its arguments. The optimal control problem is to find an u∗ ∈ Uad such that C(u∗ ) ≤ C (u) for all u ∈ Uad. Identifying D in the general optimization problem stated earlier with Uad defined by Uad = {u(·) ∈ Co (Ic; R) : xu (t1 ; xo , to ) = x1 },

(2.4)

we have reformulated the optimal control problem as an optimization problem on the set of all admissible controls. Note that in this problem formulation, the set Uad corresponds to the set of all admissible controls u(·) such that the solutions to (2.2) satisfy condition (ii) (i.e. xu is the solution to a two-point boundary-value problem). Evidently, Uad is generally a complicated set! In particular, when f is a nonlinear function of x, it may not be possible to express xu (t1 ; xo , to ) explicitly. We may also formulate the foregoing simple optimal control problem in a different way by rewriting the control u as u = x˙ − f (t, x), (2.5) and substituting it into (2.3) to obtain ˜ C(x(·)) =

Z

t1

f˜o (t, x(t), x( ˙ t))dt,

(2.6)

to

def where x˙ = dx/dt, and f˜o (t, x, x) ˙ = fo (t, x, x˙ − f (t, x)). Now, the optimal control problem can be reposed as a trajectory optimization problem of finding an admissible trajectory x(·) ∈ Σ defined by Σ = {x(·) ∈ C1 (Ic; R) : x(to ) = xo and x(t1 ) = x1 } (2.7) such that C˜ is minimized, where C1 (Ic; R) denotes the space of all real-valued continuously

differentiable functions defined on Ic and endowed with the norm: kx(·)k = max |x(t)| + max |x( ˙ t)|. t∈Ic

t∈Ic

(2.8)

This formulation leads to the simplest standard problem in classical calculus of variations. Remark 2.1 If we allow the controls to be piecewise continuous functions of t, then Co (Ic; R) in (2.4) is replaced by Cpo(Ic; R), the space of all real-valued piecewise continuous functions of t defined on Ic. In the second problem formulation, the set of all admissible trajectories is replaced by Σ = {x(·) ∈ Cp1 (Ic; R) : x(to ) = xo and x(t1 ) = x1 }, where Cp1 (Ic; R) denotes the space of all real-valued continuous functions defined on Ic having piecewise continuous derivatives on Ic, and endowed with the norm: kx(·)k = max |x(t)| + ess. sup |x(t)|, ˙ t∈Ic

(2.9)

t∈Ic

where “ess. sup” denotes essential supremum (i.e. ess. supt∈Ic |x( ˙ t)| is the infimum of constants α such that |x( ˙ t)| ≤ α for almost all t ∈ Ic). We shall return to the foregoing simplest optimal control problem later in Chapter 3. 2.1 Existence of Optimal Solutions Consider again the general optimization problem of minimizing C over D. Here, we embed D in a normed linear space V so that a neighborhood 8

of a point in D is defined. Moreover, we may define the continuity of C on D in the usual way. Now, if C is continuous on D, and D is a compact subset of a finite-dimensional normed linear space V (i.e. Given any sequence {v k } in D, there exists a subsequence {v ki } converging to an element in D.), then it follows from a theorem due to Weierstrass [1] that C attains its absolute minimum and maximum on D. This result is also valid when V is infinite dimensional. Note that this result gives a sufficient condition for the existence of an absolute minimum and maximum of C on D. It is not necessary as exhibited by the following simple example: Let D =] − 1, 1] ⊂ R and C (v) = v 2 . Obviously, C is continuous on D, and has an absolute minimum at v = 0, and an absolute maximum at v = 1. But D is not compact. The requirement on continuity of C can be relaxed. Tonelli introduced the following notion of semi-continuity: Definition 2.1 A real-valued function C on a normed linear space V is lower (resp. upper) semi-continuous at a point vˆ ∈ V , if for every ǫ > 0, there exists a δ > 0 such that C(v) − C(ˆ v ) ≥ −ǫ (resp. ≤ ǫ) for all v ∈ ηδ (ˆ v) def

where ηδ (ˆ v ) = {v ∈ V : kˆ v − vk < δ}. Note that if C is both upper and lower semi-continuous at vˆ, then it is continuous at vˆ. Evidently, semi-continuity, as the name implies, corresponds to “half” the definition of continuity. The following theorem is an extension of Weierstrass’ theorem mentioned earlier. Theorem 2.1 Let C be a lower semi-continuous real-valued function defined on a compact subset D of a normed linear space V . Then, C has an absolute minimum on D. Proof: Let µ = inf v∈D C(v). Thus, there exists a sequence {v k } in D such that C(v k ) → µ as k → ∞. Since D is compact, we can extract a subsequence {v ki } converging to v ∈ D. Evidently, C(v ki ) → µ. From the assumption that C is lower semi-continuous on D, we have C (v) ≤ limki→∞ C (v ki ) = µ. Since C(v ) must be finite, thus µ > −∞ and C(v) = µ. ¤ In a similar manner, we can prove that if C is upper semi-continuous on a compact subset D of a normed linear space V , then C attains its absolute maximum on D. In optimal control problems, the requirement that the set of all admissible controls or trajectories be compact represents a severe restriction. Thus, the application of Theorem 2.1 to these problems is rather limited. 2.2 Optimality Conditions Consider again the general optimization problem of minimizing or maximizing a real-valued function C over a nonempty subset D of a normed linear space V . Let v ∗ ∈ D be an optimal element. We are interested in deriving necessary conditions which v ∗ must satisfy, and also sufficient conditions which ensure that v ∗ is optimal. One approach is to consider the behavior of C along rays emanating from v ∗ as illustrated by the sketches given in Fig. 2.1. In Fig. 1(a), v ∗ lies in the interior of D. Consider a ray R(h; v ∗ ) = {v ∈ V : v = ∗ v + αh, α ≥ 0} emanating from v ∗ along the direction specified by a nonzero vector h ∈ V . If D is bounded, then there exists an α ˆ > 0 such that the ray intersects ∂D (the boundary of D), and the closed line segment L(v ∗ , v ∗ + αh) ˆ joining v ∗ and v ∗ + α ˆ h ∈ ∂D lies completely ∗ in D. Note that since v is an interior point of D, we may choose any nonzero vector 9

(b)

(a)

.v* . v* D

D

Figure 1: Rays emanating from v ∗ . (a) v ∗ lies in the interior of D; (b) v ∗ lies on the boundary of D.

h ∈ V . However, the corresponding α ˆ generally depends on the choice of h. Now, a necessary condition for v ∗ to be optimal is that C(v) ≥ C(v ∗ ) for all v ∈ L(v ∗ , v ∗ + αh) ˆ for any nonzero h ∈ V . We observe that C = C(v), with v restricted to the line segment L(v ∗ , v ∗ + αh), ˆ is a real-valued function of one variable α whose values lie in the interval [0, α[. ˆ Thus, if C is differentiable along L(v ∗ , v ∗ + αh), ˆ we can establish a necessary condition for optimality in terms of its derivative. In Fig. 1 (b), v ∗ lies on the boundary of D. In this case, only those rays emanating from v ∗ that are directed toward the interior of D are admissible. A necessary condition for v ∗ to be optimal is that C(v) ≥ C (v ∗ ) for all v’s along these admissible rays restricted to D. The foregoing simple idea is fundamental to our subsequent development of necessary conditions for optimality. To formalize this idea, we introduce a few definitions. Definition 2.2 Let h be a nonzero vector in the linear space V . A point v is said to be an internal point (resp. radial point) of D in the direction h, if there exists an α ˆ > 0 such that (v + αh) ∈ D for |α| < α ˆ (resp. for 0 ≤ α < α). ˆ Note that in the above definition, V is a linear space (not necessarily normed). Evidently, when V is a normed linear space, then an interior point of D is also an internal point of D for all directions h. Next, we introduce the notion of Gateaux differential which generalizes the notion of the directional derivative of a real-valued function of many variables. Let V be a real vector space, and C be a function on D ⊆ V , and taking its values in R (a normed linear space with norm defined by |y |). Definition 2.3 Let v be a radial point in D, and h a nonzero vector in V . If the limit ¯ 1 d DC(v; h)= lim (C (v + αh) − C (v)) = C(v + αh)¯¯ (2.10) α→0 α dα α=0 exists, then DC(v; h) is called the Gateaux differential of C at v with increment h. If DC (v; h) exists for every nonzero h ∈ V , then C is said to be Gateaux differentiable at v. Example 2.1 Let C be a real-valued differentiable function of n variables v = (v1 , . . . , vn ) defined on the n-dimensional real coordinate space V = Rn . Let h = (h1 , . . . , hn ) be a nonzero 10

vector in V . Then, n ¯ X ∂C d ¯ DC(v, h) = C(v + αh)¯ = ( v ) hi , dα ∂vi α=0 i=1

(2.11)

which is simply the directional derivative of C at v in the direction h in calculus [1]. Example 2.2 Let C be a real functional defined on V = C0 ([0, 1]; R) given by Z 1 f (t, v(t))dt, C(v) = 0

where f is continuous with respect to t and v , and has a continuous partial derivative with respect to v for all t ∈ [0, 1]. Let h = h(t) be a nonzero function in V . Then Z 1 ¯ d ¯ f (t, v(t) + αh(t))dt¯ . DC(v; h) = α=0 dα 0 Interchanging the order of differentiation and integration, we have Z 1 Z 1 ¯ ∂f d ¯ DC(v; h) = (t, v(t))h(t)dt. f (t, v(t) + αh(t))¯ dt = α=0 0 ∂v 0 dα

(2.12)

In the definition of a Gateaux differential, the vector space V is not necessarily normed. Therefore, the properties of Gateaux differential are not related easily to continuity. When V is normed, we may introduce a stronger notion of a differential which is a generalization of the differential of a real-valued function of many variables in calculus [1].

Definition 2.4 Let C be a function on D, an open subset of a normed linear space V , and taking its values in R (a normed linear space with norm defined by |y |). If for fixed v ∈ D and each h ∈ V , there exists a dC(v; h) ∈ R such that dC(v; ·) is a linear continuous mapping on V into R, and |C(v + h) − C(v) − dC(v; h)| = 0, khk k hk→0 lim

(2.13)

then C is said to be Fr´echet differentiable at v, and dC(v; h) is the Fr´echet differential of C at v with increment h. The following properties of Fr´echet differentials are useful in computation. •Property 1 If C has a Fr´echet differential, it is unique. ˜ (v; h) satisfying the conditions of Proof: Assume there exist two distinct dC(v; h) and dC Definition 2.4. Then, using triangle inequality, we have ˜ (v; h)| = | − C(v + h) + C(v) + dC (v; h) + C(v + h) − C(v) −dC(v; ˜ |dC (v; h) − dC h)| ˜ (v; h)|. ≤ |C(v + h) − C(v) − dC(v; h)| + |C(v + h) − C(v) −dC Since condition (2.13) holds if and only if |C(v + h) −C (v) −dC(v; h)| = o(khk), the above ˜ (v; h)| = o(khk). Since both dC (v; ·) and dC(v; ˜ inequality implies that |dC(v; h) − dC ·) are 11

˜ linear continuous mappings on V , we have dC(v; h)−dC(v; h) = 0 for all h ∈ V , contradicting ˜ that dC(v; h) and dC(v; h) are distinct. ¤ •Property 2 If the Fr´echet differential of C exists at v ∈ D, then the Gateaux differential also exists at v, and they are equal. Proof: From (2.13), we have, for any nonzero h ∈ V , lim

k αhk→0

or

|C(v + αh) − C(v) − dC (v; αh)| = 0, kαhk

|C(v + αh) − C(v) − dC (v; αh)| = 0. α Since dC(v; ·) is a linear function on V , hence dC (v; αh) = αdC (v; h). Thus lim

α→0

It follows that

¯C(v + αh) − C(v) ¯ ¯ lim ¯¯ − dC (v; h)¯ = 0. α→0 α def

DC(v; h) = lim

α→0

C(v + αh) − C(v) = dC (v; h). ¤ α

From the foregoing properties, the Fr´echet differential of C can be found by first computing the Gateaux differential DC(v; h), and then verifying whether condition (2.13) with dC (v; h) replaced by DC(v; h) is satisfied. Example 2.3 Consider again Example 2.2. We wish to show that the Fr´echet differential dC(v; h) is also given by (2.12). Consider ¯Z 1 ¯ ∂f ¯ ¯ |C(v + h) − C(v) − DC(v; h)| = ¯ (f (t, v (t) + h(t)) − f (t, v (t)) − (t, v(t))h(t))dt¯. ∂v 0 For a fixed t, we have by the one-dimensional mean-value theorem [1]: f (t, v (t) + h(t)) − f (t, v (t)) =

∂f (t, v¯(t))h(t), ∂v

where |v(t) − v( ¯ t)| ≤ |h(t)|. Since ∂f/∂v is uniformly continuous in t and v, hence, given an ǫ > 0, there exists a δ > 0 such that for |h| < δ , ¯ ¯ ∂f ∂f ¯ ¯ (t, v)¯ < ǫ. ¯ (t, v + h) − ∂v ∂v It follows that ¶ ¯ ¯Z µ ∂f ¯ ¯ 1 ∂f (t, v(t)) h(t)dt¯ ≤ ǫkhk |C(v + h) − C(v) − DC(v; h)| = ¯ (t, v¯(t)) − ∂v ∂v 0 def

for khk = maxt∈[0,1] |h(t)| < δ. Thus, condition (2.13) is satisfied with dC (v; h) = DC (v; h). 12

Remark 2.2 Since dC(v, ·) is a continuous or bounded linear functional on V into R, we can write ′ dC (v; h) = C (v)h, ′

where C (v) corresponds to that linear functional which is called the Fr´echet derivative of C ′ at v. Moreover, C (v) is an element of V ∗ , the conjugate space of V (the space of all bounded linear functionals on V ). In the special case where V is a real Hilbert space, we can write dC(v; h) = (h, ∇C(v)), ′

where (·, ·) denotes the inner product on V . By the Riesz’ representation theorem [2], C (v ) can be identified with an element ∇C(v) ∈ V , called the gradient of C at v. Next, we extend the notions of relative minimum and maximum (or relative extremum) in ordinary calculus to a more general setting. Again, let C be a real-valued function defined on D ⊂ V , a normed linear space. Definition 2.5 C has a relative minimum (resp. maximum) at a point v ∗ ∈ D, if there exists an ǫ-neighborhood ηǫ (v ∗ ) such that C(v ∗ ) ≤ C (v) (resp. ≥ C (v)) for all v ∈ ηǫ (v ∗ ) for def some ǫ > 0, where ηǫ (v ∗ )= {v ∈ D : kv − v ∗ k < ǫ}. Now, we are ready to develop conditions for optimality. Theorem 2.2 If v ∗ is a minimum point of C such that v ∗ is an internal point in D in the direction h ∈ V , and ∗

DC (v ; h), exist, then

¯ d2 ¯ ∗ D C(v ; h)= 2 C(v + αh)¯ α=0 dα 2

def

∗

DC (v ∗ ; h) = 0 and D2 C(v ∗ ; h) ≥ 0.

(2.14)

Proof: For every h ∈ V , g = C(v ∗ + αh) is a real-valued function of the real variable α. If v is a minimum point of C, then α = 0 is a minimum point of g. By ordinary calculus [1], ∗

¯ ¯ dg ¯ d2 g ¯ = D2 C(v ∗ ; h) ≥ 0. ¤ = DC(v ∗ ; h) = 0, and 2 ¯ ¯ dα α=0 dα α=0 Remark 2.3 Theorem 2.2 is valid for both global and relative extremum points of C. It is the basic result for classical calculus of variations. Remark 2.4 A point v at which DC(v; h) = 0 for all h ∈ V is called a stationary point of C. From Theorem 2.2, a global or relative extremum point is a stationary point. However, a stationary point may not be an extremum point of C (e.g. a saddle point of C ). Theorem 2.3 If in Theorem 2.2, v ∗ is a radial point of D in the direction h, and DC(v ∗ ; h) exists, then DC (v ∗ ; h) ≥ 0. (2.15) Proof: Since v ∗ is a radial point of D, then there exists an α ˆ > 0 such that the line segment L(v ∗ , v ∗ + αh) ˆ lies in D. Consider the real-valued function g = C(v ∗ + αh) of α 13

defined for 0 ≤ α ≤ α. ˆ Since v ∗ is a minimum point of C, then α = 0 is a minimum point of g. Hence, dg ¯¯ = DC (v ∗ ; h) ≥ 0. ¯ dα α=0 Otherwise, there exists an interval [0, α′ [ over which g(α) < g(0) = C (v ∗ ), contradicting the minimality of v ∗ . ¤ Corollary 2.1 If in Theorem 2.3, D is a convex set (i.e. for any pair v and v ′ ∈ D, their convex combination αv + (1 − α)v ′ ∈ D for all 0 ≤ α ≤ 1), then (2.15) reduces to DC (v ∗ ; v − v ∗ ) ≥ 0 for all v ∈ D.

(2.16)

The above result follows from the fact that since D is convex, v ∗ + α(v − v ∗ ) ∈ D for 0 ≤ α ≤ 1. Setting h = v − v ∗ in (2.15) gives the desired result. Remark 2.5 Inequalities (2.15) and (2.16) are called variational inequalities. When C is Fr´echet differentiable at v ∗ , then (2.16) can be rewritten as dC (v ∗ ; v ) ≥ dC (v ∗ ; v ∗ ) for all v ∈ D. or inf dC(v ∗ ; v) = dC(v ∗ ; v ∗ ).

v∈D

(2.17)

Equation (2.17) can be regarded as a minimum principle. Remark 2.6 When D is not convex, inequality (2.15) holds for certain admissible directions h (see Fig. 2.1(b)). These admissible directions form a cone with vertex at v ∗ . This result is of basic importance in the derivation of necessary conditions for optimal control to be discussed later. Now, we consider the special case where C is a convex functional defined on a convex set D ⊆ V , i.e. C satisfies C((1 − λ)v + λ˜ v ) ≤ (1 − λ)C(v) + λC(˜ v ) for all v, v˜ ∈ D, and 0 ≤ λ ≤ 1.

(2.18)

The following result show that the variational inequality (2.16) is also sufficient for optimality. Theorem 2.4 Let C be a convex functional defined on a convex set D ⊆ V . If v ∗ ∈ D satisfies the variational inequality (2.16), then v ∗ is optimal. Proof: From the convexity of C, we have C(v ∗ + λ(v − v ∗ )) ≤ (1 − λ)C(v ∗ ) + λC(v ) for 0 ≤ λ ≤ 1, and v ∈ D, which can be written as C (v ∗ + λ(v − v ∗ )) − C (v ∗ ) ≤ C (v) − C (v ∗ ) for λ 6= 0. λ Letting λ → 0, we have DC (v ∗ ; v − v ∗ ) ≤ C(v) − C(v ∗ ). 14

By hypothesis, DC(v ∗ ; v − v ∗ ) ≥ 0, which in view of the above inequality, implies C(v) ≥ C(v ∗ ) or v ∗ is optimal. ¤ Finally, if C is strictly convex (i.e. C satisfies (2.18) with strict inequality when v 6= v˜ and 0 < λ < 1), then we have the uniqueness of the optimal element. Theorem 2.5 If C is strictly convex on a convex set D ⊆ V , and has an optimal element v ∗ , then v ∗ is unique. Proof: Suppose that C has a minimum µ at v ∗ and v˜∗ , and v ∗ 6= v˜∗ . Then vˆ = (v ∗ +˜ v ∗ )/2 ∈ D. From the strict convexity of C, we have 1 1 v ∗ ) = µ = min C(v ). C(ˆ v ) < C(v ∗ ) + C(˜ v∈D 2 2 Thus, C(ˆ v ) < µ, contradicting the optimality of v ∗ and v˜∗ . ¤

References [1] T.M. Apostol, Mathematical Analysis, Addison-Wesley, Reading, MA, 1957. [2] K. Yosida, Functional Analysis (Fourth Edition), Springer-Verlag, New York, 1974.

15...