Les coupes des spectraèdres

Piste rouge Le 28 décembre 2010  - Ecrit par  Didier Henrion Voir les commentaires (7)

Les spectraèdres sont des objets à la géométrie complexe, une généralisation des polyèdres dont les arêtes et les faces peuvent être incurvées. On peut visualiser les spectraèdres à condition de les découper en tranches, et c’est l’objet de cet article.

Un cône familier

Prenons un cornet de glace :

et mangeons la crème glacée.
Que reste-t-il ? Un cône, que voici, un peu aseptisé et
la tête en bas :

Maintenant coupons ce cône d’un geste vif mais précis :

Ah il y a encore de la glace à l’intérieur... posons une fine
plaque de verre sur le cône coupé :

retirons la plaque du cône, et regardons-la par dessus. Que voit-on ?
Un beau disque rouge :

Et si nous avions coupé le cône original, mais de manière oblique ?
Voici ce que l’on pourrait obtenir :

La zone rouge sur la plaque, que l’on va appeler une coupe, a maintenant
une forme différente :

c’est une ellipse.
Si on coupe le cône verticalement, on obtient une hyperbole à
une branche :

Et si l’incision suit l’inclinaison du cône, on obtient
une parabole :

Nous obtenons ainsi la fameuse famille
des coniques déjà bien étudiées pendant l’Antiquité,
et mentionnées par exemple au début de cet article.

Un cône plus compliqué

Il existe cependant d’autres cônes que notre cornet glacé, aux géométries
plus complexes, mais également plus intéressantes. Ces cônes sont difficiles à visualiser car ils vivent dans des espaces de grande dimension. Ci-dessus nous avons observé le cône du cornet glacé, un objet vivant dans un espace tri-dimensionnel, à l’aide de coupes planes, c’est-à-dire bi-dimensionnelles. Pour ces notions de dimensions, on pourra consulter ce
film.

Ci-dessous nous allons observer les coupes tri-dimensionnelles d’un cône
bien particulier, le cône semi-défini. Une coupe du cône semi-défini s’appelle un spectraèdre. Cette terminologie sera motivée
par la suite.

L’équation quadratique et son spectraèdre

Pour se familiariser avec les spectraèdres, démarrons avec l’équation
quadratique

$ax^2+bx+c=0$.

Le mathématicien Laurent Schwartz mentionne dans son autobiographie [1] que pendant son enfance, son père — dont les souvenirs de mathématiques n’étaient guère brillants — lui dit un jour « tu apprendras plus tard que $ax^2+bx+c$ est toujours égal à zéro ». Pour le contredire, essayons de trouver les conditions que doivent satisfaire les nombres réels $a$, $b$ et $c$ pour que l’inégalité quadratique

$ax^2+bx+c \geq 0$

soit vérifiée pour tout nombre réel $x$. Tout d’abord remarquons que $a\geq 0$ puisque notre inégalité doit rester valable quand $x$ est très grand. Ensuite remarquons que les solutions réelles de l’équation $ax^2+bx+c=0$ sont bien connues des lycéens, à savoir les racines $(-b\pm\sqrt{\Delta})/2a$ pour autant que le discriminant $\Delta=b^2-4ac$ soit positif. Si le discriminant est nul ou négatif, c’est-à-dire si $4ac-b^2\geq 0$, alors il n’y a pas de racines réelles distinctes, et le terme $ax^2+bx+c$ ne peut pas changer de signe, donc notre inégalité est satisfaite. Dans l’espace de coordonnées $a$,$b$,$c$ la région délimitée
par les inégalités

$a \geq 0, \quad 4ac-b^2 \geq 0$

est un ensemble qui n’est pas borné, le voici :

Le lecteur attentif aura sans doute remarqué que cet ensemble
ressemble étrangement au cône du cornet de glace ci-dessus
(avec d’autres couleurs). En fait
il s’agit du même ensemble, à la différence près que le
cornet est borné. Voici l’ensemble non-borné sous un autre
angle :

