Chapitre IV. Mini-maximisation. Dualisation de problèmes...
Le calcul explicite de ϕ (x) est aisé : ϕ (x) = f (x) si x ∈ C, +∞ sinon.
Donc, notre premier problème de mini-maximisation est celui de la minimisation sur C de f (x), c’est-à-dire ni plus ni moins que le problème (P) originel.
Regardons maintenant ce qu’est le second problème de mini-maximisation. Il faut
considérer
(λ, μ) ∈ R
m
×
R
+
p −→ ψ (λ, μ) := inf
x∈R n
L (x, λ, μ) .
La fonction ψ est concave et semi-continue supérieurement (finie sur une partie
convexe de R m × (R + )
p ). On appelle problème dual de (P), et on le notera (D),
le problème de la maximisation de ψ sur R m × (R + )
p . Cette fonction duale est
également notée Θ parfois. Si f et ψ désignent les valeurs optimales dans (P ) et
(D) respectivement, on a toujours f ψ (la différence f − ψ s’appelle le saut de
dualité (1) ).
Si (P) est un problème de minimisation convexe, avec un ensemble S ( = ∅)
de solutions et un ensemble M ( = ∅) de multiplicateurs de Lagrange, on a :
f = ψ et les solutions du problème dual (D) sont exactement les multiplicateurs
de Lagrange du problème (P).
Si on a accès à un
λ, μ
∈ M , comment en déduit-on les solutions de (P) ?
Réponse : Ce sont les x qui
– minimisent L
·, λ, μ
sur R n ;
– sont dans C et vérifient μ j g j (x) = 0 pour tout j = 1, . . . , p.
Si L
·, λ, μ
est minimisée en un seul point, comme c’est le cas lorsque f est
strictement convexe par exemple, ce point est automatiquement solution de (P).
Références. Section 4 du chapitre VII de [12].
* Exercice IV.1. Soit l : (x, y) ∈ R n × R m −→ l(x, y) une fonction différentiable
sur R n × R m , X ⊂ R n et Y ⊂ R m deux convexes fermés non vides.
1 ◦ ) – Montrer l’équivalence des deux assertions suivantes :
(i) l est convexe-concave sur X × Y ;
(ii)
⎧
⎪ ⎨
⎪ ⎩
∇ x l(x 1 , y 1 ) − ∇ x l(x 2 , y 2 ), x 1 − x 2
∇ y l(x 1 , y 1 ) − ∇ y l(x 2 , y 2 ), y 1 − y 2
pour tout (x 1 , y 1 ) et (x 2 , y 2 ) dans X × Y.
(1) D’autres appellations sont parfois utilisées ; ainsi entendre parler de fossé de dualité avec
l’accent québécois est charmant...
130
Le calcul explicite de ϕ (x) est aisé : ϕ (x) = f (x) si x ∈ C, +∞ sinon.
Donc, notre premier problème de mini-maximisation est celui de la minimisation sur C de f (x), c’est-à-dire ni plus ni moins que le problème (P) originel.
Regardons maintenant ce qu’est le second problème de mini-maximisation. Il faut
considérer
(λ, μ) ∈ R
m
×
R
+
p −→ ψ (λ, μ) := inf
x∈R n
L (x, λ, μ) .
La fonction ψ est concave et semi-continue supérieurement (finie sur une partie
convexe de R m × (R + )
p ). On appelle problème dual de (P), et on le notera (D),
le problème de la maximisation de ψ sur R m × (R + )
p . Cette fonction duale est
également notée Θ parfois. Si f et ψ désignent les valeurs optimales dans (P ) et
(D) respectivement, on a toujours f ψ (la différence f − ψ s’appelle le saut de
dualité (1) ).
Si (P) est un problème de minimisation convexe, avec un ensemble S ( = ∅)
de solutions et un ensemble M ( = ∅) de multiplicateurs de Lagrange, on a :
f = ψ et les solutions du problème dual (D) sont exactement les multiplicateurs
de Lagrange du problème (P).
Si on a accès à un
λ, μ
∈ M , comment en déduit-on les solutions de (P) ?
Réponse : Ce sont les x qui
– minimisent L
·, λ, μ
sur R n ;
– sont dans C et vérifient μ j g j (x) = 0 pour tout j = 1, . . . , p.
Si L
·, λ, μ
est minimisée en un seul point, comme c’est le cas lorsque f est
strictement convexe par exemple, ce point est automatiquement solution de (P).
Références. Section 4 du chapitre VII de [12].
* Exercice IV.1. Soit l : (x, y) ∈ R n × R m −→ l(x, y) une fonction différentiable
sur R n × R m , X ⊂ R n et Y ⊂ R m deux convexes fermés non vides.
1 ◦ ) – Montrer l’équivalence des deux assertions suivantes :
(i) l est convexe-concave sur X × Y ;
(ii)
⎧
⎪ ⎨
⎪ ⎩
∇ x l(x 1 , y 1 ) − ∇ x l(x 2 , y 2 ), x 1 − x 2
∇ y l(x 1 , y 1 ) − ∇ y l(x 2 , y 2 ), y 1 − y 2
pour tout (x 1 , y 1 ) et (x 2 , y 2 ) dans X × Y.
(1) D’autres appellations sont parfois utilisées ; ainsi entendre parler de fossé de dualité avec
l’accent québécois est charmant...
130