Point col

En mathématiques, un point-selle (en anglais : saddle point) d'une fonction $f$ définie sur un produit cartésien $X \times Y$ de deux ensembles $X$ et $Y$ est un point $({\bar {x}},{\bar {y}})\in X\times Y$ tel que :

$y\mapsto f({\bar {x}},y)$ atteint un maximum en ${\bar {y}}$ sur $Y$ ;
et $x\mapsto f(x,{\bar {y}})$ atteint un minimum en ${\bar {x}}$ sur $X$ .

Sur le graphe de la fonction

(x,y)\mapsto x^{2}-y^{2}

, le point en rouge

(0;0;0)

est associé à l'unique point-selle

(0;0)

de cette fonction.

Certains auteurs inversent les maximum et minimum ( $f({\bar {x}},\cdot )$ a un minimum en ${\bar {y}}$ et $f(\cdot ,{\bar {y}})$ a un maximum en ${\bar {x}}$ ), mais cela ne modifie pas qualitativement les résultats (on peut revenir au cas présent par un changement de variables).

Le terme point-selle fait référence à la forme de selle de cheval que prend le graphe de la fonction lorsque $X$ et $Y$ sont des intervalles de $\mathbb {R}$ . On utilise aussi l'appellation point col, en renvoyant alors à l'image du col de montagne.

La notion de point-selle intervient :

en optimisation, comme concept permettant d'énoncer des conditions assurant l'existence de solution primale-duale ;
en théorie des jeux ;
pour déterminer des solutions particulières de certaines équations qui ne sont pas des minima ou des maxima de fonctionnelle d'énergie.

Définition

Voici une définition assez générale de la notion de point-selle d'une fonction définie sur un produit cartésien d'ensembles. Aucune structure n'est requise sur ces ensembles. La fonction doit par contre prendre ses valeurs dans l'ensemble des réels $\mathbb {R}$ (ou plus généralement dans la droite réelle achevée ${\bar {\mathbb {R} }}$ ).

Point-selle — Soient $X$ et $Y$ deux ensembles et $f:X\times Y\to {\bar {\mathbb {R} }}$ une fonction pouvant prendre les valeurs $\pm \infty$ . On dit que $({\bar {x}},{\bar {y}})\in X\times Y$ est un point-selle de $f$ sur $X \times Y$ si

$\forall \,(x,y)\in X\times Y:\qquad f({\bar {x}},y)\leqslant f({\bar {x}},{\bar {y}})\leqslant f(x,{\bar {y}}).$

Dans les conditions ci-dessus, $f({\bar {x}},{\bar {y}})$ est appelée la valeur-selle de $f$ .

