PDE methods for multiscale control and differential games

PDE methods for multiscale control and differential games

Martino Bardi

Department of Pure and Applied Mathematics University of Padua, Italy

Kickoff Meeting I.T.N. SADCO ENSTA, Paris, March 3rd, 2011

Plan

Two-scale systems: examples and motivations

The Hamilton-Jacobi approach to Singular Perturbations Representation of the limit control problem:

Uncontrolled fast variables

Homogenization in low dimensions

Two-scale systems

Dynamical systems with two groups of variables evolving on different time-scales(xs,yτ),τ =s/ε, 0< ε <<1, governed by ODEs

x˙s=f(xs,ys) xs ∈Rⁿ, y˙_s= ¹_εg(x_s,y_s) y_s ∈R^m, or by Stochastic DEs

dxs=f(xs,ys)ds+ σ(xs,ys)dWs

dy_s= ¹_εg(x_s,y_s)ds+ ^√1_εν(x_s,y_s)dW_s Hope to simplify the model in the limitε →0:

aSingular Perturbationproblem.

Two-scale systems

Dynamical systems with two groups of variables evolving on different time-scales(xs,yτ),τ =s/ε, 0< ε <<1, governed by ODEs

x˙s=f(xs,ys) xs ∈Rⁿ, y˙_s= ¹_εg(x_s,y_s) y_s ∈R^m, or by Stochastic DEs

dxs=f(xs,ys)ds+ σ(xs,ys)dWs

dy_s= ¹_εg(x_s,y_s)ds+ ^√1_εν(x_s,y_s)dW_s Hope to simplify the model in the limitε →0:

aSingular Perturbationproblem.

The theory is classical for Ordinary Differential Equations, see Levinson and Tychonov 1952, O’Malley’s book 1974, and has a large literature also for systemswith controls,

x˙_s=f(x_s,y_s,αs) y˙_s= ¹_εg(x_s,y_s,αs),

αs a measurable control function taking values in a given setA, see Kokotovi´c - Khalil - O’Reilly book 1986 (deterministic case)

Bensoussan 1988, Kushner 1990 also stochastic case:

dxs =f(xs,ys,αs)ds+ σ(xs,ys,αs)dWs

dy_s = ¹_εg(x_s,y_s,α_s)ds+ ^√1_εν(x_s,y_s,α_s)dW_s Main motivation: reducing the dimensionof the state space.

There are many different models in Physics, Engineering, Finance,....

The theory is classical for Ordinary Differential Equations, see Levinson and Tychonov 1952, O’Malley’s book 1974, and has a large literature also for systemswith controls,

x˙_s=f(x_s,y_s,αs) y˙_s= ¹_εg(x_s,y_s,αs),

αs a measurable control function taking values in a given setA, see Kokotovi´c - Khalil - O’Reilly book 1986 (deterministic case)

Bensoussan 1988, Kushner 1990 also stochastic case:

dxs =f(xs,ys,αs)ds+ σ(xs,ys,αs)dWs

dy_s = ¹_εg(x_s,y_s,α_s)ds+ ^√1_εν(x_s,y_s,α_s)dW_s Main motivation: reducing the dimensionof the state space.

There are many different models in Physics, Engineering, Finance,....

Example 1: Mechanical system with Large Damping

Thelarge time behaviorof

X¨ =F(X,t) − X˙ ε is described by x(s) :=X(s/ε)that solves

岨x =F(x,s/ε) − ˙x. In the autonomous case ( F =F(x) ) this writes

x˙_s =y_s y˙s = ^F(xs_ε^)−y2 ^s, The limit is theQuasi-Static approximation

x˙ =F(x).

F. Hoppensteadt, "Quasi-Static state analysis...", Courant L. N. 2010

Example 1: Mechanical system with Large Damping

Thelarge time behaviorof

X¨ =F(X,t) − X˙ ε is described by x(s) :=X(s/ε)that solves

岨x =F(x,s/ε) − ˙x. In the autonomous case ( F =F(x) ) this writes

