En 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 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érentiables au sens classique (celui de Fréchet). Lorsque la différentiabilité a lieu dans un sens plus faible on parle doptimisation non lisse ou doptimisation 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 doptimisation 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 splines (représentés par un nombre fini de paramètres). Les 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 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 PX

Soit un espace vectoriel sur de dimension finie, qui désigne l'ensemble auquel appartiennent les paramètres que l'on cherche à optimiser. Étant de dimension finie, il n'y a pas de restriction à supposer que cet espace vectoriel est muni d'un produit scalaire, noté , qui en fait un espace euclidien. La norme associée à ce produit scalaire est notée . Le problème d'optimisation considéré s'exprime mathématiquement comme celui qui consiste à minimiser une fonction sur une partie de . La fonction a de nombreuses appellations, ce qui permet de varier le vocabulaire : fonction-coût, coût, fonction-objectif, objectif, critère, etc. L'ensemble 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 , s'écrit au choix comme suit :

.

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

.

On adjoint souvent le qualificatif global à cette notion de solution pour la distinguer d'autres notions présentées ci-dessous. On peut remarquer également que l'on remplace parfois par dans l'écriture du problème d'optimisation 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 est une solution locale ou minimum local ou minimiseur local du problème s'il existe un voisinage de tel que minimise sur . Par ailleurs, on dit que est une solution stricte [resp. une solution locale stricte] si est admissible et si (inégalité stricte) pour tout différent de [resp. pour tout différent de où est un voisinage de ].

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

Il faut rappeler quand même ici qu'une partie de (un espace vectoriel suffit pour cette notion) est un cône si , ce qui signifie que doit appartenir à chaque fois que est un réel strictement positif (i.e., ) et . 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 au sens de Bouligand., qui suffit en dimension finie. On peut préciser que ce cône tangent à en , noté ci-dessous, est l'ensemble des directions tangentes à en , c'est-à-dire des directions pour lesquelles il existe des suites d'éléments de et d'éléments de telles que

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

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 Peano dès 1887 G. Peano (1887). Applicazioni Geometriche del Calcolo Infinitesimale. Fratelli Bocca Editori, Torino. G. Peano (1908). Formulario Mathematico, Editio V. Fratelli Bocca Editori, Torino., puis par Kantorovitch en 1940 L.V. Kantorovich (1940). On an efficient method for solving some classes of extremum problems. Doklady Akad. Nauk SSSR, 28, 212–215., mais il est passé inaperçu ou a été oublié B.T. Polyak (2001). History of mathematical programming in the USSR: analyzing the phenomenon. Mathematical Programming, 91, 401–416. S. Dolecki, G.H. Greco (2007). Towards historical roots of necessary conditions of optimality – Regula of Peano. Control and Cybernetics, 36, 491–518.. On peut en donner une expression plus compacte en introduisant les notions de gradient et de cône dual.

La dérivée première de en étant une application linéaire de dans , par le théorème de Riesz-Fréchet, il existe un unique vecteur vérifiant

Ce vecteur est appelé le gradient de en . Il dépend manifestement du produit scalaire de l'espace euclidien .

Soit une partie non vide de l'espace euclidien . Le cône dual (positif) de est l'ensemble défini par

pour tout C'est un cône convexe fermé non vide.

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

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

Le résultat obtenu se résulte ainsi, par l'abréviation CN1 pour désigner une condition nécessaire d'optimalité du premier ordre.

On dit que est un point stationnaire ou un point critique du problème , 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é la dérivée directionnelle de en dans la direction , c'est-à-dire la limite lorsque du quotient différentiel .

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

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

Problèmes d'optimisation sans contrainte

Le problème que l'on considère dans cette section est celui de minimiser la fonction sur tout entier, problème que l'on écrit

Dès lors, l'ensemble admissible est l'espace vectoriel .

Conditions du premier ordre sans contrainte

Le cône tangent à en est l'espace tout entier. Comme le dual de est , la CN1 générique exprime que le gradient est nul en un minimum local de sur . Cette condition d'optimalité est parfois appelée « équation de Fermat » pour rappeler une condition similaire trouvée, dans le cas d'un polynôme réel d'une variable réelle, par Pierre de Fermat vers 1629, c'est-à-dire environ quarante ans avant l'invention du calcul différentiel par Newton et LeibnizJ. Mawhin, Analyse — Fondements, Techniques, Évolution, De Boeck, 1992..

Lorsque est convexe, ces conditions deviennent des conditions nécessaires et suffisantes d'optimalité globale de .

Conditions du deuxième ordre sans contrainte

On désigne ci-dessous par la dérivée seconde de en , qui est une application bilinéaire symétrique de dans , et par la hessienne de en pour le produit scalaire de l'espace euclidien , qui est l'unique opérateur linéaire auto-adjoint sur vérifiant

On peut rappeler également les notions de semi-définie positivité et définie positivité d'un opérateur auto-adjoint sur , associées au produit scalaire de , qui sont utilisées dans les résultats ci-dessous :