Programmation dynamique - Believe | A different … · 2010-07-24 · Exemple Soit un consommateur qui possède une richesse initiale x0. Il consomme ct, t0[0 ;T-1] (i.e. il ne consomme

Programmation dynamique Vade-mecum rédigé par Alain GAUGRIS, consultant en économie internationale ([email protected]) © 2005

Objectif On désire agir sur un système (discret ou continu) dont l’état est décrit, à l’instant t∈[0,…,T,…+4[ par une variable d’état x (dont on connaît l’état initial x0 ou non), au moyen de paramètres appelés contrôles ou politiques, et notés u (u=u(t) : contrôle en boucle ouverte ; ou u=u(x,t) : contrôle en boucle fermée ou feedback. Le système est régi par une loi d’évolution f telle que xt+1=f(t,xt,ut). Enfin, un contrôle u est dit admissible si le couple (xt,ut) vérifie les contraintes imposées. SOMMAIRE 1. Programmation dynamique discrète................................................................................................................ 1

1.1. Horizon fini.......................................................................................................................................... 1 1.2. Horizon infini....................................................................................................................................... 5 1.3. Cas stochastique, horizon fini .............................................................................................................. 7

2. Calcul des variations ..................................................................................................................................... 11 2.1. Horizon fini........................................................................................................................................ 11 2.2. Horizon infini..................................................................................................................................... 13

3. Contrôle optimal en temps continu. Horizon fini.......................................................................................... 13 3.1. Principe de Pontryaguine ........................................................................................................................... 13 3.2. Programmation dynamique en temps continu. Horizon fini....................................................................... 15

4. Exercices ....................................................................................................................................................... 17 4.1. Programmation discrète ............................................................................................................................. 17

4.1.1. Enoncés ............................................................................................................................................... 17 4.1.2. Corrections .......................................................................................................................................... 18

4.2. Calcul des variations .................................................................................................................................. 25 4.2.1. Enoncés ............................................................................................................................................... 25 4.1.2. Correction............................................................................................................................................ 26

Bibliographie......................................................................................................................................................... 30

1. Programmation dynamique discrète

1.1. Horizon fini Programme t∈[0,…,T], où T est appelé l’horizon. On cherche à résoudre le programme

⎪⎩

⎪⎨⎧

⎩⎨⎧

==Ρ +

xxuxtfx

xVx ttt

0

11),,(

)()(

où est la fonction de valeur du problème (où le maximum

est la fonction objectif.

∑−

=

+=1

0)(),,(max)(

T

tTttu

xguxtUxV

est pris sur les contrôles admissibles) ; ∑−

=

1

0

),,(T

ttt uxtU

Vade-mecum rédigé par Alain GAUGRIS, consultant en économie internationale ([email protected]) © 2005 1

mailto:[email protected]

Principe de résolution Théorème 1

Posons ⎪⎨⎧ =Ρ + uxtfxxs ttt ),,(),( 11 ⎧

⎪⎩⎩ xs⎨ = x

xsV ),(

∑−

=

+1T

avec =),( xsV )(),,(maxst

TttuxguxtU

Nota Bene : V(x)=V(0,x) selon ces notations Suppo tte dsons que P1(s,x), s [0 ;T-1], adme es solutions. La fonction V est alors caractérisée ∈par la récurrence rétrograde :

[ ]⎧ ++= ),,(,1(),,(max),( uxtftVuxtUxtV

⎩ = )()(),( iixgxTV T

(i) est appelée équation de Ham

)1()(i

ut

ilton-Jacobi-Bellman.

⎨

Le Théorème 1 permet de déterminer V(t,x) de façon rétrograde. On connaît V(T,x). On en déduit, en résolvant un problème de maximisation sur u, V(T-1,x) puis, en reportant la valeur de V(T-1,x) dans (1)(i), V(T-2,x) ; et ainsi de suite jusqu’à V(0,x).

males (sans oublier de vérifier leur dmissibilité). Le contrôle optimal à utiliser à l’instant 0 est = , puis, à l’instant 1

Ρ +

=

1

),,(

ma

)(

0

0

1

0

2

βxx

uxtfxx ttt

tu

L’équation de programmation dynamique se réécrit dans ce cas

On détermine en même temps les politiques opti)0,( 0

* xuua O** **)1,( 11 xuu = avec ),,0( 001 uxfx = ; et ainsi de suite : )1,( *

1*

1 += ++ txuu tt avec ),,( ***

1 ttt uxtfx =+ . Cas particulier

+−

∑ )(),(x1

ββ xguxUT

TTttt

⎪⎪⎪

⎩

⎪⎪⎪

⎨

⎧

⎪⎩

⎪⎨

⎧

==

=

( )⎪⎩ = )(),( xgxTJ

⎪⎨⎧

⎥⎦

⎤⎢⎣

⎡++= + ),,(,1),(max),( 1 uxtftJuxUxtJ

t

t

u ββ

avec

⎥⎦

⎤⎢⎣

⎡+= ∑

−

=

1

)(),(1max),(T

stTTtt

su

xguxUxsJ ββ


Exemple Soit un consommateur qui possède une richesse initiale x0. Il consomme ct, t0[0 ;T-1] (i.e. il ne consomme pas à la dernière période). Ce qui n’est pas consommé à chaque étape est placé au taux 0. Le programme du consommateur s’écrit :

On spécifie U et g : et

⎪⎩

⎪⎨⎧

−=

+

−

−

=∑

ttt

T

tTtc

cxxcs

xgcU

1

1

0..

)()(max

α−= 1)( xxU α−= 1)( xxg , 10 <<α . On a donc :

⎪⎩

⎪⎨⎧

−=

+

+

−

=

−−∑ttt

T

tTtc

cxxcs

xc

1

1

0

11

..

max αα

On applique le Théorème 1 : • •

α−== 1)(),( xxgxTV [ ]αα −− −+=− 11 )(max),1( cxxxTV

c

Le maximum est donné par l’égalisation à 0 de la dérivée première de V(T-1,x) :

21

2

)(

0))(1()1(),1(

*

**

**

===⇔

−=⇔

=−−−−=∂−∂

−−

−−

bavecbxxc

cxc

cxcc

xTV

αα

αααα

D’où :

[ ]

αα

αα

ααα

αα

−−

−−

−−−

−−

⋅=

=

+=

−+=−

1

11

111

11

22

)()(),1(

xbbxb

bbxbxxbxxTV

αα −−=− 1),1( xbxTV • [ ]ααα −−− −+=− 11 )(max),2( cxbcxTV

c


xb

bc

cxbc

cxbcc

−=⇔

=−−−−=∂

−−−

−−

)(

0))(1()1(

**

**

ααα

αα αα

cxbc −=⇔ )( **

x

+=⇔

−

1

)

*

α

D’où

TV −∂ ,2(

( )α

α−

− ⎟⎞

⎜⎛=

113 bx

ααα

αα

α

αα

α

αα

α

−−−

−

−−

−

−−

−

−−

−

⎠⎝ +

⎥⎥⎦

⎤

⎢⎢⎣

⎡+⎟

⎠⎞

⎜⎝⎛+

=

⎥⎥⎦

⎤⎡⎟⎠⎞

⎜⎝⎛+

⎞⎛

⎟⎠⎞

⎜⎝⎛+

+⎟⎠⎞

⎜⎝⎛+

=

⎟⎠⎞

⎝ ++⎟

⎠⎞

⎝ +

11

1

11

11

11

1

11

11

11

1

11

b

bbb

x

bbb

xb

bxb

b

xb

bbxb

⎜⎛ −⎜

⎛=− ),2( xbxTV

α−

⎢⎢⎣

+⎟⎠

⎜⎝ +

= 1

1 bx

α

⇔α

α−

− ⎟⎠⎞

⎜⎝⎛+

=−b

bxxTV1

),2( 1

Et ainsi de suite…

upposons, pour terminer l’exemple rapidement, que T=2, et réécrivons le problème de

Sdépart :

∑=

−− +1

0

12

1

, 10

maxt

tccxc αα

000*0

1

11*1

1

1

31

1)(

1),0(

21)(

21),1(

),2(

xxb

bxcetxb

bxV

xxcetbavecxbxV

xxV

=+

=⎟⎠⎞

⎜⎝⎛+

=•

===•

=•

−−

−−

−

αα

αα

α

On en déduit que :

00*0

1

31)(

31),0( xxcavecxxV =⎟⎠⎞

⎜⎝⎛= −

−α

α

000*00

*1 3

231 xxxcxx =−=−= Or,


011*1 3

121)( xxxc == D’où

000*11

*2 3

131

32 xxxcxx =−=−= Et

En résumé :

0;31

31;

32

31;

*20

*2

0*10

*1

0*00

*0

==

==

==

cxx

xcxx

xcxx

Economiquement, ce résultat signifie que, pour maximiser sa richesse (x) à chaque étape, le consommateur doit :

- Consommer en première période (0) un tiers de sa richesse initiale (x0). Il lui reste donc deux tiers de sa richesse initiale en début de deuxième période (1) ;

- Consommer également un tiers de sa richesse initiale en deuxième période (1), de sorte qu’en troisième période, sa richesse (x2) soit égale à un tiers de sa richesse initiale.

Ce résultat corrobore l’intuition qui est, sur 3 périodes, de consommer avec la même intensité à chaque période lorsque le taux d’intérêt est nul et que l’on désire maximiser sa richesse à chaque étape.

1.2. Horizon infini plus apparaître de condition terminale, et on se restreint au cas où la

Hypothèse :

Le problème ne fait

fonction objectif est de type ∑ ),(t

ttt uxUβ . +∞

=0

MtxU ≤≤ ),(0 et tt r)1(1+

=β , avec r>0

Cette hypothèse assure la convergence de la série. On cherche à résoudre

()( ⎪⎩

⎪⎨⎧

⎩⎨⎧

==Ρ +

xxuxfx

cs

xVx ttt

0

13),(

..

)

∑avec +∞

= +0

),()1(

1t

tttuuxU

r la fonction de valeur du problème.

Le principe de programmation dynamique est encore valable, à de petites modifications près.

= max)(xV


Théorème 2

( )⎥⎦⎤

⎢⎣⎡

++= ),(

11),(max)( uxfV

ruxUxVV e st caractérisée par la récurrence

u

Remarque : Il n’y a plus de condition terminale. On ne peut donc plus déterminer V par une méthode rétrograde. En fait, la fonction de valeur est désormais une inconnue du problème ; très souvent, on intuite sa forme. Calcul de V Méthode 1 : méthode de point fixe On pose 0)(0 =xV et on définit par récurrence la suite de fonctions Vn par

( )⎥⎦⎣ +1 ru

⎤⎢⎡ +=+ ),(1),(max)(1 uxfVuxUx nn V

Pro spo ition 1 La s itu e Vn est la fonction de valeur du problème avec horizon fini et condition terminale

nulle −∈=Ρ+ Ttuxfx ttt 1 ]1,0[),,(

⎪⎩ ⎩ = xx0

⎪

⎪⎪⎨

⎧ −

=∑

cs

uxtUx

n

ttt

1

04

..

),,(max)(

⎨⎧

On a aussi { }∑

−

= +− 0,...,, )1(110 ttuuu rn

=1

),(1max)(n

ttn uxUxV

Théorème 3

xxV ∀→ ),( Vn

n+∞→

Méthode 2 : trouver ( ) ( )( )*** ,1

1),()(/, uxfVr

uxUxVuV+

+= et construire par *u

itération. Intuitivement, la politique optimale ne dépend pas de t. Remarquons tout d’abord que :

( )( )( )∑=)(xRSi u=u(x) est une politique admissible et

+∞

= +0,

11

tttt xuxU

r avec ( )( )ttt xuxfx ,1 =+

et , il est facile de vérifier que : xx =0 ( ) ( )( ))(,1

1)()( xuxfRr

xuxUxR+

++= .

La récurrence est alors établie de la façon suivante : on choisit une politique admissible

)(0 xu , et on lui associe définie par 0R( )

( )∑+∞

= +=

00 )(,

11)(

tttt xuxU

rxR avec ( ))(, 01 ttt xuxfx =+

et . xx =0

Cette fonction vérifie ( ) ( )( ))(,1 0000 r+

1)(,)( xuxfRxuxUxR += .

On en déduit une politique admissible en maximisant 1u ( )),(1

1),( 0 uxfRr

uxU+

+ .


Par récurrence, on définit par nR ( )∑+∞

= +=

0

)()1(

1)(t

tnttn xuxUr

xR et en maximisant 1+nu

( )),(1),( uxfRuxU n+ . 1 r+

On montre que nR est une suite croissante qui converge vers V.

1.3. Cas stochastique, horizon fini L’évolution du système fait intervenir, à chaque étape, une variable aléatoire :

),,,(1 tttt uxtfx ω=+ , où tω est un paramètre aléatoire de loi connue. ),/(. ttt uxPLa fonction objectif s’écrit

⎥⎦

⎤⎢⎣

⎡+ΙΕ= ∑

=

1

0)(),,,(),(

T

tTttt xguxtUuxJ ω

−

.

La fonction de valeur s’écrit

⎥⎦

⎤⎢⎣

⎡+ΙΕ== ∑

−

=

1

0

* )(),,,(sup),()(T

tTttt xguxtUxJxV ωπ

π,

où ),...,,( *

1*1

*0

*−= Tµµµπ , où associe à chaque état un contrôle *

tµ tx )(**ttt xu µ= .

Théorème 4

)()( *0 xJx = , où est obtenue par l’algorithme suivant : *

0JV

( )⎪⎩⎨ +ΙΕ=

=

+ ),,,(),,,(max)()()(

*1

*

*

tttttttutt

TTT

uxtfJuxtUxJxgxJ

ωω ⎪⎧

[ ]Si maximise le terme de droite, la politique est optimale, où )(** xu tt µ= ),...,,( *

1*1

*0

*−= Tµµµπ

),,,( *1 tttt uxtfx ω=+ .

Exemple Dans une entreprise, l’évolution du stock est défini par : ),0max(1 tttt uxx ω−+=+ , où :

tx est la quantité de stock disponible

tu est la quantité commandée au cours de la période t

tω est la demande adressée à l’entreprise L’e rise doit, au début de chaque pntrep ériode, décider de la commande à passer. On suppose tω ~ i.i.d. La fo ninction objectif à mi miser est

⎥⎦

⎤⎢⎣

⎡−++ΙΕ ∑

−

=

1

0)(

T

ttttt uxHcu ω ,

avec ),0max(3),0max()( tttttttt t uxuxuxH −−+−+=−+ ωωω . H(x) est le coût de pénalité pour stockage inutile, ou le coût correspondant à une demande non satisfaite (le coût lié à la


perte d’un client est ici trois fois su ’un stock). cpérieure à celui lié à l’existence d est un coefficient représentant le oût d our plifier les calcu c ’achat. On suppose ici c=1 p sim ls. On suppose également que le stock disponible et la demande sont à valeurs entières positives, que la valeur maximale de est 2 (i.e. on ne peut pas stocker plus de deux unités), et que )( tt ux +

⎜⎜⎜⎛ ==ΙΡ ,0)0( tω

⎝ ==ΙΡ==ΙΡ

2,0)2(7,0)1(1

t

ωω . En d’autres termes, on suppose qu’on a entre 0 et 2 clients à chaque

t

pér robabilité. iode, répartis à chaque période selon cette loi de pOn suppose enfin que T=3 et 00 =x .

0)(3 =xJLe coût terminal étant nul : , on déroule : ( )[ ]

[ ])(min

),0max(3),0max(min

),(,3),(min),2(

2222222

u

uxuxcu

uxfVuxUx

u

u

ϕ

ωω

=

−−+−++ΙΕ=

+ΙΕ=V

xu

• x=0 [ ]),0max(3),0max()( 2222220 uucuu −+−+ΙΕ= ωωϕ Si u=0 . ωω ∀=− ),0max( 2u 02 ),0max(3), 0max(3 222. ωω =− u d’où

[ ]

3,3)22,017,001,0(3

),0max(3),0max(300)0(

2[ ]

=×+×+×=

20

ΙΕ=++ΙΕ=

ωωϕ

Si u=1 [ ][ ]

)12,007,001,0(3)02,007,011,0()1,0max(3)1,0max(

),0max(3),0max(1(

22

222220

×+×+×+×+×+×+=−+−+ΙΕ=

−+−+ΙΕ

cc

uucuωω

) =

7,17,0 =+= c

ωωϕ

Si u=2

]

)0(3))2, 2

+[ 0max(3)2,0max(2)2( 20 +−+ΙΕ= c ωϕ ω −

17,021,0(2 ×+×+= c9,29,02 =+= c

Or, mi)0, 7,1)1()(n2( 00 === ϕϕ u . On obtient donc 1)0(*2 =u V

u

• x=1 [ ])1,0max(3)1,0max()( 2222221 uucuu −−+−++ΙΕ= ωωϕ

Si u=0

[ ]

7,0)2,0(3)11,0()1,0max(3)1,0max()0( 221

=+×=−+−ΙΕ= ωωϕ

Si u=1


[ ]

9,)17,021,0(

)2,0max(3)2,0max()1( 221

=×+×+=

19,0 =+

−+−+ΙΕ=

cc

c ωωϕ

Si u=2

)3,0max(3)3,0max(2)2(1

=+=

[ ]

9,39,12)12,027,031,0(2

22

×+×+×+=−+−+ΙΕ=

c

c ωωϕc

On obtient donc )1(2u V0* = et (2,1)=0,7 • x=2

[ ])22 222 uu ,0max(3),0max()( 2222 cuu −−+−++ΙΕ= ωωϕ Si u=0

[ ]

9,0)17,021,0()2,0max(3)2,0max()0( 222

=×+×=−+−ΙΕ= ωωϕ

Si u=1 [ ]

9,29,1)12,027,031,0(

)3,0max(3)3,0max()1( 222

=+×+×+×+=

−+−+ΙΕ=c

c ωωϕ

c= Si u=2

(2 +=[ ]

9,49,22)22,037,041,0

)4,0max()4,0max(2)2( 222

=+=+×+×

3×

−+−+ΙΕ=

c

cϕ ωωc

D’où 0)2(*2 =u et V(2,2)=0,9

Nota Bene : Il n’était pas nécessaire de mener ces calculs, étant donné la contrainte 2≤+ ux .

( )[ ,(min),1( uxUxV ΙΕ= ]

[ ])(

),2(),0max(3),0max(min

),(,2)

1111111111

u

uxVuxuxcu

uxfV

xu

u

ωωω −++−−+−++ΙΕ=

+

minu

ψ=

• x=0 Si u=2

[ ][ ])2,2()17,021,0(2

)2,2()2,0max(3)2,0max(2)2(

1

1110

ωωωωψ

−+×+×+ΙΕ=−+−+−+ΙΕ=

VcVc

Or, on sait que V(2,0)=1,7 V(2,1)=0,7 V(2,2)=0,9 Donc :

82,309,049,034,09,2)1,09,07,07,02,07,1(9,02)2(0

=+++=×+×+×++= cψ

Si u=1


7,07,01,0()12,0(3)11,0(1)1,2()1,0max(3)1,0max()1( 1110

=+++=×+×+×+×+=

[ ]

96,219,107,06,01,1)7,1

−+−+−+ΙΕ= ωωωψ Vc

Si u=0

[ ]

3,3)1,1(3)22,017,001,0(3

),2(),0max(3),0max()0( 1110

==×+×+×=

−++−ΙΕ= ωωωψ V

et )0(*1uDonc 96,2mi)0,1( ==V

u)(n 0 uψ 1= .

• x=1 Si u=0

,0[ ]

15,319,107,06,01,0)77,11,07,0()12,0(3)11,0(

)1,2()1,0max(3)1,0max( 111

=+++=×+×+×+×=

)0(1ψ = −+−+−ΙΕ ωωω V

Si u=1

7,[ ]

82,234,049,009,09,01)7,12,07,009,01,0()0(3)17,021,0(1

)2,2()2,0max(3)2,0max()1( 1111

=++++=×+×+×++×+×+=

−+−+−+ΙΕ= ωωωψ Vc

Si u=2

0[ ]

67,414,063,02,04,13,02)7,02,9,07,0()12,027,031,0(2

3,2()3,0max(3)3,0max(2)2( 1111

=+++++=×+×+×+×+×+=

−+−+−+ΙΕ= ωωωϕ Vc

Nota Be ile étant donné la contrainte. ne : Calcul inut Donc 82,2)(min)1,1( 1 == uV ψ et 1)1(*

1 =u . u

• x=2 0)2(*

1 =u . D’emblée, la contrainte oblige [ ]

82,134,049,009,07,02,0)7,12,07,07,09,01,0()17,021,0()2,2()2,0max(3)2,0max()2,1( 111

=++++=×+×+×+×+×=−+−+−ΙΕ= ωωω VV

Donc V(1,2)=1,82 et 0)2(*1 =u .

Récapitulons :

V(2,0)=1,7 et u=1 V(2,1)=0,7 et u=0 V(2,2)=0,9 et u=0 V(1,0)=2,96 et u=1 V(1,1)=2,82 et u=1 V(1,2)=1,82 et u=0

( )[ ]),(,1),(min),0( 0000 xUxV

uuxfVu +ΙΕ=

Or, par hypothèse, 00 =x .


Donc=

[ ])(min

),1(),0max(3),0max(min)0,0(

0

0000000

u

uVuucuV

u

u

Γ

−+−+−+ΙΕ= ωωω

Si u=0

0000

=×+×=−++−ΙΕ ωωω V

[ ]

3,3)22,017,0(3),1(),0max(3),0max()0( =Γ

Si u=1

82,)10

+[ ]

054,4072,2282,07,1)96,27,021,0(2,0(311,01

)1,1()1,0max(3)1,0max()1( 000

=++=×+××+×+=

−+−+−+ΙΕ=Γ ωωω Vc

Si u=2

×[ ]

648,5592,0974,1182,09,2)96,22,082,27,082,11,0()17,021,0(2

2,1()2,0max(3)2,0max(2)2( 0000

=+++=+×+×+×+×+=

−+−+−+ΙΕ=Γ ωωω Vc

3,3)(min 0 =Γ uu

et 0)0(*0 =u . Donc )0,0( =V

2. Calcul des variations On passe en temps continu.

2.1. Horizon fini On cherche à é dr sou re un problème d’optimisation dynamique de la forme :

⎪⎩

⎪⎨⎧

⎩⎨⎧

==Ρ

T

T

xTxxx

cs

xJx

)()0(

..

)(max)(5

où )(),(,)( & ( ) dttxtxtLxJT

∫= 0

Nota bene : (J )x est une fonctionnelle, id est une application qui associe un nombre réel à une fonction. Théorème 5 (condition d’Euler) Condition nécessaire Si x 0)0( xx = et TxTx =)(maximise s au bord J sous les contrainte , alors

( )2((),(, xtxtLdxx && ) ( ))(),(,) txtxtLt &=

dt

où (.)(.)xLL (.)(.)

xLLx ∂∂

= x& ∂&∂

= et

Condition suffisante Si est concave, si L x vérifie (2) ainsi que les contraintes au bord, alors x est solution optimale de P5.


Cas particuliers - Si ne dépend pas de L x , l’équation d’Euler s’écrit =xL& constante - Si ne dépend pas de , toute solution de l’équation d’Euler est solution de L t

=− xfxf && =− xfxf &&constante. Toute solution non constante de constante est solution d’Euler.

La marche à suivre est donc :

1. Ecrire l’équation d’Euler 2. ésoudre cette équation, ce qui fera apparaître deux constantes d’in gration R té3. éterminer les constantes d’intégration en imposant les conditions au bord D4. vérifier si l’on peut assurer que l’on a un extremum

Conditions de transversalité

a. oût terminal C

( ) (⎪⎩

⎪⎨⎧

=+Ρ ∫

0

)6

)0(..)((),(,max

xxcsTxgdtxtxt

T& 0

)tL

Proposition 2 Condition nécessaire

[ ]Tt ,0∈∀ , ( )( ) ( )(),(,)(),(, txtxtLtxtxtLdtd

xx &&& =Si x est solution de P6, alors elle vérifie (2) ) (2.1) et l alité au point terminal ( ) ( ) 0)(')(),(, =+ TxgTxTxTLx &&a condition de transvers (2.2) Condition suffisante Si L et g sont concaves, si x vérifie (2.1) et (2.2), alors x est une solution optimale de P6.

b. Contraintes terminales (problème d’extrémité liée)

( )

( )⎪⎩

⎪⎨

⎧

⎩⎨⎧

=Φ=Ρ

∫

0),()0(

..

)(),(,max

11

0

0

7

1

ttxxx

cs

dttxtxtLt

&

où Φ est C1. L’extrémité est assujettie à appartenir à la courbe 0),( =Φ xt . Proposition 3 Si ),( 1tx est une solution de 7Ρ , alors x est solution de (2.1) ; elle vérifie la condition initiale

0)0( xx = , et ),( 1tx vérifie la condition de transversalité écrite en : 1t( ) ( )( ) ( )( ) ( )( ) ( ) ( ) ( )( ) ( ) ( )( )[ ] 0,,,, 111 =,,,, 11111111111 −Φ+Φ txttxLtxttxtxttLtt xxxt &&&&& xtLtxtxx &

c. Extrémité libre soumise à un coût (on en connaît pas T)

(t ) (⎪⎩

⎪⎨⎧

=+Ρ ∫ )

0 118

)0(..)(,)(),(,max 1

xxcstxtGdttxtxL

t&

0


Proposition 4 Si ; el condition initiale ),( 1x est une solution de 8Ρ alors x est solution de (2.1) le vérifie lat ,

0)0( xx , et tx int :

= )1 vérifie les conditions limites écrites au po⎧

=+−=+

00

tx

xx

GLxLGL

&

&

& ,( 1t

⎩⎨

2.2. Horizon infini

⎪⎩⎨

= 0

09)0(.. xxcs

⎪⎧Ρ ∫ −),(max dtexxL rt& +∞

Pro spo ition 5 Condition nécessaire

Si x est une solution de , elle vérifie l’équation d’Euler 9Ρ [ ] rtx

rtx eLeL

dtd −− =& (2.3)

Condition suffisante SOIT Si L est concave et bornée, si rt

t, si est continue, et si x vérifie xL& 0)(lim =−

+∞→tx xL&e

(2.3), alors x est optimale. SOIT Si L est concave et négative, si est continue, et si x vérifie (2.3), xL& xL& 0lim =−

+∞→ xrt

tLe &

alors x est optimale.

Fonction de valeur : Soit ∫+∞

=00 ),(max)( exxLxV & − dtrt , avec L concave.

Proposition 6

( ) ( ) ( )( )0,0' **0 xxLxV x &&−=V e ost c ncave. V est différentiable et , avec une solution optimale.

3. Contrôle optimal en temps continu. Horizon fini

x&

( ))(),(,)(' tutxtftx = L’équation d’évolution est une équation différentielle :

( ) ( )

⎪⎩

⎪⎪⎨

⎧⎥⎤

⎢⎡ +∫ )()(),(,max TxGdttutxtL

T

.1

Fonction de Pontryaguine :

Hamiltonien :

( )⎪ =

=⎦⎣

Ρ

0

0

10

)0()(),(,)('

xxtutxtftx

3 . Principe de Pontryaguine

),,(),,(),,,( uxtLuxtpfpuxtdef

+=h )( Lxp += &

),,,(sup),,( puxtpxtu

def

h=Η


Théorème 6 ( )*,u une solution de 10 . Alors il existe une fonction [ ] IRTp →,0:* , dite vecteur *x ΡSoit

adjoint, telle que : ( ))(,),(, ** tputxth - )(* tu réalise max

u

- ),( ** px est une solution du système d’équations différentielles ordinaires d’Hamilton-Jacobi et v s suivantes : érifie les conditions-limite

(−= )(),(),(,)(' * tptutxtt h )( )⎪⎩ = )(),(),(,)(' * tptutxttx

p

p

x

h et ⎪

⎨⎧ ( )

⎩⎨⎧

==

0

*

)0()(')(

xxTxGTp

Remarque : ( ))(),(),(,)(' * tptutxttx ph= n’est autre que ( ))(),(,)(' * tutxtftx = . Calculs à mener :

1. Ecrire la fonction de Pontryaguine h 2. Calculer xh 3. Calculer *u (contrôle qui maximise )

u

))(),(*

ttpt

ns en tenant com

d

h

4. Remplacer, dans xh , par *u

Ecrire (

⎨⎧ −= ),(,)(' utxttp xh5. )⎩ = )(),(,)(' * tutxftx

et résoudre ces équatio pte

des conditions au bor

(

( )⎩⎨⎧

==

0)0()(')(

xxTxGTp

Condition suffisante : Proposition 7 Si h est concave, si ( )**, px véri e Pontr aguine et si fie les conditions d y

( ) ttptu ∀= ,0)(),(txtu ),(, ***h , alors ( )**,ux est optimal.

orizon infini :

11..cs

Condition nécessaire : Si est une commande optimale et si est la trajectoire associée,

H

⎪⎩ ⎩

⎨ = 0)0( xx

⎪⎨

⎧

=Ρ∫+∞ −

0

),(),(max

uxfxdteuxL rt

& ⎧

),(),,(),,,,( 00 uxLepuxtfpppuxt rttdef

−+=h

*u *x ( ) **0 /, upp∃ réalise

( )0** ),(,),(,max ptputxt

uh pour presque tout t, et

( )( )

⎪⎪⎩

⎪⎪⎨

∂−= ),(),(,)(' tutxt

xtp⎧ ∂h

∂∂

= 0***

0***

),(),(),(,)('

),(

ptptutxtp

tx

ptp

h


3.2. Progra

mmation dynamique en temps continu. Horizon fini

)( ) ( ⎤⎥⎦

+T

malité

⎨

⎩⎨⎧ ≥=

⎥⎦= tssusxsfsx

csx ,)(),(,)('

..)

∫≥s

t

xtu duxLxt )(),(,), ,, θθθ où xtux ,, est solution de

≥ tss ,)(

⎢⎣∫ )()(),(,00 TxGdttutxtL

⎡= max)(xV

Principe d’opti

On note ( ) ( )

⎪⎪⎧ ⎤

⎢⎣⎡ +∫ TxGdssusxsL

tV

T

t)()(),(,max

,( ( )⎪⎪⎩ = xtx )(

( ) (+≤∀∀ xtu sxsVVstu )(,(,, ,,θ )(⎧ = usxsfsx ),(,)(' )

⎩⎨ = xtx )(

( ) ( ))(,)(,s p),(, sVdxLxtVtt

+=≥ ∫ θθθu ,,,, sxs xtus xtu

u∀

Equation d’Hamilton-Jacobi-bellman Théorème 7

*u est une politique optimale si et seulement si

( ) ( ) ( ) ( ) 0),(),(,max**

=∂

+⎭⎬⎫

⎩⎨⎧ ttx

tVutxtftL uu

u (l’équation d’Hamilton-),(,),(

** ∂∂∂

+ txxVtutx uu

Jacobi-Bellman) admet une solution V(t,x) différentiable et vérifiant V(T,x)=G(x) , et que x∀*u vérifie le maximum de l’équation.

Remarque : fxVL ∂

+ correspond à la fonction de Pontryaguine. ∂

: ier membre de l’équation d’HJB :

Calculs à mener

1. Ecrire le prem

),(),,(),(),,( txtVuxtftx

xVtuxL

∂∂

+∂∂

+

2. Rechercher le u qui maximise cette quantité, soit 3. Intuiter la forme de la fonction de valeur et résoudre l’équation différentielle

),(* txu

0),(),,(),(),,( ** =∂∂

+∂∂

+ txtVuxtftx

xVtuxL en tenant compte des contraintes

V(T,x)=G(x) et x(0)=x0.

On utilise souvent le résul =j

jkx0

0)

Identification

tat suivant : Si ∑ −

k

jk t(α=

− ),( tx∀ , alors 0)( =tiα

),( kit ≤∀ . Par exemple, si 0)()()( =++ tytyt γβα , alors 0)()()( === ttt γβα t∀ .


Application aux problèmes de contrôle linéaires quadratiques Un problème de contrôle est linéaire quadratique si l’équation d’état est linéaire et la fonction objectif quadratique. Le problème s’écrit :

⎪⎪

⎩

⎪⎪

⎨ +=⎠⎝

Ρ

∫sFusExsxxt

t

)()()('222

),( ,

⎧

=

−+⎟⎞

⎜⎛ −−

xtx

TxDTCxdssBusAxT

)(

)()()(1)(1max 222

12

es constantes positives.

e est :

où A, B, C, et D sont d

( ) )(21),,,( 22 FuExpBuAxpuxt +++−=Η La fonction de Pontryaguine de ce problèm

et l’équation d’HJB est 0),(),,,(max =∂∂

+Η txtVpuxt

u. Le maximum est atteint pour

B

pFpu

BFpAxpExpxt

221),,(

222* +⎟⎠⎞

⎜⎝⎛ −=Η . == )(* , et il vaut alors u

⎪⎪⎩

⎪⎪⎨

⎧

−=

=⎟⎞∂J

L’équation de Bellman s’écrit ⎠⎜⎝⎛∂

+−∂∂

+∂∂

2

222

21),(

022

1

DxCxxTJ

xBFAx

xJEx

tJ

On recherche une solution sous la forme : )()()(21),( 2 txtxtxtV γβα ++−= .

quelques calculs : ( )

Il vient, après ( )12)(22 )(221

1 −− −tTKeKD ω),( 1

)(

21221

21

⎟⎟⎠

⎞⎜⎜⎝

⎛

−−−

−+−=

−tTK

DCex

cxxtVω

ωωω ,

vec a

⎪ =2K⎪⎪

⎪⎪

⎨

⎧

−

+=

⎠⎝

⎟⎟⎞

⎜⎜⎛

++=

2

21

22

21

ω

ω

DB

E

BF

BAFEE

FB

Et le contrôle optim

⎪⎪⎪

⎟⎟⎞

⎜⎜⎛

+−=

⎠⎝2

222ω

AFEEB

⎪⎪ 2 AFK

⎩ − 1ωD

( )

⎟⎟⎟⎟⎟

⎠

⎞

al s’exprime :

⎜⎝⎜⎜−=

∂=),(

BxBxtu ⎜

⎜⎛

−

⎟⎟⎠

⎞⎜⎜⎝

⎛−

−−+ −

−

1)(22

1

)(

21

1*

1

1

tTK

tTK

eKD

CexxFJF ω

ωωω . ∂


4. Exercices

4.1. Programmation discrète

s

our agir sur un système discret IP. En notant la

variable d’état à chaque instant t [0,3], elle définit une fonction objectif et une

condition terminale , telles que la fonction de valeur du problème s’écrive

’entreprise cherche à minimiser la fonction de valeur, sachant que le système est régi par la tat a pour valeur initiale 1.

Exercice 2

sous les con= xx0

contrainte

On doit minimiser le critère étant donné l’équation d’évolution

⎪⎪⎧

⎪⎪

⎩

⎪⎨

=≥−

≥−+=

−−−=∑

40)(

05,08,0

..

321

Tux

uuxu

cs

uxuMin

ttt

T

ttttu

ice 4

Résoudre le problème quadratique

4.1.1. Enoncé Exercice 1 Une entreprise dispose d’une politique u p tx

∈ ( )∑−

=

+1

0

22T

ttt tux

( ) 2TT xxg =

( ) 21

0

22T

T

ttt xtux ++∑

−

=

.

Lloi d’évolution ttt uxx =+1 et que la variable d’é

0x

Trouver les extrema de traintes ⎧ +=+ uxx ttt 1 et sous la

.

( )∑=

−+3

042

tt

u xxte t

⎩⎨

10 ≤≤ u

Exercice 3

( )( )∑=

−−−=T

tttt uxuuJ

132)(

( )tttt uxux −+=+ 5,08,01 .

Le programme s’écrit : ⎪⎪⎨ ⎪

⎧+1xt

Exerc

( )[ ]

( )

⎪⎪⎪⎪

⎩

( )

⎪⎪⎪

⎩

⎪⎪⎪

⎨

⎧

⎪⎩

⎪⎨

⎧

==−=

++

+

−

=∑

41..

21

21

0

1

1

0

222

Tx

uxxcs

xuxMin

ttt

T

tTttu


Exercice 5

Résoudre le problème ⎪

⎪⎨

⎧

⎪⎪⎩

⎪⎪⎨

≥≥≥

=+++

000

1

..

24

3

2

1

3

32

xxx

x

cs

xxxMax

⎩

⎧ −=

+

+

=∑ lnln

1

3

04

urxx

xuMax

ttt

ttu

Le système IP s’écrit donc ∈

++−

=∑

1

,..

min

)(

0

1

2

1

0

222

xx

IRuxcs

xtux

xIPttt

T

tTttu

. Pour résoudre ce problème linéaire

⎩

⎪⎪⎪⎧

⎪⎩

⎪⎨

⎧

=−=

∈

++

+

−

=∑

1

,..

min

0

1

2

1222

xuxx

IRuxcs

xtux

ttt

tt

T

StTttu

. D’après HJB, la fonction de valeur du

problème est alors caractérisée par la récurrence rétrograde suivante :

⎪⎨⎧ −+−+−=

23

22 ,1max),(

x

uxtVtuxxtV ttttut

•

( )⎪⎪ ⎧ + 21

1

xx

⎪⎪⎩

Exercice 6

Résoudre le programme suivant :

⎢⎢⎢⎢

⎪⎪

⎪⎪⎨

>≥>=

00,

0)0(.. 0

rxu

xxcs

tt

⎢⎢⎢

⎣

⎡

4.1.2. Corrections Exercice 1

( )( )

⎪⎪⎪

⎩

⎪⎪⎪

⎨

⎧

⎪⎩

⎪⎨

⎧

=−=+ ux

tt

quadratique, on pose ⎪⎨),( xsIP

( )( )

⎪⎪

( ) ( )[ ]⎪⎩ =),3( xVOn en déduit :

( ) ( ) ( )[ ]222

22

222 2max,2

2

uxuxxVu

−−+−=

Pour résoudre ce programme de maximisation, la condition nécessaire d’optimalité (CNO) est ’annuler la dérivée première de V en u : d


( )222 024 uxu =−+−⇔

22

2

26

0(.)

xu

uV

=⇔

=∂∂

32*

2xu =

)

⇔

⎥⎥⎦

⎤

⎢⎢⎣

⎡⎟⎠⎞

⎜⎝⎛ −−⎟

⎟⎠

⎞⎜⎜⎝

⎛⎟⎠⎞

⎜⎝⎛+−=

22

2

222

2 332 xxxx D’où ( 2,2 xV

⎥⎦

⎤⎢⎣

⎡+−−+−=

932

92 2

222

22

22

2 xxxx 2x

( ) 222 3

5,2 xxV −=

( ) ( ) ⎥⎦⎤

⎢⎣⎡ −++−• ( ) =1 max,1 xV 2

1121

21 3

51

uxuxu

CNO : ( ) 03

102 111 =−−− uxu

11

111 310

3102 xuu =+−⇔

310

34 xu =⇔

⇔ 1*1 2

5 xu =

⎥⎥⎦

⎤D’où ( )

⎢⎢ ⎜

⎜ +−= 211,1 xxV

⎣

⎡⎟⎠⎞

⎜⎝⎛ −+⎟

⎟⎠

⎞

⎝

⎛⎟⎠⎞

⎜⎝⎛

2

11

2

1 25

35

25 xxx

⎟⎠⎞

⎜⎝

=41x ⎛ −−

⎟⎠⎞

⎜⎝⎛−+−−=

2541523

35

425

2

2

121

21 xxx

( ) 211 2

7,1 xxV −=

)• ( ) ([ ]0000 ,1max,0

0

uxVxxVu

−−−=

( ) ⎥⎦⎤

⎢⎡ +−= 0max x⎣

− 2002

70

uxu

CNO : ( ) 070 000∂u

=−⇔=∂ uxV

par hypothèse. Donc 00 xu =⇔

Or, 10 =x 10 =u .


En résumé :

00

2

1

==

00

01

3

2

001

00

==

=−===

xu

uxxxu

Et

Exercice 2

•

xu

( )∑−

=

=++1

0

222 1T

tTtt xtux .

( )

⎢⎢⎢⎢⎢⎢

⎣

⎡

⎪⎩

⎪⎨

⎧

≤≤=+=

−+

+

=∑

10..

2

0

1

3

04

uxx

uxxcs

xxteMax

ttt

tt

u

ut

44 2),4( xxV −=

( ) ( )[ ]333103 23max),3( 3

3

uxxexV u

u+−+=

≤≤ •

CNO : 32023

3

3

=⇔

=−

u

u

e

e

⇔32ln~ *

3 =u <0

Or, 03(.)3

23

2

>=∂∂ ue

uV . En d’autres termes, est convexe, décroissante

jusqu’à

),3( 3xV

32ln~ *

3 =u , et croissante ensuite. Or, 10 ≤≤ u . Donc le maximum est

atteint pour 1*3 =u puisque est croissante sur [0,1]. ),3( 3xV

Ainsi, )1(23),3( 333 +−+= xxexV ⇔ 23),3( 33 −−= xexV

• ( )[ ])(232max),2( 2221022

2

uxexexV u

u+−−++=

≤≤

CNO : ⇔=− 012 2ue21ln~ *

2 =u <0

Or, 22(.)2

2

2ue

uV

=∂∂ >0

On se retrouve dans exactement la même configuration que précédemment. On choisit donc 1*

2 =u


Et )1(232),2( 222 +−−++= xexexV ⇔ 35),2( 2 −= exV

( )[ ]35max),1( 1• 10 1 ≤≤u1

1 −++ exexV u =

CNO : 01 =ue impossible 10 1 ≤≤∀ u ),1( 1x est en fait une fonction strictement croissante, et le maximum est atteint

sur [0,1] pour

V1*

1 =u On obtient 35),1( 11 −++= exexV ⇔ 36),1( 11 −+= xexV

• (0 ) ( )[ ]36max, 0001000

−+++=≤≤

uxexxu

A nouveau, ( )0,0 xV est strictement croissante, et le maximum est atteint pour

V

1*0 =u . On obtient ( ) 262,0 00 −+= exxV .

⎪

⎪⎪⎨

⎧

⎩⎨⎧

=+=

−+

+

=≤≤∑

xxuxx

cs

xteMin

ttt

t

u

ut

0

1

3

0410

..

2

•

( )xt

⎪⎩( ) 44 2,4 xxV −=

• ( ) ( ) ( )[ ]333303 23,3 3

3

uxxeMinxV u

u+−+=

≤≤

En se servant du raisonnement tenu lors de la maximisation, on obtient instantanément que 0*

3 =u et ( ) 333 23,3 xxxV −+= ⇔ ( ) 33 3,3 xxV −= . • ( ) ( ) ( )[ ]222102 32,2 2

2

uxxeMinxV u

u+−++=

≤≤.

On sait d’avance que 0*2 =u et ( ) 5,2 2 =xV .

• [ ]5),1( 11011

1

++=≤≤

xeMinxV u

u

0*1 =u et 6),1( 11 += xxV

( )[ ]6),0( 0001•

0 00 +++= uxxMinxV

≤≤u

0*0 =u et 62),0( 00 += xxV

Exercice 3

• ,5 5xV •

( ) 0=( ) ( )[ ] ( )44044404 332,4

44

xuMinuxuMinxVuu

−=−−−=≥≥

On sait à vue d’œil que 0*4 =u et ( ) 44 3,4 xxV −=

) )• (( ( )[ ][ ] [ ]3333 5,408,3,3 xuxxV 30333301,05,032

33

uMinuxuuMinuu

−=−+−−−−=≥≥

On sait à vue d’œil que 0*3 =u et ( ) 33 5,4,3 xxV −=

• ( ) ( ) ( )[ ][ ] [ ]22022222202 25,535,05,08,05,432,222

xuMinuxuuxuMinxVuu

−−=−+−−−−=≥≥

contrainte empêche cette fois-ci de conclure rapidement. 02 ≥uLa


*2u est telle . Oque r, 025,535,0 22 ≥−− xu 0)( 22 ≥− ux par contrainte, donc ne peut

pas être supérieur à L’unique solution est alors

2u

2x .

2*2 xu = et 22 6,5),2( xxV −= .

• ( ) ( ) ( )[ ][ ] [ ]1101111110111 uu

8,568,05,08,06,532,1 xuMinuxuuxuMinxV −−=−+−−−−=

De ière, xu =≥≥

la même man *1 1 et 11 48,6),1( xxV −=

Exercice 4

•

244 2

),4 x =1( xV

• ( ) ( ) ⎥⎦⎤

⎢⎣⎡= 22

32

31

21),

3

Minxu

−++ 333 23( uxuxV

CN 33 =O : ( 0)3 −− xu u ⇔ 3*3 2

1 xu =

2⎞V 3333 222 ⎠⎝⎥⎦⎢⎣

2

32 11

211),3( ⎟⎜

⎛ −+⎥⎤

⎢⎡

⎟⎠⎞

⎜⎝⎛+= xxxxx

2

322 11⎟⎞

⎜⎛ + xx 33 2

121

42⎟⎠⎞

⎜⎝⎛+

⎠⎝= x

233 4

3),3( xxV

( ) ( ) ⎥⎦⎤

⎢⎣⎡ −++= 2

2222

222 4

321),2(

2

uxuxMinxVu

•

0)(23

222 =−− uxu CNO :

⇔ 22 23

25 xu =

⇔ 2*2 5

3 xu =

2331 ⎞⎛⎛ ⎛

22

2

2222 5

3452

),2( ⎟⎟⎠

⎜⎜⎝

⎟⎠⎞

⎜⎝⎛−

⎠

⎞⎜⎜⎝

⎟⎠⎞

⎜⎝

+= xxxxxV

+⎟⎟

2

222

22 5

243

259

21

⎟⎠⎞

⎜⎝⎛+⎟

⎠⎞

⎜⎝⎛ += xxx

222 5

4) =,2( xxV

( ) ⎥⎦⎤

⎢⎣⎡ +++= 2

1121

211 )(

54

21)

1

uxuxMinxu

CNO :

,1(V•

⇔ 1*1 13

8 xu = 0)(58

111 =−− uxu


2

111 35132 ⎝⎟⎠

⎜⎝ ⎠⎝

1

22

1 18481),1( ⎟

⎠⎞

⎜⎛ −+⎟

⎞⎜⎛

⎟⎞

⎜⎛+= xxxxxV ⇔ 2

11 2621),1( xxV =

( ) ( ) ⎥⎦260u

⎤⎢⎣⎡ −++= 2

0200 1211

21),0( uuMinxV

CNO :

•

0)1(1321

0 −u 0 =− u ⇔ 342*

0 =u 1

2

341

261

342 ⎠⎜⎝⎛ −

⎠⎝ ⎠⎝

2

02122111),0( ⎟

⎞+⎟⎟⎞

⎜⎜⎛

⎟⎞

⎜⎛+=xV

2312019519), x⇔ 0( 0 =V

xercice 5 e triplet optimal est

EL ( ) ( )0,1,0,, *

3*2

*1 =xxx .

En effet, raisonnons par l’absurde et supposons que , ε−=1*2x 0>ε .

λε=*1x et , ( )ελ−1*

3x [ ]1,0∈λ . On a alors On a donc xx Exercice 6

• ln x= •

424)1(2)1(424 *3

*2

*1 <−−=−+−+=++ λεεελελεx

( 4,4 xV ) 4

[ ])ln(ln),3( 33333

urxuMaxxVu

−+=

CNO : 011

333

=−

−urxu

⇔ 0333 =+− urxu

⇔ 3*3 2

xru =

⎟⎠⎞

⎜⎝⎛ −+⎟

⎠⎞

⎜⎝⎛= 3333 2

ln2

ln),3( xrrxxrxV

⇔ ⎟⎠⎞

⎜⎝⎛= 33,3(

2ln2) xrxV

• ⎥⎦

⎤⎢⎣

⎡⎥⎦⎤

⎢⎣⎡ −+= )(2

ln2ln),2( 22222

urxruMaxxVu

= ( ) ⎟⎟⎠

⎞⎜⎜⎝

⎛⎟⎠⎞

⎜⎝⎛ − ²

2ln 222

2

urxruMaxu

Or, ln(.) est une fonction croissante. Il suffit donc de déterminer le sens de variation de

( ) ²2 222 ⎟

⎠⎞

⎜⎝⎛ − urxru .

( )( ) ( )22

2

22

22

2

2

2222

42

42

urxruurxru

urxru−−−=

∂

⎥⎦

⎤⎢⎣

⎡⎟⎠⎞

⎜⎝⎛ −∂


( ) ( )[ ]2222

22

2

24

urxuurxr−−−=

( )( )urxurxr 34 222

2

−−=

32

2rx

u =On peut alors établir le tableau de variations : les racines sont xu 22 r= ou , et

0

32rx

2rx

+ - +

Puisque, par hypothèse, 0≥ 1 −=+ ttt rxx e n d ine que . Par

, le maximum est atteint en

u , et qu , o ev00 >x tt rxu <

3

2*2

rxu =conséquent .

t ⎟⎟⎠

⎞⎜⎜⎝

⎛⎟⎠⎞

⎜⎝⎛ −+⎟

⎠⎞

⎜⎝⎛=

32ln2

3ln),2( 2

22

2rx

rxrrxxV E

⎥⎥⎦

⎤

⎢⎢⎣

⎡⎟⎟⎠

⎞⎜⎜⎝

⎛⎟⎠⎞

⎜⎝⎛ −=

22

22

323ln

rxrxrrx

⇔ ⎟⎟⎠

⎞⎜⎜⎝

⎛=

27ln),2(

32

5

2xr

xV

• ⎥⎥⎦

⎤

⎢⎢⎣

⎡⎟⎟⎠

⎞⎜⎜⎝

⎛ −+=

27)(lnln, u)1(

211

5

111

urxrMaxxVu

Comme précédemment, on étudie le sens de variation de ( )3111 urxu − .

0)(

1

3111 =

∂−∂

uurxu ⇔ ( ) 0)(3 2

1113

11 =−−− urxuurx

tenant exactement le même raisonnement que précédemment, on obtient que

⇔ 0)4()( 112

11 =−− urxurx

41*

1rxu =En .

Et 274

ln),1( 1 =xV 4

31

15

1⎟⎠⎞

⎜⎝⎛ −

rxrxrrx

⇔ 944

11 4

ln),1( rxV ⎟⎟⎠

⎜⎜⎝

=x ⎞⎛

94

0000 4

lnln),0(0

rurx

uMaxxVu

⎟⎠⎞

⎜⎝⎛ −

+= •


Comme précédemment, on recherche les racines : ( )

00

4000 =

∂−∂

uurxu

⇔ 0)5()( 003

00 =−− urxurx

On obtient 5

0*0u =

rx.

Et 9

40

05ln),0( r

rx

xV ⎟⎟⎞

= 0

0rxrx ⎜

⎜⎛ −

⇔ ⎥45⎟⎟⎠

⎜⎜⎝

⎦

⎤⎢⎣

⎡= 5

50

14

0 5ln),0(

xrxV .

4.2. Calcul des variations

4.2.1. Enoncés Exercice 1 Trouver les extrémales des problèmes suivants :

(a) sous les conditions x(0)=0 et x(1)=1

) sous les conditions x(0)=0 et x(1)=1

les conditions x(0 =1

ns x(0)=0 t x(1)=1

Résoudre sous les contraintes x(1)=0, x(3)=a

cas a=0 et a=2 montrer que la solution est une droite. b) Dans le cas a=1, montrer que la solution optimale est composée de deux segments de

droite. Ecrire l’équation d’Euler.

Exercice 3

Résoudre

( )∫ ++=1

0

2 23)( dttxxxJ &

∫=1

0)( dtxxJ &(b

(c) ∫= 0)( dtxxxJ & sous )=0 et x(1)

(d) ∫= 0)( dtxtxxJ & sous les conditio e

1

1

Exercice 2

( )∫ −3

1

22 1 dtxxMin &

a) Dans le

( )∫ +1

21mint

dtx& sous les contraintes x(0)=0 et ( ) ( )( ) 133 21

21

0

=−+− txt

Exercice 4 Soit )dtx1 &&

b) Résoudre le problème d’extrémalité sous les contraintes x(0)=1, x(T)=1

(TxxxxJ 22 416)( ∫ −+=

0

a) Ecrire la condition d’Euler


Exercice 5 Soit )(2416)( &&

a) Ecrire la condition d’Euler b) Ecrire la condition de transversalité c) Trouver les fonctions x qui vérifient la condition d’Euler, la condition de

transversalité et la condition x(0)=1

d) Même que

( )∫ +−+=T

TxdtxxxxxJ0

2222

stion avec ( )∫ +−+=T

xxxJ 216)( & Txdtxx0

2 )(4 &

4.1 tion Exercice 1 On sait que les extremales de (, &

.2. Correc

( )∫T

dttxtxtL0

)(), sont solutions de l’équation d’Euler

0=− xx LdtdL & .

(a) Ici, on a = . Donc ( ))(),(, txtxtL & txx 232 ++& 3=xL , xLx && 2= et xLdtd

x &&& 2= . Donc on a

x&&23 =

23

=⇔ x&&

at +3 x⇔ & =2

battx ++=⇔ 2

43

Or, x(0)=0 et x(1)=1, donc ⎪⎩ ⎪⎩ 44

⎪⎨⎧ ⎪

⎨⎧ =

⇔=

10

30 bb

. Ainsi, ( )1341 2 += tx==+ 1 aa .

Ici, on a (, xtL(b) ))(), txt & = x& . Donc 0( =xL , 1=xL& 0=xLdtd et & . On a donc 0=0 x(t)

vérifiant x(0)=0 et x(1)=1. Donc toutes les courbes vérifiant x(0)=0 et x(1)=1 sont des males.

(c)

∀

extré

Ici, on a ( ))(),(, txtxtL & = xx& . Donc xLx &= , xLx =& et xLdt x && =d . On a donc =

) Ici, on a = . Donc

x& x& .

Donc toutes les courbes vérifiant x(0)=0 et x(1)=1 sont des extrémales.

(d ( ))(),(, txtxtL & xtx& xtLx &= , txLx =& et xtxLdtd

x && += . Donc on a

0=⇔+=xt& xxtx & . Il n’y a donc pas d’extrémales satisfaisant les contraintes.


Exercice 2

Rés⎪⎧ −∫ dtxxMin 1

3

1

22 &

n a

x& et

( )olvons ⎨ ⎧ =x 0)1( .

⎪⎩ ⎩

⎨ = axcs

)3(..

O ( )22 1),,( xxxxtL && −= .

)1(2 2 xxLx && −−= ( ) xxxxxxxdtdL

d2)1(2xL −=x t

dx &&&&&&

22 2)1(4)1(2 +−−=−−=

Donc l’équation xx &&&& +− ))1(2 2 si

d’Euler s’écrit : 22 xxxxxxx &&&&&& −−=−⇔+−−= 1(2)1(2)1(4 xxx 0≠x .

e x=0 est une extrémale, et 1=x& est une extrémale. On voit qu a) Dans les cas a=0 et a=2, mOn a xtL

onc

Or, J(0)=0 et =xJ avec tel que

ontrons que la solution est une droite. 0)1(), 22 ≥−= xxx && ,(

∫ ≥−=3

1

22 0)1()( dtxxxJ & D

1x 1=x& . 0)( 1

x=0 vérifie les conditions initiale et terminale pour a=0. vérifie les conditions initiale et terminale pour a=2, et 1)(1 −= ttx 1)(1 =tx&

b) Dans le cas a=1, montrons q imale est composée de 2 segments deue la solution opt droite. Dans le cas a=1, on peut prendre comme extrémale :