x˙_s =y_s y˙s = ^F(xs_ε^)−y2 ^s, The limit is theQuasi-Static approximation

x˙ =F(x).

F. Hoppensteadt, "Quasi-Static state analysis...", Courant L. N. 2010

Example 2: Control systems with stable fast variables

In Example 1 the formal limit

x˙_s =f(x_s,y_s), 0=g(x_s,y_s)

is correct: it fits in theReduced Order Method. For control system the ROM gives in the limit the DIFFERENTIAL-ALGEBRAIC system

x˙_s =f(x_s,y_s,αs), 0=g(x_s,y_s,αs),

provided that (roughly speaking) the "fast subsystem" (with frozen x ) y˙_τ =g(x,y_τ,α_τ)

has anequilibriumregime with anasymptotically stabilizing feedback, see Kokotovi´c - Khalil - O’Reilly book 1986.

Examples in Engineering: high gain feedback, cheap control,....

BUT, many other models doNOT have this stabilityproperty!

Example 2: Control systems with stable fast variables

In Example 1 the formal limit

x˙_s =f(x_s,y_s), 0=g(x_s,y_s)

is correct: it fits in theReduced Order Method. For control system the ROM gives in the limit the DIFFERENTIAL-ALGEBRAIC system

x˙_s =f(x_s,y_s,αs), 0=g(x_s,y_s,αs),

provided that (roughly speaking) the "fast subsystem" (with frozen x ) y˙_τ =g(x,y_τ,α_τ)

has anequilibriumregime with anasymptotically stabilizing feedback, see Kokotovi´c - Khalil - O’Reilly book 1986.

Examples in Engineering: high gain feedback, cheap control,....

BUT, many other models doNOT have this stabilityproperty!

Example 3: Control systems in oscillating media

Thehomogenizationproblem x˙_s=f

x_s,x_s ε, αs



, J = Z t

0

l x_s,x_s

ε , αs



ds+h x_t,x_t

ε



by settingys=xs/εcan be written as x˙s =f(xs,ys, αs) y˙_s = ¹_εf(x_s,y_s, α_s) J =Rt

0l(x_s,y_s, α_s)ds+h(x_t,y_t) that is a Singular Perturbation problem withg =f.

Example 4: Financial models

The evolution of a stock S withstochastic volatilityσis d log Ss = γds+σ(ys)dWs

dy_s = ¹_ε(m−y_s) +^√ν_εdW˜_s

see Fouque - Papanicolaou - Sircar, book 2000, for empirical data and many examples.

Merton portfolio optimizationproblem with stochastic volatility:

investβs in the stock Ss,1− β_s in a bond with interest rate r . Then the wealth x_s evolves as

dxs = (r+ (γ −r)βs)xsds+xsβsσ(ys)dWs

dy_s = ¹_ε(m−y_s)ds+ ^√ν_εdW˜_s

Problem: maximize the expected utility at time t, E[h(xt)], h increasing concave function.

Example 5: Control systems on thin structures

State constraint on the z variables x˙_s=f(x_s,z_s, α_s)

z˙s=g(xs,zs, αs) |z_s| ≤ ε, by settingy_s=z_s/εbecomes

x˙_s =f(x_s,εy_s, αs)

y˙_s = ¹_εg(x_s,εy_s, αs) |y_s| ≤1.

This can be used to justify models of optimal control ongraphsor networks.

The H-J approach to Singular Perturbations

General control system with TWO controllers

dx_s =f(x_s,y_s,αs,βs)ds+ σ(x_s,y_s,αs,βs)dW_s, x_s ∈Rⁿ, αs ∈A, β_s∈B, dy_s = ¹_εg(x_s,y_s,αs,βs)ds+^√1_εν(x_s,y_s,αs,βs)dW_s, y_s ∈R^m,

x₀=x, y₀=y

Cost-payoff functional (αminimizes,βsmaximizes)

