Univérsité Ibn Zohr Année Univérsitaire 15-16
Faculté des Sciences - Agadir Filière: SMA-6
Département de Mathématiques Pr: M.SADIK
Travaux Dirigés n◦ 2 - Optimisation
Exercice 1 (Lemme de Farkas-Minkowski)
Soit V un espace de Hilbert (e.v.n), ai ∈ V , i ∈ I ensemble fini d’indice et b ∈ V .
Montrer que : {w ∈ V / < ai , w >≥ 0, i ∈ I} ⊂ {w ∈ V / < b, w >≥ 0} si et seulement s’il existe
λi ≥ 0, i ∈ I, tels que : X
b= λi ai .
i∈I
C’est-à-dire b appartient à un cône convexe fermé engendrè par les ai .
Exercice 2
min J(x)
On considère le problème de minimisation suivant: où
x∈K
J : Rn → R
x = (x1 , . . . , xn ) 7→ J(x) = − ni=1 ln(xi + ai )
P
Pn
et K l’ensemble défini par: K = {(x1 , . . . , xn )t ∈ Rn , xi ≥ 0 ∀i, i=1 xi = 1}
a = (a1 , . . . , an )t est un vecteur donné de Rn dont toutes les composantes sont strictement positives.
1. Montrer l’existence et l’unicité d’une solution u = (u1 , . . . , un )t .
2. Ecrire les relations KKT associées à ce problème.
3. En déduire qu’il existe un réel ξ tel que pour tout i , ui = max(0, ξ − ai ).
4. On pose n = 4 et a = (0, 25; 0, 5; 0, 75; 1)t trouver u et ξ.
Exercice 3
Etant donné u = (u1 , . . . , u2 ) ∈ Rn on cherche un élément x = (x1 , . . . , xn ) ∈ Rn vérifiant x1 ≤ x2 ≤
· · · ≤ xn le plus proche possible de u (au sens de la norme euclidienne usuelle de Rn )
1. Formaliser cette question comme un problème de minimisation convexe, et préciser la nature
de l’ensemble des contraintes.
2. Décrire les conditions caractérisant l’unique élément x̄ = (x̄1 , . . . , x̄n ) répondant à la question.
3. on traite ici un exemple dans R4 : étant donné u = (2, 1, 5, 4), trouver l’unique x̄ = (x̄1 , x̄2 , x̄3 , x̄4 )
vérifiant x1 ≤ x2 ≤ · · · ≤ x4 à distance minimale de u.
4. L’algorithme d’UZAWA est une méthode numérique itérative pour résoudre de ce type de
problèmes. Décrire cette méthode en l’appliquant à ce problème ( Question 1) .
1
Exercice 4
Soit V = Rn , on considère le problème de minimisation convexe suivant:
Inf J(v),
(P)
F (v) ≤ 0
où J est une fonction convexe continue de Rn dans R et F une fonction covexe continue de Rn dans
Rm . Pour ε > 0, nous introduisons alors le problème sans contraintes
m
1X
[max(Fi (v), 0)]2 ;
(Pε ) inf J(v) +
v∈V ε i=1
On suppose que J est strictement convexe et coercive, que Fi sont convexes et continue pour 1 ≤
i ≤ m, et que l’ensemble
K = {v ∈ Rn , Fi (v) ≤ 0∀i ∈ {1, . . . , m}}
et non vide. Montrer que (P) resp. (Pε ) admet une solution unique noté u (resp. uε ) et que
lim uε = u
ε→0
Exercice 5
Pour minimiser f : Rn → R on considère en générale x0 donné puis xk+1 = xk + tk dk où dk est
une direction de descente pour f en xk et où le pas tk n’est pas obtenu par une minimisation
unidimentionnelle exacte mais par une recherche linéaire dont le succès consiste juste à satisfaire les
deux conditions suivantes (appelée règles de Wolfe):
h(tk ) ≤ h(0) + tk m1 h0 (0), règle (1)
h0 (tk ) ≥ m2 h0 (0) règle (2)
où h(t) = f (xk + tdk ) et 0 < m1 < m2 < 1 sont deux constantes fixées. Dans la suite on suppose :
- f minorée de classe C 1 et ∇f (.) Lipschitzienne sur l’ensemble {x : f (x) ≤ f (x0 )} (L est la
constante de Lipschitz);
- Que la recherche unidimensionnelle donne bien à chaque itération un pas respsctant les deux
règles de Wolfe.
- Que les directions de descentes successives vérifient :
h∇f (xk ), dk i
ck = − ≥δ>0
k∇f (xk )kkdk k
1. Exprimer les régles (1) et (2) de Wolfe à l’aide de la fonction f (au lieu de la fonction h).
2. En utilisant la première règle de Wolfe montrer que:
f (xk ) − f (xk+1 ) ≥ m1 ck k ∇f (xk ) kk xk+1 − xk k .
3. En utilisant la deuxième règle de Wolfe, montrer que :
(1 − m2 )ck k ∇f (xk ) k≤ L k xk+1 − xk k
4. En déduire
m1 (1 − m2 ) 2
f (xk ) − f (xk+1 ) ≥ δ k ∇f (xk ) k2
L
P∞
5. En déduire que k=0 k∇f (xk )k2 converge, donc ∇f (xk ) → 0.
6. On suppose de plus que f est coercive et strictement convexe. Montrer alors que xk converge
vers x∗ le min unique de f .
