A function V E C(@) is a viscosity subsolution of (1) if, for any o E C(@)and any al maximum to EQ of V-o we have F(x0,V(xo),Vo(xo)≤0 A function V E C( )is a viscosity supersolution of(1)if, for any oE C(Q2)and any local minimum To E Q2 of V-o we have F(x0,V(xo),Vo(x0)≥ A function V E C(Q2)is a viscosity solution of(1) if it is both a subsolution and a This definition may at first sight appear strange, though in practice it is often easy to use. Note that derivatives in(24 ) and(25) appear only on the smooth function There re a number of equivalent formulations, and the key point is that the definitions relate sub-or superdifferentials(of functions which need not be differentiable) to inequalities associated with the HJ equation The superdiferential of a function V E C(Q2)is defined by +v(x)={A∈R: lim sup y y→x,y∈ The subdifferential of a function V E C(S)is defined by Dv(x)={A∈R”: liminf V()-(a)-(y-) If V E C(S) then D+v(r)= D-v(a)=fvv(a)). In general, A E D+v(a)iff there exists E C(Q)such that Vo(r)=A and V-o has a local maximum at and A E D-V() iff there exists o E C(@2)such that Vo(a)=A and V-o has a loc minimum at ?r Therefore the viscosity definition is equivalently characterized by F(x,V(x),)≤0VA∈Dv(x) F(x,V(x),A)≥0VA∈Dv( Example 2.2 Continuing with Example 2. 1, we see that {1}if-1<x<0 D+V(r)= d-v(ar) {-1}if0<x<1 V(0)=[-1,1] Consequently V is ity solution of(20) However, the function Vi is not is viscosity solution, since OE D-Vi(0)=[1,1],and 0-120
A function V ∈ C(Ω) is a viscosity subsolution of (1) if, for any φ ∈ C 1 (Ω) and any local maximum x0 ∈ Ω of V − φ we have F(x0, V (x0), ∇φ(x0)) ≤ 0 (24) A function V ∈ C(Ω) is a viscosity supersolution of (1) if, for any φ ∈ C 1 (Ω) and any local minimum x0 ∈ Ω of V − φ we have F(x0, V (x0), ∇φ(x0)) ≥ 0 (25) A function V ∈ C(Ω) is a viscosity solution of (1) if it is both a subsolution and a supersolution. This definition may at first sight appear strange, though in practice it is often easy to use. Note that derivatives in (24) and (25) appear only on the smooth function φ. There are a number of equivalent formulations, and the key point is that the definitions relate sub- or superdifferentials (of functions which need not be differentiable) to inequalities associated with the HJ equation. The superdifferential of a function V ∈ C(Ω) is defined by D +V (x) = {λ ∈ Rn : lim sup y→x, y∈Ω V (y) − V (x) − λ(y − x) |x − y| ≤ 0} (26) The subdifferential of a function V ∈ C(Ω) is defined by D −V (x) = {λ ∈ Rn : lim inf y→x, y∈Ω V (y) − V (x) − λ(y − x) |x − y| ≥ 0} (27) If V ∈ C 1 (Ω) then D+V (x) = D−V (x) = {∇V (x)}. In general, λ ∈ D+V (x) iff there exists φ ∈ C 1 (Ω) such that ∇φ(x) = λ and V − φ has a local maximum at x; and λ ∈ D−V (x) iff there exists φ ∈ C 1 (Ω) such that ∇φ(x) = λ and V − φ has a local minimum at x. Therefore the viscosity definition is equivalently characterized by F(x, V (x), λ) ≤ 0 ∀ λ ∈ D +V (x) (28) and F(x, V (x), λ) ≥ 0 ∀ λ ∈ D −V (x) (29) Example 2.2 Continuing with Example 2.1, we see that D+V (x) = D−V (x) = {1} if − 1 < x < 0 {−1} if 0 < x < 1 D+V (0) = [−1, 1], D−V (0) = ∅. (30) Consequently V is a viscosity solution of (20). However, the function V1 is not is viscosity solution, since 0 ∈ D−V1(0) = [−1, 1], and |0| − 1 6≥ 0. 11
Properties. Some properties of viscosity solutions 1.(Consistency. If V E C(@)is a viscosity solution of (1), then for any point a E Q at which v is differentiable we have F(a,v(a), VV(a))=0 2. If V is locally Lipschitz continuous in Q, then F(a,V(), VV(r))=0 a.e. in Q 3. (Stability ) Let VEC(S)(n>0 be viscosity solutions of FN(,V(a), Vv(a))=0 in Q and assume VN- V locally uniformly in 9, and FN- F locally uniformly in 2×R×Rn,asN→∞. Then v∈C(9) is a viscosity solution of(1) 4.(Monotonic change of variable. Let V E C(Q)be a viscosity solution of (1)and 业∈C(R) be such thatΦ(t)>0. Then w=重(V) is a viscosity solution of F(a,yW()),y(W(a)vW(a))=0 (31) where=更-1 2.2 Value Functions are Viscosity Solutions 2.2.1 The Distance Function is a Viscosity Solution We showed in Example 2.2 that in the specific case at hand the distance function is a viscosity solution. Let's now consider the general case. We use the dynamic programming principle(22) to illustrate a general methodology Subsolution property. Let EC(Q2)and suppose that V-o attains a local maximum at o E Q; so there exists r>0 such that the ball B(o, r)CQ and (x)-(x)≤V(xo)-(xo)x∈B(xo,r) We want to show that Vo(xo)|-1≤ Let hE R, and set a =To+th. Then for t>0 sufficiently small E B(ao, r),and from (32) -(o(o+ th)-(ao))<-((o+th) ) V(o Now from the dynamic programming principle(22)we ve (xo)≤th+V(xo+th)
Properties. Some properties of viscosity solutions: 1. (Consistency.) If V ∈ C(Ω) is a viscosity solution of (1), then for any point x ∈ Ω at which V is differentiable we have F(x, V (x), ∇V (x)) = 0. 2. If V is locally Lipschitz continuous in Ω, then F(x, V (x), ∇V (x)) = 0 a.e. in Ω. 3. (Stability.) Let V N ∈ C(Ω) (N ≥ 0) be viscosity solutions of F N (x, V N (x), ∇V N (x)) = 0 in Ω, and assume V N → V locally uniformly in Ω, and F N → F locally uniformly in Ω × R × Rn , as N → ∞. Then V ∈ C(Ω) is a viscosity solution of (1). 4. (Monotonic change of variable.) Let V ∈ C(Ω) be a viscosity solution of (1) and Ψ ∈ C 1 (R) be such that Φ0 (t) > 0. Then W = Φ(V ) is a viscosity solution of F(x, Ψ(W(x)), Ψ 0 (W(x))∇W(x)) = 0 (31) where Ψ = Φ−1 . 2.2 Value Functions are Viscosity Solutions 2.2.1 The Distance Function is a Viscosity Solution We showed in Example 2.2 that in the specific case at hand the distance function is a viscosity solution. Let’s now consider the general case. We use the dynamic programming principle (22) to illustrate a general methodology. Subsolution property. Let φ ∈ C 1 (Ω) and suppose that V −φ attains a local maximum at x0 ∈ Ω; so there exists r > 0 such that the ball B(x0, r) ⊂ Ω and V (x) − φ(x) ≤ V (x0) − φ(x0) ∀ x ∈ B(x0, r). (32) We want to show that |∇φ(x0)| − 1 ≤ 0. (33) Let h ∈ Rn , and set x = x0 + th. Then for t > 0 sufficiently small x ∈ B(x0, r), and so from (32), −(φ(x0 + th) − φ(x0)) ≤ −(V (x0 + th) − V (x0)) (34) Now from the dynamic programming principle (22) we have V (x0) ≤ t|h| + V (x0 + th) (35) 12
Combining(34)and(35)we find that )-o(x0)≤th, 1<0 Send t」0 to obtain h l Vo(xo)h-1≤ Since h E Rn is arbitrary we obtain (32)as required. This proves that V is a viscosity subsolution a e. supersolution proerty, Let E C(Q)and suppose that V-p attains a local minimum at o E Q; so there exists r>0 such that the ball B(o, r)CQ and V(x)-o(x)≥V(xo)-o(x0)x∈B(xo,r) 39 We want to show that Vo(xo)|-1≥0. Suppose that(40) is false, so that Vo(xo)|-1≤-a<0 (41) for some 1>a>0. By making r>0 smaller if necessary, we may assume V(x)-1≤-a/2<0yx∈B(xo,r) By the fundamental theorem of calculus. we have o(x)=0(x0)+/Va(x+(1-7)xo)(x-xo)dhy Now from the dynamic programming relation(22), pick z*E B(ao, r),2*+ ro, such that V(xo0)=|xo-2|+V(2) Using this and(39)we have ((2*)-0(xo)≥|z*-xo However, from( 42) and(43)we must have (0(2)-0(x0)≤(1-a/2)z*-ol Inequalities(45)and(46)are in contradiction, so in fact(40)holds. This proves that V is a supersolution It can be seen here that the dynamic programming principle provided the key inequal ities to derive the sub- and supersolution relations
Combining (34) and (35) we find that −(φ(x0 + th) − φ(x0)) ≤ t|h|, (36) and so −( φ(x0 + th) − φ(x0) t|h| ) − 1 ≤ 0 (37) Send t ↓ 0 to obtain − 1 |h| ∇φ(x0)h − 1 ≤ 0. (38) Since h ∈ Rn is arbitrary we obtain (32) as required. This proves that V is a viscosity subsolution. Supersolution property. Let φ ∈ C 1 (Ω) and suppose that V −φ attains a local minimum at x0 ∈ Ω; so there exists r > 0 such that the ball B(x0, r) ⊂ Ω and V (x) − φ(x) ≥ V (x0) − φ(x0) ∀ x ∈ B(x0, r). (39) We want to show that |∇φ(x0)| − 1 ≥ 0. (40) Suppose that (40) is false, so that |∇φ(x0)| − 1 ≤ −α < 0 (41) for some 1 > α > 0. By making r > 0 smaller if necessary, we may assume |∇φ(x)| − 1 ≤ −α/2 < 0 ∀ x ∈ B(x0, r). (42) By the fundamental theorem of calculus, we have φ(x) = φ(x0) + Z 1 0 ∇φ(γx + (1 − γ)x0)(x − x0)dγ (43) Now from the dynamic programming relation (22), pick z ∗ ∈ B(x0, r), z ∗ 6= x0, such that V (x0) = |x0 − z ∗ | + V (z ∗ ). (44) Using this and (39) we have −(φ(z ∗ ) − φ(x0)) ≥ |z ∗ − x0|. (45) However, from (42) and (43) we must have −(φ(z ∗ ) − φ(x0)) ≤ (1 − α/2)|z ∗ − x0|. (46) Inequalities (45) and (46) are in contradiction, so in fact (40) holds. This proves that V is a supersolution. It can be seen here that the dynamic programming principle provided the key inequalities to derive the sub- and supersolution relations. 13
2.2.2 Optimal Control Value Function is a Viscosity Solution Dynamic programming. The dymamic programming principle states that for every t, ti v(t, r)=inf/L((s), u(s)ds+v(r, a(r) We now prove this(by a standard technique in optimal control FixrE[ t, ti], and u( Ut tr. Let a() denote the corresponding trajectory with initial state r(t)=T, and consider (r, r(r). Let e>0 and choose u1(E Ur,t1, with trajectory T1()on r, ti] with i(r)=a(r) be such that V(r,(r)2J(,r(r);u1()-E Define u2(s) u(s)t≤s<r u1(s) ≤t1 (48) with trajectory T2(), 2(t)=a. Now T2(s=r(s),sEt, rl, and T2(s)=T1(s),sE[r, til V(r,x)≤J(t, f L((s), u(s))ds+v((ti) C L((s),u(s))ds+L(1(s),u1(s))ds +v/(a(ti)) CL(a(s), u(s))ds+V(r,(r))+e using(47). Therefore V(t,x)≤inf L(r(s),u(s)ds+v(r, a(r))+e Since e>0 was arbitrary, we have V(t,x)≤inf L(a(s), u(s))ds+v(r, z(r)) u( Elt This proves one half of (6) For the second half of (6), let u(EUt, tr, and let a( be the corresponding trajectory with a(t)=.. Then (t,x;u()=hL(x(),(s)ds+v(r(1) ft L((s),u(s)ds+ L(r(s), u(s)ds +v(r(ti)) >L(e(s),u(s)ds+v(r, a(r) N J(t, r;u()) inf I L((s), u(s)ds+v(r, i(r)))
2.2.2 The Optimal Control Value Function is a Viscosity Solution Dynamic programming. The dynamic programming principle states that for every r ∈ [t, t1], V (t, x) = inf u(·)∈Ut,r Z r t L(x(s), u(s)) ds + V (r, x(r)) . (6) We now prove this (by a standard technique in optimal control). Fix r ∈ [t, t1], and u(·) ∈ Ut,t1 . Let x(·) denote the corresponding trajectory with initial state x(t) = x, and consider (r, x(r)). Let ε > 0 and choose u1(·) ∈ Ur,t1 , with trajectory x1(·) on [r, t1] with x1(r) = x(r) be such that V (r, x(r)) ≥ J(r, x(r); u1(·)) − ε. (47) Define u2(s) = u(s) t ≤ s < r u1(s) r ≤ s ≤ t1 (48) with trajectory x2(·), x2(t) = x. Now x2(s) = x(s), s ∈ [t, r], and x2(s) = x1(s), s ∈ [r, t1]. Next, V (r, x) ≤ J(t, x; u2(·)) = R t1 t L(x(s), u(s)) ds + ψ(x(t1)) = R t r L(x(s), u(s)) ds + R r t L(x1(s), u1(s)) ds + ψ(x(t1)) = R t r L(x(s), u(s)) ds + V (r, x(r)) + ε (49) using (47). Therefore V (t, x) ≤ inf u(·)∈Ut,r Z r t L(x(s), u(s)) ds + V (r, x(r)) + ε. (50) Since ε > 0 was arbitrary, we have V (t, x) ≤ inf u(·)∈Ut,r Z r t L(x(s), u(s)) ds + V (r, x(r)) . (51) This proves one half of (6). For the second half of (6), let u(·) ∈ Ut,t1 , and let x(·) be the corresponding trajectory with x(t) = x. Then J(t, x; u(·)) = R t1 t L(x(s), u(s)) ds + ψ(x(t1)) = R r t L(x(s), u(s)) ds + R t1 r L(x(s), u(s)) ds + ψ(x(t1)) ≥ R r t L(x(s), u(s)) ds + V (r, x(r)). (52) Now minimizing, we obtain V (t, x) = infu(·)∈Ut,t1 J(t, x; u(·)) ≥ infu(·)∈Ut,t1 { R r t L(x(s), u(s)) ds + V (r, x(r))} (53) 14
which is the desired second half of(6). This establishes the dynamic programming prin- de Regularity. By regularity we mean the degree of continuity or differentiability; i.e. of smoothness. The regularity of value functions is determined by both the regularity of the data defining it(e.g. f, L, v ), and on the nature of the optimization problem. In many applications, the value function can readily be shown to be continuous, even Lipschitz, but not C in general. The finite horizon value function V(t, r)defined by (5)can be shown to be bounded and Lipschitz continuous under the following (rather strong) assumptions on the problem data: f, L, y are bounded with bounded first order derivatives. We shall It should be noted that in general it can happen that value functions fail to be con tinuous. In fact, the viscosity theory is capable of dealing with semicontinuous or even only locally bounded functions Viscosity solution. Let us re-write the HJ equation(7)as follows: at v(t, 2)+ H(,VV(, 2))=0 in(o, t1)X R with a new definition of the hamiltonian {-入·f(x,)-L(x,t)} The sign convention used in(7)relates to the maximum principle in PDE, and is compat ible with the convention used for the general HJ equation(1). Note that the Hamiltonian is now conver in入. A function V E C(to, til x R)is a viscosity subsolution(resp. supersolution) of (7) if for all∈Ch(to,t1)×Rn) 0 o(s0,x0)+H(xo,Vo(s0,x0)≤0(resp.≥ (54) at every point(so, o) where V-o attains a local maximum(resp. minimum). V viscosity solution if it is both a subsolution and a supersolution We now show that the value function V defined by(5)is a viscosity solution of(7) Subsolution property. Let EC((to, t1)xR)and suppose that V-o attains a local maximum at(so, to); so there exists r >0 such that V(t, r)-p(t, a)<V(so, to)-(so, o)Vlr-aol<r, t-sol <r.(55) Fix u(t)=u E U for all t(constant control) and let 5( denote the corresponding state trajectory with f(so)=co. By standard ODE estimates, we have IE(so+h)-tol<r for all 0 s hs ho(some ho>0)-since U and f are bounded. Then by(55) V(so +h, 5(so+ h))-(so+h, S(so+h))<v(so, to)-o(so, to (57)
which is the desired second half of (6). This establishes the dynamic programming principle (6). Regularity. By regularity we mean the degree of continuity or differentiability; i.e. of smoothness. The regularity of value functions is determined by both the regularity of the data defining it (e.g. f, L, ψ), and on the nature of the optimization problem. In many applications, the value function can readily be shown to be continuous, even Lipschitz, but not C 1 in general. The finite horizon value function V (t, x) defined by (5) can be shown to be bounded and Lipschitz continuous under the following (rather strong) assumptions on the problem data: f, L, ψ are bounded with bounded first order derivatives. We shall assume this. It should be noted that in general it can happen that value functions fail to be continuous. In fact, the viscosity theory is capable of dealing with semicontinuous or even only locally bounded functions. Viscosity solution. Let us re-write the HJ equation (7) as follows: − ∂ ∂tV (t, x) + H(x, ∇xV (t, x)) = 0 in (t0, t1) × Rn , (7)0 with a new definition of the Hamiltonian H(x, λ) = sup v∈Rm {−λ · f(x, v) − L(x, v)} . (9)0 The sign convention used in (7)’ relates to the maximum principle in PDE, and is compatible with the convention used for the general HJ equation (1). Note that the Hamiltonian is now convex in λ. A function V˜ ∈ C([t0, t1] × Rn ) is a viscosity subsolution (resp. supersolution) of (7)’ if for all φ ∈ C 1 ((t0, t1) × Rn ), − ∂ ∂tφ(s0, x0) + H(x0, ∇φ(s0, x0)) ≤ 0 (resp. ≥ 0) (54) at every point (s0, x0) where V˜ − φ attains a local maximum (resp. minimum). V˜ is a viscosity solution if it is both a subsolution and a supersolution. We now show that the value function V defined by (5) is a viscosity solution of (7)’. Subsolution property. Let φ ∈ C 1 ((t0, t1)×Rn ) and suppose that V −φ attains a local maximum at (s0, x0); so there exists r > 0 such that V (t, x) − φ(t, x) ≤ V (s0, x0) − φ(s0, x0) ∀ |x − x0| < r, |t − s0| < r. (55) Fix u(t) = u ∈ U for all t (constant control) and let ξ(·) denote the corresponding state trajectory with ξ(s0) = x0. By standard ODE estimates, we have |ξ(s0 + h) − x0| < r (56) for all 0 ≤ h ≤ h0 (some h0 > 0) - since U and f are bounded. Then by (55) V (s0 + h, ξ(s0 + h)) − φ(s0 + h, ξ(s0 + h)) ≤ V (s0, x0) − φ(s0, x0) (57) 15