J^ε(t,x,y, α, β) :=

Z t 0

l(x_s,y_s,αs,βs)ds+h(x_t,y_t)

Lower value function, whereΓ(t)are the nonanticipating strategies, B(t)the open-loop controls

u^ε(t,x,y) := inf

α∈Γ(t) sup

β∈B(t)

E[J^ε(t,x,y, α[β], β)]

The H-J approach to Singular Perturbations

General control system with TWO controllers

dx_s =f(x_s,y_s,αs,βs)ds+ σ(x_s,y_s,αs,βs)dW_s, x_s ∈Rⁿ, αs ∈A, β_s∈B, dy_s = ¹_εg(x_s,y_s,αs,βs)ds+^√1_εν(x_s,y_s,αs,βs)dW_s, y_s ∈R^m,

x₀=x, y₀=y

Cost-payoff functional (αminimizes,βsmaximizes) J^ε(t,x,y, α, β) :=

Z t 0

l(x_s,y_s,αs,βs)ds+h(x_t,y_t)

Lower value function, whereΓ(t)are the nonanticipating strategies, B(t)the open-loop controls

u^ε(t,x,y) := inf

α∈Γ(t) sup

β∈B(t)

E[J^ε(t,x,y, α[β], β)]

The H-J approach to Singular Perturbations

General control system with TWO controllers

dx_s =f(x_s,y_s,αs,βs)ds+ σ(x_s,y_s,αs,βs)dW_s, x_s ∈Rⁿ, αs ∈A, β_s∈B, dy_s = ¹_εg(x_s,y_s,αs,βs)ds+^√1_εν(x_s,y_s,αs,βs)dW_s, y_s ∈R^m,

x₀=x, y₀=y

Cost-payoff functional (αminimizes,βsmaximizes) J^ε(t,x,y, α, β) :=

Z t 0

l(x_s,y_s,αs,βs)ds+h(x_t,y_t)

Lower value function, whereΓ(t)are the nonanticipating strategies, B(t)the open-loop controls

u^ε(t,x,y) := inf

α∈Γ(t) sup

β∈B(t)

E[J^ε(t,x,y, α[β], β)]

H-J-Bellman-Isaacs equation for the SP problem

Dynamic Programming method:

in thedeterministiccaseσ, ν ≡0, the value function solves

(CP_ε)











∂u^ε

∂t +H

x,y,Dxu^ε,^Dy_ε^uε

=0 in(0, +∞) ×Rⁿ×R^m,

u^ε(0,x,y) =h(x,y) in Rⁿ×R^m,

H(x,y,p,q) =min

β∈Bmax

α∈A {−p·f(x,y, α, β) −q·g(x,y, α, β) −l(x,y, α, β)} , in the viscosity sense.

In thestochasticcaseσ 6=0 orν 6=0 the H-J-B-I equation is

∂u^ε

∂t +min

β∈Bmax

α∈A L^ε_α,βu^ε−l(x,y, α, β) =0 in(0, +∞) ×Rⁿ×R^m, L^ε_α,β=infinitesimal generator of the process with constant controlsα, β it is of 2nd order involving also D²_xx,D²_yy/ε,D_xy² /√

ε.

This H-J-B-I PDE is (degenerate) parabolic.

Again, u^εis theuniqueviscosity solutionof the Cauchy problem.

In thestochasticcaseσ 6=0 orν 6=0 the H-J-B-I equation is

∂u^ε

∂t +min

β∈Bmax

α∈A L^ε_α,βu^ε−l(x,y, α, β) =0 in(0, +∞) ×Rⁿ×R^m, L^ε_α,β=infinitesimal generator of the process with constant controlsα, β it is of 2nd order involving also D²_xx,D²_yy/ε,D_xy² /√

ε.

This H-J-B-I PDE is (degenerate) parabolic.

Again, u^εis theuniqueviscosity solutionof the Cauchy problem.

Plan of the method:

1 pass to the limit asε →0 in the PDE

