Conditions d'optimalité

Soit ${\displaystyle \mathbb {E} }$ un espace vectoriel sur ${\displaystyle \mathbb {R} }$ de dimension finie, qui désigne l'ensemble auquel appartiennent les paramètres que l'on cherche à optimiser. Étant de dimension finie, il n'y a pas de restriction à supposer que cet espace vectoriel est muni d'un produit scalaire, noté ${\displaystyle \langle \cdot ,\cdot \rangle }$, qui en fait un espace euclidien. La norme associée à ce produit scalaire est notée ${\displaystyle \|\cdot \|}$. Le problème d'optimisation considéré s'exprime mathématiquement comme celui qui consiste à minimiser une fonction ${\displaystyle f:\mathbb {E} \to \mathbb {R} }$ sur une partie ${\displaystyle X}$ de ${\displaystyle \mathbb {E} }$. La fonction ${\displaystyle f}$ a de nombreuses appellations, ce qui permet de varier le vocabulaire : fonction-coût, coût, fonction-objectif, objectif, critère, etc. L'ensemble ${\displaystyle X}$ est appelé l'ensemble admissible du problème et un point lui appartenant est appelé point admissible. Ce problème, désigné ci-après ${\displaystyle (P_{X})}$, s'écrit au choix comme suit :

Une solution ou minimum ou minimiseur de ce problème est un point ${\displaystyle x_{*}}$ de l'espace vectoriel ${\displaystyle \mathbb {E} }$ vérifiant deux conditions : il doit être admissible et minimiser le critère sur l'ensemble admissible. Ceci s'écrit

On adjoint souvent le qualificatif global à cette notion de solution pour la distinguer d'autres notions présentées ci-dessous. Signalons également que l'on remplace parfois ‘‘${\displaystyle \inf }$’’ par ‘‘${\displaystyle \min }$’’ dans l'écriture du problème d'optimisation ${\displaystyle (P_{X})}$ lorsqu'il est certain que ce problème a une solution.

Dans certaines sous-disciplines de l'optimisation, on utilise parfois la locution malheureuse solution optimale qui, avec le sens de solution donné ci-dessus, est un pléonasme (dans cette locution, le mot solution signifie en réalité point admissible, mais il nous semble préférable de laisser au mot solution son sens habituel de solution d'un problème).

On introduit aussi d'autres notions de solutions. Ainsi on dit que ${\displaystyle x_{*}}$ est une solution locale ou minimum local ou minimiseur local du problème ${\displaystyle (P_{X})}$ s'il existe un voisinage ${\displaystyle V}$ de ${\displaystyle x_{*}}$ tel que ${\displaystyle x_{*}}$ minimise ${\displaystyle f}$ sur ${\displaystyle X\cap V}$. Par ailleurs, on dit que ${\displaystyle x_{*}}$ est une solution stricte [resp. une solution locale stricte] si ${\displaystyle x_{*}}$ est admissible et si ${\displaystyle f(x_{*})<f(x)}$ (inégalité stricte) pour tout ${\displaystyle x\in X}$ différent de ${\displaystyle x_{*}}$ [resp. pour tout ${\displaystyle x\in X\cap V}$ différent de ${\displaystyle x_{*}}$ où ${\displaystyle V}$ est un voisinage de ${\displaystyle x_{*}}$].

Lorsqu'une fonction atteint un minimum en un point, elle varie peu dans le voisinage de ce point. Mathématiquement, cette observation se traduit par le fait que sa dérivée y est nulle. Ceci est une condition d'optimalité du premier ordre bien connue pour un problème sans contrainte (ces conditions sont présentées à la section problèmes sans contrainte ci-dessous). Si l'on veut établir une expression similaire dans le cas des problèmes avec contrainte, il est nécessaire de dire ce qu'est l'approximation au premier ordre de l'ensemble admissible en un point, de linéariser cet ensemble en ce point, comme on peut le faire pour la fonction-coût. Ceci conduit à la notion de cône tangent, développée dans un autre article.

Rappelons quand même ici qu'une partie ${\displaystyle K}$ de ${\displaystyle \mathbb {E} }$ (un espace vectoriel suffit pour cette notion) est un cône si ${\displaystyle \mathbb {R} _{++}K\subset K}$, ce qui signifie que ${\displaystyle td}$ doit appartenir à ${\displaystyle K}$ chaque fois que ${\displaystyle t}$ est un réel strictement positif (i.e., ${\displaystyle t>0}$) et ${\displaystyle d\in K}$. Un cône n'est pas un objet de l'algèbre linéaire, mais de l'analyse convexe. On rencontre donc ici une première manifestation de l'importance de cette dernière théorie en optimisation.