si si

222 )1( dtxx &

Ecrivons les équations d’Euler : est donc optimale, et pourtant elle n’est que par morceaux.

est elle que x=0 et sont des extrémales. est donc optimale, bien qu’elle ne soit que par morceaux Exercice 3

ésolvons

0)(2 =tx 21 ≤≤ t 0)1(2 =x 2)(2 −= ttx 32 ≤≤ t 1)3(2 =x

On a bien 22 )(xJ

.

∫ −=3

1

0)1(2)1(2 222

222 =−+− xxxx && .

)(2 tx 1C

2x 1=x& 2x1C

( ) (

R

)⎪⎩ ⎩ =13 21t

que si on étu( )⎪

⎧∫ )(),(,1

dttxtxtLMaxt

&

( )⎪

⎪⎨

⎨⎧

−+−=

30)0(

.. 21

0

2

xtx

cs

dtx&

n sait die le problème

( )⎪

⎪⎨

⎩⎨⎧

=Φ=

Ρ

),)0(

..11

0

0

txx

c, on a :

Si 1,tx er

⎪⎧

+∫ 11

Mint

O

⎪⎩ 0(txs

) est une solution du problème P, alors x est solution de l’équation d’Eul([ ]TtLL

dtd

xx ,0, ∈∀=& , avec la condition initiale vérifiée 0)0( xx = , et ( )1,tx vérifie la


condition de transversalité, écrite en 1t : ( ) ( ) ( ) ( )[ ] 0),,)(()(),(( 11111 ,(,),,), 11111 =−Φ+ xxLxxtLtxtxtxtx xt &&&&

On applique ce résultat à nΦ txtttLt xx & &

otre cas. On a :

( ) 2121 xL &+= , 0=xL , ( ) ( ) 2

12212 12

21 −−

+=+= xxxxLx &&&&&

On a donc

1

( ) 21210 −

+= xxdtd

&& ( ) cxx =+⇔− 2

121 && , c étant une constante

2

22

1 ccx−

=⇔ & , donc Kx =& , avec K constante ⎟⎟⎠

⎞⎜⎜⎝

⎛

−±= 2

2

1 ccK

βα += tx , avec K=α . Par ailleurs, la condition initiale x(0)=0 implique que 0=β . Donc ( ) ( ) ( ) 13)(3, 2

12

11 −−+−=Φ txttx . On sait par ailleurs que On peut calculer , et )3(2),( 11 −=Φ ttxt ( )3)(2),( 11 −=Φ txtxx . On sait que la condition de transversalité est de la forme :

( ) ( ) ( ) ( )[ ] 0),,(,,)(),()(),(,),( 1111111111 =−Φ+Φ xxtLxxtLtxttxtxtxtLttx xxxt &&&& &&

( ) ( ) ( ) ( )[ ] 011)(3)(21)3(2 21221211

2121 =+−+−++−

−− xxxtxtxxxt &&&&&& Ici, ( ) ( )( ) 013)(2)3(2 22

11 =+−−+−⇔ xxtxxt &&&

11)( ttx α= et α=)( 1tx& . Or, On remplace : ( ) ( ) ( )( ) 013232 22

11 =+−−+− αααα tt 033 =+−⇔ α . Donc 1=α .

111)( tttx ==α . On a donc

( ) ( )2

131320, 12

11 ±=⇔=−⇔=Φ tttx (en fait, 2

1±=c ) Donc

Exercice 4 Soit

e) Ecrivons la condition d’Euler. On a

( )∫ −+=T

dtxxxxxJ0

221 416)( && .

xxxxxxtL &&& 416),,( 22 −+= . xxLx &432 −=

xxLx 42 −= &&

xxLdtd

x &&&& 42 −=

Donc, la condition d’Euler s’écrit : xxxxxx &&&&&& =⇔−=− 1642432 Les solutions sont donc du type

f) Résolvons le problème d’extrémalité sous les contraintes x(0)=1 et x(T)=1.