On peut multiplier un point de coordonnées $a$,$b$,$c$ dans l’ensemble par n’importe quel réel positif $k$, et le point résultant de coordonnées $ka$, $kb$, $kc$ appartient également à l’ensemble, cela montre bien que l’ensemble n’est pas borné.
C’est d’ailleurs la définition d’un cône : un
ensemble invariant par multiplication par un scalaire positif.
L’ensemble que nous avons obtenu est le cône quadratique,
l’un des plus simples des spectraèdres.

Convexité du spectraèdre

Une autre propriété intéressante de l’ensemble obtenu est sa
convexité, c’est-à-dire la propriété de contenir tout segment reliant deux de ses points. Voir par exemple cet article pour une étude de la convexité du logo du CNRS.

Voici comment prouver la convexité de notre spectraèdre.

Soient $a_1$, $b_1$, $c_1$
les coordonnées d’un premier point du spectraèdre, donc telles que

$a_1 x^2 + b_1 x + c_1 \geq 0$

pour tout réel $x$, et soient $a_2$,$b_2$,$c_2$
les coordonnées d’un second point du spectraèdre, donc telles que

$a_2 x^2 + b_2 x + c_2 \geq 0$

pour tout réel $x$. Les points du segment reliant ces deux points ont pour coordonnées $(ka_1+(1-k)a_2)$, $(kb_1+(1-k)b_2)$,
$(kc_1+(1-k)c_2)$ où $k$ est un réel compris entre 0 et 1, et donc en utilisant les deux inégalités ci-dessus, nous obtenons

$k a_1 x^2 + k b_1 x + k c_1 \geq 0$

et

$(1-k) a_2 x^2 + (1-k) b_2 x + (1-k) c_2 \geq 0$

que l’on combine pour obtenir finalement

$(k a_1 + (1-k) a_2) x^2 + (k b_1 + (1-k) b_2) x + (k c_1 + (1-k) c_2) \geq 0$

pour tout réel $x$ et tout réel $k$ entre 0 et 1, ce qui prouve que le segment entier est inclus dans le spectraèdre, qui est donc convexe.

Une coupe déjà rencontrée

Dans l’espace de coordonnées $a$, $b$, $c$,
notre spectraèdre est un objet tri-dimensionnel
décrit par les deux inégalités $a \geq 0$
et $4ac - b^2 \geq 0$.
En posant par exemple $a=1$ nous obtenons, dans le plan
de coordonnées $b$, $c$ un objet bi-dimensionnel
qui est décrit par l’inégalité $4c-b^2 \geq 0$.
Cela revient à couper le spectraèdre par le plan $a=1$ :

et la région rouge ainsi délimitée est une parabole
de la même famille que celle obtenue auparavant
avec notre cornet glacé. C’est également un
spectraèdre, mais cette fois-ci il est planaire.
Par ailleurs on peut montrer facilement que les sections
coniques mentionnées auparavant sont toutes des spectraèdres.

Le spectraèdre de Cayley

Maintenant essayons de généraliser et considérons l’inégalité
quadratique

$ax^2+bx+c+dy+exy+fy^2 \geq 0$

où nous avons maintenant deux variables $x$ et $y$.
Quelle est la géométrie de l’ensemble $K$ des coefficients réels $a$, $b$, $c$, $d$, $e$, $f$ tels que cette inégalité soit satisfaite pour tous réels $x$ et $y$ ?

Il est bien difficile de représenter l’ensemble $K$ car il vit dans
un espace à six dimensions ! Ce que l’on peut faire, comme
auparavant, c’est fixer certains
coefficients pour diminuer le nombre de degrés de liberté.
Par exemple en posant $a=c=f=1$ on ne garde que les trois
coefficients $b$, $d$, $e$. C’est ce que l’on appelle une
section ou coupe affine, et géométriquement cela revient
effectivement à couper l’ensemble $K$, tout comme nous
avons initialement coupé le cornet glacé.
Voici ce que l’on obtient dans l’espace $b$, $d$, $e$ quand
on coupe $K$ par les trois plans $a=1$, $c=1$, $f=1$ :