Nous utiliserons ici la notion de cône tangent au sens de Bouligand[1], qui suffit en dimension finie. Précisons que ce cône tangent à ${\displaystyle X}$ en ${\displaystyle x}$, noté ${\displaystyle \operatorname {T} _{x}X}$ ci-dessous, est l'ensemble des directions tangentes à ${\displaystyle X}$ en ${\displaystyle x}$, c'est-à-dire des directions ${\displaystyle d}$ pour lesquelles il existe des suites ${\displaystyle \{x_{k}\}_{k\in \mathbb {N} }}$ d'éléments de ${\displaystyle \mathbb {E} }$ et ${\displaystyle \{t_{k}\}_{k\in \mathbb {N} }}$ d'éléments de ${\displaystyle \mathbb {R} }$ telles que

La notion de cône tangent permet d'obtenir aisément une condition nécessaire d'optimalité du premier ordre pour le problème générique ${\displaystyle (P_{X})}$ — on suppose donc ici que le critère de ce problème est différentiable. Cette condition exprime que la fonction-coût ${\displaystyle f}$ croît depuis un minimum local ${\displaystyle x_{*}}$ en suivant une direction tangente, ce qui se traduit mathématiquement par

C'est ce que nous appellerons la forme géométrique de l'optimalité au premier ordre. Ce résultat avait déjà été exprimé par Peano dès 1887[2]^,[3], puis par Kantorovitch en 1940[4], mais il est passé inaperçu ou a été oublié[5]^,[6]. On peut en donner une expression plus compacte en introduisant les notions de gradient et de cône dual.

