Scribd
Importer
84 vues1 page

Optimisation Convexe dans Rd: Exercices et Théorèmes

Cet exercice contient plusieurs questions sur l'optimisation convexe dans Rd. Il présente des définitions de convexité, coercivité et semi-continuité inférieure pour des fonctions. Il demande également de déterminer si certaines fonctions satisfont ces propriétés et d'étudier la convergence d'algorithmes d'optimisation.

Transféré par

scienceszovuste
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
84 vues1 page

Optimisation Convexe dans Rd: Exercices et Théorèmes

Cet exercice contient plusieurs questions sur l'optimisation convexe dans Rd. Il présente des définitions de convexité, coercivité et semi-continuité inférieure pour des fonctions. Il demande également de déterminer si certaines fonctions satisfont ces propriétés et d'étudier la convergence d'algorithmes d'optimisation.

Transféré par

scienceszovuste
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

TD.

Optimisation dans Rd

Exercise 1. Soit f ∈ C 1 (C) où C ⊂ Rd est un ouvert convexe. Montrer les équivalences suivantes:
f convexe ⇔ f (y) ≥ f (x) + h∇f (x), y − xi ∀x, y ∈ C
⇔ h∇f (x) − ∇f (y), x − yi ≥ 0 ∀x, y ∈ C.
f str. convexe ⇔ f (y) > f (x) + h∇f (x), y − xi ∀x, y ∈ C, x 6= y
⇔ h∇f (x) − ∇f (y), x − yi > 0 ∀x, y ∈ C, x 6= y;
ky − xk2
f α-convexe ⇔ f (y) ≥ f (x) + h∇f (x), y − xi + α ∀x, y ∈ C,
2
⇔ h∇f (x) − ∇f (y), x − yi ≥ αky − xk2 ∀x, y ∈ C;
et si f est de classe C 2 :
f convexe ⇔ D2 f (x)  0 ∀x ∈ C ,
f str. convexe ⇐ D2 f (x)  0 ∀x ∈ C .
f α-convexe ⇔ D2 f (x)  αId ∀x ∈ C .
Exercise 2. Déterminer si les fonctions suivantes sont semi-continues inférieurement, coercives, convexes
(éventuellement strictement ou fortement).
x21
f1 (x) = − cos(kxk) , f2 (x) = kxk + 1|x1 |>1 (x) , f3 (x) = x2 + 1kxk≤1 (x) ,
2
f4 (x) = cosh(kxk) , f5 (x) = exp(−hx, vi) f6 (x) = f5 (x) + 1kxk=1
q
f7 (x) = (x21 + x22 ) + x21 + x22 − sin(x21 + x22 )
où x = (x1 , . . . , xd ) ∈ Rd , 1A est la fonction indicatrice convexe de l’ensemble A ⊂ Rd et v ∈ Rd
Exercise 3. Déterminer si les fonctions de l’exercice précedent admetettent un minimiseur et s’il est
unique. Si possible, donner une caracterisation des minimiseurs en utilisant les conditions d’optimalité.
Exercise 4. Soit f ∈ C 1 (Rd ) et ∇f L-lipschitzienne, montrer que si τ < 2/L alors
f (x − τ ∇f (x)) < f (x)
pour tout x. Donner un contre-exemple pour τ = 2/L.
Exercise 5. Soit f ∈ C 1 (X × X) où X est une espace vectoriel normé de dimension finie. Supposons
f bornée inférieurement, coercive et convexe et considérons l’algorithme d’optimisation alternée: Soit
x0 = (x01 , x02 ) ∈ X × X, pour n ≥ 0:
xn+1
1 ∈ arg min f (ξ, xn2 ) , xn+1
2 ∈ arg min f (xn+1
1 , ξ)
ξ∈X ξ∈X

(1) Montrer que l’algorithme est bien défini pour toute condition initiale et que
f (xn+1 ) ≤ f (xn )
et que donc il existe f ∗ ∈ R tel que f (xn ) → f ∗ lorsque n → ∞.
(2) Montrer qu’il existent x∗ ∈ X × X, y ∗ ∈ X × X et une sous-suite (xkl )l telle que xkl → x∗ et
xkl +1 → y ∗ lorsque l → ∞.
(3) Montrer que pour tout ξ ∈ X
f (xkl +1 ) ≤ f (xk1l +1 , xk2l ) ≤ f (ξ, xk2l ) , f (xk1l +1 , xk2l +1 ) ≤ f (xkl )
En déduire que f (y1 , x2 ) = f ∗ et que
∂x1 f ((y1 , x2 )) = 0
(4) Utiliser le même type de raisonnement pour montrer que
∂x2 f (y) = 0
et que cela implique ∂x2 f ((y1 , x2 )) = 0
(5) Conclure que (y1 , x2 ) est un minimiseur et que donc x et y sont aussi des minimiseurs.
Exercise 6. Déterminer si l’algorithme d’optimisation alternée et de descente de gradient à pas constant
sont bien définis et s’ils convergent pour les fonctions suivantes définies sur R × R
f (x1 , x2 ) = |x1 | − x1 x2 + |x2 | , f (x1 , x2 ) = log(exp(x1 + x2 ) + 1) + |x1 |2 + |x2 |2
1

Vous aimerez peut-être aussi