Chapitre IV. Mini-maximisation. Dualisation de problèmes...
– Y est borné, ou bien il existe x 0 ∈ X tel que l(x 0 , y) → −∞ quand y →
+∞, y ∈ Y ;
alors l’ensemble des points-selles de l sur X × Y est un convexe compact non
vide de X × Y.
Posons à présent
ϕ : x ∈ X −→ ϕ(x) := sup
y∈Y
l(x, y) (à valeurs + ∞ éventuellement),
ψ : y ∈ Y −→ ψ(y) := inf
x∈X
l(x, y) (à valeurs − ∞ éventuellement).
Les définitions mêmes d’inf et de sup font que l’on a toujours les inégalités :
ψ(y) l(x, y) ϕ(x) pour tout (x, y) ∈ X × Y . Et (x, y) est un point-selle de
l sur X × Y si et seulement si ψ(y) ϕ(x) ; dans ce cas ψ(y) = ϕ(x) est la
valeur-selle de l sur X × Y.
Il est naturel d’associer à l les deux problèmes d’optimisation suivants :
(1)
⎧
⎨
⎩
Minimiser
sup
y∈Y
l(x, y)
(problème de « minimisation de sup »)
pour x ∈ X;
(2)
⎧
⎨
⎩
Maximiser
inf
x∈X
l(x, y)
(problème de « maximisation d’inf »)
pour y ∈ Y.
Alors, une condition nécessaire et suffisante pour que l ait des points-selles sur
X × Y est
min
x∈X
ϕ(x) = max
y∈Y
ψ(y)
(i.e. optima égaux et atteints).
Dans ce cas, (x, y) est un point-selle exactement lorsque x minimise ϕ sur X et y
maximise ψ sur Y.
IV.2. Points-selles de lagrangiens
Considérons le problème (basique) de la minimisation d’une fonction-objectif
sous des contraintes exprimées par des égalités et des inégalités :
(P)
⎧
⎪ ⎨
⎪ ⎩
Minimiser f (x)
h i (x) = 0 pour i = 1, . . . , m et
g j (x) 0 pour j = 1, . . . , p (x ∈ C en bref).
128