III.4. Conditions de minimalité du second ordre
Commentaire :
– La relation
A
−1 =
m
i=1
μ i a i a
i , alliée à
m
i=1
μ i = n, indique que
A
−1 /n est
une combinaison convexe de matrices symétriques semi-définies positives de rang
1 construites à partir des vecteurs a i normaux aux facettes de P . Elle traduit une
« tangence simultanée » de l’ellipsoïde optimal E à certaines facettes de P , ce que
l’intuition de la géométrie du problème laissait supposer.
– La constante
√
n obtenue dans l’encadrement de f est indépendante de P ,
notamment du nombre m de doubles inégalités le décrivant. Un exemple simple
dans R 2 , en considérant un carré P et donc une boule fermée pour E, montre que
cette constante ne peut être améliorée.
– Le centre des ellipsoïdes-candidats E avait été fixé à l’origine, mais on peut
aisément imaginer que s’il avait été libre (c’est-à-dire un paramètre additionnel
dans le problème), la symétrie de P aurait de toute façon conduit à un E optimal
centré à l’origine.
*** Exercice III.22. Soit P un polyèdre convexe fermé de R n décrit de la manière
suivante
P := {x ∈ R
n
| |a i , x b i pour tout i = 1, . . . , m}
où les a i sont des vecteurs de R n et les b i des réels.
On suppose que P est borné et d’intérieur non vide.
Soit E un ellipsoïde plein de R n décrit de la manière suivante
E := c + {Bu | | u 1} ,
(3.13)
où c ∈ R n et B ∈ S n (R) est définie positive. E est ainsi centré en c et de volume
proportionnel à dét B.
On considère le problème qui consiste à chercher l’ (ou les) ellipsoïde(s) E
contenu(s) dans P de volume maximal.
1 ◦ ) Décrire l’inclusion E ⊂ P sous la forme d’une conjonction d’inégalités
g i (c, B) 0 pour tout i = 1, . . . , m
où les g i sont des fonctions convexes de (c, B) ∈ R n × S n (R) .
2 ◦ ) Formaliser le problème de la recherche d’un ellipsoïde E contenu dans P
de volume maximal comme un problème de minimisation convexe.
99
Commentaire :
– La relation
A
−1 =
m
i=1
μ i a i a
i , alliée à
m
i=1
μ i = n, indique que
A
−1 /n est
une combinaison convexe de matrices symétriques semi-définies positives de rang
1 construites à partir des vecteurs a i normaux aux facettes de P . Elle traduit une
« tangence simultanée » de l’ellipsoïde optimal E à certaines facettes de P , ce que
l’intuition de la géométrie du problème laissait supposer.
– La constante
√
n obtenue dans l’encadrement de f est indépendante de P ,
notamment du nombre m de doubles inégalités le décrivant. Un exemple simple
dans R 2 , en considérant un carré P et donc une boule fermée pour E, montre que
cette constante ne peut être améliorée.
– Le centre des ellipsoïdes-candidats E avait été fixé à l’origine, mais on peut
aisément imaginer que s’il avait été libre (c’est-à-dire un paramètre additionnel
dans le problème), la symétrie de P aurait de toute façon conduit à un E optimal
centré à l’origine.
*** Exercice III.22. Soit P un polyèdre convexe fermé de R n décrit de la manière
suivante
P := {x ∈ R
n
| |a i , x b i pour tout i = 1, . . . , m}
où les a i sont des vecteurs de R n et les b i des réels.
On suppose que P est borné et d’intérieur non vide.
Soit E un ellipsoïde plein de R n décrit de la manière suivante
E := c + {Bu | | u 1} ,
(3.13)
où c ∈ R n et B ∈ S n (R) est définie positive. E est ainsi centré en c et de volume
proportionnel à dét B.
On considère le problème qui consiste à chercher l’ (ou les) ellipsoïde(s) E
contenu(s) dans P de volume maximal.
1 ◦ ) Décrire l’inclusion E ⊂ P sous la forme d’une conjonction d’inégalités
g i (c, B) 0 pour tout i = 1, . . . , m
où les g i sont des fonctions convexes de (c, B) ∈ R n × S n (R) .
2 ◦ ) Formaliser le problème de la recherche d’un ellipsoïde E contenu dans P
de volume maximal comme un problème de minimisation convexe.
99