for all 0<hs ho. Now from the dynamic programming principle(6)we have (so, To) L(E(s), u(s)ds +V(so+h, 5(so+h)) which with(57) implies o(S0+h,、(s0+h)-叫(s0,xo)_1 h L(x(s),u(s)ds≤ Send h→0 to obtain 0 o(so, co)-Vo(so, ro)f(o, u)-L(, u)<0 Now maximize over u to obtain at p(so, To)+sup -Vo(so, ro)f(ao, u)-L(ro, u)<0 This proves that v is a viscosity subsolution Supersolution property. Let E C((to, ti)x R") and suppose that V-o attains a local minimum at(so, o); so there exists r>0 such that V(t,x)-o(t,x)≥V(s0,xo)-0(s0,x0)|x-xo|<r,|t-so|<r.(62) gain by OdE estimates, there exists ho >0 such that E(so+)-tol <r for all< hs ho and all u( ) E Uso, t1, where $()denotes the corresponding state trajectory with E(so)=To Assume the supersolution property is false, i. e. there exists a>0 such that P(so, co)+sup-Vo(so, c o)f(ao, u)-L(o, u))<-3ah<0, (64) where 0< h< ho. Now(64) implies 0 ,5(s)-Vo(s,5(s)f((s),u(s))-L(5(s),(s)≤-2ah<0.(65) for all s E[so, So+h] and all u()EUso, ti, for h >0 sufficiently small By the dynamic programming formula( 6), there exists uo()EUso,t1 such that soth V(50,xo)2/L(5(s),0()ds+V(50+h,56(0+1)-ah(60
for all 0 < h ≤ h0. Now from the dynamic programming principle (6) we have V (s0, x0) ≤ Z s0+h s0 L(ξ(s), u(s)) ds + V (s0 + h, ξ(s0 + h)) (58) which with (57) implies −( φ(s0 + h, ξ(s0 + h)) − φ(s0, x0)) h ) − 1 h Z s0+h s0 L(x(s), u(s)) ds ≤ 0. (59) Send h → 0 to obtain − ∂ ∂tφ(s0, x0) − ∇φ(s0, x0)f(x0, u) − L(x0, u) ≤ 0. (60) Now maximize over u to obtain − ∂ ∂tφ(s0, x0) + sup u∈U {−∇φ(s0, x0)f(x0, u) − L(x0, u)} ≤ 0. (61) This proves that V is a viscosity subsolution. Supersolution property. Let φ ∈ C 1 ((t0, t1) × Rn ) and suppose that V − φ attains a local minimum 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. (62) Again by ODE estimates, there exists h0 > 0 such that |ξ(s0 + h) − x0| < r (63) for all 0 ≤ h ≤ h0 and all u(·) ∈ Us0,t1 , where ξ(·) denotes the corresponding state trajectory with ξ(s0) = x0. Assume the supersolution property is false, i.e. there exists α > 0 such that − ∂ ∂tφ(s0, x0) + sup u∈U {−∇φ(s0, x0)f(x0, u) − L(x0, u)} ≤ −3αh < 0, (64) where 0 < h < h0. Now (64) implies − ∂ ∂tφ(s, ξ(s)) − ∇φ(s, ξ(s))f(ξ(s), u(s)) − L(ξ(s), u(s)) ≤ −2αh < 0, (65) for all s ∈ [s0, s0 + h] and all u(·) ∈ Us0,t1 , for h > 0 sufficiently small. By the dynamic programming formula (6), there exists u0(·) ∈ Us0,t1 such that V (s0, x0) ≥ Z s0+h s0 L(ξ0(s), u0(s)) ds + V (s0 + h, ξ0(s0 + h)) − αh (66) 16
where So( denotes the corresponding trajectory with $(so)=To, and combining this with(62) we have d(s0+,50(s0+b)-(s0,xo)1/0+ h L(50(s),to(s)ds≥-a.(67) However, integration of(65)implies 0(s0+h,50(so+b)-(0,20)、_1/+ L(50(s),uo(s)ds≤-2a which contradicts(67) since a>0. This proves the supersolution propert 2.3 Comparison and Uniqueness The most important features of the theory of viscosity solutions are the powerful com- parison and uniqueness theorems. Comparison theorems assert that inequalities holdin on the boundary and /or terminal time also hold in the entire domain. Uniqueness follows from this. Such results are important, since they guarantee unique characterization of viscosity solutions, and ensure that convergent approximations converge to the correc limit. In the context of optimal control problems, value functions are the unique viscosity solutions In this section we give a detailed proof of the comparison and uniqueness results for a class of Dirichlet problems, and apply this to equation(20) for the distance function. We Iso present without proof results for Cauchy problems of the type(7),(8) 2.3.1 Dirichlet Problem Here we follow [ 3, Chapter II] and consider the HJ equation (a)+H(, vv(a))=0 in 3, a special case of (1) To help get a feel for the ideas, suppose Vi, V2 E C(@)nc(@2)(i.e. are smooth) satisfy Vi()+H(a, Vvi())<0(subsolution) V2(a)+H(a, vv2(a))20(supersolution Vi<V2 on aQ(boundary condition) Let Io E Q be a maximum point of Vi-V2. Now if o E& (interior, not on boundary then VVi(o)=VV2(ao) and subtracting the first second line of(70) from the first gives
where ξ0(·) denotes the corresponding trajectory with ξ(s0) = x0, and combining this with (62) we have −( φ(s0 + h, ξ0(s0 + h)) − φ(s0, x0)) h ) − 1 h Z s0+h s0 L(ξ0(s), u0(s)) ds ≥ −α. (67) However, integration of (65) implies −( φ(s0 + h, ξ0(s0 + h)) − φ(s0, x0)) h ) − 1 h Z s0+h s0 L(ξ0(s), u0(s)) ds ≤ −2α. (68) which contradicts (67) since α > 0. This proves the supersolution property. 2.3 Comparison and Uniqueness The most important features of the theory of viscosity solutions are the powerful comparison and uniqueness theorems. Comparison theorems assert that inequalities holding on the boundary and/or terminal time also hold in the entire domain. Uniqueness follows from this. Such results are important, since they guarantee unique characterization of viscosity solutions, and ensure that convergent approximations converge to the correct limit. In the context of optimal control problems, value functions are the unique viscosity solutions. In this section we give a detailed proof of the comparison and uniqueness results for a class of Dirichlet problems, and apply this to equation (20) for the distance function. We also present without proof results for Cauchy problems of the type (7), (8). 2.3.1 Dirichlet Problem Here we follow [3, Chapter II] and consider the HJ equation V (x) + H(x, ∇V (x)) = 0 in Ω, (69) a special case of (1). To help get a feel for the ideas, suppose V1, V2 ∈ C(Ω)∩C 1 (Ω) (i.e. are smooth) satisfy V1(x) + H(x, ∇V1(x)) ≤ 0 (subsolution) V2(x) + H(x, ∇V2(x)) ≥ 0 (supersolution) (70) in Ω and V1 ≤ V2 on ∂Ω (boundary condition). (71) Let x0 ∈ Ω be a maximum point of V1 − V2. Now if x0 ∈ Ω (interior, not on boundary) then ∇V1(x0) = ∇V2(x0) and subtracting the first second line of (70) from the first gives V1(x0) − V2(x0) ≤ 0 17
which implies V(x)-V2(x)≤v(xo)-V2(xo)≤0x∈ If it happened that o E aQ, then using(71) V1(x)-V2(x)≤V(x0)-V2(xo)≤0Vx∈9 Therefore Vi V2 in Q, a comparison result Comparison implies uniqueness for the Dirichlet problem V=y on aQ2 To see this, suppose Vi and v2 are two solutions. Now Vi=V2= v on aS. Then by the comparison result, we get Vi V2 in Q2. Similarly, interchanging Vi, V2 we again apply comparison to obtain V2 <Vi in Q2. Hence Vi= V2 in Q2 This illustrates the role of sub- and supersolutions and boundary conditions in the comparison and uniqueness theory. We now give a precise theorem and proof ( 3, Theorem II.3. 1 ). This result does not use convexity or any connection to optimal control, and applies generally Theorem 2. 3 Let s be a bounded open subset of R. Assume Vi, V2 E C(S)are,re- spectively, viscosity sub-and supersolution of (69), and satisfy the inequality(71)on the boundary. Assume that H satisfie H(x,))-H(y,川川≤1(x-y|(1+1A), forx,y∈9,A∈Rn, where wl:[0.,+∞)→0,+∞) is continuous, nondecreasing with w1(0)=0(1 is called a modulus). Then V1<V2 in Q2. PROOF. For e>0 define the continuous function on Q2 x Q by 重(x,y)=Vi(x)-V2(y) Let(xa,y)∈9×9 be a maximum point for e over S2×!.Then max(V1-V2)(x)≤maxΦ2(x,x)≤max重(x,y)=更(xe,v) x∈9 x∈9 We claim that lim sup重(x2,y)=0, which together with(77)proves the theorem
which implies V1(x) − V2(x) ≤ V1(x0) − V2(x0) ≤ 0 ∀ x ∈ Ω. (72) If it happened that x0 ∈ ∂Ω, then using (71) V1(x) − V2(x) ≤ V1(x0) − V2(x0) ≤ 0 ∀ x ∈ Ω. (73) Therefore V1 ≤ V2 in Ω, a comparison result. Comparison implies uniqueness for the Dirichlet problem V (x) + H(x, ∇V (x)) = 0 in Ω, V = ψ on ∂Ω. (74) To see this, suppose V1 and V2 are two solutions. Now V1 = V2 = ψ on ∂Ω. Then by the comparison result, we get V1 ≤ V2 in Ω. Similarly, interchanging V1, V2 we again apply comparison to obtain V2 ≤ V1 in Ω. Hence V1 = V2 in Ω. This illustrates the role of sub- and supersolutions and boundary conditions in the comparison and uniqueness theory. We now give a precise theorem and proof ([3, Theorem II.3.1]). This result does not use convexity or any connection to optimal control, and applies generally. Theorem 2.3 Let Ω be a bounded open subset of Rn . Assume V1, V2 ∈ C(Ω) are, respectively, viscosity sub- and supersolution of (69), and satisfy the inequality (71) on the boundary. Assume that H satisfies |H(x, λ) − H(y, λ)| ≤ ω1(|x − y|(1 + |λ|)), (75) for x, y ∈ Ω, λ ∈ Rn , where ω1 : [0, +∞) → [0, +∞) is continuous, nondecreasing with ω1(0) = 0 (ω1 is called a modulus). Then V1 ≤ V2 in Ω. (76) Proof. For ε > 0 define the continuous function on Ω × Ω by Φε(x, y) = V1(x) − V2(y) − |x − y| 2 2ε . Let (xε, yε) ∈ Ω × Ω be a maximum point for Φε over Ω × Ω. Then max x∈Ω (V1 − V2)(x) ≤ max x∈Ω Φε(x, x) ≤ max x,y∈Ω Φε(x, y) = Φε(xε, yε). (77) We claim that lim sup ε→0 Φε(xε, yε) = 0, (78) which together with (77) proves the theorem. 18
Let us prove(78). Now the fact that Φ(x,x)≤Φ2(xe,ye) te -yel ≤V(x)-V2(v)≤C for suitable C>0(recall V2 is bounded on Q2), and so x-y|≤(Ce) Therefore xe-y→0as and by continuity, V2(e)-v2(ye)-0 as E-0; hence(79) gives lre-ye12 We now need to consider where the points e, ye lie Case(i). Suppose ag, ye E Q(both interior points), for all sufficiently small e >0. Let o()=(2)--,o2()=12()+-uP Now o1, 2 E C( Q2), ae is a local maximum for V1-2, and ye is a local minimum for V2-o1. Alse 2(xe) The viscosity sub- and supersolution definition implies V1(x)+H(xe,)≤0 V2(v)+H(ye,)≥0. Subtracting we have (x)-V2(y)+H( <0 and using the assumption on H V(x2)-V(v)≤u1(|x-/1+2-ml This implies 重(xe,y)≤u1(xe-yl(1+ and hence(78) follows using( 81)and( 82) 19
Let us prove (78). Now the fact that Φε(xε, xε) ≤ Φε(xε, yε) implies |xε − yε| 2 2ε ≤ V2(xε) − V2(yε) ≤ C (79) for suitable C > 0 (recall V2 is bounded on Ω), and so |xε − yε| ≤ (Cε) 1/2 . (80) Therefore |xε − yε| → 0 as ε → 0, (81) and by continuity, V2(xε) − V2(yε) → 0 as ε → 0; hence (79) gives |xε − yε| 2 2ε → 0 as ε → 0. (82) We now need to consider where the points xε, yε lie. Case (i). Suppose xε, yε ∈ Ω (both interior points), for all sufficiently small ε > 0. Let φ1(y) = V1(xε) − |xε − y| 2 2ε , φ2(x) = V2(yε) + |x − yε| 2 2ε , (83) Now φ1, φ2 ∈ C 1 (Ω), xε is a local maximum for V1 − φ2, and yε is a local minimum for V2 − φ1. Also, ∇φ1(yε) = xε − yε ε = ∇φ2(xε). (84) The viscosity sub- and supersolution definition implies V1(xε) + H(xε, xε−yε ε ) ≤ 0, V2(yε) + H(yε, xε−yε ε ) ≥ 0. (85) Subtracting we have V1(xε) − V2(yε) + H(xε, xε − yε ε ) − H(yε, xε − yε ε ) ≤ 0 (86) and using the assumption on H V1(xε) − V2(yε) ≤ ω1(|xε − yε|(1 + |xε − yε| ε )). (87) This implies Φε(xε, yε) ≤ ω1(|xε − yε|(1 + |xε − yε| ε )), (88) and hence (78) follows using (81) and (82). 19
Case(i). Now suppose there exists a subsequence e,;→0asi→∞ such that e;∈Og orye;∈0.Ifxs;∈9, V(xa1)-V2(ve:)≤V(x1)-V(ve)→0 (89) asi→∞, or if y;∈Og, V(x;)-V2(ye;)≤(xe;)-V(ve;)→0 asi→o; hence(78) This completes the proof The distance function is the unique viscosity solution of(20),(21). At first sight Theorem 2.3 does not apply to(20),(21). This is because equation(20) does not have the additive V-term that(69)has, and this term was used in an essential way in the proof of Theorem 2.3. In fact, in general viscosity solutions to equations of the form I(, VV)=0 may not be unique! For instance, in the context of the Bounded Real Lemma both the available storage and required supply are viscosity solutions of equations of the type( 91) It turns out that comparison/uniqueness for HJ equation(20) for the distance function can be proved, either directly using additional hypothesis(such as convexity 3, Theorem II.5.9), or via a transformation as we now show We use the Kruskoy transformation. a useful trick. Define W=重(V)=1-e where V is the distance function(19). Then W is a viscosity solution of W(x)+|VV(x)-1=0in9, W=0 on aQ by the general properties of viscosity solutions mentioned above. By Theorem 2.3, we see that w is the unique viscosity solution of (93), and hence V=()-1(W)=-log(1-W) is the unique viscosity solution of (20),(21). Comparison also follows in the same way 2.3.2 Cauchy Problem In this section we simply state without proof an example of a comparison/uniqueness result, 3, Theorem III.3.15]. There are many results like this available, with variot kinds of structural assumptions(e.g(95),(96)which must be checked in order to apply
Case (ii). Now suppose there exists a subsequence εi → 0 as i → ∞ such that xεi ∈ ∂Ω or yεi ∈ ∂Ω. If xεi ∈ ∂Ω, V1(xεi ) − V2(yεi ) ≤ V2(xεi ) − V2(yεi ) → 0 (89) as i → ∞, or if yεi ∈ ∂Ω, V1(xεi ) − V2(yεi ) ≤ V1(xεi ) − V1(yεi ) → 0 (90) as i → ∞; hence (78). This completes the proof. The distance function is the unique viscosity solution of (20), (21). At first sight Theorem 2.3 does not apply to (20), (21). This is because equation (20) does not have the additive V -term that (69) has, and this term was used in an essential way in the proof of Theorem 2.3. In fact, in general viscosity solutions to equations of the form H(x, ∇V ) = 0 (91) may not be unique! For instance, in the context of the Bounded Real Lemma both the available storage and required supply are viscosity solutions of equations of the type (91). It turns out that comparison/uniqueness for HJ equation (20) for the distance function can be proved, either directly using additional hypothesis (such as convexity [3, Theorem II.5.9]), or via a transformation as we now show. We use the Kruskov transformation, a useful trick. Define W = Φ(V ) 4 = 1 − e −V , (92) where V is the distance function (19). Then W is a viscosity solution of W(x) + |∇V (x)| − 1 = 0 in Ω, W = 0 on ∂Ω, (93) by the general properties of viscosity solutions mentioned above. By Theorem 2.3, we see that W is the unique viscosity solution of (93), and hence V = Ψ(W) 4 = Φ−1 (W) = − log(1 − W) (94) is the unique viscosity solution of (20), (21). Comparison also follows in the same way. 2.3.2 Cauchy Problem In this section we simply state without proof an example of a comparison/uniqueness result, [3, Theorem III.3.15]. There are many results like this available, with various kinds of structural assumptions (e.g. (95), (96)) which must be checked in order to apply them. 20