On a :

tt BeAetx 44)( −+ +=

⎩⎨⎧

+=+=

− TT BeAeBA

4411

)2()1(

BA −=→ 1)1( ATT BeeB −+−=→→ 4)1(1)2()1(

TT

T

eeeB 44

41−

−=⇔ − et TT

T

eeeA 44

4 1−−

= −

−


Et donc tTT

Tt

TT

T

eee

eeee

etx 444

44

44

4 11)( −−−

−

−−

+−−

=

Les extrémales trouvées correspondent-elles à des minimales ou des maximales ? Pour le savoir, étudions la fonction .

On a

uvvuvuvuf 416),(:),( 22 −+a

vuuf 432 −=∂∂ , 322

2

=∂∂

uf , 4

2

−=∂∂

∂vuf , uv

vf 42 −=∂∂ , 22

2

=∂∂

vf .

La matrice hessienne de f est donc ⎥⎦

⎤⎢⎣

⎡−

−24432

, et le mineur principal d’ordre 1 est 32.

es, tous les onvexe. Les extrémales

e 5 +

TTxx

0

222 )(16 &

l’instant terminal est fixé) et l’on

tudie un pr )⎨

+0

)xg , alors si x est

Le déterminant (ou mineur d’ordre 2) est 32x2-4x4=64-16>0. En d’autres termmineurs principaux sont positifs ; ce qui signifie que f(u,v) est cexhibées correspondent donc à des minimas. ExericSoit ∫ +−= xdtxxxJ2 24)( &( )On sait que si la condition terminale n’est pas fixée (mais

oblème avec coût terminal, i.e. ( )⎪⎧Ρ ∫ ()(),(, TdttxtxtLMaxT

& (⎪

é⎩ = 0)0(.. xxcs

extrémale, i.e. solution de P, alors elle vérifie : xxLd& L

dt= , [ ]Tt ,0∈∀ (condition d’Euler), et

la condition de transversalité au point terminal s’écrit : ( ) 0)(')( =+ TxgTLx& . Ecrivons la condition d’Euler :

&432 −= , 42 −= & , xxLx x& xxL xxLdtd

x &&&& 42 −

a) La condition d’Euler s’écrit donc : xx 16=&& c, coLa

vers solution s’écrit don mme dans l’Exercice 4, de la forme : tt BeAetx 44)( += .

b) La condition de trans alité s’écrit : 0)()(4)(

−+

4)(2 =⇔−=− TxTxTxTx && c) Tr vons maintenanou t les fonctions qui vérifient la condition d’Euler, la condition de

ansversalité et la condition initiale x(0)=1.

l, on trouve

tr

Ainsi : )1()2( ⎩⎨⎧

−=+

− TT BeAeBA

44 441

( )( )0)(

1)0(==

Txx&

TT

T

eeeB 44

4

−+= et TT

T

eeeA 44

4

−

−

+= Après calcu

Donc, l’extrémale x(t) est telle que tTT

Tt

TT

T

eee

eeee

etx 444

44

44

4

)( −−−

−

++

+=

d) Mêmes questions avec 22 )(416)( &&

précédemment ; quant à la condition de transversalité : . On a donc encore une fois

nc⎩⎨⎧

−=+−− 1442 BeAeBeAe

( )∫ +−+=T

TxdtxxxxxJ0

La condition d’Euler est la même que1)(4)(2 −=− TxTx&& tt BeAetx 44)( −+ += .

Do [ ] [ ]=+

−−

14444 TTTT

BA


TT

T

eeeBA 44

4

1241121 −

−

+−

=−= . Après résolution, on trouve

tTT

Tt

T eee 44

4 14112 − −+

−= TT e

eetx 4

4444 12412)( −

−− ++Donc

ee4

S, Intertemporal macroeconomics, Blackwell

ic analysis, Cambridge versity press

LMAN, Introduction to the mathematical theory of control process, Academic press

imitri P. BERTSEKAS, Dynamic programming nd stochastic control, Academic press

TSEKAS, Dynamic programming, determining and stochastic control, Prentice-hall

ophe CULIOL Introduction à l’optimisation, Ellipses

Gabrielle DEMANGE et Jean-Charles ROCHET, Méthodes mathématiques de la finance, conomicae

urs d’optimisation, Ecole Polytechnique

ond W. RISHEL, Deterministic and stochastic control, Springer-V Michael D. INTRILLIGATOR, Mathematical optimization and economic theory, prentice Hall N. V. Krylov, Controlled diffusion processes, Springer-Verlag LOGAN, App Enid R. Pinch, Optimal control and the calculus of variations, Oxford University Press STOKEY et LUCAS, Recursive methods in Economic dynamics, Harward university press SARGENT, Dynamic macroeconomic theory, Harward university press Charlotte STIEBEL, Optimal control of discrete time stochastic systems. Lecture notes in economics, Springer-Verlag

Bibliographie AZARIADIS et COSTA BEAVIS et DOBBS, Optimisation and stability theory for economuni

BEL D a Dimitri P. BER

Jean-Christ I,

E FAURE, Co Wendell H. FLEMING et Raym

erlag

lied mathematics, Wiley


Documents

Programmation dynamique - Believe | A different … · 2010-07-24 · Exemple Soit un consommateur qui possède une richesse initiale x0. Il consomme ct, t0[0 ;T-1] (i.e. il ne consomme