• La dérivée première ${\displaystyle f'(x)}$ de ${\displaystyle f}$ en ${\displaystyle x}$ étant une application linéaire de ${\displaystyle \mathbb {E} }$ dans ${\displaystyle \mathbb {R} }$, par le théorème de Riesz-Fréchet, il existe un unique vecteur ${\displaystyle \nabla f(x)\in \mathbb {E} }$ vérifiant
  
  ${\displaystyle \forall \,h\in \mathbb {E}$ :\qquad \langle \nabla f(x),h\rangle =f'(x)\cdot h.}
  Ce vecteur ${\displaystyle \nabla f(x)}$ est appelé le gradient de ${\displaystyle f}$ en ${\displaystyle x}$. Il dépend manifestement du produit scalaire de l'espace euclidien ${\displaystyle \mathbb {E} }$.

• Soit ${\displaystyle P}$ une partie non vide de l'espace euclidien ${\displaystyle \mathbb {E} }$. Le cône dual (positif) de ${\displaystyle P}$ est l'ensemble défini par
  
  ${\displaystyle P^{+}:=\{d\in \mathbb {E}$ :\langle d,x\rangle \geqslant 0} pour tout ${\displaystyle x\in P\}.}$
  C'est un cône convexe fermé non vide.

Avec ces deux concepts, l'expression géométrique de l'optimalité donnée ci-dessus devient

Cette condition est générique et c'est elle qui sera particularisée ci-dessous à des problèmes dont l'ensemble admissible a une structure plus précise. Le travail sera dans chaque cas celui de trouver une expression plus pratique, plus accessible au calcul, du cône dual du cône tangent, conduisant ainsi à la forme analytique de l'optimalité.

Résumons le résultat obtenu. On utilise l'abréviation CN1 pour désigner une condition nécessaire d'optimalité du premier ordre.

On dit que ${\displaystyle x_{*}}$ est un point stationnaire ou un point critique du problème ${\displaystyle (P_{X})}$, si ce point est admissible et s'il vérifie la condition d'optimalité du premier ordre donnée dans le résultat ci-dessus.

Lorsque l'ensemble admissible est convexe, on dispose d'une CN1 ne faisant pas intervenir le cône tangent. On y a noté ${\displaystyle f'(x;d)}$ la dérivée directionnelle de ${\displaystyle f}$ en ${\displaystyle x}$ dans la direction ${\displaystyle d}$, c'est-à-dire la limite lorsque ${\displaystyle t\downarrow 0}$ du quotient différentiel ${\displaystyle (f(x+td)-f(x))/t}$.

Enfin, lorsque à la fois l'ensemble admissible est convexe et le critère est convexe sur l'ensemble admissible, la condition précédente est une condition nécessaire et suffisante d'optimalité du premier ordre, une propriété que l'on résume par l'abréviation CNS1. Il n'y a alors plus de distinction entre minimum local et global.

Pour les problèmes convexes, il n'y a donc pas de distinction entre un minimum local et global : tous les minima locaux sont globaux. C'est une seconde manifestation de l'importance de l'analyse convexe en optimisation.

Le cône tangent à ${\displaystyle \mathbb {E} }$ en ${\displaystyle x_{*}\in \mathbb {E} }$ est l'espace ${\displaystyle \mathbb {E} }$ tout entier. Comme le dual de ${\displaystyle \mathbb {E} }$ est ${\displaystyle \{0\}}$, la CN1 générique exprime que le gradient ${\displaystyle \nabla f(x_{*})}$ est nul en un minimum local ${\displaystyle x_{*}}$ de ${\displaystyle f}$ sur ${\displaystyle \mathbb {E} }$. Cette condition d'optimalité est parfois appelée « équation de Fermat » pour rappeler une condition similaire trouvée, dans le cas d'un polynôme réel d'une variable réelle, par Pierre de Fermat vers 1629, c'est-à-dire environ quarante ans avant l'invention du calcul différentiel par Newton et Leibniz[7].

Lorsque ${\displaystyle f}$ est convexe, ces conditions deviennent des conditions nécessaires et suffisantes d'optimalité globale de ${\displaystyle x_{*}}$.

Nous désignons ci-dessous par ${\displaystyle f''(x)}$ la dérivée seconde de ${\displaystyle f}$ en ${\displaystyle x}$, qui est une application bilinéaire symétrique de ${\displaystyle \mathbb {E} \times \mathbb {E} }$ dans ${\displaystyle \mathbb {R} }$, et par ${\displaystyle \nabla ^{2}f(x)}$ la hessienne de ${\displaystyle f}$ en ${\displaystyle x\in \mathbb {E} }$ pour le produit scalaire ${\displaystyle \langle \cdot ,\cdot \rangle }$ de l'espace euclidien ${\displaystyle \mathbb {E} }$, qui est l'unique opérateur linéaire auto-adjoint sur ${\displaystyle \mathbb {E} }$ vérifiant

Rappelons également les notions de semi-définie positivité et définie positivité d'un opérateur auto-adjoint ${\displaystyle A}$ sur ${\displaystyle \mathbb {E} }$, associées au produit scalaire de ${\displaystyle \mathbb {E} }$, qui sont utilisées dans les résultats ci-dessous :

• ${\displaystyle A}$ est semi-défini positif si ${\displaystyle \langle Av,v\rangle \geqslant 0}$ pour tout vecteur ${\displaystyle v\in \mathbb {E} }$,
• ${\displaystyle A}$ est défini positif si ${\displaystyle \langle Av,v\rangle >0}$ pour tout vecteur ${\displaystyle v\in \mathbb {E} \setminus \{0\}}$.

Les résultats suivants résument les conditions nécessaires du second ordre (CN2) et les conditions suffisantes du second ordre (CS2) pour les problèmes d'optimisation sans contrainte.

On peut se servir de ces conditions du second ordre comme suit. La CN1 de Fermat est un système non linéaire qui a quelques chances d'être bien posé. Par exemple si ${\displaystyle \mathbb {E} =\mathbb {R} ^{n}}$ est équipé du produit scalaire euclidien, ce système est formé de ${\displaystyle n}$ équations (les dérivées partielles du critère) à ${\displaystyle n}$ inconnues. Si on calcule toutes les solutions de l'équation de Fermat (ceci est rarement une tâche aisée), on dispose, par définition, de tous les points stationnaires du critère. Ceux-ci ne sont pas nécessairement des minimiseurs de ${\displaystyle f}$. Les conditions du deuxième ordre permettent souvent de sélectionner parmi ces points stationnaires ceux qui sont des minima locaux. En effet, d'après ces conditions

• si ${\displaystyle x_{*}}$ est un point stationnaire tel que ${\displaystyle \nabla ^{2}f(x_{*})}$ n'est pas semi-défini positif, alors ${\displaystyle x_{*}}$ n'est pas un minimum local (condition nécessaire),
• si ${\displaystyle x_{*}}$ est un point stationnaire tel que ${\displaystyle \nabla ^{2}f(x_{*})}$ est défini positif, alors ${\displaystyle x_{*}}$ est un minimum local strict (condition suffisante).

On ne recouvre pas ainsi tous les cas, puisque l'on pourrait avoir un point stationnaire ${\displaystyle x_{*}}$ avec une hessienne ${\displaystyle \nabla ^{2}f(x_{*})}$ semi-défini positif, mais non défini positif (il a un noyau non trivial, une valeur propre nulle). L'ambiguïté de tels cas peut parfois être levée en examinant des conditions d'ordre plus élevé.

L'ensemble admissible du problème d'optimisation considéré dans cette section n'est pas l'espace ${\displaystyle \mathbb {E} }$ tout entier, comme pour les problèmes sans contrainte de la section précédente, mais une partie de celui-ci, définie par un nombre fini de contraintes d'égalité :

Ces contraintes sont spécifiées au moyen d'une fonction

où ${\displaystyle \mathbb {F} }$ est, tout comme ${\displaystyle \mathbb {E} }$, un espace euclidien (de dimension finie) dont le produit scalaire est aussi noté ${\displaystyle \langle \cdot ,\cdot \rangle }$. Les dimensions des espaces sont notées

Il sera souvent approprié de supposer qu'en la solution ${\displaystyle x_{*}}$ recherchée, la jacobienne ${\displaystyle c'(x_{*})}$ de la contrainte vérifie

Ceci requiert certainement d'avoir ${\displaystyle m\leqslant n}$, c'est-à-dire d'avoir moins de contraintes que de variables à optimiser. Lorsque cette hypothèse est vérifiée, l'ensemble admissible ${\displaystyle X_{E}}$ est, dans un voisinage de ${\displaystyle x_{*}}$, une variété (concept de base de la géométrie différentielle que l'on peut voir comme une surface ayant des propriétés de représentation particulières) de dimension ${\displaystyle n-m}$.

Le problème d'optimisation considéré dans cette section s'écrit donc

où ${\displaystyle f:\mathbb {E} \to \mathbb {R} }$ en est le critère.

L'ensemble admissible ${\displaystyle X_{E}}$ d'un problème ${\displaystyle (P_{E})}$ convexe est donc un sous-espace affine de ${\displaystyle \mathbb {E} }$, donc un convexe.

Comme le montre le cas générique, les conditions nécessaires d'optimalité du premier ordre peuvent s'obtenir en trouvant une représentation convenable du cône tangent à l'ensemble admissible ${\displaystyle X_{E}}$ et en prenant ensuite son cône dual.

On note ${\displaystyle {\mathcal {N}}(A)}$ le noyau et ${\displaystyle {\mathcal {R}}(A)}$ l'image d'une application linéaire ${\displaystyle A:\mathbb {E} \to \mathbb {F} }$ entre deux espaces euclidiens ${\displaystyle \mathbb {E} }$ et ${\displaystyle \mathbb {F} }$. L'adjointe de ${\displaystyle A}$ est l'application linéaire ${\displaystyle A^{*}:\mathbb {F} \to \mathbb {E} }$ définie par la relation ${\displaystyle \langle Au,v\rangle =\langle u,A^{*}v\rangle }$, pour tout ${\displaystyle u\in \mathbb {E} }$ et tout ${\displaystyle v\in \mathbb {F} }$. On rappelle qu'en dimension finie, on a

Cette identité joue un rôle-clé dans le passage de la forme géométrique (utilisant la partie gauche de l'identité) à la forme analytique (utilisant sa partie droite) des conditions d'optimalité du premier ordre.

Le résultat suivant montre que le cône tangent est inclus dans un sous-espace vectoriel ; il lui sera égal dans les bons cas.

Dans l'inclusion ${\displaystyle \operatorname {T} _{x}X_{E}\subset {\mathcal {N}}(c'(x))}$, le cône tangent ${\displaystyle \operatorname {T} _{x}X_{E}}$ ne dépend que de l'ensemble admissible ${\displaystyle X_{E}}$, alors que ${\displaystyle {\mathcal {N}}(c'(x))}$ dépend de la fonction ${\displaystyle c}$ utilisée pour définir ${\displaystyle X_{E}}$. Il peut y avoir plusieurs fonctions ${\displaystyle c}$ définissant le même ensemble ${\displaystyle X_{E}}$. Du point de vue de l'optimisation, toutes ne conviennent pas. Celles qui permettent d'obtenir des conditions d'optimalité sont celles pour lesquelles l'égalité ${\displaystyle \operatorname {T} _{x}X_{E}={\mathcal {N}}(c'(x))}$ a lieu. On dit alors que la contrainte ${\displaystyle c}$ (léger abus de langage, il faudrait dire la fonction ${\displaystyle c}$ utilisée pour définir ${\displaystyle X_{E}}$) est qualifiée en ${\displaystyle x}$ (sous-entendu «pour représenter ${\displaystyle X_{E}}$»).

Voici le résultat principal assurant que la contrainte ${\displaystyle c}$ est qualifiée en un point. On y retrouve la condition mentionnée ci-dessus assurant que ${\displaystyle X_{E}}$ est une variété dans le voisinage ${\displaystyle x}$.

Voici une conséquence pratique de la notion de qualification de contrainte. Au lieu d'utiliser la fonction ${\displaystyle c}$ pour représenter l'ensemble admissible ${\displaystyle X_{E}}$, on pourrait utiliser la fonction ${\displaystyle {\tilde {c}}:\mathbb {E} \to \mathbb {R} }$, définie par ${\displaystyle {\tilde {c}}(x)=\|c(x)\|^{2}/2}$, puisque ${\displaystyle {\tilde {c}}(x)=0}$ si, et seulement si, ${\displaystyle c(x)=0}$. Ceci paraît attrayant puisque l'on a ainsi remplacé toutes les contraintes d'égalité, en nombre potentiellement grand, par une seule contrainte. Cependant, la contrainte ${\displaystyle {\tilde {c}}}$ a encore moins de chance d'être qualifiée que ${\displaystyle c}$ puisque ${\displaystyle \nabla {\tilde {c}}(x)=c'(x)^{*}c(x)=0}$ en un point ${\displaystyle x\in X_{E}}$ et donc ${\displaystyle {\mathcal {N}}({\tilde {c}}'(x))=\mathbb {E} }$, qui est le plus souvent trop grand. Il n'est donc, en général, pas recommandé de remplacer ${\displaystyle c}$ par ${\displaystyle {\tilde {c}}}$.

Lorsque la contrainte est qualifiée, le cône tangent est le sous-espace vectoriel ${\displaystyle {\mathcal {N}}(c'(x))}$, dont le dual est alors son orthogonal ${\displaystyle {\mathcal {N}}(c'(x))^{\perp }={\mathcal {R}}(c'(x)^{*})}$. Par la CN1 générique, le gradient de ${\displaystyle f}$ en un minimum local de ${\displaystyle f}$ sur ${\displaystyle X_{E}}$ appartient à ce dernier ensemble, ce qui conduit aux conditions nécessaires d'optimalité du premier ordre (CN1) de Lagrange[8].

Ce résultat, parfois appelé méthode du multiplicateur de Lagrange, est attribué à Lagrange qui l'énonça dans sa Méchanique analytique (1788). On en trouve toutefois déjà des traces dans des travaux d'Euler sur les problèmes isopérimétriques (1744). Lagrange utilisa d'abord cette méthode pour résoudre un problème de calcul des variations sous contraintes et plus tard, dans sa Théorie des fonctions analytiques (1797), il l'applique aux problèmes de la forme ${\displaystyle (P_{E}).}$ [9]^,[10]

En l'absence de qualification de la contrainte, l'existence du multiplicateur n'est plus assurée, si bien que la condition nécessaire d'optimalité de Lagrange peut ne pas avoir lieu. Un exemple est donné dans la section suivante.

En pratique, il est souvent commode de retrouver la condition de Lagrange en introduisant le lagrangien du problème.

La variable ${\displaystyle x}$ est aussi appelée variable primale ; quant au couple ${\displaystyle (x,\lambda )}$, on lui donne parfois le nom de variable(s) primale(s)-duale(s).

Le lagrangien joue un rôle essentiel en optimisation avec contraintes. Le multiplicateur porte ce nom car il multiplie les contraintes dans le lagrangien, par l'intermédiaire du produit scalaire de ${\displaystyle \mathbb {F} }$. Sous les hypothèses du résultat ci-dessus, les conditions nécessaires d'optimalité du premier ordre peuvent maintenant s'écrire comme suit

Nous avons noté ${\displaystyle \nabla _{x}}$ [resp. ${\displaystyle \nabla _{(x,\lambda )}}$] le gradient par rapport à ${\displaystyle x}$ [resp. à ${\displaystyle (x,\lambda )}$]. Ce système (non linéaire, en toute généralité) permet souvent de calculer une solution du problème d'optimisation ${\displaystyle (P_{E})}$. En réalité, cette solution est ce que nous avons appelé un point stationnaire. Ce n'est pas nécessairement un minimum local du problème (ce point peut être un maximum local, qui n'est a priori pas ce que l'on cherche !), sauf si celui-ci est convexe.

Pour les problèmes non convexes, ce sont les conditions du second ordre qui permettrons de sélectionner les minima locaux parmi les points stationnaires calculés.

Il est utile de spécifier les conditions d'optimalité de Lagrange lorsque ${\displaystyle \mathbb {E} =\mathbb {R} ^{n}}$, ${\displaystyle \mathbb {F} =\mathbb {R} ^{m}}$ et que l'on munit ces espaces du produit scalaire euclidien

Il y a alors ${\displaystyle n}$ variables ${\displaystyle x_{1},\ldots ,x_{n}}$ à optimiser et les ${\displaystyle m}$ contraintes du problème ${\displaystyle (P_{E})}$ sont données explicitement au moyen de ${\displaystyle m}$ fonctions ${\displaystyle c_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$ :

Le lagrangien du problème s'écrit

Observons que le multiplicateur de Lagrange ${\displaystyle \lambda \in \mathbb {R} ^{m}}$ a autant de composantes qu'il y a de contraintes ; chacune des composantes ${\displaystyle \lambda _{i}}$ étant associée à une contrainte ${\displaystyle c_{i}}$ ; on dit d'ailleurs que le multiplicateur ${\displaystyle \lambda _{i}}$ est associé à la contrainte ${\displaystyle c_{i}}$. Si on utilise ${\displaystyle \nabla }$ pour désigner le gradient d'une fonction réelle de ${\displaystyle n}$ variables par rapport au produit scalaire euclidien, c'est-à-dire le vecteur de ses dérivées partielles, les conditions d'optimalité s'écrivent sous la forme d'un système de ${\displaystyle n+m}$ équations à ${\displaystyle n+m}$ inconnues ${\displaystyle (x_{*},\lambda _{*})}$ :

On voit donc qu'en la solution le gradient du critère est combinaison linéaire des gradients des contraintes (on se rappelle qu'en optimisation sans contrainte le gradient du critère est nul).

Voici un exemple de problème avec 2 variables et 2 contraintes, avec solution, mais sans multiplicateur optimal et donc sans condition de Lagrange (c'est l'absence de qualification des contraintes qui produit cet effet) :

L'unique point admissible est le point ${\displaystyle x_{*}=(0,0)}$, qui est donc l'unique solution du problème. Cependant les contraintes ne sont pas qualifiées en ce point car le cône tangent est réduit à ${\displaystyle \{(0,0)\}}$ alors que le noyau de la jacobienne des contraintes est ${\displaystyle \{d\in \mathbb {R} ^{2}:d_{2}=0\}}$ (on note par ailleurs que cette jacobienne, qui est une matrice ${\displaystyle 2\times 2}$ ne saurait alors être surjective). Dans cet exemple, les conditions de Lagrange ne sont pas vérifiées (il n'y a pas de multiplicateur optimal), puisque le gradient de ${\displaystyle f}$ en la solution ne peut être combinaison linéaire des gradients des contraintes (ces derniers sont linéairement dépendants) :

Comme en optimisation sans contrainte, les conditions d'optimalité du second ordre permettent de sélectionner les éventuelles solutions parmi les points stationnaires (i.e., les points vérifiant la condition de Lagrange). Ces conditions du second ordre des problèmes avec contraintes d'égalité diffèrent de celles des problèmes sans contrainte sur deux points :

• ce n'est pas la hessienne du critère qui intervient dans ces conditions, mais la hessienne du lagrangien,
• la hessienne du lagrangien n'est pas semi-définie positive sur l'espace ${\displaystyle \mathbb {E} }$ des variables primales tout entier, mais sur le cône tangent.

D'où proviennent ces différences ?

En optimisation sans contrainte, les conditions nécessaires du second ordre résultent du fait que dans le voisinage d'une solution, le critère prend une valeur supérieure à celle qu'il prend en la solution. Un développement de Taylor du critère autour d'une solution et l'utilisation du fait que son gradient est nul en la solution impliquent alors immédiatement que la hessienne du critère doit être semi-définie positive en la solution. Dans le cas des problèmes avec contraintes d'égalité, utiliser la même démarche ne conduirait nulle part, car le gradient du critère n'est pas nécessairement nul en une solution (selon la condition de Lagrange, il est dans l'image de l'adjointe de la jacobienne de la contrainte). En réalité, c'est le gradient du lagrangien qui s'annule en une solution. C'est donc un développement de Taylor de cette fonction qui pourra apporter de l'information sur sa hessienne. Ceci explique le premier point ci-dessus. Par ailleurs, il est clair que sur l'ensemble admissible le lagrangien prend les mêmes valeurs que le critère, si bien qu'il prend aussi des valeurs supérieures à celle qu'il a en une solution. C'est la relation de monotonie recherchée qui conduira à la semi-définie positivité de la hessienne du lagrangien. Cependant, ce n'est que sur la variété des contraintes que cette relation de monotonie a lieu, si bien que la semi-définie positivité de la hessienne du lagrangien ne sera vérifiée que sur la variété linéarisée qu'est le cône tangent. Ceci explique le second point ci-dessus.

On devrait à présent mieux comprendre les conditions nécessaires du second ordre (CN2) pour un problème avec contraintes d'égalité, que voici.

Ce résultat donne-t-il suffisamment de conditions ou aurait-on pu en obtenir d'autres ? Ce sont les bonnes conditions car, comme en optimisation sans contrainte, si l'on remplace la semi-définie positivité par la définie positivité, on obtient des conditions suffisantes d'optimalité du second ordre (abrégées par CS2).

On notera que les CS2 ne requièrent pas d'hypothèse de qualification de contrainte.

Vérifier la (semi-)définie positivité de la hessienne du lagrangien ${\displaystyle L_{*}:=\nabla _{xx}^{2}\ell (x_{*},\lambda _{*})}$ dans le noyau de ${\displaystyle c'(x_{*})}$ ne pose pas de difficulté, pourvu que l'on puisse calculer une base de ce noyau. On peut en effet voir ce noyau comme l'image d'une application linéaire injective ${\displaystyle B:\mathbb {R} ^{p}\to \mathbb {E} }$ tel que ${\displaystyle c'(x_{*})B=0,}$ avec ${\displaystyle p=n-\dim {\mathcal {R}}(c'(x_{*})).}$ Il suffit alors de vérifier la (semi-)définie positivité de ${\displaystyle B^{*}L_{*}B}$, ce qui peut se faire en temps polynomial par des techniques d'algèbre linéaire.

Soit ${\displaystyle \mathbb {E} }$ un espace euclidien muni d'un produit scalaire noté ${\displaystyle \langle \cdot ,\cdot \rangle }$ ; on note ${\displaystyle \|\cdot \|}$ la norme associée. On s'intéresse aux vecteurs propres d'une application linéaire ${\displaystyle A:\mathbb {E} \to \mathbb {E} }$ auto-adjointe. Par exemple, on pourrait avoir ${\displaystyle \mathbb {E} =\mathbb {R} ^{n}}$, muni du produit scalaire euclidien, et ${\displaystyle A}$ une matrice symétrique.

Le problème d'optimisation

Dans ce but, on considère le quotient de Rayleigh ${\displaystyle q_{r}:\mathbb {E} \to \mathbb {R} }$, défini en ${\displaystyle x\in \mathbb {E} \setminus \{0\}}$ par

Comme ${\displaystyle q_{r}}$ est constant le long des rayons issus de zéro, il revient au même de minimiser la fonction quadratique ${\displaystyle q:\mathbb {E} \to \mathbb {R} }$ définie en ${\displaystyle x\in \mathbb {E} }$ par

sur la sphère unité ${\displaystyle S:=\{x\in \mathbb {E}$ :\|x\|=1\}.} On considère donc le problème d'optimisation avec une unique contrainte d'égalité suivant

Ce problème a toujours une solution (le critère est continu et, comme ${\displaystyle \mathbb {E} }$ est de dimension finie, ${\displaystyle S}$ est compact). Calculons les points stationnaires du problème d'optimisation.

Conditions d'optimalité du premier ordre

La fonction ${\displaystyle x\mapsto \|x\|-1}$ est non différentiable en zéro, mais cela n'a pas trop d'importance, car la solution est de norme un. On préfère toutefois définir l'ensemble admissible au moyen de la contrainte ${\displaystyle x\mapsto c(x):=(1-\|x\|^{2})/2}$, qui se dérive plus facilement. Cette contrainte est qualifiée en tout point admissible, car sa jacobienne ${\displaystyle h\mapsto -\langle x,h\rangle }$ est surjective si ${\displaystyle x\neq 0}$. Pour calculer la solution du problème d'optimisation, on introduit son lagrangien, qui prend en ${\displaystyle (x,\lambda )\in \mathbb {E} \times \mathbb {R} }$ la valeur

Comme il y a une seule contrainte, il y a un seul multiplicateur ${\displaystyle \lambda }$.

Les conditions d'optimalité de Lagrange s'écrivent

Dès lors, ${\displaystyle {\bar {x}}}$ est un point stationnaire de multiplicateur ${\displaystyle {\bar {\lambda }}}$ si, et seulement si, ${\displaystyle {\bar {x}}}$ est un vecteur propre unitaire de ${\displaystyle A}$, de valeur propre ${\displaystyle {\bar {\lambda }}}$. Ce multiplicateur est aussi la valeur du critère en ${\displaystyle {\bar {x}}}$, puisque ${\displaystyle q({\bar {x}})=\langle A{\bar {x}},{\bar {x}}\rangle ={\bar {\lambda }}\|{\bar {x}}\|^{2}={\bar {\lambda }}}$. Dès lors, une solution du problème d'optimisation est un vecteur propre unitaire de valeur propre minimale. Si au lieu de minimiser ${\displaystyle \langle Ax,x\rangle }$, on minimisait ${\displaystyle -\langle Ax,x\rangle }$ ou on maximisait ${\displaystyle \langle Ax,x\rangle }$, une solution du problème d'optimisation serait un vecteur propre unitaire de valeur propre maximale.

Conditions d'optimalité du deuxième ordre

La hessienne du lagrangien en une solution primale-duale ${\displaystyle ({\bar {x}},{\bar {\lambda }})}$ du problème d'optimisation est l'opérateur auto-adjoint ${\displaystyle (A-{\bar {\lambda }}I)}$ sur ${\displaystyle \mathbb {E} .}$ Comme ${\displaystyle {\bar {\lambda }}}$ est la valeur minimale de ${\displaystyle q}$ sur la sphère unité, on a ${\displaystyle \langle Ax,x\rangle \geqslant {\bar {\lambda }}}$ pour tout vecteur unitaire ${\displaystyle x.}$ On peut en déduire que ${\displaystyle \langle (A-{\bar {\lambda }}I)x,x\rangle \geqslant 0}$ pour tout vecteur ${\displaystyle x\in \mathbb {E} ,}$ ce qui signifie que la hessienne du lagrangien ${\displaystyle A-\lambda I}$ est semi-définie positive dans tout l'espace ${\displaystyle \mathbb {E} }$, pas seulement dans l'espace tangent à la contrainte comme l'assurent les CN2. C'est le caractère quadratique du critère et des contraintes qui permet d'avoir cette propriété.

Si un couple ${\displaystyle ({\bar {x}},{\bar {\lambda }})}$ vérifie les CS2, alors ${\displaystyle {\bar {x}}}$ est un vecteur propre de ${\displaystyle A}$ de valeur propre ${\displaystyle {\bar {\lambda }}}$ ; de plus ${\displaystyle \langle Ax,x\rangle >\langle A{\bar {x}},{\bar {x}}\rangle ={\bar {\lambda }}}$, pour tout vecteur unitaire ${\displaystyle x}$, voisin mais différent de ${\displaystyle {\bar {x}}}$. On en déduit aisément que ${\displaystyle \langle Ax,x\rangle >{\bar {\lambda }}}$ pour tout ${\displaystyle x}$ unitaire différent de ${\displaystyle \pm {\bar {x}}}$ (on peut par exemple prendre ${\displaystyle t\in {]0,1]}}$ assez petit pour que ${\displaystyle x_{t}/\|x_{t}\|}$, avec ${\displaystyle x_{t}:=(1-t){\bar {x}}+tx}$, soit voisin mais différent de ${\displaystyle {\bar {x}}}$ et développer la relation ${\displaystyle \langle Ax_{t},x_{t}\rangle >{\bar {\lambda }}\|x_{t}\|^{2}}$ qui en résulte). On en déduit que ${\displaystyle {\bar {\lambda }}}$ est la valeur propre minimale et est simple (i.e., l'espace propre associé est de dimension 1). La réciproque est également vraie : si la plus petite valeur propre de ${\displaystyle A}$ est simple, les CS2 sont vérifiées.

Résultats obtenus

Dans cette section, on considère le problème d'optimisation avec contraintes d'égalité et d'inégalité, que l'on écrit sous la forme suivante

Cette écriture exprime le fait que l'on cherche à minimiser un critère ${\displaystyle f:\mathbb {E} \to \mathbb {R} }$ défini sur un espace euclidien ${\displaystyle \mathbb {E} }$ dont l'argument ${\displaystyle x}$, qui est le vecteur des variables à optimiser, l'inconnue de ce problème, est contraint de respecter un nombre fini de contraintes spécifiées par des fonctions ${\displaystyle c_{i}:\mathbb {E} \to \mathbb {R} }$. Le produit scalaire de l'espace euclidien est noté ${\displaystyle \langle \cdot ,\cdot \rangle }$. On y trouve des contraintes d'égalité et d'inégalité en nombre fini, repérées par des ensembles finis d'indices ${\displaystyle E}$ et ${\displaystyle I}$, dont le cardinal est noté

Le nombre total de contraintes est noté ${\displaystyle m:=m_{E}+m_{I}}$.

Il est commode de supposer que les ensembles d'indices ${\displaystyle E}$ et ${\displaystyle I}$ forment une partition de l'ensemble des ${\displaystyle m}$ premiers entiers ${\displaystyle \{1,\ldots ,m\}}$ :

Si ${\displaystyle v\in \mathbb {R} ^{m}}$, on note ${\displaystyle v_{E}}$ le vecteur de ${\displaystyle \mathbb {R} ^{m_{E}}}$ formé des composantes ${\displaystyle v_{i}}$ de ${\displaystyle v}$ avec ${\displaystyle i\in E}$. De même pour ${\displaystyle v_{I}}$. On peut alors rassembler les fonctions réelles ${\displaystyle c_{i}}$ en une seule fonction ${\displaystyle c:\mathbb {E} \to \mathbb {R} ^{m}}$, dont les composantes ${\displaystyle c_{E}}$ et ${\displaystyle c_{I}}$ sont utilisées pour définir les contraintes d'égalité et d'inégalité.