2 associate to the limit PDE a "limit control problem"

1 was developed in the papers

O. ALVAREZ - M. B. : SIAM J. Cont. ’01, Arch. Rat. Mech. Anal. ’03, Memoir A.M.S. ’10;

O. A. - M. B. - C. MARCHI : J. D. E. ’07, ’08 (more than 2 scales) under boundedness assumptions on the fast state variables, and for unbounded but uncontrolled fast variables in

M. B. - A. CESARONI - L. MANCA : SIAM J. Financial Math. 2010 M. B. - A. CESARONI : European J. Control 2011

Methods are related toHOMOGENIZATIONof H- J equations:

P.L.Lions- Papanicolaou- Varadhan 1986, L.C.Evans 1989, ...

Plan of the method:

1 pass to the limit asε →0 in the PDE

2 associate to the limit PDE a "limit control problem"

1 was developed in the papers

O. ALVAREZ - M. B. : SIAM J. Cont. ’01, Arch. Rat. Mech. Anal. ’03, Memoir A.M.S. ’10;

O. A. - M. B. - C. MARCHI : J. D. E. ’07, ’08 (more than 2 scales) under boundedness assumptions on the fast state variables, and for unbounded but uncontrolled fast variables in

M. B. - A. CESARONI - L. MANCA : SIAM J. Financial Math. 2010 M. B. - A. CESARONI : European J. Control 2011

Methods are related toHOMOGENIZATIONof H- J equations:

P.L.Lions- Papanicolaou- Varadhan 1986, L.C.Evans 1989, ...

Plan of the method:

1 pass to the limit asε →0 in the PDE

2 associate to the limit PDE a "limit control problem"

1 was developed in the papers

O. ALVAREZ - M. B. : SIAM J. Cont. ’01, Arch. Rat. Mech. Anal. ’03, Memoir A.M.S. ’10;

O. A. - M. B. - C. MARCHI : J. D. E. ’07, ’08 (more than 2 scales) under boundedness assumptions on the fast state variables, and for unbounded but uncontrolled fast variables in

M. B. - A. CESARONI - L. MANCA : SIAM J. Financial Math. 2010 M. B. - A. CESARONI : European J. Control 2011

Methods are related toHOMOGENIZATIONof H- J equations:

P.L.Lions- Papanicolaou- Varadhan 1986, L.C.Evans 1989, ...

1 Searcheffective Hamiltonian H andeffective initial data hs. t.

u^ε(t,x,y) →u(t,x) asε →0, u solution of

(CP)