Autrement dit, $y\mapsto f({\bar {x}},y)$ atteint un maximum en ${\bar {y}}$ sur $Y$ et $x\mapsto f(x,{\bar {y}})$ atteint un minimum en ${\bar {x}}$ sur $X$ . Rien n'est requis en dehors de la croix $(\{{\bar {x}}\}\times Y)\cup (X\times \{{\bar {y}}\})$ , si bien que l'image de la selle ou du col peut être trompeuse comme lorsque $f:\mathbb {R} ^{2}\to \mathbb {R}$ est définie par $f (x, y)= x 2 y 2$ (tous les points de l'axe des ordonnées sont des points-selles).

On pourra souvent se ramener à la définition précédente par un changement de variable. Par exemple, le point $(0,0)\in \mathbb {R} ^{2}$ n'est pas un point-selle de la fonction $(x,y)\in \mathbb {R} ^{2}\mapsto xy+(x^{3}+y^{3})$ , au sens de la définition ci-dessus, mais le devient localement après le changement de variable ${\tilde {x}}=x+y$ et ${\tilde {y}}=x-y$ .

Résultat d'existence

Le résultat d'existence de point-selle ci-dessous[1] rappelle celui de Weierstrass sur l'existence d'un minimiseur de fonction, mais requiert une hypothèse de convexité-concavité de $f$ . Sans cette dernière hypothèse, pas de point-selle garanti comme le montre l'exemple de la fonction

$f(x,y)=x^{2}+y^{2},~~{\mbox{sur}}~[-1,1]\times [-1,1].$

Existence de point-selle — Supposons que $X$ et $Y$ soient des convexes compacts non vides d'espaces vectoriels de dimension finie et que

pour tout $y \in Y$ , $f (•, y)$ est convexe semi-continue inférieurement,
pour tout $x \in X$ , $f (x,•)$ est concave semi-continue supérieurement.

Alors $f$ a un point-selle dans $X \times Y$ .

Ce résultat généralise l'identité de von Neumann qui traite du cas où $f$ est bilinéaire et les ensembles $X$ et $Y$ sont des simplexes de dimension finie.

Propriétés

Le résultat suivant est fondamental dans la théorie de la dualité en optimisation, dans laquelle on définit un problème primal par

$(P)\quad \inf _{x\in X}\,\sup _{y\in Y}\,f(x,y)$

et le problème dual associé par

$(D)\quad \sup _{y\in Y}\,\inf _{x\in X}\,f(x,y).$

On dit alors qu'il n'y a pas de saut de dualité si

$\sup _{y\in Y}\,\inf _{x\in X}\,f(x,y)=\inf _{x\in X}\,\sup _{y\in Y}\,f(x,y),$

l'inégalité ≤ dite de dualité faible étant toujours garantie.

Caractérisation des points-selles — Un couple de points $({\bar {x}},{\bar {y}})\in X\times Y$ est un point-selle de $f$ sur $X \times Y$ si, et seulement si, ${\bar {x}}$ est solution du problème primal $(P)$ , ${\bar {y}}$ est solution du problème dual $(D)$ et il n'y a pas de saut de dualité.

L'ensemble des points-selles d'une fonction $f:X\times Y\to {\bar {\mathbb {R} }}$ a une structure très particulière, comme le montre le résultat suivant : c'est un produit cartésien. On y a noté $Sol(P)$ l'ensemble des solutions du problème primal $(P)$ et $Sol(D)$ l'ensemble des solutions du problème dual $(D)$ .

Produit cartésien des points-selles — Supposons que la fonction $f:X\times Y\to {\bar {\mathbb {R} }}$ ait un point-selle. Alors

l'ensemble des points-selles de $f$ est le produit cartésien $Sol(P) \times Sol(D)$ ,
la fonction $f$ prend une valeur constante sur $Sol(P) \times Sol(D)$ , disons ${\bar {f}}$ ,
on a
${\begin{array}{c}\operatorname {Sol} (P)=\bigcap _{y\in Y}\{x\in X:f(x,y)\leqslant {\bar {f}}\}\\\operatorname {Sol} (D)=\bigcap _{x\in X}\{y\in Y:f(x,y)\geqslant {\bar {f}}\}.\end{array}}$

Point-selle en calcul différentiel

Utilisation de la hessienne

Pour déterminer si un point critique d'une fonction de classe $C 2$ de $n$ variables à valeurs réelles $f (x 1,..., x n)$ est un point-selle on calcule la matrice hessienne en ce point. Si la forme quadratique définie par la hessienne est non dégénérée et de type $(p, q)$ avec $p > 0, q > 0$ (ce qui, pour $n =2$ , revient à dire que le déterminant de la matrice hessienne est strictement négatif), on a un point-selle après changement et regroupement des variables (selon le lemme de Morse).

Par exemple, le gradient et la hessienne de la fonction $f (x, y)= x 2 - y 2$ s'écrivent

$\nabla f(x,y)={\begin{pmatrix}2x\\-2y\end{pmatrix}}\qquad {\mbox{et}}\qquad \nabla ^{2}f(x,y)={\begin{pmatrix}2&0\\0&-2\end{pmatrix}}.$

Le gradient est donc nul en $(0;0)$ (c'est un point critique) et la hessienne a une valeur propre strictement positive (2) et une valeur propre strictement négative (-2). Par conséquent, $(0;0)$ est un point-selle.

Ce critère ne donne pas de condition nécessaire : pour la fonction $(x,y)\mapsto f(x,y)=x^{4}-y^{4}$ , le point $(0;0)$ est un point-selle mais la hessienne en ce point est la matrice nulle. Donc la hessienne n'a pas de valeur propre strictement positive et négative.

Annexes

Note

Voir Maurice Sion (1958) et le théorème 1.1 chez Brezis (1973).

Articles connexes

Bibliographie

H. Brézis (1973), Opérateurs Maximaux Monotones et semi-groupes de contractions dans les espaces de Hilbert. Mathematics Studies 5. North-Holland, Amsterdam. (ISBN 978-0-7204-2705-9).
(en) M. Sion (1958), « On general minimax theorems », Pacific Journal of Mathematics 8, 171-176.

Portail de l'analyse

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Voir Maurice Sion (1958) et le théorème 1.1 chez Brezis (1973).