Voir la source de Conditions d'optimalité

En [[Optimisation (mathématiques)|optimisation mathématique]], les '''conditions d'optimalité''' sont un ensemble d'équations, d'inéquations (c'est-à-dire des inégalités) et d'expressions diverses (par exemple, la [[Matrice copositive|copositivité de matrices]]) vérifiées par une solution d'un problème d'optimisation (on parle alors de '''conditions nécessaires''' d'optimalité) ou qui permettent d'affirmer qu'un point qui les vérifie est solution du problème d'optimisation considéré (on parle alors de '''conditions suffisantes''' d'optimalité). Ces expressions analytiques de l'optimalité sont utiles entre autres pour :
* calculer les solutions d'un problème d'optimisation,
* vérifier l'optimalité d'un point donné,
* concevoir des algorithmes de résolution.

Cet article se limite aux conditions d'optimalité des problèmes d'optimisation ''différentiable'' et de ''dimension finie''.

Les plus importantes sont les conditions KKT.

== Préambule ==

Cet article se limite aux conditions d'optimalité des problèmes d'optimisation ''différentiable'' et de ''dimension finie''. Le terme ''différentiable'' signale que les fonctions définissant le problème sont supposées [[Différentielle#Définition de la différentielle|''différentiables'']] au sens classique (celui de Fréchet). Lorsque la différentiabilité a lieu dans un sens plus faible on parle d{{'}}''[[optimisation non lisse]]'' ou d{{'}}''[[optimisation non différentiable]]'', discipline dans laquelle on établit des conditions d'optimalité plus fines que celles présentées dans cet article. Il ne sera donc pas non plus question ici des problèmes d{{'}}''[[optimisation combinatoire]]'' dans lesquels les variables prennent des valeurs discrètes, si bien que la différentiabilité requise n'a pas de sens. Quant aux termes ''dimension finie'', ils font référence au fait que l'on cherche la valeur optimale d'un nombre fini de paramètres (mais ceux-ci doivent pouvoir varier continûment). Le système à optimiser peut, quant à lui, être de dimension infinie, comme c'est le cas de l'optimisation d'une forme géométrique (de dimension infinie) décrite par des [[spline]]s (représentés par un nombre fini de paramètres). Les [[Conditions d'optimalité (dimension infinie)|conditions d'optimalité des problèmes d'optimisation de dimension infinie]] sont considérées ailleurs.

On parle de '''conditions du premier ordre''' si ces conditions font intervenir les dérivées premières des objets définissant le problème (il faudra définir ce que l'on entend par la ''dérivée'' de l'ensemble admissible du problème), mais pas les dérivées d'ordre supérieur, et de '''conditions du second ordre''' si ces conditions font intervenir les dérivées secondes des objets définissant le problème, mais pas les dérivées d'ordre supérieur.

Les conditions d'optimalité d'un problème d'optimisation avec contraintes introduisent des ''variables cachées'', les '''multiplicateurs''' ou '''variables duales''', qui n'apparaissent pas dans l'énoncé du problème et qui sont donc difficiles à appréhender (elles appartiennent à un autre espace que celui des variables à optimiser). Elles jouent cependant un rôle crucial dans la compréhension du problème, notamment parce qu'elles s'interprètent comme des ''coûts marginaux'', très utiles en pratique ; il est donc important de s'y familiariser.

Les conditions d'optimalité sont présentées ci-dessous pour des problèmes d'optimisation de généralité (et de difficulté) croissante. Celles énoncées pour un problème d'une certaine généralité peuvent être utilisées pour exprimer les conditions d'optimalité d'un problème qui l'est moins, car celui-ci pourra toujours être vu comme un cas particulier du premier problème. Le lecteur pressé peut donc directement aborder le cas du problème le plus abstrait, mais il lui manquera alors certaines notions coutumièrement utilisées à des niveaux d'abstraction moindres.

'''Connaissances supposées''' : le [[Différentielle|calcul différentiel]], l'[[algèbre linéaire]], les bases de l'[[analyse convexe]] (en particulier le [[lemme de Farkas]]).

== Le problème générique ==

=== Le problème ''P<sub>X</sub>'' ===

Soit <math>\mathbb{E}</math> un [[espace vectoriel]] sur <math>\mathbb{R}</math> de [[espace vectoriel#Définition de la dimension|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é <math>\langle\cdot,\cdot\rangle</math>, qui en fait un [[espace euclidien]]. La [[Norme (mathématiques)|norme]] associée à ce produit scalaire est notée <math>\|\cdot\|</math>. Le problème d'optimisation considéré s'exprime mathématiquement comme celui qui consiste à minimiser une [[Application (mathématiques)|fonction]] <math>f:\mathbb{E}\to\mathbb{R}</math> sur une partie <math>X</math> de <math>\mathbb{E}</math>. La fonction <math>f</math> a de nombreuses appellations, ce qui permet de varier le vocabulaire : '''fonction-coût''', '''coût''', '''fonction-objectif''', '''objectif''', '''critère''', ''etc''. L'ensemble <math>X</math> 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 <math>(P_X)</math>, s'écrit au choix comme suit :

<center>
<math>(P_X)\qquad\inf_{x\in X}\;f(x)\qquad\mbox{ou}\qquad\inf\;\{f(x):x\in X\}\qquad\mbox{ou}\qquad\begin{cases}\inf\;f(x)\\x\in X\end{cases}</math>.
</center>

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

<center>
<math>x_*\in X\qquad\mbox{et}\qquad f(x_*)\leqslant f(x)\quad\mbox{pour tout}\quad x\in X</math>.
</center>

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 ‘‘<math>\inf</math>’’ par ‘‘<math>\min</math>’’ dans l'écriture du problème d'optimisation <math>(P_X)</math> 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 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 <math>x_*</math> est une '''solution locale''' ou '''minimum local''' ou '''minimiseur local''' du problème <math>(P_X)</math> s'il existe un [[voisinage (mathématiques)|voisinage]] <math>V</math> de <math>x_*</math> tel que <math>x_*</math> minimise <math>f</math> sur <math>X\cap V</math>. Par ailleurs, on dit que <math>x_*</math> est une '''solution stricte''' [resp. une '''solution locale stricte'''] si <math>x_*</math> est admissible et si <math>f(x_*)< f(x)</math> (inégalité stricte) pour tout <math>x\in X</math> différent de <math>x_*</math> [resp. pour tout <math>x\in X\cap V</math> différent de <math>x_*</math> où <math>V</math> est un voisinage de <math>x_*</math>].
<!--
=== Cône tangent ===

Lorsqu'une fonction atteint un minimum en un point, elle varie peu dans le [[voisinage (mathématiques)|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|''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.

Rappelons qu'une partie <math>K</math> de <math>\mathbb{E}</math> (un espace vectoriel suffit ici) est un '''cône''' si <math>\mathbb{R}_+K\subset K</math>, ce qui signifie que <math>td</math> doit appartenir à <math>K</math> chaque fois que <math>t</math> est un réel positif (i.e., <math>t\geqslant 0</math>) et <math>d\in K</math>. 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.

Comme le calcul d'une dérivée, le calcul d'une ''direction tangente'' requiert un passage à la limite. Il ne suffit pas en effet de prendre comme cône tangent à une partie <math>X</math> de <math>\mathbb{E}</math> en un point <math>x</math>, ce que l'on appelle parfois le '''cône radial''' en <math>x</math>, qui est le cône défini par
<center>
<math>\operatorname{T}_x^rX:=\{d\in\mathbb{E}:x+td\in X</math> pour tout <math>t>0</math> petit<math>\}</math>.
</center>
En effet, le cône radial à un cercle de <math>\mathbb{R}^2</math> est vide en tout point, si bien que l'on ne retrouve pas avec cette notion, celle des directions tangentes qui est plus familière. Une définition qui suffira à notre propos est la suivante (en dimension infinie, on connaît d'autres notions de cône tangent et celle présentée ci-dessous est alors dite '''au sens de Bouligand'''<ref>G. Bouligand (1932), ''Introduction à la Géométrie Infinitésimale Directe'', Gauthier- Villars, Paris.</ref>). La notation <math>t_k \downarrow 0</math> signifie que les réels <math>t_k</math> tendent vers zéro par des valeurs strictement positives.

{{Théorème|Direction tangente|On dit que <math>d\in\mathbb{E}</math> est une '''direction tangente''' à <math>X\subset\mathbb{E}</math> en <math>x\in\mathbb{E}</math> s'il existe des suites <math>\{x_k\} \subset\mathbb{E}</math> et <math>\{t_k\} \subset\mathbb{R}</math> telles que <math>\{x_k\} \subset X</math>, <math>t_k \downarrow 0</math> et <math>(x_k - x)/t_k\to d</math>.|style=background-color:#eeeeff;}}
{{Théorème|Cône tangent|Le '''cône tangent''' à <math>X\subset\mathbb{E}</math> en <math>x\in\mathbb{E}</math> est l'ensemble des directions tangentes à <math>X</math> en <math>x</math>. On le note <math>\operatorname{T}_xX</math> (notation de la [[Espace tangent|géométrie différentielle]]) ou <math>\operatorname{T}_X(x)</math> (notation de l'[[analyse convexe]]).|style=background-color:#eeeeff;}}

La définition précédente est la plus opérationnelle, celle qui est la plus utilisée, mais elle n'est pas facile à interpréter. En faisant jouer le rôle principal aux directions <math>d_k:=(x_k - x)/t_k</math>, on montre aisément qu'il revient au même de dire que <math>d\in \operatorname{T}_xX</math> si, et seulement si, il existe des suites <math>\{d_k\}\subset\mathbb{E}</math> et <math>\{t_k\}\subset\mathbb{R}</math> telles que

<center>
<math>d_k \to d, \qquad t_k \downarrow 0\qquad \mbox{et}\qquad x+t_kd_k\in X</math>.
</center>

Autrement dit, <math>d</math> est tangente à <math>X</math> en <math>x</math> s'il existe une suite de directions <math>d_k\subset\mathbb{E}</math> convergeant vers <math>d</math>, telles que <math>x+\mathbb{R}_{++}d_k</math> rencontre <math>X</math> en des points de plus en plus proche de <math>x</math> lorsque <math>k\to\infty</math> ; on a noté

<center>
<math>\mathbb{R}_{++}:=\{t\in\mathbb{R}:t>0\}</math>.
</center>

Voici quelques propriétés du cône tangent. Elles utilisent les notations et concepts suivants :
* <math>\overline{X}</math> l'[[Adhérence (mathématiques)|adhérence]] de <math>X</math> (aussi notée <math>\operatorname{adh}X</math>),
* <math>X^\circ</math> l'[[Intérieur (topologie)|intérieur]] de <math>X</math> (aussi noté <math>\operatorname{int}\,X</math>),
* <math>\operatorname{aff}\,X</math> l'[[Sous-espace affine engendré|enveloppe affine]] de <math>X</math>,
* <math>\operatorname{intr}\,X</math> l'[[intérieur relatif]] de <math>X</math> (aussi noté <math>\operatorname{ri}\,X</math>).
On rappelle que <math>\operatorname{aff}\,X-\operatorname{aff}\,X</math> est le sous-espace vectoriel associé au [[Espace affine#Sous-espaces affines|sous-espace affine]] <math>\operatorname{aff}\,X</math>.

{{Théorème|Propriétés du cône tangent|
# <math>\operatorname{T}_xX</math> est un cône [[Fermé (topologie)|fermé]] (non nécessairement [[Ensemble convexe|convexe]]),
# <math>\operatorname{T}_xX</math> est vide si <math>x\notin \overline{X}</math>,
# <math>\operatorname{T}_xX=\mathbb{E}</math> si <math>x\in X^\circ</math>,
# <math>\operatorname{T}_xX=\operatorname{aff}\,X-\operatorname{aff}\,X</math> si <math>x\in \operatorname{intr}\,X</math>,
# si <math>\{X_i\}_{i\in I}</math> est une famille de parties <math>X_i</math> de <math>\mathbb{E}</math>, on a
## <math>\operatorname{T}_x(\cap_{i\in I}X_i)\subset \cap_{i\in I}\operatorname{T}_xX_i</math>,
## <math>\operatorname{T}_x(\cup_{i\in I}X_i)\supset \cup_{i\in I}\operatorname{T}_xX_i</math>, avec égalité si <math>I</math> est fini.|style=background-color:#ffeedd;}}

Dans le cas où l'ensemble est [[Ensemble convexe|convexe]], on peut relier le cône radial au cône tangent et donner quelques propriétés supplémentaires de ce dernier.

{{Théorème|Cône tangent à un [[Ensemble convexe|ensemble convexe]]|Soit <math>x</math> un point dans l'adhérence d'un [[Ensemble convexe|convexe]] <math>C</math> de <math>\mathbb{E}.</math> Alors
# <math>\operatorname{T}_x^rC=\mathbb{R}_{++}(C-x)</math> et est [[Ensemble convexe|convexe]],
# <math>\operatorname{T}_xC=\overline{\operatorname{T}_x^rC}</math>,
# <math>\operatorname{T}_xC</math> est [[Ensemble convexe|convexe]],
# <math>\operatorname{aff}\,(\operatorname{T}_xC)=\operatorname{aff}\,(\operatorname{T}^r_xC)=(\operatorname{aff}\,C)-x</math>.|style=background-color:#ffeedd;}}
-->

=== Forme géométrique de l'optimalité au premier ordre ===

Lorsqu'une fonction atteint un minimum en un point, elle varie peu dans le [[voisinage (mathématiques)|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 d'optimisation sans contrainte|''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 <math>K</math> de <math>\mathbb{E}</math> (un espace vectoriel suffit pour cette notion) est un ''[[Cône (analyse convexe)|cône]]'' si <math>\mathbb{R}_{++}K\subset K</math>, ce qui signifie que <math>td</math> doit appartenir à <math>K</math> chaque fois que <math>t</math> est un réel strictement positif (i.e., <math>t>0</math>) et <math>d\in K</math>. 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.

On utilisera ici la notion de '''[[Cône tangent#Cône tangent|cône tangent au sens de Bouligand]]'''<ref>{{Ouvrage|auteur1=[[Georges Bouligand]]|titre=Introduction à la Géométrie Infinitésimale Directe|lieu=Paris|éditeur=Gauthier- Villars|année=1932}}.</ref>, qui suffit en dimension finie. Précisons que ce ''cône tangent'' à <math>X</math> en <math>x</math>, noté <math>\operatorname{T}_xX</math> ci-dessous, est l'ensemble des '''directions tangentes''' à <math>X</math> en <math>x</math>, c'est-à-dire des directions <math>d</math> pour lesquelles il existe des suites <math>\{x_k\}_{k \in \mathbb{N}}</math> d'éléments de <math>\mathbb{E}</math> et <math>\{t_k\}_{k \in \mathbb{N}}</math> d'éléments de <math>\mathbb{R}</math> telles que
<center>
<math>
\{x_k\} \subset X,\qquad t_k \downarrow 0\qquad\mbox{et}\qquad\frac{x_k - x}{t_k}\to d.
</math>
</center>

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 <math>(P_X)</math> — on suppose donc ici que le critère de ce problème est différentiable. Cette condition exprime que la fonction-coût <math>f</math> croît depuis un minimum local <math>x_*</math> en suivant une direction tangente, ce qui se traduit mathématiquement par

<center>
<math>\forall\,d\in \operatorname{T}_{x_*}X:\qquad f'(x_*)\cdot d\geqslant 0.</math>
</center>

C'est ce qu'on appelle la ''forme géométrique'' de l'optimalité au premier ordre. Ce résultat avait déjà été exprimé par [[Giuseppe Peano|Peano]] dès 1887<ref>{{it}} G. Peano (1887). [http://historical.library.cornell.edu/cgi-bin/cul.math/docviewer?did=00610002\&seq=1 ''Applicazioni Geometriche del Calcolo Infinitesimale'']. Fratelli Bocca Editori, Torino.</ref>{{,}}<ref>{{it}} G. Peano (1908). ''Formulario Mathematico'', Editio V. Fratelli Bocca Editori, Torino.</ref>, puis par [[Leonid Kantorovitch|Kantorovitch]] en 1940<ref>{{en}} L.V. Kantorovich (1940). On an efficient method for solving some classes of extremum problems. ''Doklady Akad. Nauk SSSR'', 28, 212–215.</ref>, mais il est passé inaperçu ou a été oublié<ref>{{en}} B.T. Polyak (2001). History of mathematical programming in the USSR: analyzing the phenomenon. ''Mathematical Programming'', 91, 401–416.</ref>{{,}}<ref>{{en}} S. Dolecki, G.H. Greco (2007). Towards historical roots of necessary conditions of optimality – Regula of Peano. ''Control and Cybernetics'', 36, 491–518.</ref>. On peut en donner une expression plus compacte en introduisant les notions de ''gradient'' et de ''cône dual''.

* La [[Différentielle#Définition de la différentielle|dérivée première]] <math>f'(x)</math> de <math>f</math> en <math>x</math> étant une application linéaire de <math>\mathbb{E}</math> dans <math>\mathbb{R}</math>, par le [[Théorème de représentation de Riesz (Fréchet-Riesz)|théorème de Riesz-Fréchet]], il existe un unique vecteur <math>\nabla f(x)\in\mathbb{E}</math> vérifiant

<center><math>\forall\,h\in\mathbb{E}:\qquad\langle\nabla f(x),h\rangle=f'(x)\cdot h.</math></center><br />Ce vecteur <math>\nabla f(x)</math> est appelé le '''gradient''' de <math>f</math> en <math>x</math>. Il dépend manifestement du produit scalaire de l'espace euclidien <math>\mathbb{E}</math>.

* Soit <math>P</math> une partie non vide de l'espace euclidien <math>\mathbb{E}</math>. Le '''cône dual (positif)''' de <math>P</math> est l'ensemble défini par

<center><math>P^+:=\{d\in\mathbb{E}:\langle d,x\rangle\geqslant 0</math> pour tout <math>x\in P\}.</math></center><br />C'est un [[Cône (analyse convexe)|cône]] convexe fermé non vide.

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

<center>
<math>\nabla f(x_*)\in(\operatorname{T}_{x_*}X)^+.</math>
</center>

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.

{{Ancre|cn1-générique}}{{Ancre|peano-kantorovitch}}
{{Théorème|CN1 de Peano-Kantorovitch|Si <math>x_*</math> est un minimum local de <math>(P_X)</math> et si <math>f</math> est dérivable en <math>x_*</math>, on a
<center>
<math>\forall d \in \operatorname{T}_{x_*} X\,:\quad f'(x_*) \cdot d \geqslant 0</math>,
</center>
ce qui s'écrit aussi
<center>
<math>\nabla f(x_*) \in (\operatorname{T}_{x_*}X)^+</math>.
</center>}}

On dit que <math>x_*</math> est un '''point stationnaire''' ou un '''point critique''' du problème <math>(P_X)</math>, 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é <math>f'(x;d)</math> la '''dérivée directionnelle''' de <math>f</math> en <math>x</math> dans la direction <math>d</math>, c'est-à-dire la limite lorsque <math>t\downarrow0</math> du quotient différentiel <math>(f(x+td)-f(x))/t</math>.

{{Théorème|CN1 lorsque <math>X</math> est convexe|Si l'ensemble admissible <math>X</math> est convexe, si <math>x_*</math> est un minimum local de <math>(P_X)</math> et si <math>f</math> admet des dérivées directionnelles en <math>x_*</math>, on a
<center>
<math>\forall x\in X\,:\quad f'(x_*) \cdot (x-x_*) \geqslant 0</math>.
</center>}}

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 [[Équivalence logique|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.

{{Théorème|CNS1 lorsque <math>(P_X)</math> est convexe|Si l'ensemble admissible <math>X</math> est convexe, si le critère <math>f</math> est convexe sur <math>X</math> et si <math>f</math> admet des dérivées directionnelles en <math>x_*</math>, alors <math>x_*</math> est un minimum de <math>(P_X)</math> si, et seulement si,
<center>
<math>\forall x\in X\,:\quad f'(x_*) \cdot (x-x_*) \geqslant 0</math>.
</center>}}

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.

== Problèmes d'optimisation sans contrainte ==

Le problème que l'on considère dans cette section est celui de minimiser la fonction <math>f</math> sur <math>\mathbb{E}</math> tout entier, problème que l'on écrit

<center>
<math>\inf_{x\in\mathbb{E}}\;f(x).</math>
</center>

Dès lors, l'ensemble admissible <math>X</math> est l'espace vectoriel <math>\mathbb{E}</math>.

=== Conditions du premier ordre sans contrainte ===

Le [[cône tangent]] à <math>\mathbb{E}</math> en <math>x_*\in\mathbb{E}</math> est l'espace <math>\mathbb{E}</math> tout entier. Comme le dual de <math>\mathbb{E}</math> est <math>\{0\}</math>, la [[#cn1-générique|CN1 générique]] exprime que le gradient <math>\nabla f(x_*)</math> est nul en un minimum local <math>x_*</math> de <math>f</math> sur <math>\mathbb{E}</math>. Cette condition d'optimalité est parfois appelée « équation de Fermat » pour rappeler [[Théorème de Fermat sur les points stationnaires|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 [[Isaac Newton|Newton]] et [[Gottfried Wilhelm Leibniz|Leibniz]]<ref>J. Mawhin, ''Analyse — Fondements, Techniques, Évolution'', De Boeck, 1992.</ref>.

{{Théorème|CN1 de Fermat|Si <math>x_*</math> est un minimum local de <math>f</math> sur <math>\mathbb{E}</math> et si <math>f</math> admet des dérivées directionnelles en <math>x_*</math>, on a
<center>
<math>\forall x\in \mathbb{E}\,:\quad f'(x_*;x-x_*) \geqslant 0</math>.
</center>
Si, de plus, <math>f</math> est dérivable en <math>x_*</math>, on a
<center>
<math>f'(x_*) =0\qquad\mbox{ou}\qquad\nabla f(x_*) =0</math>.
</center>|énoncé=Si <math>x_*</math> est un minimum local de <math>f</math> sur <math>\mathbb{E}</math> et si <math>f</math> admet des dérivées directionnelles en <math>x_*</math>, on a
<center>
<math>\forall x\in \mathbb{E}\,:\quad f'(x_*).(x-x_*) \geqslant 0</math>.
</center>
Si, de plus, <math>f</math> est dérivable en <math>x_*</math>, on a
<center>
<math>f'(x_*) =0\qquad\mbox{ou}\qquad\nabla f(x_*) =0</math>.
</center>}}

Lorsque <math>f</math> est convexe, ces conditions deviennent des conditions nécessaires et suffisantes d'optimalité ''globale'' de <math>x_*</math>.

{{Théorème|CNS1 pour une fonction convexe|Soient <math>f</math> une fonction ''convexe'' sur <math>\mathbb{E}</math> et <math>x_*\in\mathbb{E}</math>.
* Si <math>f</math> admet des dérivées directionnelles en <math>x_*</math>, alors <math>x_*</math> est un minimum global de <math>f</math> sur <math>\mathbb{E}</math> si, et seulement si,
<center>
<math>\forall x\in \mathbb{E}\,:\quad f'(x_*;x-x_*) \geqslant 0</math>.
</center>
* Si <math>f</math> est dérivable en <math>x_*</math>, alors <math>x_*</math> est un minimum global de <math>f</math> sur <math>\mathbb{E}</math> si, et seulement si,
<center>
<math>f'(x_*) =0\qquad\mbox{ou}\qquad\nabla f(x_*) =0</math>.
</center>|énoncé=Soient <math>f</math> une fonction ''convexe'' sur <math>\mathbb{E}</math> et <math>x_*\in\mathbb{E}</math>.
* Si <math>f</math> admet des dérivées directionnelles en <math>x_*</math>, alors <math>x_*</math> est un minimum global de <math>f</math> sur <math>\mathbb{E}</math> si, et seulement si,
<center>
<math>\forall x\in \mathbb{E}\,:\quad f'(x_*). (x-x_*) \geqslant 0</math>.
</center>
* Si <math>f</math> est dérivable en <math>x_*</math>, alors <math>x_*</math> est un minimum global de <math>f</math> sur <math>\mathbb{E}</math> si, et seulement si,
<center>
<math>f'(x_*) =0\qquad\mbox{ou}\qquad\nabla f(x_*) =0</math>.
</center>}}

=== Conditions du deuxième ordre sans contrainte ===

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

<center>
<math>\forall\,h\in\mathbb{E}:\qquad f''(x)\cdot(h,h)=\langle\nabla^2f(x)h,h\rangle.</math>
</center>

Rappelons également les notions de '''semi-définie positivité''' et '''définie positivité''' d'un opérateur auto-adjoint <math>A</math> sur <math>\mathbb{E}</math>, associées au produit scalaire de <math>\mathbb{E}</math>, qui sont utilisées dans les résultats ci-dessous :
* <math>A</math> est [[Matrice autoadjointe positive|semi-défini positif]] si <math>\langle Av,v\rangle\geqslant 0</math> pour tout vecteur <math>v\in\mathbb{E}</math>,
* <math>A</math> est [[Matrice définie positive|défini positif]] si <math>\langle Av,v\rangle>0</math> pour tout vecteur <math>v\in\mathbb{E}\setminus\{0\}</math>.

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.

{{Théorème|CN2 des problèmes sans contrainte|Si <math>f</math> est dérivable dans un voisinage d'un point <math>x_*\in\mathbb{E}</math> et deux fois dérivable en <math>x_*</math> et si <math>x_*</math> est un minimum local de <math>f</math> sur <math>\mathbb{E}</math>, alors <math>\nabla f(x_*) = 0</math> et <math>\nabla^2 f(x_*)</math> est semi-défini positif.}}
{{Théorème|CS2 des problèmes sans contrainte|Si <math>f</math> est dérivable dans un voisinage d'un point <math>x_*\in\mathbb{E}</math> et deux fois dérivable en <math>x_*</math> et si <math>\nabla f(x_*) = 0</math> et <math>\nabla^2 f(x_*)</math> est défini positif, alors <math>x_*</math> est un minimum local ''strict'' de <math>f</math> sur <math>\mathbb{E}</math>.}}

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 <math>\mathbb{E}=\mathbb{R}^n</math> est équipé du produit scalaire euclidien, ce système est formé de <math>n</math> équations (les dérivées partielles du critère) à <math>n</math> 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 <math>f</math>. 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
<!-- [FIGURE 1D] -->
* si <math>x_*</math> est un point stationnaire tel que <math>\nabla^2f(x_*)</math> n'est pas semi-défini positif, alors <math>x_*</math> n'est pas un minimum local (condition nécessaire),
* si <math>x_*</math> est un point stationnaire tel que <math>\nabla^2f(x_*)</math> est défini positif, alors <math>x_*</math> est un minimum local strict (condition suffisante).
On ne recouvre pas ainsi tous les cas, puisque l'on pourrait avoir un point stationnaire <math>x_*</math> avec une hessienne <math>\nabla^2f(x_*)</math> 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é.

== Problèmes d'optimisation avec contraintes d'égalité ==
=== Le problème (''P<sub>E</sub>'') ===

L'ensemble admissible du problème d'optimisation considéré dans cette section n'est pas l'espace <math>\mathbb{E}</math> 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é :

<center>
<math>X_E:=\{x\in \mathbb{E}:c(x)=0\}.</math>
</center>

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

<center>
<math>c: \mathbb{E} \to \mathbb{F},</math>
</center>

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

<center>
<math> n:=\dim \mathbb{E}\qquad\mbox{et}\qquad m:=\dim \mathbb{F}.</math>
</center>

Il sera souvent approprié de supposer qu'en la solution <math>x_*</math> recherchée, la [[jacobienne]] <math>c'(x_*)</math> de la contrainte vérifie

<center>
<math>c'(x_*)</math> est [[Surjection|surjective]].
</center>

Ceci requiert certainement d'avoir <math>m\leqslant n</math>, c'est-à-dire d'avoir moins de contraintes que de variables à optimiser. Lorsque cette hypothèse est vérifiée, l'ensemble admissible <math>X_E</math> est, dans un voisinage de <math>x_*</math>, une [[Variété (géométrie)|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 <math>n-m</math>.
<!-- FIGURE -->

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

<center>
<math>
(P_E) \quad \left\{ \begin{array}{l}
\inf\; f(x) \\ c(x) = 0,
\end{array} \right.
</math>
</center>

où <math>f : \mathbb{E} \to \mathbb{R}</math> en est le critère.

{{Théorème|Problème <math>(P_E)</math> convexe|On dit que le '''problème <math>(P_E)</math> est convexe''' si la contrainte <math>c</math> est [[Application affine|affine]] et si le critère <math>f</math> est [[Fonction convexe#Fonction convexe définie sur un espace vectoriel|convexe]] sur <math>X_E</math>.}}

L'ensemble admissible <math>X_E</math> d'un problème <math>(P_E)</math> convexe est donc un [[Espace affine#Sous-espaces affines|sous-espace affine]] de <math>\mathbb{E}</math>, donc un [[Ensemble convexe|convexe]].

=== Conditions du premier ordre avec contraintes d'égalité ===

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 <math>X_E</math> et en prenant ensuite son cône dual.

On note <math>\mathcal{N}(A)</math> le [[Application linéaire#Noyau et image|noyau]] et <math>\mathcal{R}(A)</math> l'[[Application linéaire#Noyau et image|image]] d'une application linéaire <math>A:\mathbb{E}\to\mathbb{F}</math> entre deux espaces euclidiens <math>\mathbb{E}</math> et <math>\mathbb{F}</math>. L'[[Opérateur adjoint|adjointe]] de <math>A</math> est l'application linéaire <math>A^*:\mathbb{F}\to\mathbb{E}</math> définie par la relation <math>\langle Au,v\rangle=\langle u,A^*v\rangle</math>, pour tout <math>u\in\mathbb{E}</math> et tout <math>v\in\mathbb{F}</math>. On rappelle qu'en dimension finie, on a

<center>
<math>\mathcal{N}(A)^\perp=\mathcal{R}(A^*)</math>.
</center>

Cette [[Opérateur adjoint#Orthogonalité|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 cône tangent à ''X<sub>E</sub>'' ====

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.

{{Théorème|Estimation du cône tangent <math>\operatorname{T}_xX_E</math>|Si <math>c: \mathbb{E} \to \mathbb{F}</math> est dérivable en <math>x \in X_E</math>, alors <math>\operatorname{T}_x X_E \subset \mathcal{N}(c'(x)).</math>}}

Dans l'inclusion <math>\operatorname{T}_x X_E \subset \mathcal{N}(c'(x))</math>, le cône tangent <math>\operatorname{T}_x X_E</math> ne dépend que de l'ensemble admissible <math>X_E</math>, alors que <math>\mathcal{N}(c'(x))</math> dépend de la fonction <math>c</math> utilisée pour définir <math>X_E</math>. Il peut y avoir plusieurs fonctions <math>c</math> définissant le même ensemble <math>X_E</math>. 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é <math>\operatorname{T}_x X_E = \mathcal{N}(c'(x))</math> a lieu. On dit alors que la ''contrainte'' <math>c</math> (léger [[abus de langage]], il faudrait dire la ''fonction <math>c</math> utilisée pour définir <math>X_E</math>'') est qualifiée en <math>x</math> (sous-entendu «pour représenter <math>X_E</math>»).

{{Théorème|Qualification d'une contrainte d'égalité|On dit que la contrainte <math>c : \mathbb{E} \to \mathbb{F}</math> est '''qualifiée''' en <math>x</math> (pour représenter <math>X_E</math>) si <math>c</math> est différentiable en <math>x</math> et si <math>\operatorname{T}_x X_E = \mathcal{N}(c'(x)).</math>}}

Voici le résultat principal assurant que la contrainte <math>c</math> est qualifiée en un point. On y retrouve la condition mentionnée ci-dessus assurant que <math>X_E</math> est une variété dans le voisinage <math>x</math>.

{{Théorème|Condition suffisante de qualification d'une contrainte d'égalité|Si <math>c: \mathbb{E}\to\mathbb{F}</math> est <math>C^1</math> dans un voisinage de <math>x\in X_E</math> et si <math>c'(x)</math> est surjective, alors <math>c</math> est qualifiée en <math>x.</math>}}

Voici une conséquence pratique de la notion de qualification de contrainte. Au lieu d'utiliser la fonction <math>c</math> pour représenter l'ensemble admissible <math>X_E</math>, on pourrait utiliser la fonction
<math>\tilde{c}:\mathbb{E}\to\mathbb{R}</math>, définie par <math>\tilde{c}(x)=\|c(x)\|^2/2</math>, puisque <math>\tilde{c}(x)=0</math> si, et seulement si, <math>c(x)=0</math>. 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 <math>\tilde{c}</math> a encore moins de chance d'être qualifiée que <math>c</math> puisque <math>\nabla\tilde{c}(x)=c'(x)^*c(x)=0</math> en un point <math>x\in X_E</math> et donc <math>\mathcal{N}(\tilde{c}'(x))=\mathbb{E}</math>, qui est le plus souvent trop grand. Il n'est donc, en général, pas recommandé de remplacer <math>c</math> par <math>\tilde{c}</math>.

==== Condition de Lagrange ====

Lorsque la contrainte est qualifiée, le cône tangent est le ''sous-espace vectoriel'' <math>\mathcal{N}(c'(x))</math>, dont le dual est alors son orthogonal <math>\mathcal{N}(c'(x))^\perp=\mathcal{R}(c'(x)^*)</math>. Par la [[#cn1-générique|CN1 générique]], le gradient de <math>f</math> en un minimum local de <math>f</math> sur <math>X_E</math> appartient à ce dernier ensemble, ce qui conduit aux conditions nécessaires d'optimalité du premier ordre (CN1) de [[Joseph-Louis Lagrange|Lagrange]]<ref>{{Chapitre |prénom= Joseph-Louis |nom=Lagrange | titre = Manière plus simple et plus générale de faire usage de la formule de l'équilibre donnée dans la section deuxième   | titre ouvrage = Mécanique analytique. Tome premier. pages = 77-112 | lire en ligne = https://gallica.bnf.fr/ark:/12148/bpt6k229946s/f95 | consulté le = 10/03/2011}}</ref>.

{{Théorème|CN1 de [[Joseph-Louis Lagrange|Lagrange]]|Soit <math>x_*</math> un minimum local de  <math>(P_E)</math>. Supposons que <math>f</math> et <math>c</math> soient dérivables en <math>x_*</math> et que la contrainte  <math>c</math> soit qualifiée en <math>x_*</math> au sens de la définition ci-dessus. Alors, il existe un vecteur <math>\lambda_* \in \mathbb{F}</math> tel que
<center>
<math>\nabla f(x_*) + c'(x_*)^* \lambda_* = 0,</math>
</center>
où <math>\nabla f(x_*)</math> est le gradient de  <math>f</math> en  <math>x_*</math> et <math>c'(x_*)^*</math> est l'opérateur adjoint de la jacobienne <math>c'(x_*)</math> pour les produits scalaires donnés sur  <math>\mathbb{E}</math> et  <math>\mathbb{F}</math>. Le vecteur <math>\lambda_*</math> est unique si <math>c'(x_*)</math> est
surjective.}}

Ce résultat, parfois appelé '''méthode du multiplicateur de Lagrange''', est attribué à [[Joseph-Louis Lagrange|Lagrange]] qui l'énonça dans sa ''Méchanique analytique'' (1788). On en trouve toutefois déjà des traces dans des travaux d'[[Leonhard Euler|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 <math>(P_E).</math> <ref>{{en}} C.B. Boyer (1968). ''A History of Mathematics''. Princeton University Press, Princeton, New Jersey.</ref>{{,}}<ref>V. Alexeev, V. Tikhomirov, S. Fomine (1982). ''Commande Optimale''. Mir, Moscou.</ref>

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.

{{Théorème|Lagrangien du problème <math>(P_E)</math>|On appelle '''lagrangien du problème <math>(P_E)</math>''', la fonction <math>\ell : \mathbb{E} \times \mathbb{F} \to \mathbb{R}</math> définie en <math>(x,\lambda)\in \mathbb{E} \times \mathbb{F}</math> par
<center>
<math>
\ell (x,\lambda) := f(x) + \langle\lambda,c(x)\rangle.
</math>
</center>
Le vecteur <math>\lambda</math> porte le nom de '''multiplicateur (de Lagrange)''' ou '''variable duale'''.}}

La variable <math>x</math> est aussi appelée '''variable primale''' ; quant au couple <math>(x,\lambda)</math>, 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 <math>\mathbb{F}</math>. Sous les hypothèses du résultat ci-dessus, les conditions nécessaires d'optimalité du premier ordre peuvent maintenant s'écrire comme suit

<center>
<math>\left\{\begin{array}{l} \nabla_x \ell (x_*, \lambda_*) = 0 \\ c(x_*) = 0 \end{array}\right.\qquad\mbox{ou}\qquad\nabla_{(x,\lambda)} \ell (x_*, \lambda_*) = 0.</math>
</center>

On note ici <math>\nabla_x</math> [resp. <math>\nabla_{(x,\lambda)}</math>] le gradient par rapport à <math>x</math> [resp. à <math>(x,\lambda)</math>]. Ce système (non linéaire, en toute généralité) permet souvent de calculer une ''solution'' du problème d'optimisation <math>(P_E)</math>. En réalité, cette ''solution'' est ce qu'on appelle 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 le type de solution recherché), sauf si celui-ci est convexe.

{{Théorème|CS1 pour un problème <math>(P_E)</math> convexe|Supposons que le problème <math>(P_E)</math> soit convexe, que <math>f</math> soit dérivable en <math>x_*\in\mathbb{E}</math> et qu'il existe un multiplicateur <math>\lambda_*\in \mathbb{F}</math> tel que <math>(x_*,\lambda_*)</math> vérifie
<center>
<math>\left\{\begin{array}{l} \nabla_x \ell (x_*, \lambda_*) = 0 \\ c(x_*) = 0.\end{array}\right.</math>
</center>
Alors <math>x_*</math> est un ''minimum global'' de <math>(P_E)</math>.}}

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.

==== Minimisation d'une fonction de ''n'' variables soumise à ''m'' contraintes ====

Il est utile de spécifier les conditions d'optimalité de Lagrange lorsque <math>\mathbb{E}=\mathbb{R}^n</math>, <math>\mathbb{F}=\mathbb{R}^m</math> et que l'on munit ces espaces du produit scalaire euclidien
<center>
<math>
\langle u,v\rangle=u^{\!\top\!} v=\sum_i\,u_iv_i.
</math>
</center>
Il y a alors <math>n</math> variables <math>x_1, \ldots, x_n</math> à optimiser et les <math>m</math> contraintes du problème <math>(P_E)</math> sont données explicitement au moyen de <math>m</math> fonctions <math>c_i:\mathbb{R}^n\to\mathbb{R}</math> :
<center>
<math>
c_1(x_1,\ldots,x_n)=0, \quad\ldots,\quad c_m(x_1,\ldots,x_n)=0.
</math>
</center>
Le lagrangien du problème s'écrit
<center>
<math>
\ell(x,\lambda)=f(x)+\lambda^{\!\top\!} c(x)=
f(x)+\sum_{i=1}^m\,\lambda_i c_i(x).
</math>
</center>
Observons que le multiplicateur de Lagrange <math>\lambda\in\mathbb{R}^m</math> a autant de composantes qu'il y a de contraintes ; chacune des composantes <math>\lambda_i</math> étant associée à une contrainte <math>c_i</math> ; on dit d'ailleurs que le multiplicateur <math>\lambda_i</math> est associé à la contrainte <math>c_i</math>. Si on utilise <math>\nabla</math> pour désigner le gradient d'une fonction réelle de <math>n</math> 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 <math>n+m</math> équations à <math>n+m</math> inconnues <math>(x_*,\lambda_*)</math> :
<center>
<math>
\nabla f(x_*)+\sum_{i=1}^m(\lambda_*)_i\nabla c_i(x_*)=0\in\mathbb{R}^n
\qquad\mbox{et}\qquad
c(x_*) = 0 \in\mathbb{R}^m.
</math>
</center>
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) :
<!-- FIGURE -->

<center>
<math>
f(x) = x_1+x_2,
\quad
c_1(x) = \frac{1}{2} \left(x_1^2 + (x_2-1)^2 - 1\right)
\quad\mbox{et}\quad
c_2(x) = \frac{1}{2} \left(x_1^2 + (x_2+1)^2 - 1\right).
</math>
</center>

L'unique point admissible est le point <math>x_*=(0,0)</math>, 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 à <math>\{(0,0)\}</math> alors que le noyau de la jacobienne des contraintes est <math>\{d\in\mathbb{R}^2:d_2=0\}</math> (on note par ailleurs que cette jacobienne, qui est une matrice <math>2\times 2</math> 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 <math>f</math> en la solution ne peut être combinaison linéaire des gradients des contraintes (ces derniers sont linéairement dépendants) :
<center>
<math>
\nabla f(x_*)=\begin{pmatrix}1\\1\end{pmatrix},
\qquad
\nabla c_1(x_*)=\begin{pmatrix}0\\-1\end{pmatrix}
\qquad\mbox{et}\qquad
\nabla c_2(x_*)=\begin{pmatrix}0\\1\end{pmatrix}.
</math>
</center>

=== Conditions du deuxième ordre avec contraintes d'égalité ===

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 <math>\mathbb{E}</math> 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.

{{Théorème|CN2 pour le problème <math>(P_E)</math>|Soit <math>x_*\in \mathbb{E}</math> un minimum local de <math>(P_E)</math>. Supposons que <math>f</math> et <math>c</math> soient dérivables dans un voisinage de <math>x_*</math> et deux fois dérivables en <math>x_*</math> et que la contrainte <math>c</math> soit qualifiée en <math>x_*</math>. Alors, il existe un multiplicateur <math>\lambda_* \in \mathbb{F}</math> tel que l'on ait
<math>\nabla_x\ell(x_*,\lambda_*)=0</math> et
<center>
<math>
\forall d \in \mathcal{N}(c'(x_*))\,:\quad \langle \nabla_{xx}^2\ell(x_*,\lambda_*) d,d\rangle \geqslant 0.
</math>
</center>}}

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''').

{{Théorème|CS2 pour le problème <math>(P_E)</math>|Supposons que <math>f</math> et <math>c</math> soient dérivables dans un voisinage de <math>x_* \in \mathbb{E}</math> et deux fois dérivables en <math>x_*</math>. Supposons que <math>c(x_*) = 0</math> et qu'il existe <math>\lambda_* \in \mathbb{F}</math> tel que l'on ait <math>
\nabla_x \ell(x_*, \lambda_*) = 0</math> et
<center>
<math>
\forall d \in \mathcal{N}(c'(x_*)) \setminus \{0\}\,:\quad
\langle \nabla_{xx}^2\ell(x_*,\lambda_*) d,d\rangle > 0.
</math>
</center>
Alors <math>x_*</math> est un minimum local strict de <math>(P_E)</math>.}}

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 <math>L_*:=\nabla_{xx}^2\ell(x_*,\lambda_*)</math> dans le [[Application linéaire#Noyau et image|noyau]] de <math>c'(x_*)</math> 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 <math>B:\mathbb{R}^p\to\mathbb{E}</math> tel que <math>c'(x_*)B=0,</math> avec <math>p=n-\dim\mathcal{R}(c'(x_*)).</math> Il suffit alors de vérifier la (semi-)définie positivité de <math>B^*L_*B</math>, ce qui peut se faire en temps polynomial par des techniques d'algèbre linéaire.

=== Interprétation marginaliste des multiplicateurs de Lagrange ===

=== Exemple : vecteurs propres et quotient de Rayleigh ===

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

'''''Le problème d'optimisation'''''

Dans ce but, on considère le [[quotient de Rayleigh]] <math>q_r:\mathbb{E}\to\mathbb{R}</math>, défini en <math>x\in\mathbb{E}\setminus\{0\}</math> par
<center>
<math>
q_r(x):=\frac{\langle Ax,x\rangle}{\|x\|^2}.
</math>
</center>
Comme <math>q_r</math> est constant le long des rayons issus de zéro, il revient au même de minimiser la fonction quadratique <math>q:\mathbb{E}\to\mathbb{R}</math> définie en <math>x\in\mathbb{E}</math> par
<center>
<math>
q(x):=\frac{1}{2}\,\langle Ax,x\rangle,
</math>
</center>
sur la sphère unité <math>S:=\{x\in\mathbb{E}:\|x\|=1\}.</math> On considère donc le problème d'optimisation avec une unique contrainte d'égalité suivant
<center>
<math>
\inf_{\|x\|=1}\;q(x).
</math>
</center>
Ce problème a toujours une solution (le critère est continu et, comme <math>\mathbb{E}</math> est de dimension finie, <math>S</math> est compact). Calculons les points stationnaires du problème d'optimisation.

'''''Conditions d'optimalité du premier ordre'''''

La fonction <math>x\mapsto\|x\|-1</math> 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 <math>x\mapsto c(x):=(1-\|x\|^2)/2</math>, qui se dérive plus facilement. Cette contrainte est qualifiée en tout point admissible, car sa jacobienne <math>h\mapsto -\langle x,h\rangle</math> est surjective si <math>x\ne0</math>. Pour calculer la solution du problème d'optimisation, on introduit son lagrangien, qui prend en <math>(x,\lambda)\in\mathbb{E}\times\mathbb{R}</math> la valeur
<center>
<math>
\ell(x,\lambda)=\frac{1}{2}\langle Ax,x\rangle+\frac{\lambda}{2}(1-\|x\|^2).
</math>
</center>
Comme il y a une seule contrainte, il y a un seul multiplicateur <math>\lambda</math>.

Les conditions d'optimalité de Lagrange s'écrivent
<center>
<math>
\left\{\begin{array}{l}
Ax=\lambda x\\
\|x\|=1.
\end{array}\right.
</math>
</center>
Dès lors, <math>\bar{x}</math> est un point stationnaire de multiplicateur <math>\bar{\lambda}</math> si, et seulement si, <math>\bar{x}</math> est un vecteur propre unitaire de <math>A</math>, de valeur propre <math>\bar{\lambda}</math>. Ce multiplicateur est aussi la valeur du critère en <math>\bar{x}</math>, puisque <math>q(\bar{x})=\langle A\bar{x},\bar{x}\rangle=\bar{\lambda}\|\bar{x}\|^2=\bar{\lambda}</math>. Dès lors, une solution du problème d'optimisation est un vecteur propre unitaire de valeur propre minimale. Si au lieu de minimiser <math>\langle Ax,x\rangle</math>, on minimisait <math>-\langle Ax,x\rangle</math> ou on ''maximisait'' <math>\langle Ax,x\rangle</math>, 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 <math>(\bar{x},\bar{\lambda})</math> du problème d'optimisation est l'opérateur auto-adjoint <math>(A-\bar{\lambda} I)</math> sur <math>\mathbb{E}.</math> Comme <math>\bar{\lambda}</math> est la valeur minimale de <math>q</math> sur la sphère unité, on a <math>\langle Ax,x\rangle\geqslant\bar{\lambda}</math> pour tout vecteur unitaire <math>x.</math> On peut en déduire que <math>\langle(A-\bar{\lambda}I)x,x\rangle\geqslant 0</math> pour tout vecteur <math>x\in\mathbb{E},</math> ce qui signifie que la hessienne du lagrangien <math>A-\lambda I</math> est semi-définie positive dans tout l'espace <math>\mathbb{E}</math>, 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 <math>(\bar{x},\bar{\lambda})</math> vérifie les CS2, alors <math>\bar{x}</math> est un vecteur propre de <math>A</math> de valeur propre <math>\bar{\lambda}</math> ; de plus <math>\langle Ax,x\rangle>\langle A\bar{x},\bar{x}\rangle=\bar{\lambda}</math>, pour tout vecteur unitaire <math>x</math>, voisin mais différent de <math>\bar{x}</math>. On en déduit aisément que <math>\langle Ax,x\rangle>\bar{\lambda}</math> pour tout <math>x</math> unitaire différent de <math>\pm\bar{x}</math> (on peut par exemple prendre <math>t\in{]0,1]}</math> assez petit pour que <math>x_t/\|x_t\|</math>, avec <math>x_t:=(1-t)\bar{x}+tx</math>, soit voisin mais différent de <math>\bar{x}</math> et développer la relation <math>\langle Ax_t,x_t\rangle>\bar{\lambda}\|x_t\|^2</math> qui en résulte). On en déduit que <math>\bar{\lambda}</math> 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 <math>A</math> est simple, les CS2 sont vérifiées.

'''''Résultats obtenus'''''

{{Théorème|Vecteurs propres et quotient de Rayleigh|Soit <math>\mathbb{E}</math> un espace euclidien et <math>A:\mathbb{E}\to\mathbb{E}</math> une application linéaire ''auto-adjointe''. On considère le problème d'optimisation suivant :
<center>
<math>
\inf_{\|x\|=1}\;\langle Ax, x\rangle.
</math>
</center>
* Un vecteur unitaire est un vecteur propre de <math>A</math> si, et seulement si, c'est un ''point stationnaire'' de ce problème ; les multiplicateurs associés sont les valeurs propres correspondantes.
* Un vecteur est vecteur propre unitaire de valeur propre minimale si, et seulement si, il est ''solution'' de ce problème.
* Les conditions ''suffisantes'' d'optimalité du second ordre de ce problème sont vérifiées en une solution si, et seulement si, la valeur propre associée à cette solution est simple}}

== Problèmes d'optimisation avec contraintes d'égalité et d'inégalité ==

=== Le problème (''P<sub>EI</sub>'') ===

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
<center>
<math>
(P_{EI}) \quad \left\{ \begin{array}{l}
\inf\,  f(x) \\
c_i (x) = 0, \quad i \in E \\
c_i(x) \leqslant 0, \quad i \in I.
\end{array} \right.
</math>
</center>
Cette écriture exprime le fait que l'on cherche à minimiser un critère <math>f:\mathbb{E}\to\mathbb{R}</math> défini sur un [[espace euclidien]] <math>\mathbb{E}</math> dont l'argument <math>x</math>, 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 <math>c_i:\mathbb{E}\to\mathbb{R}</math>. Le produit scalaire de l'espace euclidien est noté <math>\langle\cdot,\cdot\rangle</math>. On y trouve des contraintes d'égalité et d'inégalité en nombre fini, repérées par des ensembles finis d'indices <math>E</math> et  <math>I</math>, dont le [[Cardinalité (mathématiques)|cardinal]] est noté 
<center>
<math>m_E:=|E| \qquad\mbox{et}\qquad m_I:=|I| </math>.
</center>
Le nombre total de contraintes est noté <math>m:=m_E+m_I</math>.

Il est commode de supposer que les ensembles d'indices <math>E</math> et <math>I</math> forment une [[Partition (mathématiques)|partition]] de l'ensemble des <math>m</math> premiers entiers <math>\{1, \ldots, m\}</math> :
<center>
<math>
E \cup I=\{1, \ldots, m\} \qquad\mbox{et}\qquad E \cap I = \varnothing.
</math>
</center>
Si <math>v\in \mathbb{R}^m</math>, on note <math>v_E</math> le vecteur de <math>\mathbb{R}^{m_E}</math> formé des composantes <math>v_i</math> de <math>v</math> avec <math>i\in E</math>. De même pour <math>v_I</math>. On peut alors rassembler les fonctions réelles <math>c_i</math> en une seule fonction <math>c:\mathbb{E}\to\mathbb{R}^m</math>, dont les composantes <math>c_E</math> et <math>c_I</math> sont utilisées pour définir les contraintes d'égalité et d'inégalité.

L'ensemble admissible de <math>(P_{EI})</math> est noté
<center>
<math>
X_{EI}:=\{x\in \mathbb{E}:c_E(x)=0, c_I(x)\leqslant 0\}.
</math>
</center>
Ici et ci-dessous, les ''inégalités vectorielles'' doivent être comprises composante par composante : pour un vecteur <math>v</math>, <math>v\leqslant 0</math> signifie que <math>v_i\leqslant 0</math> pour tout indice <math>i</math>. Si en un point admissible <math>x</math>, <math>c'(x)</math> est surjective, cet ensemble se présente autour de <math>x</math> comme une partie de la [[Variété (géométrie)|variété]] <math>\{z\in\mathbb{E}:c_E(z)=0\}</math> formée des points qui vérifient aussi l'inégalité <math>c_I(z)\leqslant 0</math>.
<!--
FIGURE. Une image idéalisée de cet ensemble pourrait être celle représentée ci-dessus. Notons que rien n'impose que la solution soit sur la frontière de <math>X_{EI}</math> comme dans la figure, mais c'est dans ce cas que le problème est le plus complexe à analyser.
-->

{{Ancre|problème-pei-convexe}}
{{Théorème|Problème <math>(P_{EI})</math> convexe|On dit que le '''problème <math>(P_{EI})</math> est convexe''' si la contrainte d'égalité <math>c_E</math> est affine, si les contraintes d'inégalité <math>c_i</math> (<math>i\in I</math>) sont convexes et si le critère <math>f</math> est convexe sur <math>X_{EI}.</math>}}

L'ensemble admissible <math>X_{EI}</math> d'un problème <math>(P_{EI})</math> convexe est clairement [[Ensemble convexe|convexe]].

Comme la [[#cn1-générique|CN1 générique]] l'a montré, l'écriture des conditions d'optimalité du premier ordre passe par la détermination du cône tangent à l'ensemble admissible. Ce cône tangent en <math>x</math> est un concept ''local'', dans le sens où une modification de l'ensemble admissible en dehors d'un voisinage de <math>x</math> n'aura pas d'incidence sur le cône tangent en ce point. Dès lors si une contrainte d'inégalité prend une valeur strictement négative en <math>x</math>, disons <math>c_i(x)<0</math>, une perturbation de cette contrainte ne modifiera pas l'ensemble admissible dans le voisinage de <math>x.</math> Il est donc nécessaire de pouvoir nommer les contraintes d'inégalité qui sont nulles au point considéré, ce qui conduit à la notion suivante.

{{Théorème|Contrainte active et inactive|On dit qu'une contrainte d'égalité ou d'inégalité <math>c_i</math> est '''active''' en <math>x</math> si <math>c_i(x) = 0</math>. On note
<center>
<math>I^0(x)\equiv I^0_x:= \{i \in I : c_i (x) = 0\}
</math>
</center>
l'ensemble des indices des contraintes d'inégalité actives en <math>x</math>. On adopte la notation simplifiée <math>I^0_*:=I^0(x_*).</math> Une contrainte d'inégalité qui n'est pas active en un point donné, y est dite '''inactive'''.}}

Les problèmes d'optimisation avec contraintes d'inégalité sont considérablement plus difficiles à analyser et à résoudre numériquement (un calcul analytique, sur papier, est rarement possible et d'ailleurs souvent difficile lui aussi) que les problèmes rencontrés jusqu'ici. Lorsqu'il n'y a que des contraintes d'égalité, la compréhension du problème repose sur l'[[Analyse (mathématiques)|analyse mathématique]] classique, en particulier sur le [[théorème des fonctions implicites]], ce qui explique que les conditions de Lagrange sont en général vues dans un cours de calcul différentiel et font ainsi partie du bagage de beaucoup de mathématiciens ou d'autres scientifiques. La situation est différente lorsque des contraintes d'inégalité sont présentes, car il faut alors faire appel à des outils spécifiques, essentiellement ceux de l'[[analyse convexe]], moins souvent enseignés. Par ailleurs, numériquement, la difficulté principale provient du fait que, d'une manière ou d'une autre, le calcul de la solution détermine forcément les contraintes qui sont actives en cette solution. Si ces contraintes actives étaient connues, on pourrait se ramener au cas des problèmes avec seulement des contraintes d'égalité lisses. Or il y a <math>2^{m_I}</math> manières de rendre les <math>m_I</math> contraintes d'inégalité actives. C'est à ce nombre exponentiel que l'on fait allusion lorsque l'on parle de la '''combinatoire des problèmes d'optimisation avec contraintes d'inégalité'''. Celle-ci est redoutable et en rapport direct avec la [[Problème P = NP|conjecture ''P = NP'']], puisqu'un problème d'[[optimisation quadratique]] non convexe (i.e., un problème avec un critère quadratique non convexe et des contraintes affines) est [[NP-hard|NP ardu]]. On est donc en présence d'un problème pour lequel il est vraisemblable que le '''principe de conservation des ennuis''' s'applique ; on veut dire par là que la difficulté du problème ne peut être éliminée en lui trouvant une autre formulation équivalente. Ainsi, on pourrait penser simplifier le problème en reformulant les contraintes d'inégalité par l'une des contraintes d'égalité apparemment plus simples et équivalentes suivantes
<center>
<math>
\max(0,c_I(x))=0
\qquad\mbox{ou}\qquad
\|\max(0,c_I(x))\|^2=0.
</math>
</center>
Cependant la première contrainte est non lisse et la seconde, bien qu'une fois différentiable, n'est en général pas qualifiée dans le sens discuté [[#Le cône tangent à XEI|ci-dessous]].

=== Conditions du premier ordre pour (''P<sub>EI</sub>'') ===

Si les conditions nécessaires d'optimalité des problèmes avec contraintes d'égalité ont été établies au {{XVIIIe siècle}}, celles des problèmes avec contraintes d'inégalité sont beaucoup plus récentes, puisqu'elles datent du milieu du {{XXe siècle}}. Il est vraisemblable que le besoin d'une analyse fine de ces questions ait été stimulé par l'augmentation des moyens de calcul. Le développement de l'[[analyse convexe]] a aussi permis de poser la théorie sur des bases solides, notamment avec le [[lemme de Farkas]]<ref>{{de}} J. Farkas, ''[http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN243919689_0124&DMDID=dmdlog4 Theorie der einfachen Ungleichungen]'', [[Journal für die reine und angewandte Mathematik]], 124 (1902) {{p.|1-27}}</ref> qui sera ci-dessous une des clés permettant de passer de la version géométrique à la version analytique des conditions d'optimalité du premier ordre.

==== Le cône tangent à ''X<sub>EI</sub>'' ====

Le résultat suivant permet d'affirmer que le cône tangent est inclus dans le '''cône linéarisant''', noté <math>\operatorname{T}'_xX_{EI}</math> et défini ci-dessous ; il lui sera égal dans les bons cas.

{{Théorème|Estimation du cône tangent <math>\operatorname{T}_xX_{EI}</math>|Si <math>x \in X_{EI}</math> et si <math>c_{E\cup I^0(x)}</math> est dérivable en <math>x</math>, alors
<center>
<math>
\operatorname{T}_x X_{EI} \subset \operatorname{T}'_xX_{EI}:=\{d \in \mathbb{E} : c'_E(x)\cdot d = 0, \; c'_{I^0(x)} (x) \cdot d \leqslant 0\}.
</math>
</center>}}

Observons que, comme annoncé, seules les contraintes d'inégalité ''actives'' interviennent dans l'estimation du cône tangent qu'est le cône linéarisant. On retrouverait le noyau de la jacobienne des contraintes s'il n'y avait que des contraintes d'égalité.

On peut faire, sur l'inclusion précédente, les mêmes remarques que celles sur l'estimation du cône tangent à des contraintes d'égalité par le noyau de la jacobienne de ces contraintes : <math>\operatorname{T}_x X_{EI}</math> ne dépend que de l'ensemble admissible <math>X_{EI}</math>, pas de la manière de le décrire par la fonction <math>c</math>, alors que <math>\operatorname{T}'_x X_{EI}</math> dépend manifestement de <math>c</math>. Il peut y avoir plusieurs fonctions <math>c</math> définissant le même ensemble admissible et, 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é <math>\operatorname{T}_x X_{EI} = \operatorname{T}'_xX_{EI}</math> a lieu ; d'ailleurs le premier cône est difficile à calculer s'il n'est égal au second, alors que l'on dispose d'une formule explicite pour le second. On introduit donc la notion de qualification de (fonctions définissant les) contraintes suivante.

{{Théorème|Qualification de contraintes d'égalité et d'inégalité|On dit que les contraintes <math>c : \mathbb{E} \to \mathbb{R}^m</math> du problème d'optimisation <math>(P_{EI})</math> sont '''qualifiées''' en <math>x</math> (pour représenter <math>X_{EI}</math>) si <math>c_{E\cup I^0(x)}</math> est différentiable en <math>x</math> et si <math>\operatorname{T}_x X_{EI} = \operatorname{T}'_xX_{EI}.</math>}}

En général, le cône tangent et le cône linéarisant diffèrent, car le premier n'est pas nécessairement convexe, alors que le second l'est (c'est un cône polyédrique convexe). Par ailleurs, la notion de qualification ''des'' contraintes a un aspect ''global'', dans le sens où elle porte sur toutes les fonctions définissant le problème d'optimisation ; il n'est pas question d'utiliser cette notion fonction par fonction parce que le cône tangent à une intersection d'ensembles n'est pas égal à l'intersection des cônes tangents à ces ensembles (voir l'[[Cône tangent#Propriétés|article sur le cône tangent]]).

Comme pour les problèmes avec contraintes d'égalité, il n'est presque jamais judicieux de remplacer les contraintes de <math>(P_{EI})</math> par l'unique contrainte d'égalité équivalente <math>\tilde{c}(x)=0</math>, où <math>\tilde{c}:\mathbb{E}\to\mathbb{R}</math> est définie par
<center>
<math>
\tilde{c}(x)=\frac{1}{2}\|c_E(x)\|_2^2+\frac{1}{2}\|c_I(x)^+\|_2^2,
</math>
</center>
même si le fait de n'avoir qu'une seule contrainte est ''a priori'' attrayant. Cette dernière contrainte a, en effet, l'inconvénient de n'être pratiquement jamais qualifiée, puisque <math>\nabla\tilde{c}(x)= c'_E(x)^*c_E(x)+c_I'(x)^* c_I(x)^+</math> est nul en tout point admissible. Dès lors, pour cette contrainte, <math>\operatorname{T}'_xX_{EI}=\mathbb{E}</math>, qui est pratiquement toujours trop grand, plus grand que <math>\operatorname{T}_xX_{EI}</math>.

Vérifier si les contraintes sont qualifiées est une tâche difficile. Cela requiert le calcul du cône tangent, que l'on voudrait surtout éviter s'il n'est pas identique au cône linéarisant. On connaît un certain nombre de conditions ''suffisantes'' de qualification de contraintes, qui sont plus subtiles que lorsque seules des contraintes d'égalité sont présentes. Elles sont présentées dans l'article [[Qualification de contraintes]].

==== Conditions de Karush, Kuhn et Tucker (KKT) ====
{{Voir homonymes|KKT}}

On suppose dans cette section que les contraintes du problème <math>(P_{EI})</math> sont qualifiés, au sens précisé dans la section précédente. Si l'on veut trouver une expression plus explicite de la condition nécessaire d'optimalité du première ordre en <math>x</math>, à savoir <math>\nabla f(x)\in(\operatorname{T}_xX_{EI})^+</math>, il faut calculer le cône dual du cône tangent, que l'on suppose donc égal au cône dual du cône linéarisant <math>(\operatorname{T}'_xX_{EI})^+</math>. Il s'agit donc de calculer le dual d'un cône convexe polyédrique. Le [[lemme de Farkas]] fournit une réponse à cette question. Une version légèrement généralisée est donnée ci-dessous.

{{Théorème|Lemme de Farkas généralisé|Soient <math>\mathbb{E}</math> et <math>\mathbb{F}</math> deux espaces euclidiens, <math>A:\mathbb{E}\to \mathbb{F}</math> une application linéaire et <math>K</math> un cône convexe non vide de <math>\mathbb{E}</math>. Alors
<center>
<math>
\{y\in \mathbb{F} : A^*y\in K^+\}^+ = \operatorname{adh}\{Ax : x\in K\}.
</math>
</center>}}

On ne peut pas se passer de l'adhérence dans le membre de droite de l'identité car le cône <math>A(K)</math> n'est pas nécessairement fermé (même si <math>K</math> est fermé) alors que, en tant que cône dual, le cône du membre de gauche est toujours fermé. Signalons que si <math>K</math> est un cône convexe ''polyédrique'' (comme l'[[Orthant|orthant positif]] d'un certain <math>\mathbb{R}^p</math>), alors <math>A(K)</math> est un [[polyèdre]] convexe, donc un fermé ; dans ce cas, on peut ôter l'adhérence dans le membre de droite.

Simplifions les notations en posant <math>J:=I^0(x)</math>, <math>A_E:=c'_E(x)</math> et <math>A_J:=c'_J(x)</math>. On peut établir une expression ''duale'' du cône
<center>
<math>
(\operatorname{T}'_xX_{EI})^+:=\{d \in \mathbb{E} : A_E d = 0, \; A_J  d \leqslant 0\}^+,
</math>
</center>
en utilisant le lemme de Farkas généralisé avec
* <math>\mathbb{E}=\mathbb{R}^{m_E}\times\mathbb{R}^{m_J}</math> muni du produit scalaire euclidien,
* <math>\mathbb{F}=\mathbb{R}^n</math> muni du produit scalaire euclidien,
* <math>A=\begin{pmatrix}A_E^{\!\top}&A_J^{\!\top}\end{pmatrix}:(\lambda_E,\lambda_J)\in\mathbb{E}\mapsto A_E^{\!\top\!}\lambda_E+A_J^{\!\top\!}\lambda_J \in\mathbb{F}</math>,
* <math>K=\mathbb{R}^{m_E}\times\mathbb{R}^{m_J}_-</math>.
On a noté <math>\mathbb{R}^{m_J}_-:=\{\lambda_J\in\mathbb{R}^{m_J}: \lambda_J\leqslant 0\}</math>. On vérifie facilement que
<center>
<math>
K^+=\{0\}\times \mathbb{R}^{m_J}_-
\qquad\mbox{et}\qquad
A^*=\begin{pmatrix}A_E\\A_J\end{pmatrix}.
</math>
</center>
Par le lemme de Farkas, on trouve alors la [[représentation duale]] du cône linéarisant suivante (il n'est pas nécessaire de prendre l'adhérence de l'ensemble obtenu, car il est fermé par sa polyédricité)
<center>
<math>
(\operatorname{T}'_xX_{EI})^+=\{A_E^{\!\top\!}\mu_E+A_J^{\!\top\!}\mu_J:\mu_E\mathbb{R}^{m_E},~\mu_J\in\mathbb{R}^{m_J}_-\}.
</math>
</center>
On en déduit les conditions nécessaires d'optimalité du premier ordre suivantes, dites de Karush, Kuhn et Tucker (KKT). Elles sont fondamentales.

{{Ancre|cn1-KKT}}
{{Théorème|CN1 de Karush, Kuhn et Tucker|Soit <math>x_*</math> un minimum local de <math>(P_{EI})</math>. Supposons que <math>f</math> et <math>c_{E\cup I^0_*}</math> soient dérivables en <math>x_*</math> et que les contraintes soient qualifiées en <math>x_*</math>. Alors, il existe <math>\lambda_* \in \mathbb{R}^m</math> tel que l'on ait
<center><math>
(\mbox{KKT})\quad
\left\{\begin{array}{cl}
(a)&
\nabla f(x_*) + c'(x_*)^* \lambda_* = 0 \\
(b)&
c_E(x_*) = 0 \\
(c)&
c_I(x_*) \leqslant 0 \\
(d)&
(\lambda_*)_I \geqslant 0 \\
(e)&
(\lambda_*)_I^{\!\top\!} c_I(x_*) = 0,
\end{array} \right.
</math></center>
où <math>\nabla f(x_*)</math> est le gradient de <math>f</math> en <math>x_*</math> et <math>c'(x_*)^*: \mathbb{R}^m\to \mathbb{E}</math> est l'opérateur adjoint de la jacobienne <math>c'(x_*)</math> pour le produit scalaire donné sur <math>\mathbb{E}</math>.}}

Un point <math>x_*</math> vérifiant les conditions (KKT) ci-dessus est dit '''stationnaire''' pour le problème <math>(P_{EI})</math>.

Les conditions nécessaires d’optimalité ci-dessus ont longtemps été attribuées à Kuhn et Tucker (1951<ref>{{en}} H.W. Kuhn, A.W. Tucker (1951). Nonlinear programming. In J.Neyman, éditeur, ''Proceedings of the second Berkeley Symposium on Mathematical Studies and Probability'', pages 481–492. University of California Press, Berkeley, California.</ref>). Après bien des années, on constata que ces conditions avaient déjà été données par Karush (1939<ref>{{en}} W.E. Karush (1939). Minima of Functions of Several Variables with Inequalities as Side Conditions. Master’s thesis, Department of Mathematics, University of Chicago, Chicago.</ref>) dans une thèse qui ne fut jamais publiée, mais qui est décrite dans le compte rendu historique de Kuhn<ref>{{en}} H.W. Kuhn (1976). Nonlinear programming: a historical view. In R.W. Cottle, C.E. Lemke, éditeurs, ''Nonlinear Programming'', SIAM-AMS Proceedings IX, pages 1–26. American Mathematical Society, Providence, RI.</ref>. Une approche différente conduisant au même résultat a été suivie par John (1948<ref>{{en}} F. John (1948). Extremum problems with inequalities as subsidiary conditions. In K.O. Friedrichs, O.E. Neugebauer, J.J. Stokes, éditeurs, ''Studies and Essays'', Courant Anniversary Volume, pages 186–204. Wiley Interscience, New York.</ref>), également avant les travaux de Kuhn et Tucker.

Avant de discuter le système (KKT), introduisons le '''lagrangien''' du problème, qui a la même forme que pour les problèmes d'optimisation avec contraintes d'égalité.

{{Ancre|lagrangien-pei}}
{{Théorème|Lagrangien du problème <math>(P_{EI})</math>|On appelle '''lagrangien du problème <math>(P_{EI})</math>''', la fonction <math>\ell : \mathbb{E} \times \mathbb{R}^m \to \mathbb{R}</math> définie en <math>(x,\lambda)\in \mathbb{E} \times \mathbb{R}^m</math> par
<center>
<math>
\ell (x,\lambda) := f(x) + \lambda^{\!\top\!}c(x)= f(x) + \sum_{i=1}^m\lambda_ic_i(x).
</math>
</center>
Le vecteur <math>\lambda</math> porte le nom de '''multiplicateur''' (de Karush, Kuhn et Tucker ou de Lagrange) ou '''variable duale'''.}}

La variable <math>x</math> est aussi appelée '''variable primale''' ; quant au couple <math>(x,\lambda)</math>, on lui donne parfois le nom de '''variable(s) primale(s)-duale(s)'''.

Voici quelques commentaires sur les conditions de Karush, Kuhn et Tucker.
* On reconnaît dans (KKT)-(a) la nullité du gradient du lagrangien par rapport à la variable primale, <math>\nabla_x\ell(x_*,\lambda_*)=0</math>, équation qui était déjà présente pour les problèmes d'optimisation avec contraintes d'égalite et que l'on peut aussi écrire<center><math>\nabla f(x_*)+\sum_{i=1}^m(\lambda_*)_i\nabla c_i(x_*)=0,</math></center>où les gradients sont pris par rapport au produit scalaire équipant <math>\mathbb{E}</math>. Si l'espace euclidien <math>\mathbb{E}</math> est <math>\mathbb{R}^n</math> muni du produit scalaire euclidien, ces gradients sont les vecteurs des dérivées partielles par rapport aux <math>n</math> variables <math>x_1, \ldots, x_n.</math>
* Les conditions (KKT)-(b) et (KKT)-(c) certifient l'admissibilité de la solution.
* Les deux dernières conditions sont attachées aux contraintes d'inégalité. La première, (KKT)-(d), assure que les multiplicateurs optimaux associés aux contraintes d'inégalité sont positifs. Ce signe serait chaque fois changé si au lieu d'avoir un problème de minimisation on avait un problème de maximisation, ou si on avait écrit les contraintes sous la forme <math>c_I(x)\geqslant 0</math> au lieu de <math>c_I(x)\leqslant 0</math>, ou encore si on avait utilisé le signe <math>-</math> au lieu du signe <math>+</math> dans la définition du lagrangien.
* La dernière condition, (KKT)-(e), est connue sous le nom de '''condition de complémentarité'''. Du fait du signe de <math>(\lambda_*)_I</math> et de <math>c_I(x_*)</math>, elle est équivalente à<br /><center><math>\forall\,i\in I:\qquad(\lambda_*)_ic_i(x_*)=0,</math></center>si bien que soit <math>(\lambda_*)_i=0</math> soit <math>c_i(x_*)=0</math>, lorsque <math>i\in I</math>. C'est de cette alternative que provient le nom de ''complémentarité''. Cette condition s'écrit aussi<center><math>\forall\,i\in I:\qquad c_i(x_*)<0~~\Longrightarrow~~(\lambda_*)_i=0.</math></center>Autrement dit, ''les multiplicateurs associés aux contraintes d'inégalité inactives sont nuls''. Pour certains problèmes, l'implication ci-dessus est remplacée par une équivalence :<center><math>\forall\,i\in I:\qquad c_i(x_*)<0~~\Longleftrightarrow~~(\lambda_*)_i=0.</math></center>On dit alors que l'on a '''complémentarité stricte'''.
* Les conditions (KKT)-(cde) peuvent être rassemblées sous l'une des formes compactes suivantes (il y en a d'autres)<center><math>0\leqslant (\lambda_*)_I\perp(-c_I(x))\geqslant 0\qquad\mbox{ou}\qquad\min((\lambda_*)_I,(-c_I(x_*)))=0,</math></center>qui exprime la positivité de <math>(\lambda_*)_I</math>, celle de <math>-c_I(x_*)</math> et l'orthogonalité de ces deux vecteurs pour le produit scalaire euclidien. Les systèmes de ce type, appelés [[problèmes de complémentarité]], ont fait l'objet d'études systématiques, conduisant à une discipline à part entière. Celle-ci englobe donc l'[[optimisation (mathématiques)|optimisation]] et se généralise à ce que l'on appelle les problèmes d'[[Inéquation variationnelle|inéquations variationnelles]].

Les conditions de KKT sont compliquées et difficiles à résoudre numériquement (elles ne le sont analytiquement que pour de rares problèmes à la structure particulière ; des [[#Exemples|exemples]] sont donnés ci-dessous). Il n'y a cependant ni trop ni trop peu de conditions, comme le montre la démonstration de la propriété suivante, stipulant que, si le problème est convexe, ces conditions sont suffisantes pour impliquer l'optimalité globale.

{{Théorème|CS1 pour un problème <math>(P_{EI})</math> convexe|Considérons le problème <math>(P_{EI})</math>, que l'on suppose convexe au sens défini [[#problème-pei-convexe|ci-dessus]]. Soit <math>x_*</math> un point vérifiant les contraintes de <math>(P_{EI})</math>. Si <math>f</math> et <math>c</math> sont dérivables en <math>x_*</math> et s'il existe <math>\lambda_*\in\mathbb{R}^m</math> tel que les conditions de Karush, Kuhn et Tucker (KKT) ci-dessus soient vérifiées, alors <math>x_*</math> est un minimum global de <math>(P_{EI}).</math>}}

==== Ensemble des multiplicateurs optimaux ====

Soit <math>\lambda_*\in\R^m</math> un multiplicateur optimal (ou solution duale) associé à une solution <math>x_*\in\mathbb{E}</math> du [[#Le problème (PEI)|problème <math>(P_{EI})</math>]]. Il sera utile d'introduire les ensembles d'indices suivants :
<center><math>
I^{0+}_*:=\{i\in I^0_*:(\lambda_*)_i>0\}
\qquad\mbox{et}\qquad
I^{00}_*:=\{i\in I^0_*:(\lambda_*)_i=0\}.
</math></center>
Ce sont donc des ensembles d'indices qui dépendent à la fois de <math>x_*</math> et <math>\lambda_*</math>. Les contraintes d'indices <math>i\in I_*^{0+}</math> sont dites '''fortement actives''' et celles d'indices <math>i\in I_*^{00}</math> sont dites '''faiblement actives'''. Ces dernières, bien qu'actives (<math>c_i(x_*)=0</math>), peuvent être ôtées du problème sans modifier la stationnarité de <math>x_*</math> (<math>(\lambda_*)_i=0</math>).

Il peut y avoir plus d'une solution duale <math>\lambda_*</math> associée à une solution primale <math>x_*</math>. L'ensemble des multiplicateurs associés à <math>x_*</math> est noté
<center><math>
\Lambda_*:=\Lambda(x_*):=
\{\lambda_*\in\R^m:
(x_*,\lambda_*)~\mbox{est solution primale-duale de}~
(P_{EI})\}.
</math></center>
La solution <math>x_*</math> étant fixée, les [[#cn1-KKT|conditions d'optimalité de KKT]] montrent que <math>\Lambda_*</math> est un polyèdre convexe de <math>\R^m</math> :
<center><math>
\Lambda_*=\{\lambda\in\R^m:
\nabla
f(x_*)+c(x_*)^*\lambda = 0,~
\lambda_{I^0_*}\geqslant 0,~
\lambda_{I\setminus I^0_*}=0\}.
</math></center>
En particulier, <math>\Lambda_*</math> est fermé. Il est non vide si les contraintes sont qualifiées en <math>x_*</math> (théorème [[#cn1-KKT|d'optimalité de KKT]]). Par ailleurs, <math>\lambda_*\in\Lambda_*</math> est un sommet de <math>\Lambda_*</math> si <math>c'_{E\cup I^{0+}_*}(x_*)</math> est surjective. En particulier, <math>\Lambda_*</math> n'a pas de sommet si <math>c'_E(x_*)</math> n'est pas surjective.

Cet ensemble <math>\Lambda_*</math> est clairement réduit à un seul multiplicateur si les [[Qualification de contraintes#Indépendance linéaire (QC-IL)|conditions de qualification (QC-IL)]] ([[indépendance linéaire]] des gradients des contraintes actives) sont vérifiées en <math>x_*</math>. Mais, l'unicité du multiplicateur optimal a lieu, en fait, sous une condition plus faible que [[Qualification de contraintes#Indépendance linéaire (QC-IL)|(QC-IL)]], mais plus forte que la qualification de Mangasarian-Fromovitz [[Qualification de contraintes#Mangasarian-Fromovitz (QC-MF)|(QC-MF)]], celle que donne le résultat suivant<ref>{{en}} J. Kyparisis (1985). On uniqueness of Kuhn-Tucker multipliers in nonlinear programming. ''Mathematical Programming'', 32, 242–246.</ref>. Cette condition est aussi nécessaire et suffisante et est parfois appelée la '''condition de qualification de Mangasarian-Fromovitz stricte''' (QC-MFS).

{{Théorème|Unicité du multiplicateur|Soit <math>x_*</math> un point stationnaire de <math>(P_{EI})</math> (donc <math>f</math> et <math>c_{E\cup I^0_*}</math> sont supposées différentiables en <math>x_*</math> et <math>\Lambda_*\not=\varnothing</math>). Alors <math>\Lambda_*</math> est un singleton si, et seulement si, il existe <math>\lambda_*\in\Lambda_*</math> tel que
<center><math>
\left.\begin{array}{r}
\sum_{i\in E\cup I^0_*}\alpha_i\nabla c_i(x_*)=0\\
\alpha_i\geqslant0~\mbox{pour tout}~i\in I^{00}_*
\end{array}\right\}
\quad\Longrightarrow\quad
\alpha_{E\cup I^0_*}=0.
</math></center>}}

Mais en toute généralité, <math>\Lambda_*</math> peut ne pas être réduit à un point. En ce qui concerne le caractère borné de <math>\Lambda_*</math>, on a le résultat suivant<ref>{{en}} J. Gauvin (1977). A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming. ''Mathematical Programming'', 12, 136–138.</ref>.

{{Théorème|Bornitude des multiplicateurs|Soient <math>(x_*,\lambda_*)</math> un couple vérifiant les [[#cn1-KKT|conditions de KKT]] (donc <math>f</math> et <math>c_{E\cup I^0_*}</math> sont supposées différentiables en <math>x_*</math>) et <math>\Lambda_*</math> l'ensemble convexe fermé non vide des multiplicateurs optimaux associés à <math>x_*</math>. Alors <math>\Lambda_*</math> est borné si, et seulement si, la [[Qualification de contraintes#Mangasarian-Fromovitz (QC-MF)|condition de qualification de Mangasarian-Fromovitz (QC-MF)]] a lieu en <math>x_*</math>.}}

==== Résolution analytique des conditions d'optimalité ====

Les conditions d'optimalité de Karush, Kuhn et Tucker permettent d'affirmer que, sous certaines conditions, en particulier de qualification des contraintes, une solution locale de <math>(P_{EI})</math> est un point stationnaire de ce problème, ce qui veut dire qu'elle vérifie l'ensemble des relations désignées par (KKT) ci-dessus. Pour calculer les solutions de <math>(P_{EI})</math>, on pourra donc, dans un premier temps, calculer les solutions du système d'optimalité (KKT). Toutefois, ce calcul est beaucoup plus difficile que lorsqu'il n'y a que des contraintes d'égalité. La difficulté vient de la présence d'inégalités et, en particulier, des conditions de complémentarité. On y retrouvera la ''combinatoire des problèmes d'optimisation avec contraintes d'inégalité'', confirmant ainsi le ''principe de conservation des ennuis'' déjà évoqué.

En général, il faut utiliser des algorithmes spécifiques pour résoudre ce système d'optimalité (c'est ce à quoi est consacré une grande partie de l'[[optimisation numérique]]). Dans certains cas, cependant, en particulier pour des problèmes de petite taille ayant peu de contraintes d'inégalité ou des problèmes très structurés, on peut chercher les solutions de ce système (KKT) analytiquement en considérant l'une après l'autre toutes les manières de satisfaire les contraintes d'inégalité. Dans chaque cas considéré, on suppose qu'un certain nombre de contraintes d'inégalité sont actives et que les autres ne le sont pas. Soit <math>J\subset I</math>, l'ensemble des indices des contraintes d'inégalité supposées actives en la solution : <math>c_{E\cup J}(x_*)=0</math> et <math>c_{J^c}(x_*)<0</math> (on a noté <math>J^c</math> le complémentaire de <math>J</math> dans <math>I</math>). Du fait de la complémentarité, <math>(\lambda_*)_{J^c}=0</math> et on est donc conduit à chercher les solutions du système de <math>n+|E\cup J|</math> équations à <math>n+|E\cup J|</math> inconnues suivant
<center>
<math>
\left\{\begin{array}{l}
\nabla f(x_*) + c'_{E\cup J}(x_*)^* (\lambda_*)_{E\cup J}=0\\
c_{E\cup J}(x_*) = 0.
\end{array}\right.
</math>
</center>
Si une solution <math>(x_*,(\lambda_*)_{E\cup J})</math> de ce système vérifie <math>c_{J^c}(x_*)\leqslant 0</math> et <math>(\lambda_*)_J\geqslant 0</math>, le couple <math>(x_*,((\lambda_*)_{E\cup J},0_{J^c}))</math> est une solution de (KKT). Sinon cette solution doit être écartée. En examinant ainsi tous les ensembles <math>J\subset I</math> possibles, on peut trouver tous les points stationnaires du problème.

La méthode présentée ci-dessus est fastidieuse et, répétons-le, n'est utilisée que dans de rares cas. On notera en effet qu'avec <math>m_I</math> contraintes d'inégalité, il y a <math>2^{m_I}</math> cas à examiner, et donc <math>2^{m_I}</math> systèmes non linéaires à résoudre, ce qui peut vite devenir fastidieux. C'est ici que l'on retrouve la ''combinatoire des problèmes d'optimisation''. Le but des algorithmes d'optimisation pour problèmes avec contraintes d'inégalité est précisément de trouver des solutions du système d'optimalité (KKT), en gérant de manière efficace cette combinatoire, c'est-à-dire en évitant d'explorer toutes les possibilités. L'[[algorithme du simplexe]] en a été un des premiers exemples.

Comme pour les problèmes d'optimisation avec contraintes d'égalité, tous les points stationnaires (les solutions de (KKT)) ne sont pas solutions de <math>(P_{EI})</math>. Pour déterminer si un point stationnaire est solution de <math>(P_{EI})</math>, on pourra utiliser les conditions d'optimalité du second ordre décrites ci-dessous, de la manière suivante :
* si les CN2 ne sont pas vérifiées au point stationnaire, alors celui-ci n'est pas une solution locale de <math>(P_{EI})</math> ;
* si les CS2 sont vérifiées au point stationnaire, alors celui-ci est un minimum local strict de <math>(P_{EI})</math>.
Ces deux cas recouvrent un grand nombre de situations, mais pas toutes, car les CN2 et les CS2 ne sont pas identiques. Le cas est indéterminé lorsqu'un point stationnaire vérifie les CN2, mais pas les CS2. Alors les résultats donnés dans cet article ne sont pas suffisants et il faut recourir à des conditions d'optimalité d'ordre supérieur pour pouvoir dire si le point stationnaire est solution de <math>(P_{EI})</math>.

=== Conditions du deuxième ordre pour (''P<sub>EI</sub>'') ===

Les conditions d'optimalité du second ordre en présence de contraintes d'inégalité ne s'obtiennent ni ne s'écrivent aussi aisément que lorsqu'il n'y a que des contraintes d'égalité. D'abord, ce n'est pas le cône tangent qui intervient comme pour les problèmes avec contraintes d'égalité, mais un cône plus petit que l'on appelle le ''cône critique''. Par ailleurs, le multiplicateur optimal qui intervient dans la hessienne du lagrangien doit être déterminé en fonction de la direction choisie dans le cône critique.

==== Le cône critique ====

Il est tentant d'essayer de généraliser les conditions nécessaires du second ordre du [[#Le problème (PE)|problème <math>(P_E)</math>]] au [[#Le problème (PEI)|problème <math>(P_{EI})</math>]], en cherchant à montrer qu'en une solution primale-duale <math>(x_*,\lambda_*)</math>, on doit avoir <math>\langle L_*d,d\rangle</math> positif pour toute direction tangente <math>d\in\operatorname{T}_{x_*}X_{EI}</math>. Comme précédemment, on a noté <math>L_* := \nabla^2_{xx}\ell(x_*,\lambda_*)</math> la hessienne du [[#lagrangien-pei|lagrangien]] en <math>(x_*,\lambda_*)</math>. Ce résultat n'est pas correct, car le cône tangent <math>\operatorname{T}_{x_*}X_{EI}</math> n'est pas celui qui convient, comme le montre le problème suivant
<center><math>
\min\;\{-1/(x+1):x\in\R_+\}.
</math></center>
Ce problème a pour unique solution primale-duale <math>(x_*,\lambda_*)=(0,1)</math> et le cône tangent en la solution s'écrit <math>\operatorname{T}_{x_*}X_{EI}=\R_+</math> si bien que l'on peut prendre <math>d=1</math> comme direction tangente, mais <math>\langle L_*d,d\rangle=-2</math> n'est pas positif. On pourra voir que <math>\langle L_*d,d\rangle</math> est positif, mais pour des directions <math>d</math> dans un cône plus petit que le cône tangent.

À la recherche d'un cône plus petit, on peut observer que, comme toute solution <math>x_*</math> du [[#Le problème (PEI)|problème <math>(P_{EI})</math>]] minimise aussi <math>f</math> sur
<center><math>
X_{EI}^= := \{x\in\mathbb{E}: c_{E\cup I^0_*}(x) = 0\},
</math></center>
les conditions du second ordre des problèmes avec contraintes d'égalité donnent que <math>\langle L_*d,d\rangle</math> est positif pour toute direction <math>d\in\operatorname{T}_{x_*}X_{EI}^=</math> et toute solution duale <math>\lambda_*\in\Lambda_*</math> (celles-ci sont aussi solutions duales du problème minimisant <math>f</math> sur <math>X_{EI}^=</math>). Il faut voir cependant que le cône <math>\operatorname{T}_{x_*}X_{EI}^=</math> est trop petit, dans le sens où il ne permet pas d'établir des conditions suffisantes d'optimalité du second ordre. Considérons en effet le problème
<center><math>
\min\;\{-x^2:x\in\R_+\}.
</math></center>
Si <math>x_*=0</math>, <math>X_{EI}^= = \{0\}</math>, si bien que <math>\operatorname{T}_{x_*}X_{EI}^= = \{0\}</math> et la hessienne du lagrangien <math>L_*=-2</math> est bien définie positive sur <math>\operatorname{T}_{x_*}X_{EI}^= \setminus \{0\} = \varnothing</math>, mais <math>x_*</math> n'est pas un minimum local du problème.

Le bon cône s'avérera être le [[#Le cône tangent à XEI|cône linéarisant]] <math>\operatorname{T}'_{x_*}X_{EI,f}</math> de l'ensemble
<center><math>
X_{EI,f} := \{x\in X_{EI}: f(x)\leqslant f(x_*)\},
</math></center>
sur lequel <math>f</math> est également minimisée en une solution <math>x_*</math> du [[#Le problème (PEI)|problème <math>(P_{EI})</math>]]. Ce cône est plus petit que le cône tangent à l'ensemble admissible en <math>x_*</math>, mais suffisamment grand pour permettre d'avoir des conditions suffisantes d'optimalité du second ordre. On l'appelle le cône critique du problème.

{{Théorème|Cône critique|On appelle '''cône critique''' du [[#Le problème (PEI)|problème <math>(P_{EI})</math>]] en un point admissible <math>x\in X_{EI}</math>, l'ensemble noté et défini par
<center><math>
C(x) := \{d\in \mathbb{E}:
c_E'(x) \cdot d = 0,~
c_{I_*^0}'(x) \cdot d \leqslant 0,~
f'(x)\cdot d\leqslant 0\}.
</math></center>
Une direction <math>d\in C(x)</math> est appelée '''direction critique''' en <math>x</math>. On utilise la notation simplifiée <math>C_*:=C(x_*)</math>.}}

Dans le premier exemple ci-dessus, <math>C_*=\{0\}</math> est plus petit que le cône tangent <math>\operatorname{T}_{x_*}X_{EI}= \R_+</math>. Dans le second exemple ci-dessus, <math>C_*=\R_+</math> est plus grand que le cône tangent <math>\operatorname{T}_{x_*}X_{EI}^= = \{0\}</math>. Il est remarquable que l'optimalité au second ordre puisse être synthétisée au moyen de l'unique cône critique, alors que les deux problèmes précédents recouvrent des situations très différentes.

En un point stationnaire <math>x_*</math>, de multiplicateur <math>\lambda_*</math>, le cône critique en <math>x_*</math> s'écrit aussi
<center><math>
\begin{array}{rcl}
C_*&=&
\{d\in \mathbb{E} :
c_E'(x_*) \cdot d = 0,~
c_{I_*^0}'(x_*) \cdot d \leqslant 0,~
f'(x_*)\cdot d= 0\},
\\&=&
\{d\in \mathbb{E} :
c_{E\cup I_*^{0+}}'(x_*) \cdot d = 0,~
c_{I_*^{00}}'(x_*) \cdot d \leqslant 0\},
\end{array}
</math></center>
où les ensembles d'indices <math>I^{0+}_*</math> et <math>I^{00}_*</math> ont été introduits [[#Ensemble des multiplicateurs optimaux|ci-dessus]]. Ces expressions s'obtiennent en utilisant les [[#cn1-KKT|conditions d'optimalité de KKT]]. Observons enfin que si les conditions de complémentarité stricte sont satisfaites, le cône critique s'écrit simplement
<center><math>
C_*=\{d\in \mathbb{E}: c'_{E\cup I_*^0}(x_*) \cdot d = 0\},
</math></center>
qui est donc le cône linéarisant <math>\operatorname{T}'_{x_*}X_{EI}^=</math> (un sous-espace vectoriel). En l'absence de complémentarité stricte, ce dernier sous-espace vectoriel est contenu dans <math>C_*</math>, lui-même contenu dans <math>\operatorname{T}'_{x_*}X_{EI}</math>.

==== Trois exemples instructifs ====

Une autre difficulté dans l'établissement des conditions d'optimalité du second ordre du [[#Le problème (PEI)|problème <math>(P_{EI})</math>]] provient du fait que l'on doit prendre le multiplicateur optimal <math>\lambda_*</math> intervenant dans la hessienne du lagrangien <math>L_* := \nabla_{xx}^2\ell(x_*,\lambda_*)</math> en fonction de la direction critique choisie. Les trois exemples suivant devraient permettre de mieux comprendre pourquoi il en est ainsi et d'apprendre à sélectionner correctement les [[Quantificateur (logique)|quantificateurs]] qui s'appliquent à <math>d\in C_*</math> et <math>\lambda_*\in\Lambda_*</math>.

Considérons d'abord le problème à deux variables réelles
<center><math>
\left\{\begin{array}{l}
\min\;x_2\\
x_2\geq x_1^2,
\end{array}\right.
</math></center>
dont la solution est <math>x_*=(0,0)</math>. Il y a un unique multiplicateur optimal associé à la contrainte, valant <math>\lambda_*=1</math>. La contrainte étant active, <math>(x_*,\lambda_*)</math> est aussi la solution primale-duale du problème avec contrainte d'égalité <math>x_2=x_1^2</math>, si bien que la hessienne du [[#lagrangien-pei|lagrangien]] <math>L_*:=\nabla_{xx}^2\ell(x_*,\lambda_*)=\operatorname{diag}(2,0)</math> doit être [[matrice semi-définie positive|semi-définie positive]] dans l'espace tangent à la contrainte (voir [[#Conditions du deuxième ordre avec contraintes d'égalité|ci-dessus]]) : <math>d^\mathsf{T} L_*d\geq0</math> pour toute direction <math>d</math> dans <math>\{d\in\R^2:d_2=0\}</math>. C'est le cas le plus simple qui peut se présenter. On dira plus loin que l'on a des ''conditions d'optimalité du deuxième ordre fortes'' : quel que soit le multiplicateur optimal (il n'y en a qu'un seul ici), <math>L_*</math> est [[matrice semi-définie positive|semi-défini positif]] dans le cône critique. Ces conditions sont vérifiées s'il y a un unique multiplicateur, comme ici, ou comme lorsque la condition de qualification [[Qualification de contraintes#Affinité locale (QC-A)|(QC-A)]] ou [[Qualification de contraintes#Indépendance linéaire (QC-IL)|(QC-IL)]] a lieu.

Considérons à présent une variante du problème précédent où l'on ajoute une contrainte superflue
<center><math>
\left\{\begin{array}{l}
\min\;x_2\\
x_2\geqslant x_1^2\\
x_2\geqslant -\frac{1}{2} x_1^2.
\end{array}\right.
</math></center>
La seconde contrainte ne modifie pas la solution primale qui est toujours <math>x_*=(0,0)</math>, mais il y a maintenant plusieurs multiplicateurs optimaux formant l'ensemble <math>\Lambda_*=\{\lambda\in\R^2_+:</math> <math>\lambda_1+\lambda_2=1\}</math>. En prenant comme multiplicateur <math>\lambda_*=(1,0)</math>, un sommet de <math>\Lambda_*</math>, on ignore la seconde contrainte (comme il se doit) et on a le résultat précédent sur la [[matrice semi-définie positive|semi-définie positivité]] de <math>L_*=\operatorname{diag}(2,0)</math> dans <math>\{d\in\R^2:d_2=0\}</math>. Par contre, avec <math>\lambda_*=(0,1)</math>, l'autre sommet de <math>\Lambda_*</math>, la hessienne du lagrangien <math>L_*=\operatorname{diag}(-1,0)</math> est définie ''négative'' dans <math>\{d\in\R^2:d_2=0\}</math>. C'est normal ; le lagrangien ne voit que la seconde contrainte, ignorant la première, et <math>(0,0)</math> n'est qu'un point stationnaire du problème <math>\textstyle\min\{x_2:x_2\geqslant-\frac{1}{2} x_1^2\}</math>, pas un minimum local. On dira plus loin que l'on a des ''conditions d'optimalité du deuxième ordre semi-fortes'' : il existe un multiplicateur optimal tel que <math>L_*</math> est semi-défini positif dans le cône critique.

Considérons enfin le problème à trois variables
<center><math>
\left\{\begin{array}{l}
\min\;x_3\\
x_3\geqslant (x_1+x_2)(x_1-x_2)\\
x_3\geqslant (x_2+3x_1)(2x_2-x_1)\\
x_3\geqslant (2x_2+x_1)(x_2-3x_1).
\end{array}\right.
</math></center>
On voit que, quel que soit <math>(x_1,x_2)</math> non nul, un des membres de droite des contraintes est strictement positif. Dès lors, l'unique solution de ce problème est <math>x_*=0</math>. D'autre part, l'ensemble des multiplicateurs optimaux est le [[Simplexe|simplexe unité]] <math>\Lambda_*= \{\lambda\in\R^3_+:\lambda_1+\lambda_2+\lambda_3=1\}</math>. Enfin, la hessienne du lagrangien s'écrit
<center><math>
L(x,\lambda)=\begin{pmatrix}
2\lambda_1-6(\lambda_2+\lambda_3) &    5(\lambda_2-\lambda_3)     & 0 \\
              5(\lambda_2-\lambda_3)    & -2\lambda_1+4(\lambda_2+\lambda_3) & 0 \\
                    0         &          0          & 0
\end{pmatrix}.
</math></center>
Quelle que soit la valeur de <math>\lambda_*\in\Lambda_*</math>, <math>L_*</math> n'est pas [[matrice semi-définie positive|semi-définie positive]] sur le cône critique, qui est ici le sous-espace <math>\{d\in\R^3:d_3=0\}</math> (en effet, l'élément <math>(1,1)</math> vaut <math>8\lambda_1-6</math> et l'élément (2,2) vaut <math>4-6\lambda_1</math>, si bien qu'il faudrait que <math>\lambda_1</math> soit supérieur à 3/4 et inférieur à 2/3). On dira plus loin que l'on a des ''conditions d'optimalité du deuxième ordre faibles'' : pour toute direction critique <math>d</math>, il existe un multiplicateur optimal <math>\lambda_*</math> (dépendant de <math>d</math>) tel que <math>d^\mathsf{T} L_*d\geqslant0</math>.

==== Conditions nécessaires du second ordre ====

Voici des conditions nécessaires d'optimalité du second ordre lorsque la [[Qualification de contraintes#Mangasarian-Fromovitz (QC-MF)|qualification Mangasarian-Fromovitz (QC-MF)]] a lieu en la solution <math>x_*</math> du problème.

{{Théorème|CN2 pour <math>(P_{EI})</math> avec la qualification (QC-MF)|Soit <math>x_*</math> une solution locale du [[#Le problème (PEI)|problème <math>(P_{EI})</math>]]. Supposons que <math>f</math> et <math>c_E</math> soient <math>C^2</math> dans un voisinage de <math>x_*</math>, que <math>c_{I^0_*}</math> soit deux fois dérivable en <math>x_*</math> et que <math>c_{I\setminus I^0_*}</math> soit continue en <math>x_*</math>. Supposons également que la [[Qualification de contraintes#Mangasarian-Fromovitz (QC-MF)|qualification Mangasarian-Fromovitz (QC-MF)]] ait lieu en <math>x_*</math>. Alors
<center><math>
\forall\,d\in C_*:\quad
\exists\,\lambda_*\in\Lambda_*:\quad \langle L_*d,d\rangle\geqslant0.
</math></center>}}

Les conditions nécessaires d'optimalité du second ordre (CN2) énoncées dans ce résultat sont dites '''faibles''', car le multiplicateur optimal est choisi en fonction de la direction critique. Dans certains problèmes, on a la condition plus forte (mois souvent vérifiée) suivante
<center><math>
\exists\,\lambda_*\in\Lambda_*,\quad
\forall\,d\in C_*:\quad \langle L_*d,d\rangle\geqslant 0.
</math></center>
On dit alors que l'on a des conditions nécessaires d'optimalité du second ordre '''semi-fortes'''. Dans certains cas, l'on a des conditions encore plus fortes, à savoir
<center><math>
\forall\,\lambda_*\in\Lambda_*,\quad
\forall\,d\in C_*:\quad \langle L_*d,d\rangle\geqslant 0.
</math></center>
On dit alors que l'on a des conditions nécessaires d'optimalité du second ordre '''fortes'''. Comme l'affirme le résultat suivant, ce dernier cas est vérifié lorsque la qualification [[Qualification de contraintes#Affinité locale (QC-A)|(QC-A)]] ou [[Qualification de contraintes#Indépendance linéaire (QC-IL)|(QC-IL)]] a lieu.

{{Théorème|CN2 pour <math>(P_{EI})</math> avec la qualification (QC-A) ou (QC-IL)|Soit <math>x_*</math> une solution locale du [[#Le problème (PEI)|problème <math>(P_{EI})</math>]]. Supposons que <math>f</math> et <math>c_{E\cup I^0_*}</math> soient deux fois dérivables en <math>x_*</math> et que <math>c_{I\setminus I^0_*}</math> soit continue en <math>x_*</math>. Supposons également que la qualification [[Qualification de contraintes#Affinité locale (QC-A)|(QC-A)]] ou [[Qualification de contraintes#Indépendance linéaire (QC-IL)|(QC-IL)]] ait lieu en <math>x_*</math>. Alors
<center><math>
\forall\,\lambda_*\in\Lambda_*,\quad
\forall\,d\in C_*:\quad \langle L_*d,d\rangle\geqslant 0.
</math></center>}}

La vérification numérique des conditions nécessaires d'optimalité du second ordre n'est pas aisée. Déjà, lorsque les conditions semi-fortes ont lieu pour un multiplicateur optimal <math>\lambda_*</math>, il s'agit de vérifier que la forme quadratique <math>d\mapsto \langle L_*d,d\rangle</math> associée à la hessienne du lagrangien est semi-définie positive sur le cône critique <math>C_*</math>, qui est polyédrique, c'est-à-dire que <math>L_*</math> est [[Matrice copositive|<math>C_*</math>-copositive]]. En toute généralité, une telle vérification est un problème NP-ardu<ref>{{en}} K.G. Murty, S.N. Kabadi (1987). Some NP-complete problems in quadratic and nonlinear programming. ''Mathematical Programming'', 39, 117–129.</ref>{{,}}<ref>{{en}} P.J.C. Dickinson, L. Gijben (2011). On the computational complexity of membership problems for the completely positive cone and its dual. Rapport de recherche.</ref>. Maintenant, s'il y a aussi complémentarité stricte, le cône critique devient un sous-espace vectoriel et la vérification de la semi-définie positivité de <math>d\mapsto \langle L_*d,d\rangle</math> sur ce sous-espace est alors une opération simple d'algèbre linéaire.

==== Conditions suffisantes du second ordre ====

Les conditions suffisantes du second ordre (CS2) s'obtiennent comme pour les problèmes plus simples en requérant que <math>\langle L_*d,d\rangle</math> soit ''strictement'' positif pour un multiplicateur dépendant d'une direction critique <math>d</math> choisie dans le cône critique. Le fait que le cône critique intervienne aussi dans ces conditions suffisantes d'optimalité est une garantie de sa pertinence.

{{Théorème|CS2 pour <math>(P_{EI})</math>|Supposons que <math>f</math> et <math>c_{E\cup I^0_*}</math> soient dérivables dans un voisinage d'un point <math>x_*\in \mathbb{E}</math> et deux fois dérivables en <math>x_*</math>. Supposons également que l'ensemble <math>\Lambda_*</math> des multiplicateurs <math>\lambda_*</math> tels que <math>(x_*,\lambda_*)</math> vérifie les conditions d'optimalité de KKT ne soit pas vide. Supposons enfin que
<center><math>
\forall d\in C_*\setminus\{0\},~\exists\,\lambda_*\in\Lambda_*:\quad
\langle L_*d,d\rangle > 0,
</math></center>
ou de manière équivalente (<math>\|\cdot\|</math> est une norme arbitraire)
<center><math>
\exists\,\bar{\gamma}>0,~\forall d\in C_*,~\exists\,\lambda_*\in\Lambda_*:\quad
\langle L_*d,d\rangle\geq\bar{\gamma}\|d\|^2.
</math></center>
Alors, pour tout <math>\gamma\in{[0,\bar{\gamma}[}</math>, il existe un voisinage <math>V</math> de <math>x_*</math> tel que pour tout <math>x\in X_{EI}\cap V</math>, différent de <math>x_*</math> :
<center><math>
f(x) > f(x_*)+\frac{\gamma}{2}\|x-x_*\|^2.
</math></center>
En particulier, <math>x_*</math> est un minimum local strict de <math>(P_{EI})</math>.}}

L'inégalité obtenue en conclusion du résultat précédent est connue sous le nom de '''propriété de croissance quadratique'''. Elle montre que <math>f</math> croît au moins quadratiquement lorsqu'on se déplace de <math>x_*</math> vers l'«intérieur» de l'ensemble admissible <math>X_{EI}</math>.

=== Interprétation marginaliste des multiplicateurs de Karush, Kuhn et Tucker ===

=== Exemples ===

==== Inégalités de Hölder ====

Les [[Inégalité de Hölder|inégalités de Hölder]] généralisent l'[[inégalité de Cauchy-Schwarz]], dans le sens où elles donnent une majoration du produit scalaire euclidien de deux vecteurs <math>x</math> et <math>y\in\mathbb{R}^n</math> par leur [[Norme (mathématiques)#En dimension finie|norme <math>\ell^p</math> et <math>\ell^{p'}</math>]], plutôt que par leur [[Norme (mathématiques)#En dimension finie|norme euclidienne]]. Dans cette majoration, les scalaires <math>p</math> et <math>p'</math> doivent être pris dans <math>[1,+\infty]</math> et vérifier
<math display="block">\frac{1}{p}+\frac{1}{p'}=1.</math>
Cette relation accepte les valeurs infinies, si bien que <math>p=1</math> si, et seulement si, <math>p'=\infty</math>. Pour de tels <math>p</math> et <math>p'</math>, l''''inégalité de Hölder''' s'écrit :
<math display="block">\forall\,x,y\in\mathbb{R}^n:\quad|x^{\top\!}y|\leqslant\|x\|_p\,\|y\|_{p'}.</math>

Cette inégalité se généralise aux [[Espace de suites lp|espaces <math>\ell^p</math>]] des suites de puissance <math>p</math> sommables et aux [[Espace Lp|espaces <math>L^p</math>]] des fonctions de puissance <math>p</math> intégrables. Dans <math>\mathbb{R}^n</math>, elles peuvent être démontrées à partir d'une solution du problème de minimisation d'une fonction linéaire sur la [[Boule (topologie)|boule unité fermée]] associée à la norme <math>\ell^p</math>, à savoir <math>B_p:=\{x\in\mathbb{R}^n:\|x\|_p\leqslant 1\}</math>, problème qui s'écrit
<math display="block">(P_p)\qquad \min_{x\in B_p}\;x^{\top\!}y. </math>
Par la [[Compacité (mathématiques)|compacité]] de <math>B_p</math> (en dimension finie), ce problème a clairement une solution ; elle est unique si <math>1<p<+\infty</math>. On donne ici le calcul des solutions de ce problème par les [[#Conditions de Karush, Kuhn et Tucker (KKT)|conditions d'optimalité de Karush, Kuhn et Tucker]] et d'en déduire les inégalités de Hölder.

===== Cas où p = ∞ =====

C'est le cas le plus simple, qui peut se résoudre sans utiliser les conditions d'optimalité de KKT. En effet, le problème <math>(P_\infty)</math>, qui s'écrit
<math display="block">
(P_\infty)\qquad
\min_{-1\leqslant x \leqslant 1}\;\sum_{i=1}^n\,x_iy_i
</math>
se décompose en <math>n</math> problèmes indépendants, à savoir
<math display="block">\min_{-1\leqslant x_i \leqslant 1}\;x_iy_i</math>
dont les solutions <math>\bar{x}_i</math> sont triviales :

<math display="block">\bar{x}_i\left\{\begin{array}{lll}=-1 & \mbox{si} & y_i>0\\\in[-1,1] & \mbox{si} & y_i=0\\=1 & \mbox{si} & y_i<0.\end{array}\right.</math>

L'inégalité de Hölder correspondante s'obtient alors en observant que, quels que soient <math>x\in B_\infty</math> et <math>y\in\mathbb{R}^n</math>, on a si l'on note <math>\sigma(t)</math> le signe de <math>t\in\mathbb{R}</math> :
<math display="block">x^{\top\!}y\geqslant \bar{x}^{\top\!}y=-\sum_{i=1}^n\,\sigma(y_i)y_i=-\|y\|_1,</math>
si bien que <math>|x^{\top\!}y|\leqslant\|y\|_1</math>. On met ensuite <math>x</math> à l'échelle si ce vecteur n'est pas dans la boule unité <math>B_\infty</math>, ce qui conduit à <math>|x^{\top\!}y|\leqslant\|x\|_\infty\,\|y\|_1</math>.

===== Cas où 1 < p < ∞ =====

Si <math>y=0</math>, tout <math>x\in B_p</math> est solution et l'inégalité de Hölder est triviale.

Supposons à présent que <math>y\ne0</math>. En écrivant la contrainte <math>\|x\|^p_p/p\leqslant 1/p</math> de manière à la rendre différentiable et éviter le facteur <math>p</math> après différentiation, le lagrangien du problème <math>(P_p)</math> s'écrit
<center>
<math>
\ell(x,\lambda)=x^{\top\!}y+\frac{\lambda}{p}\left(\sum_{i=1}^n\,|x_i|^p-1\right).
</math>
</center>
Comme la contrainte est qualifiée (par les [[Qualification de contraintes#Slater (QC-S)|conditions suffisantes de Slater]] par exemple) et le problème est convexe, <math>\bar{x}</math> en est solution si, et seulement si, il existe un multiplicateur optimal <math>\bar{\lambda}\in\mathbb{R}</math> tel que les conditions de KKT suivantes soient vérifiées :
<center>
<math>
\left\{\begin{array}{l}
y_i+\bar{\lambda}_i\bar{x}_i|\bar{x}_i|^{p-2}=0,\qquad i=1,\ldots,n\\
\|\bar{x}\|_p\leqslant 1\\
\bar{\lambda}\geqslant 0\\
\bar{\lambda}(\|\bar{x}\|_p-1)=0.
\end{array}\right.
</math>
</center>
Comment résoudre ce système compliqué ? Comme le suggère la [[#Résolution analytique des conditions d'optimalité|méthode générale présentée ci-dessus]], il est souvent judicieux de commencer par considérer les conditions de complémentarité (la {{4e}}), qui ont ici une ''combinatoire'' particulièrement réduite. Il y a seulement deux possibilités (parce que le problème n'a qu'une seule contrainte) : soit le multiplicateur est nul, soit la contrainte est active. Lorsque <math>y\ne0</math>, la première condition montre clairement que le multiplicateur ne peut être nul ; la contrainte est donc active, ce qui résout du même coup la seconde condition. Gardons en mémoire que le multiplicateur optimal est positif ({{3e|condition}}) en exploitant la première condition. En prenant la norme <math>\ell^{p'}</math> de <math>y</math>, on obtient la valeur du multiplicateur optimal
<center>
<math>
\bar{\lambda}=\|y\|_{p'},
</math>
</center>
qui est donc strictement positif. En observant que <math>\bar{x}_i</math> et <math>\bar{y}_i</math> sont de signe contraire et en se rappelant que <math>y\ne0</math>, la première condition donne alors

<math display="block">\bar{x}_i=-\sigma(y_i)\left(\frac{|y_i|}{\|y\|_{p'}}\right)^{\frac{p'}{p}},</math>

où on a noté <math>\sigma(t)</math> le signe de <math>t\in\mathbb{R}</math>. En particulier, <math>\bar{x}=-y/\|y\|_2</math> si <math>p=2</math>.

L'inégalité de Hölder correspondante se déduit de ces résultats comme dans le cas <math>p=\infty</math>. Quels que soient <math>x\in B_p</math> et <math>y\in\mathbb{R}^n</math>, on a :
<center>
<math>
x^{\top\!}y\geqslant \bar{x}^{\top\!}y=
-\left(\frac{1}{\|y\|_{p'}}\right)^{\frac{p'}{p}}
\sum_{i=1}^n|y_i|^{\frac{p'}{p}+1}
=
-\frac{\|y\|_{p'}^{p'}}{\|y\|_{p'}^{p'/p}}
=
-\|y\|_{p'},
</math>
</center>
si bien que <math>|x^{\top\!}y|\leqslant\|y\|_{p'}</math>. On met ensuite <math>x</math> à l'échelle si ce vecteur n'est pas dans la boule unité <math>B_p</math>, ce qui conduit à <math>|x^{\top\!}y|\leqslant\|x\|_p\,\|y\|_{p'}</math>.

===== Cas où p = 1 =====

Le cas où <math>y=0</math> étant trivial, on considère ci-dessous que
<math>y\ne0</math>.

Il n'est pas nécessaire de résoudre <math>(P_1)</math> si l'on ne cherche qu'à obtenir l'inégalité de Hölder correspondante puisque celle-ci est identique au cas <math>p=\infty</math> déjà considéré. On cherche ici plutôt comment résoudre <math>(P_1)</math> en utilisant les conditions d'optimalité de KKT.

La première difficulté à surmonter est de récrire la contrainte <math>\|x\|_1\leqslant 1</math> de manière différentiable (la norme <math>\ell^1</math> ne l'est pas). On vérifiera sans peine que <math>\|x\|_1\leqslant 1</math> si, et seulement si, il existe un vecteur <math>v\in\mathbb{R}^n</math> tel que <math>\textstyle\sum_{i=1}^nv_i=1</math> et <math>-v\leqslant x\leqslant v</math>, si bien que le problème <math>(P_1)</math> est «équivalent» au problème en <math>(x,v)\in\mathbb{R}^n\times\mathbb{R}^n</math> suivant
<center>
<math>
(P'_1)\qquad
\left\{\begin{array}{l}
\min_{(x,v)}\;y^{\top\!}x\\
\textstyle
\sum_{i=1}^nv_i=1\\
-v\leqslant x\leqslant v.
\end{array}\right.
</math>
</center>
Ayant un domaine admissible compact et non vide, ce problème a aussi une solution ; de plus <math>\bar{x}</math> est solution de <math>(P_1)</math> si, et seulement si, <math>(\bar{x},\bar{v})</math> est solution de <math>(P'_1)</math>. Le lagrangien du problème <math>(P'_1)</math> s'écrit
<center>
<math>
\ell(x,v,\lambda,\alpha,\beta)=x^{\top\!}
y+\lambda\left(\sum_{i=1}^n\,v_i-1\right)
+\sum_{i=1}^n\alpha_i(x_i-v_i)
-\sum_{i=1}^n\beta_i(x_i+v_i).
</math>
</center>
Comme les contraintes de <math>(P'_1)</math> sont qualifiées (par [[Qualification de contraintes#Affinité locale (QC-A)|affinité locale]] par exemple) et comme le problème est convexe, <math>(\bar{x},\bar{v})</math> en est une solution si, et seulement si, il existe des multiplicateurs optimaux <math>(\bar{\lambda},\bar{\alpha},\bar{\beta})\in\mathbb{R}\times\mathbb{R}^n\times\mathbb{R}^n</math> tels que les conditions de KKT suivantes soient vérifiées :
<center>
<math>
\left\{\begin{array}{ll}
(a) &
y+\bar{\alpha}-\bar{\beta}=0\\
(b) &
\bar{\lambda} e-\bar{\alpha}-\bar{\beta}=0\\
(c) &
\textstyle
\sum_{i=1}^n\,\bar{v}_i=1\\
(d) &
-\bar{v}\leqslant \bar{x}\leqslant \bar{v}\\
(e) &
\bar{\alpha}\geqslant 0,\quad
\bar{\beta}\geqslant 0\\
(f) &
\bar{\alpha}_i(\bar{x}_i-\bar{v}_i)=0,\quad
\bar{\beta}_i(\bar{x}_i+\bar{v}_i)=0,\quad\forall\,i\in\{1,\ldots,n\},
\end{array}\right.
</math>
</center>
où <math>e</math> est un vecteur dont toutes les composantes valent&nbsp;1. Voici un système avec une ''combinatoire'' importante : <math>2^{2n}</math> manières de réaliser les conditions de complémentarité&nbsp;(f). La [[#Résolution analytique des conditions d'optimalité|méthode générale présentée ci-dessus]] est ici de peu d'utilité, mais une astuce de calcul permet d'éviter une application fastidieuse. On remarque d'abord que, par (a) et (b), l'on peut écrire <math>\bar{\alpha}</math> et <math>\bar{\beta}</math> en fonction de <math>\bar{\lambda}</math> :
<center>
<math>
\bar{\alpha}=\frac{1}{2}(\bar{\lambda} e-y)
\quad\mbox{et}\quad
\bar{\beta}=\frac{1}{2}(\bar{\lambda} e+y).
</math>
</center>
Par (e), on en déduit que <math>\bar{\lambda}\geqslant\|y\|_\infty</math>. Mais si <math>\bar{\lambda}>\|y\|_\infty</math>, <math>\bar{\alpha}</math> et <math>\bar{\beta}</math> seraient strictement positifs et on déduirait de (f) que <math>\bar{x}=\bar{v}=0</math>, en contradiction avec (c). Dès lors
<center>
<math>
\bar{\lambda}=\|y\|_\infty,
</math>
</center>
comme lorsque <math>1<p<\infty</math>. On distingue ensuite les cas :
* si <math>|y_i|<\|y\|_\infty</math>, alors <math>\bar{\alpha}_i>0</math>, <math>\bar{\beta}_i>0</math>, puis <math>\bar{x}_i=\bar{v}_i=-\bar{v}_i</math> par (e), donc <math>\bar{x}_i=\bar{v}_i=0</math>,
* si <math>y_i=\|y\|_\infty>0</math>, alors <math>\bar{\alpha}_i=0</math>, <math>\bar{\beta}_i>0</math>, donc <math>\bar{x}_i=-\bar{v}_i\leqslant 0</math> par (f) et (d),
* si <math>y_i=-\|y\|_\infty<0</math>, alors <math>\bar{\alpha}_i>0</math>, <math>\bar{\beta}_i=0</math>, donc <math>\bar{x}_i=\bar{v}_i\geqslant 0</math> par (f) et (d).
On déduit de ces observations que les solutions <math>\bar{x}</math> de <math>(P_1)</math> vérifient
<math display="block">\|\bar{x}\|_1=1,\quad \bar{x}_{I^c}=0\quad\mbox{et}\quad \bar{x}_I\cdot y_I\leqslant 0,</math>

où <math>I:=\{i:|y_i|=\|y\|_\infty\}</math>, <math>I^c</math> est son complémentaire et <math>u\cdot v</math> désigne le [[Produit matriciel#Produit d'Hadamard|produit de Hadamard]]. Inversement, on vérifie que si <math>\bar{x}</math> satisfait les conditions encadrées, si <math>\bar{v}=|\bar{x}|</math>, si <math>\bar{\lambda}=\|y\|_\infty</math>, si <math>\bar{\alpha}=(\|y\|_\infty e-y)/2</math> et si <math>\bar{\beta}=(\|y\|_\infty e+y)/2</math>, alors <math>(\bar{x},\bar{v},\bar{\lambda},\bar{\alpha},\bar{\beta})</math> satisfait les conditions d'optimalité (a)-(f), si bien qu'alors <math>\bar{x}</math> est une solution de <math>(P_1)</math>.

L'inégalité de Hölder correspondante se déduit de ces résultats comme dans le cas <math>1<p\leqslant\infty</math>. Quels que soient <math>x\in B_1</math> et <math>y\in\mathbb{R}^n</math>, on a :
<center>
<math>
x^{\top\!}y\geqslant
\bar{x}^{\top\!}y=
-\sum_{i\in I}|\bar{x}_i|\,|y_i|=
-\|y\|_\infty\sum_{i\in I}|\bar{x}_i|=
-\|y\|_\infty,
</math>
</center>
si bien que <math>|x^{\top\!}y|\leqslant\|y\|_\infty</math>. On met ensuite <math>x</math> à l'échelle si ce vecteur n'est pas dans la boule unité <math>B_1</math>, ce qui conduit à <math>|x^{\top\!}y|\leqslant\|x\|_1\,\|y\|_\infty</math>.

==== Minimisation d'une fonction quadratique sur la boule euclidienne ====

== Problèmes d'optimisation avec contraintes générales ==

=== Le problème (''P<sub>G</sub>'') ===

Dans cette section, on considère le problème d'optimisation avec contraintes plus générales, que l'on écrit sous la forme suivante
<center><math>
(P_G) \quad \left\{ \begin{array}{l}
\inf_x\,  f(x) \\
c(x) \in G.
\end{array} \right.
</math></center>
Cette écriture exprime le fait que l'on cherche à minimiser un ''critère'' <math>f:\mathbb{E}\to\mathbb{R}</math> défini sur un [[espace euclidien]] <math>\mathbb{E}</math> dont l'argument <math>x</math>, qui est le vecteur des variables à optimiser, l'inconnue de ce problème, est contraint de respecter des contraintes spécifiées par l'expression <math>c(x)\in G</math>. Celle-ci signifie que l'image de <math>x</math> par la ''fonction'' <math>c:\mathbb{E}\to\mathbb{F}</math> doit appartenir au ''convexe fermé non vide'' <math>G</math> de l'espace euclidien <math>\mathbb{F}</math>. Le produit scalaire des espaces euclidiens <math>\mathbb{E}</math> et <math>\mathbb{F}</math> sont tous deux notés <math>\langle\cdot,\cdot\rangle</math>.

On désigne par
<center><math>
X_G:=\{x\in\mathbb{E}:c(x)\in G\}=c^{-1}(G)
</math></center>
l'ensemble admissible du problème <math>(P_G)</math>.

Le problème <math>(P_G)</math> est bien une généralisation du [[#Le problème (PEI)|problème <math>(P_{EI})</math>]], puisqu'on retrouve ce dernier en prenant
<center><math>
\mathbb{F}=\R^m\quad\mbox{et}\quad G=\{0_{\R^{m_E}}\}\times\R^{m_I}_-.
</math></center>
Un des intérêts de cette formulation générale est d'avoir tout son sens en dimension infinie, ce qui n'est pas le cas de <math>(P_{EI})</math>. Il est en effet malaisé de spécifier ce qu'est un [[ensemble infini]] de contraintes d'inégalité à valeurs dans un espace de dimension infinie. On peut donc voir la généralisation proposée comme un premier pas dans l'étude des problèmes d'optimisation de dimension infinie. Les résultats obtenus sont cependant aussi utiles pour résoudre certains problèmes de dimension finie à la structure différente de celle de <math>(P_{EI})</math>. Un autre avantage de cette généralisation est de mieux faire ressortir la structure des objets manipulés, ainsi que celle des raisonnements employés.

On sait que la convexité joue un rôle crucial en optimisation. On est donc conduit à définir ce qu'est un problème <math>(P_G)</math> convexe.

{{Ancre|problème-pg-convexe}}
{{Théorème|Problème <math>(P_G)</math> convexe|On dit que le problème <math>(P_G)</math> est convexe si la fonction <math>f</math> est [[fonction convexe|convexe]] et si la [[multifonction]] <math>x\mapsto c(x)-G</math> est [[Multifonction convexe|convexe]].}}

On a la propriété attendue suivante
<center><math>
(P_G)~\mbox{est convexe}
\quad\Longrightarrow\quad
X_G~\mbox{est convexe.}
</math></center>
Dans le cas du problème <math>(P_{EI})</math>, <math>G = \{0_{\R^{m_E}}\}\times\R^{m_I}_-</math> et la convexité de <math>x\mapsto c(x)-G</math> revient à dire que <math>c_E</math> est affine et <math>c_I</math> a toutes ses composantes convexes.

=== Conditions du premier ordre pour (''P<sub>G</sub>'') ===

==== Le cône tangent à ''X<sub>G</sub>'' ====

Des conditions d'optimalité du premier ordre pour <math>(P_G)</math> peuvent s'obtenir comme pour les problèmes précédents, par l'intermédiaire de la [[#cn1-générique|condition du premier ordre générique de Peano-Kantorovitch]]. Cette condition requiert le calcul du [[cône tangent]] <math>\operatorname{T}_x X_G</math> à l'ensemble admissible <math>X_G</math>. Comme précédemment, on cherche à exprimer ce cône tangent en «linéarisant» les objets <math>c</math> et <math>G</math> qui définissent l'ensemble admissible. Cette linéarisation se fait en <math>x</math> pour <math>c</math>, qui est définie sur <math>\mathbb{E}</math>, et en <math>c(x)</math> pour <math>G</math>, qui est défini sur <math>\mathbb{F}</math>. Cette opération conduit au cône <math>\operatorname{T}'_xX_G</math>, plus grand que <math>\operatorname{T}_xX_G</math>, que l'on appelle le '''cône linéarisant''' de <math>X_G</math>.

{{Théorème|Estimation du cône tangent <math>\operatorname{T}_x X_G</math>|Si <math>c</math> est dérivable en <math>x \in X_G</math>, alors
<center><math>
\operatorname{T}_x X_G \subset
\operatorname{T}'_xX_G:=\{d \in \mathbb{E} : c'(x) d\in \operatorname{T}_{c(x)}G\}.
</math></center>}}

On n'a pas nécessairement l'égalité entre les deux cônes, car <math>\operatorname{T}'_xX_G</math> est convexe (c'est l'[[image réciproque]] par l'application linéaire <math>c'(x)</math> du cône tangent <math>\operatorname{T}_{c(x)}G</math>, qui est convexe par la convexité de <math>G</math>) alors que <math>\operatorname{T}_xX_G</math> ne l'est pas nécessairement (on n'a pas imposé à la fonction <math>c</math> définissant <math>X_G</math> d'être affine et donc l'ensemble admissible <math>X_G</math> n'est pas nécessairement convexe). C'est gênant, car c'est le cône tangent <math>\operatorname{T}_x X_G</math> qui intervient dans la [[#cn1-générique|condition nécessaire d'optimalité générique de Peano-Kantorovitch]] alors que le cône linéarisant <math>\operatorname{T}'_x X_G</math> a l'avantage d'avoir une expression analytique que l'on aimerait pouvoir exploiter. Comme pour le problème <math>(P_{EI})</math>, la notion de qualification des contraintes définissant <math>X_G</math> est liée au fait de pouvoir avoir l'égalité entre les deux cônes, ''mais pas seulement''. La technique de démonstration conduisant aux conditions d'optimalité du premier ordre de Karush, Kuhn et Tucker, technique qui sera aussi utilisée pour obtenir la condition du premier ordre ci-dessous, cherche à montrer que le gradient <math>\nabla f(x_*)</math> appartient à un cône que l'on peut expliciter. Deux ingrédients interviennent dans cette approche :
* l'égalité entre le cône tangent et le cône linéarisant, qui permet ainsi d'avoir une expression exploitable du premier,
* la polyédricité du cône linéarisant, qui permet d'éliminer la prise de l'adhérence après application du [[lemme de Farkas]].
Ici <math>\operatorname{T}'_x X_G</math> n'est pas polyédrique, parce que l'on ne veut pas imposer cette propriété restrictive de polyédricité à <math>G</math>. De manière à sélectionner les problèmes non convexes pour lesquels on peut utiliser l'approche proposée pour établir les conditions d'optimalité du premier ordre, on introduit une hypothèse, dite ''de qualification'', qui assure précisément l'égalité entre le cône tangent et le cône linéarisant (c'est la première condition ci-dessous), mais aussi le caractère fermé de l'image par <math>c'(x)^*</math> du dual du cône linéarisant (c'est la seconde condition ci-dessous).

{{Théorème|Qualification d'une contrainte générale|On dit que la fonction <math>c:\mathbb{E}\to\mathbb{F}</math> est ''qualifiée'' en <math>x\in X_G</math> pour représenter <math>X_G</math> si <math>c</math> est dérivable en <math>x</math> et si les deux conditions suivantes sont vérifiées :
<center><math>
\begin{array}{c}
\operatorname{T}_x  X_G = \operatorname{T}'_x X_G,
\\
c'(x)^* [(\operatorname{T}_{c(x)}G)^+]~\mbox{est fermé,}
\end{array}
</math></center>
où <math>c'(x)^*:\mathbb{F}\to\mathbb{E}</math> l'opérateur linéaire adjoint de la dérivée <math>c'(x): \mathbb{E}\to\mathbb{F}</math>.}}

Vérifier que <math>c</math> est qualifié pour représenter <math>X_G</math> est une tâche difficile. Cela requiert le calcul du cône tangent, que l'on voudrait surtout éviter s'il n'est pas identique au cône linéarisant. La condition ''suffisante'' de qualification la plus utilisée, généralisant au problème <math>(P_G)</math> la condition de [[Qualification de contraintes#Mangasarian-Fromovitz (QC-MF)|Mangasarian-Fromovitz]] du problème <math>(P_{EI})</math>, est celle de Robinson<ref>{{en}} S.M. Robinson (1976). Stability theory for systems of inequalities, part II: differentiable nonlinear systems. ''SIAM Journal of Numerical Analysis, 13, 487-513.</ref>. On y note <math>\operatorname{int}P</math> l'[[Intérieur (topologie)|intérieur]] d'un ensemble <math>P</math>

{{Théorème|Condition suffisante de qualification de Robinson|Si <math>c: \mathbb{E}\to\mathbb{F}</math> est <math>C^1</math> dans un voisinage de <math>x\in X_G</math> et si<center><math>\operatorname{(QC-R)}\qquad0\in\operatorname{int}(c(x)+c'(x)\mathbb{E}-G),</math></center>alors <math>c</math> est qualifiée en <math>x</math> pour représenter <math>X_G.</math>}}

Cette condition de Robinson est davantage examinée dans la section [[Qualification de contraintes#Condition suffisante de qualification de Robinson|Condition suffisante de qualification de Robinson]].

==== Conditions du premier ordre pour (''P<sub>G</sub>'') ====

Précisons quelques notations qui seront utilisées dans l'énoncé des conditions du premier ordre. Comme ci-dessus, <math>\nabla f(x_*) \in \mathbb{E}</math> est le [[gradient]] de <math>f</math> en <math>x_*</math> et <math>c'(x_*)^*: \mathbb{F}\to \mathbb{E}</math> est l'[[opérateur adjoint]] de la [[dérivée]] <math>c'(x_*): \mathbb{E}\to \mathbb{F}</math> (c'est un opérateur linéaire) pour les produits scalaires donnés sur <math>\mathbb{E}</math> et <math>\mathbb{F}</math> ; si <math>P</math> est un ensemble, <math>P^-:=-P^+</math> est le [[cône dual|cône dual négatif]] de <math>P</math> ; enfin, la notation
<center><math>
K^-\ni u\perp v\in K
</math></center>
signifie les trois conditions suivantes :
<center><math>
u\in K^-,\quad
v\in K\quad\mbox{et}\quad
\langle u,v\rangle=0.
</math></center>

{{Ancre|cn1-pg}}
{{Théorème|CN1 de <math>(P_G)</math>|Soit <math>x_*</math> un minimum local de <math>(P_G)</math>. Supposons que <math>f</math> et <math>c</math> soient dérivables en <math>x_*</math> et que <math>c</math> soit qualifiées en <math>x_*</math> pour représenter <math>X_G</math>. Alors,
* il existe <math>\lambda_* \in \mathbb{F}</math> tel que l'on ait<center><math>
\begin{array}{c}
\nabla f(x_*)+c'(x_*)^*\lambda_*=0, \\
\lambda_*\in\operatorname{N}_{c(x_*)}G,
\end{array}
</math></center>
* si, de plus, <math>G\equiv K</math> est un cône convexe, alors les conditions d'optimalité ci-dessus s'écrivent<center><math>
\begin{array}{c}
\nabla f(x_*)+c'(x_*)^*\lambda_*=0, \\
K^-\ni\lambda_*\perp c(x_*)\in K.
\end{array}
</math></center>}}

Un point <math>x_*\in\mathbb{E}</math> tel que <math>(x_*,\lambda_*)</math> vérifie les conditions d'optimalité du premier ordre ci-dessus pour un certain <math>\lambda_*\in\mathbb{F}</math> est qualifié de '''stationnaire'''.

Dans la première condition d'optimalité <math>\nabla f(x_*)+c'(x_*)^*\lambda_*=0</math>, on reconnaît le gradient du '''lagrangien''' du problème <math>(P_G)</math> qui est la fonction <math>\ell:\mathbb{E}\times\mathbb{F}\to\R</math> définie en <math>(x,\lambda)\in\mathbb{E}\times\mathbb{F}</math> par
<center><math>
\ell(x,\lambda) = f(x)+\langle\lambda,c(x)\rangle.
</math></center>
Dans le cas où <math>G\equiv K</math> est un cône convexe, on reconnait dans la seconde condition d'optimalité <math>K^-\ni\lambda_*\perp c(x_*)\in K</math>, des conditions de complémentarité généralisées, déjà présentent dans les [[#cn1-KKT|conditions de KKT]].

Lorsque le problème <math>(P_G)</math> est convexe dans le sens [[#problème-pg-convexe|précisé précédemment]], les conditions nécessaires du premier ordre deviennent suffisantes, comme pour le problème <math>(P_{EI})</math>.

{{Théorème|CS1 pour un problème <math>(P_G)</math> convexe|Supposons que le problème <math>(P_G)</math> soit convexe au sens défini [[#problème-pg-convexe|ci-dessus]], que <math>f</math> et <math>c</math> soient dérivables en <math>x_*\in X_G</math> et qu'il existe <math>\lambda_*\in\mathbb{F}</math> tel que<center><math>
\begin{array}{c}
\nabla f(x_*)+c'(x_*)^*\lambda_*=0, \\
\lambda_*\in\operatorname{N}_{c(x_*)}G.
\end{array}
</math></center>Alors <math>x_*</math> est un minimum global de <math>(P_G).</math>}}

Désignons par
<center><math>
\Lambda_*:=\{\lambda_*\in\operatorname{N}_{c(x_*)}G:\nabla f(x_*)+c'(x_*)^*\lambda_*=0\},
</math></center>
l'ensemble des multiplicateurs optimaux associés à un point stationnaire <math>x_*\in\mathbb{E}</math> de <math>(P_G)</math> et par <math>\Lambda_*^\infty</math> son [[cône asymptotique]].

{{Théorème|Propriété de bornitude de Gauvin|Supposons que <math>f</math> et <math>c</math> soient dérivables en <math>x_*\in X_G</math> et que <math>\Lambda_*</math> soit non vide. Alors
* <math>\Lambda_*^\infty=[c'(x_*)\mathbb{E}-\operatorname{T}_{c(x_*)}G]^+</math>,
* <math>\Lambda_*</math> est borné si, et seulement si, (QC-R) a lieu en <math>x_*.</math>}}

=== Conditions du deuxième ordre ===

== Annexes ==

=== Notes ===

{{Références|colonnes=2}}

=== Articles connexes ===

* [[Cône tangent]]
* [[Coût marginal]]
* [[Multiplicateur de Lagrange]] : présentation moins abstraite et donc plus abordable de l'optimalité des problèmes avec contraintes d'égalité, certains en dimension infinie.
* [[Optimisation quadratique successive]]
* [[Qualification de contraintes]]

=== Liens externes ===

* ''[http://zonecours.hec.ca/documents/39441.doc La méthode du Lagrangien]'' (1999), École des Hautes Études Commerciales, Montréal, Québec.
* ''[http://www.bibmath.net/dico/index.php3?action=affiche&quoi=./e/extremalies.html Extrema liés - Multiplicateurs de Lagrange]'' sur BibM@th.
* J. Ch. Gilbert, ''[http://www-rocq.inria.fr/~gilbert/ensta/optim.html Éléments d'Optimisation Différentiable — Théorie et Algorithmes]'', syllabus de cours à l'[[École nationale supérieure de techniques avancées|ENSTA ParisTech]], Paris.

=== Bibliographie ===

* {{en}} J. F. Bonnans, A. Shapiro (2000). ''Perturbation Analysis of Optimization Problems''. Springer Verlag, New York.
* J. Gauvin (1992). ''Théorie de la programmation mathématique non convexe''. Les Publications CRM, Montréal.
* J.-B. Hiriart-Urruty (1996). ''L’Optimisation''. Que sais-je, 3184. Presses Universitaires de France.
* {{en}} J.-B. Hiriart-Urruty, C. Lemaréchal (1993). ''Convex Analysis and Minimization Algorithms''. Grundlehren der mathematischen Wissenschaften, 305-306. Springer-Verlag.
* {{en}} R. T. Rockafellar (1993). Lagrange multipliers and optimality. ''SIAM Review'', 35, 183–238.

{{Portail|mathématiques}}

[[Catégorie:Optimisation différentiable]]