(_∂u

∂t +H x,Dxu,D_xx² u
=0 in (0, +∞) ×Rⁿ, u(0,x) =h(x) in Rⁿ

2 Intepret the effective Hamiltonian H as the Bellman-Isaacs Hamiltonian for a neweffective system

x˙s =f(xs, ηs, θs) xs ∈Rⁿ, ηs ∈E(xs), θs ∈Θ(xs) andeffectivecost functional

J(t,x, η, θ) :=

Z t 0

l(xs, ηs, θs)ds+h(xt).

This is avariational limitof the initial n+m-dimensional problem.

Step2is largely OPEN !

1 Searcheffective Hamiltonian H andeffective initial data hs. t.

u^ε(t,x,y) →u(t,x) asε →0, u solution of

(CP)

(_∂u

∂t +H x,Dxu,D_xx² u
=0 in (0, +∞) ×Rⁿ, u(0,x) =h(x) in Rⁿ

2 Intepret the effective Hamiltonian H as the Bellman-Isaacs Hamiltonian for a neweffective system

x˙s =f(xs, ηs, θs) xs ∈Rⁿ, ηs ∈E(xs), θs ∈Θ(xs) andeffectivecost functional

J(t,x, η, θ) :=

Z t 0

l(xs, ηs, θs)ds+h(xt).

This is avariational limitof the initial n+m-dimensional problem.

Step2is largely OPEN !

1 Searcheffective Hamiltonian H andeffective initial data hs. t.

u^ε(t,x,y) →u(t,x) asε →0, u solution of

(CP)

(_∂u

∂t +H x,Dxu,D_xx² u
=0 in (0, +∞) ×Rⁿ, u(0,x) =h(x) in Rⁿ

2 Intepret the effective Hamiltonian H as the Bellman-Isaacs Hamiltonian for a neweffective system

x˙s =f(xs, ηs, θs) xs ∈Rⁿ, ηs ∈E(xs), θs ∈Θ(xs) andeffectivecost functional

J(t,x, η, θ) :=

Z t 0

l(xs, ηs, θs)ds+h(xt).

This is avariational limitof the initial n+m-dimensional problem.

Step2is largely OPEN !

Definition of H: deterministic case σ ≡ 0, ν ≡ 0

Consider the fast subsystem with frozen x andε =1 (FS) y˙τ =g(x,yτ, ατ, βτ), y₀=y

and the family of value functions in R^mwith parametersx,p∈Rⁿ w(t,y;x,p) := inf

α∈Γ(t) sup

β∈B(t)

Z t 0

L(yτ, α[β]τ, βτ;x,p)dτ, L(y, α, β;x,p) :=p·f(x,y, α, β) +l(x,y, α, β)

Say (FS) isERGODICif, for all x,p,

t→+∞lim

w(t,y;x,p)

t =constant (in y ), uniformly in y

=: −H(x,p)

Definition of H: deterministic case σ ≡ 0, ν ≡ 0

Consider the fast subsystem with frozen x andε =1 (FS) y˙τ =g(x,yτ, ατ, βτ), y₀=y

and the family of value functions in R^mwith parametersx,p∈Rⁿ w(t,y;x,p) := inf

α∈Γ(t) sup

β∈B(t)

Z t 0

L(yτ, α[β]τ, βτ;x,p)dτ, L(y, α, β;x,p) :=p·f(x,y, α, β) +l(x,y, α, β)

Say (FS) isERGODICif, for all x,p,

t→+∞lim

w(t,y;x,p)

t =constant (in y ), uniformly in y

=: −H(x,p)

Definition of H: deterministic case σ ≡ 0, ν ≡ 0

Consider the fast subsystem with frozen x andε =1 (FS) y˙τ =g(x,yτ, ατ, βτ), y₀=y

and the family of value functions in R^mwith parametersx,p∈Rⁿ w(t,y;x,p) := inf

α∈Γ(t) sup

β∈B(t)

Z t 0

L(yτ, α[β]τ, βτ;x,p)dτ, L(y, α, β;x,p) :=p·f(x,y, α, β) +l(x,y, α, β)

Say (FS) isERGODICif, for all x,p,

t→+∞lim

w(t,y;x,p)

t =constant (in y ), uniformly in y

=: −H(x,p)

Definition of H: deterministic case σ ≡ 0, ν ≡ 0

Consider the fast subsystem with frozen x andε =1 (FS) y˙τ =g(x,yτ, ατ, βτ), y₀=y

and the family of value functions in R^mwith parametersx,p∈Rⁿ w(t,y;x,p) := inf

α∈Γ(t) sup

β∈B(t)

Z t 0

L(yτ, α[β]τ, βτ;x,p)dτ, L(y, α, β;x,p) :=p·f(x,y, α, β) +l(x,y, α, β)

Say (FS) isERGODICif, for all x,p,

t→+∞lim

w(t,y;x,p)

t =constant (in y ), uniformly in y

=: −H(x,p)

Example: (FS) uncontrolled, i.e.

y˙_τ =g(x,y_τ),

andergodicin the classical sense with aUNIQUE INVARIANT MEASUREµ_x. Then

−H(x,p) = Z

R^m

minα∈AL(y, α;x,p)dµ_x(y).

NO explicit formula for H in general!

Definition of H in general non-deterministic case: fast subsystem dyτ =g(x,yτ, ατ, βτ)dτ +ν(x,yτ, ατ, βτ)dWτ, y₀=y, L=trace Mσσ^T(x,y, α, β)
/2+ ...(Ma n×n symmetric matrix)

w(t,y;x,p,M) =inf

α sup

β

E

Z t 0

Ldτ

 , lim

t→+∞w/t =: −H(x,p,M)

Example: (FS) uncontrolled, i.e.

y˙_τ =g(x,y_τ),

andergodicin the classical sense with aUNIQUE INVARIANT MEASUREµ_x. Then

−H(x,p) = Z

R^m

minα∈AL(y, α;x,p)dµ_x(y).

NO explicit formula for H in general!

Definition of H in general non-deterministic case: fast subsystem dyτ =g(x,yτ, ατ, βτ)dτ +ν(x,yτ, ατ, βτ)dWτ, y₀=y, L=trace Mσσ^T(x,y, α, β)
/2+ ...(Ma n×n symmetric matrix)

w(t,y;x,p,M) =inf

α sup

β

E

Z t 0

Ldτ

 , lim

t→+∞w/t =: −H(x,p,M)

Example: (FS) uncontrolled, i.e.

y˙_τ =g(x,y_τ),

andergodicin the classical sense with aUNIQUE INVARIANT MEASUREµ_x. Then

−H(x,p) = Z

R^m

minα∈AL(y, α;x,p)dµ_x(y).

NO explicit formula for H in general!

Definition of H in general non-deterministic case: fast subsystem dyτ =g(x,yτ, ατ, βτ)dτ +ν(x,yτ, ατ, βτ)dWτ, y₀=y, L=trace Mσσ^T(x,y, α, β)
/2+ ...(Ma n×n symmetric matrix)

w(t,y;x,p,M) =inf

α sup

β

E

Z t 0

Ldτ

 , lim

t→+∞w/t =: −H(x,p,M)

Weak convergence theorem

Meta-Theorem

Fast subsystem (FS) ergodic =⇒

u^ε(t,x,y) →u(t,x) asε →0,

(in the sense of relaxed semilimits, or weak viscosity limits), and u solves (in viscosity sense)

∂u

∂t +H

x,D_xu,D_xx² u

=0

This is in fact a Theorem if the fast variables y live on the torusT^M (i.e., all data areZ^m- periodic in y ), or in all R^M but the process

dyτ =g(x,yτ)dτ + ν(x,yτ)dWτ

is an UN-controlled NON-degenerate diffusion.

The effective initial data h

For the Fast Subsystem with frozen x

(FS) dy_τ =g(x,y_τ, α_τ, β_τ)dτ + ν(x,y_τ, α_τ, β_τ)dW_τ, y₀=y, consider now the value function

v(t,y;x) := inf

α∈Γ(t) sup

β∈B(t)

E[h(x,yt)]

Definition: (FS) isSTABILIZING(to a constant) for the cost h if,∀x ,

t→+∞lim v(t,y;x) =constant (in y ), uniformly in y =:h(x) Convergence Theorem at t =0

Fast subsystem (FS) stabilizing for the cost h =⇒

tlim→0lim

ε→0u^ε(t,x,y) =h(x)

(in the sense of relaxed semilimits, or weak viscosity limits).

The effective initial data h

For the Fast Subsystem with frozen x

(FS) dy_τ =g(x,y_τ, α_τ, β_τ)dτ + ν(x,y_τ, α_τ, β_τ)dW_τ, y₀=y, consider now the value function

v(t,y;x) := inf

α∈Γ(t) sup

β∈B(t)

E[h(x,yt)]

Definition: (FS) isSTABILIZING(to a constant) for the cost h if,∀x ,

t→+∞lim v(t,y;x) =constant (in y ), uniformly in y =:h(x) Convergence Theorem at t =0

Fast subsystem (FS) stabilizing for the cost h =⇒

tlim→0lim

ε→0u^ε(t,x,y) =h(x)

(in the sense of relaxed semilimits, or weak viscosity limits).