130
CHAPITRE 5 DUALISATION, CAS NON CONVEXES
homogènes.
Si on s’en tient au cône convexe ouvert S ++
n (R) := {A ∈ S n (R) | A 0},
la fonction "conditionnement" c de A
c(A) :=
λ 1 (A)
λ n (A)
est d.c. sur S ++
n (R).
Propriété : DC(E) est stable par les propriétés usuelles de l’Analyse telles
que : addition, soustraction, multiplication, maximum d’un nombre fini de
fonctions, etc. Dans ces cas, disposer de décompositions d.c. des fonctions
composantes dans l’opération conduit à une décomposition d.c., une du
moins, de la fonction résultante.
Exemple (important) : Maximisation convexe sur un convexe
Considérons le problème d’optimisation suivant :
(P)
Maximiser h(x)
x ∈ C,
où h : E → R est une fonction convexe continue sur E et C est un
convexe fermé de E. Ce modèle de problèmes d’optimisation "terriblement"
non convexes est difficile à traiter. Penser pour s’en convaincre au cas
où f (x) = =Ax, x est une fonction quadratique convexe sur R n et C =
[−1, +1] n .
On peut reformuler (P) au-dessus en un format d.c.. En effet, (P) est équivalent à
Minimiser f (x) := i C (x) − h(x)
x ∈ E.
Le problème (P) est non convexe mais il a de la structure : la convexité est
présente deux fois (via g et h), même si une fois elle est dans le mauvais sens
(à rebours si on veut). La manière d’associer un problème "dual" ou "adjoint"
à (P) va tenir compte de cette structure ; elle sera construite non pas à partir
de f mais bien à partir de f décomposée en f = g −h (avec g et h convexes).
Plusieurs mathématiciens ont contribué à la dualisation des problèmes d.c.,
mais le grand bonhomme dans cette affaire est J. Toland. Voici sa définition :
(P
)
Minimiser f (x ∗ ) := h ∗ (x ∗ ) − g ∗ (x ∗ )
x ∗ ∈ E ∗ .
C’est à nouveau un problème d.c., et (P ) = (P). Comme cela a déjà
été dit, f n’est pas associée à f mais bien à f = g − h. Ceci peut être
CHAPITRE 5 DUALISATION, CAS NON CONVEXES
homogènes.
Si on s’en tient au cône convexe ouvert S ++
n (R) := {A ∈ S n (R) | A 0},
la fonction "conditionnement" c de A
c(A) :=
λ 1 (A)
λ n (A)
est d.c. sur S ++
n (R).
Propriété : DC(E) est stable par les propriétés usuelles de l’Analyse telles
que : addition, soustraction, multiplication, maximum d’un nombre fini de
fonctions, etc. Dans ces cas, disposer de décompositions d.c. des fonctions
composantes dans l’opération conduit à une décomposition d.c., une du
moins, de la fonction résultante.
Exemple (important) : Maximisation convexe sur un convexe
Considérons le problème d’optimisation suivant :
(P)
Maximiser h(x)
x ∈ C,
où h : E → R est une fonction convexe continue sur E et C est un
convexe fermé de E. Ce modèle de problèmes d’optimisation "terriblement"
non convexes est difficile à traiter. Penser pour s’en convaincre au cas
où f (x) = =Ax, x est une fonction quadratique convexe sur R n et C =
[−1, +1] n .
On peut reformuler (P) au-dessus en un format d.c.. En effet, (P) est équivalent à
Minimiser f (x) := i C (x) − h(x)
x ∈ E.
Le problème (P) est non convexe mais il a de la structure : la convexité est
présente deux fois (via g et h), même si une fois elle est dans le mauvais sens
(à rebours si on veut). La manière d’associer un problème "dual" ou "adjoint"
à (P) va tenir compte de cette structure ; elle sera construite non pas à partir
de f mais bien à partir de f décomposée en f = g −h (avec g et h convexes).
Plusieurs mathématiciens ont contribué à la dualisation des problèmes d.c.,
mais le grand bonhomme dans cette affaire est J. Toland. Voici sa définition :
(P
)
Minimiser f (x ∗ ) := h ∗ (x ∗ ) − g ∗ (x ∗ )
x ∗ ∈ E ∗ .
C’est à nouveau un problème d.c., et (P ) = (P). Comme cela a déjà
été dit, f n’est pas associée à f mais bien à f = g − h. Ceci peut être