Scribd
Importer
362 vues2 pages

Exam Optim M1 Isfa 11

Ce document présente deux problèmes d'optimisation. Le premier problème concerne la minimisation d'une fonction quadratique sous contraintes, et propose d'écrire le lagrangien, l'algorithme d'Uzawa et de montrer la convergence. Le second problème concerne la pénalisation intérieure d'une fonction et demande de montrer l'existence et l'unicité des solutions, et la convergence de la suite vers la solution du problème original.

Transféré par

kprepaa
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
362 vues2 pages

Exam Optim M1 Isfa 11

Ce document présente deux problèmes d'optimisation. Le premier problème concerne la minimisation d'une fonction quadratique sous contraintes, et propose d'écrire le lagrangien, l'algorithme d'Uzawa et de montrer la convergence. Le second problème concerne la pénalisation intérieure d'une fonction et demande de montrer l'existence et l'unicité des solutions, et la convergence de la suite vers la solution du problème original.

Transféré par

kprepaa
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

ISFA,

2 - `eme Annee - M1, 2010-2011


Examen - Optimisation
Duree 2h - Notes de cours autorisees

Les 2 probl`emes sont independants.


Probl`
eme 1.
On se donne m, n IN , A une matrice caree reelle de taille n, sym
etrique et positive d
efinie, b, d1 , d2 , dm des vecteurs de IRn et c1 , c2 , cm des constantes reelles. On
consid`ere lapplication quadratique
1
J : IRn IR, J(x) = < Ax, x > < b, x >
2
(o`
u < , > represente le produit scalaire usuel en IRn ) et lensemble des contraintes:
U = {x IRn ,

< di , x > ci ,

i = 1, 2, m}.

On suppose U 6= . On consid`ere le probl`eme de minimisation


(1)

Trouver x U,

J(x ) = min J(y).


xU

a) Montrer quil existe une solution unique de (1).


b) Ecrire le lagrangien et le probl`eme dual associes au probl`eme de minimisation (1).
c) Ecrire lalgorithme dUzawa pour lapproximation numerique de la solution de (1). On
(0)
note par (x(k) , p(k) ) IRn IRm
IRn+ donne).
+ la suite construite par cet algorithme ( p
d) Montrer que pour un facteur > 0 bien choisi, on a la convergence de x(k) vers x (les
notations sont celles du cours).
e) Cas particulier. On consid`ere ici
m = 1, n = 2, c1 = 0


2 1
A=
1 4
b = (2, 3)T ,

d1 = (1, 1)T .

e1) Montrer que U 6= et calculer la solution du probl`eme (1) dans ce cas.


e2) En prennant p(0) = 0 et = 13 , calculer les deux premi`eres iterations obtenues par
lalgorithme dUzawa (calculer x(0) , p(1) , x(1) , p(2) ).
Probl`
eme 2. (Un cas particulier de p
enalisation int
erieure)
Partie I
Soit n IN avec n 2 et J : IRn IR une fonction continue, coercive et strictement
convexe. Dans la suite pour tout 0 on va noter U = IRn1 [, +[ et
U = IRn1 ]0, +[ (remarquer que U est linterieur de U0 ).
Pour tout k IN on introduit la fonction Jk : U IR definie par
1
Jk (x) = J(x) +
, x = (x1 , xn )T U.
kxn
1

Ia) Montrer que le probl`eme: trouver x U0 tel que


J(x ) = min J(y)

(2)

yU0

a une solution et une seule.


Ib) Montrer que pour tout k IN le probl`eme: trouver x(k) U tel que
Jk (x(k) ) = min Jk (y)

(3)

yU

a une solution et une seule.


Indication: Montrer que pour > 0 assez petit (`a preciser) on a
inf

yU U

Jk (y) > inf Jk (y).


yU

(k)

Ic) Montrer que la suite J(x ) est bornee et en deduire que la suite x(k) est bornee.
Id) Montrer que la suite x(k) converge vers x pour k +.
Partie II: Application
On consid`ere dans cette partie n = 2 et J : IR2 IR donnee par
1
J(x1 , x2 ) = x21 + x22 x1 x2 x2 .
2
IIa) Montrer que les hypoth`eses de la Partie I sont satisfaites pour J.
IIb) Trouver la solution x du probl`eme (2) dans ce cas.
T

(k)
(k)
de (3). En eliminant
IIc) Ecrire le probl`eme satisfait par la solution x(k) = x1 , x2
(k)

x1 montrer que pour resoudre ce probl`eme il suffit de resoudre une equation scalaire avec
(k)
inconnue x2 . Montrer que cette equation a une solution strictement positive et une seule,
et que cette solution appartient `a lintervalle ]1, 1 + k1 [. En deduire que x(k) x pour
k +.

Vous aimerez peut-être aussi