Cet ensemble, que l’on peut dénommer le spectraèdre
de Cayley, ressemble à un tétraèdre régulier :

l’un des cinq solides de Platon. En effet, il a les mêmes
quatre sommets, mais ses six arêtes ne sont pas
saillantes, et ses quatre faces sont bombées.
C’est comme si on avait gonflé le tétraèdre régulier
pour obtenir le spectraèdre de Cayley.

JPEG - 15.2 ko
Arthur Cayley (1821-1895)

Arthur Cayley était un mathématicien britannique
du XIXème siècle. Il a étudié le spectraèdre
ci-dessus en travaillant sur les surfaces cubiques
aux alentours de 1850. En effet, ce spectraèdre est la composante
connexe convexe de la surface cubique dite de Cayley.
On trouvera cette surface, ainsi que plein d’autres,
sur divers sites dédiés aux surfaces cubiques, comme
celui-ci ou encore celui-là.

Pour les curieux, dans l’espace des paramètres
$b$,$d$,$e$ définis ci-dessus, le spectraèdre de Cayley
est défini par les deux inégalités suivantes

$4+bde \geq b^2+d^2+e^2, \quad 12 \geq b^2+d^2+e^2$.

D’autres spectraèdres

On peut encore généraliser en considérant des inégalités quadratiques
à trois, quatre, cinq variables, ou plus. L’ensemble des polynômes
quadratiques qui restent partout positifs définit ainsi un cône
semi-défini, dont toute coupe est un spectraèdre. Inversément,
chaque point du spectraèdre correspond à un polynôme. On appelle
le degré du spectraèdre le nombre de variables de ces polynômes
quadratiques. On peut ainsi générer plein de spectraèdres, dont voici quelques coupes tri-dimensionnelles :

JPEG - 6.6 ko
Coupe d’un spectraèdre de degré quatre
JPEG - 6.7 ko
Coupe d’un spectraèdre de degré quatre
JPEG - 6 ko
Coupe d’un spectraèdre de degré quatre
JPEG - 6.3 ko
Coupe d’un spectraèdre de degré cinq

On remarquera que ces spectraèdres ont tous les mêmes
caractéristiques : convexité, bien sûr, mais également
présence de sommets, que l’on appelle singularités.

Pour résumer, on peut dire que les spectraèdres sont faciles
à visualiser pour autant qu’on les découpe en tranches de
dimension suffisamment faible.
Dans un prochain article on étudiera une autre technique
de visualisation des spectraèdres, qui utilise la notion
géométrique de projection.

Pourquoi le nom spectraèdre ?

Comme mentionné auparavant,
ces objets sont tous des coupes affines du cône semi-défini.
Pour les spécialistes, il s’agit
plus précisément du cône des matrices symétriques à valeurs propres
non-négatives. Cela motive d’ailleurs l’appellation « spectraèdre »,
par analogie avec le terme « polyèdre »,
puisque le spectre d’une matrice est l’ensemble de ses valeurs propres.

A quoi servent les spectraèdres ?

Certains ingénieurs et mathématiciens rencontrent de tels spectraèdres
quand ils étudient des problèmes de commande des systèmes (par exemple
comment assurer que le lanceur Ariane 5 suive bien sa trajectoire atmosphérique
même en présence de rafales de vent) ou alors d’optimisation de structures
(pour concevoir les pièces d’une construction, pour assurer qu’un pont soit suffisamment solide, voir aussi ces travaux qui n’utilisent cependant pas les spectraèdres mais d’autres techniques mathématiques).

Les spectraèdres correspondants sont de dimensions allant de la dizaine au millier,
et il est bien sûr vain de vouloir les visualiser, le nombre de coupes
de faible dimension étant trop important. Il est cependant
important de pouvoir les manipuler efficacement, et c’est l’objet
de la programmation semi-définie et des inégalités matricielles
linéaires (LMI)
, une branche moderne de
l’optimisation qui permet aux ingénieurs de résoudre sur leurs
ordinateurs divers problèmes de conception.

