Point col

En mathématiques, un point col ou 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$ .

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}$ . Le terme de point col, renvoie, quant à lui, à l'image du col de montagne. Dans (au moins) une direction, le point-col est un point de maximum (pour passer d'une vallée à l'autre) et dans (au moins) une autre direction, c'est un point de minimum (pour passer d'une montagne à l'autre).

La notion de point col ou 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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

Utilisation de la hessienne[modifier | modifier le code]

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[modifier | modifier le code]

Note[modifier | modifier le code]

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

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

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

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

[1]