Par exemple, la programmation semi-définie a permis de réduire
de 15% à 20% le poids d’une partie de la voilure de l’Airbus A380 [2].

Post-scriptum :

La rédaction d’Images des maths, ainsi que l’auteur, remercient pour leur relecture attentive,
les relecteurs dont le pseudonyme est le suivant : Safi, François Guéritaud et Thibault de France.

Notes

[1L. Schwartz. Un mathématicien aux prises avec le siècle.
Odile Jacob, Paris, 1997.

[2M. Kocvara. Semidefinite problems in structural optimization and their
solution by PENNON. Workshop on semidefinite programming and robust optimization, Institute of Mathematics and its Applications, University of
Minnesota, Minneapolis, Mars 2003

Partager cet article

Pour citer cet article :

Didier Henrion — «Les coupes des spectraèdres» — Images des Mathématiques, CNRS, 2010

Commentaire sur l'article

  • Les coupes des spectraèdres

    le 28 décembre 2010 à 13:09, par le_cheveulu

    Sympa d’avoir donné des applications concrètes. Personnellement en dehors de la relativité générale, je ne connaissait d’utilisation des normes semi-définies. Cela me sera utile lors de mes cours pour motiver l’étude de ces objets. Auriez-vous plus de renseignements sur les applications en aéronautique ?

    Répondre à ce message
  • Les coupes des spectraèdres

    le 5 janvier 2011 à 17:52, par Didier Henrion

    > Sympa d’avoir donné des applications concrètes [...]
    > Auriez-vous plus de renseignements sur les applications
    > en aéronautique ?

    Bonjour

    Merci pour l’interet porte a cet article. Au sujet de la
    programmation semidefinie (donc l’optimisation sur les
    spectraedres), je peux vous recommander le livre

    Aharon Ben-Tal, Arkadi Nemirovski. Lectures on Modern
    Convex Optimization : Analysis, Algorithms, and
    Engineering Applications. MPS-SIAM Series on
    Optimization, SIAM, Philadelphia, PA, 2001

    qui s’adresse essentiellement aux ingenieurs (pas
    aux mathematiciens) et qui explique bien en quoi
    la programmation semidefinie est une extension de la
    programmation lineaire et de la programmation quadratique
    convexe. Le livre decrit aussi certains algorithmes de
    programmation semidefinie (methodes de points interieurs)
    et surtout, un certain nombre d’applications :

    • optimisation combinatoire, theorie des graphes
    • analyse de stabilite des equations differentielles
    • conception d’antennes et de reseaux d’antennes
    • conception de circuits electroniques
    • conception de structures mecaniques

    Pour plus d’informations sur l’application Airbus A380
    mentionnee dans l’article, voir la page de mon
    collegue Michal Kocvara a Birmingham :

    http://web.mat.bham.ac.uk/kocvara/pennon/eads_problems.html

    Mes collegues du LAAS ont egalement utilise la
    programmation semidefinie dans le cadre d’un projet
    sur le pilotage du lanceur Ariane 5+ :

    Denis Arzelier, Benoit Clement, Dimitri Peaucelle.
    Multi-objective H2/Hinf/impulse-to-peak control of
    a space launch vehicle. European Journal of Control,
    12(1):57-70, 2006.

    Voila j’espere que cela vous sera utile.
    Cordialement,

    Didier Henrion.

    Répondre à ce message
  • Les coupes des spectraèdres

    le 21 février 2011 à 14:29, par Caocoa

    Bonjour,
    Vous parlez dans cet article de cône semi-défini. Wikipédia m’explique que le terme « défini » a sans doute le même sens que pour la définition du produit scalaire par exemple. Problème : je ne vois pas du tout quelle peut être la propriété de « semi-définition » d’un cône…
    Merci pour cet article intéressant que je trouve original !

    Répondre à ce message
  • Les coupes des spectraèdres

    le 21 février 2011 à 14:38, par Didier Henrion

    > je ne vois pas du tout quelle peut être la propriété de
    > « semi-définition » d’un cône…

    Bonjour

    Oui la terminologie que j’utilise est surement un
    abus de langage..

    le nom « officiel » est "cone
    des matrices symetriques semi-definies positives"
    cf. par exemple la section 5.3 dans
    http://fr.wikipedia.org/wiki/Matrice_positive
    mais personnellement je trouve ce nom un
    peu long, donc j’utilise le raccourci
    « cone semi-defini »

    Pour la notion de matrice (semi-)definie positive, voir
    http://fr.wikipedia.org/wiki/Matrice_d%C3%A9finie_positive
    et noter en particulier le lien avec les formes quadratiques
    (semi-)definies positives.

    Cordialement,
    Didier.

    Répondre à ce message
  • Les coupes des spectraèdres

    le 21 février 2011 à 14:51, par Caocoa

    Merci beaucoup de vos explications presque « en direct » !
    Un peu plus loin vous dites : « dans l’espace des paramètres b,d,e définis ci-dessus, le spectraèdre de Cayley est défini par les deux inégalités suivantes » puis vous montrez deux belles inégalités. Je vois comment trouver ces inégalités quand il s’agit d’un cône « simple » mais j’aimerai comprendre comment s’y prendre avec le spectraèdre de Cayley.

    Bonne fin de journée,
    Caocoa

    Répondre à ce message
  • Les coupes des spectraèdres

    le 21 février 2011 à 15:12, par Didier Henrion

    > Un peu plus loin vous dites : « dans l’espace des
    > paramètres b,d,e définis ci-dessus, le spectraèdre de
    > Cayley est défini par les deux inégalités suivantes » puis
    > vous montrez deux belles inégalités. Je vois comment
    > trouver ces inégalités quand il s’agit d’un cône « simple » > mais j’aimerai comprendre comment s’y prendre avec le
    > spectraèdre de Cayley.

    Re-bonjour

    oui ce n’est pas complement evident, c’est vrai ;
    il faut ecrire le polynome quadratique
    de la maniere suivante
    ax^2+bx+c+dy+exy+fy^2 =
    [1 x y][c b/2 d/2 ; b/2 a e/2 ; d/2 e/2 f][1 ;x ;y]
    ou j’utilise le point virgule pour aller
    a la ligne dans un vecteur ou une matrice.
    Rappelons qu’on impose a = c = f = 1 pour avoir
    une coupe tri-dimensionnelle.
    Le polynome est semi-defini positif quand
    la matrice symmetrique 3x3 qui le forme
    est semi-definie positive. Cela revient a
    dire que la matrice A = [2 b d ; b 2 e ; d e 2]
    a toutes ses valeurs propres non-negatives
    (celles-ci sont reelles car la matrice est
    symetrique).

    Ensuite on ecrit le polynome caracteristique
    det(tI+A) ou I est la matrice identite, c’est-a-dire
    det([t+2 b d ; b t+2 e ; d e t+2]) =
    t^3+6t^2+(12-b^2-d^2-e^2)t+2(4+bdc-(b^2+d^2+e^2))
    Les coefficients en « t » de ce polynome sont les
    fonctions symmetriques elementaires des
    valeurs propres de A. Ils sont non-negatifs
    si et seulement si la matrice A est semi-definie
    positive. Les deux inegalites en decoulent.

    Cordialement,
    Didier.

    Répondre à ce message
  • Les coupes des spectraèdres

    le 21 février 2011 à 15:24, par Caocoa

    Merci de ces précisions !
    L’équivalence « Les coefficients en t de ce polynôme sont non-négatifs si et seulement si la matrice A est semi-définie positive » s’avère bien utile !

    Bonne fin de journée.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM