Qualification de contraintes

En mathématiques, lorsqu'une partie d'un espace normé est décrit par des fonctions différentiables, appelées contraintes dans ce contexte, la question se pose de savoir si l'on peut obtenir le cône tangent à cet ensemble en linéarisant ces contraintes. Si c'est le cas, on dit que les contraintes sont qualifiées. L'intérêt d'avoir des contraintes qualifiées est de disposer d'une formulation analytique du cône tangent qui, sans qualification, peut être difficile à calculer.

Cette notion est utilisée

• en optimisation pour établir les conditions d'optimalité du premier ordre,
• en géométrie différentielle, auquel cas les ensembles de départ et d'arrivée sont des variétés plutôt que des espaces vectoriels.

Connaissances supposées : le calcul différentiel, l'algèbre linéaire, les bases de l'analyse convexe, la notion de cône tangent.

Problématique

Soient $\mathbb{E}$ un espace normé, X une partie de $\mathbb{E}$ et x un point de $\mathbb{E}$. On s'intéresse au calcul du cône tangent à X en x, que l'on note

T_xX,

lorsque X est défini comme l'image réciproque d'un ensemble par une fonction. De manière plus précise, supposons que X soit défini comme suit

$X:=\{x\in P:c(x)\in Q\}\equiv P\cap\Bigl(c^{-1}(Q)\Bigr),$

où P est une partie de $\mathbb{E}$, Q est une partie d'un espace normé $\mathbb{F}$, $c:\mathbb{E}\to\mathbb{F}$ est une fonction différentiable, que l'on appelle contrainte, et l'exposant « − 1» est utilisé pour désigner l'image réciproque. On introduit le cône des contraintes linéarisées

$T'_xX:=\{d\in T_xP:c'(x)\cdot d\in T_{c(x)}Q\}\equiv\Bigl(T_xP\Bigr)\cap \Bigl(c'(x)^{-1}(T_{c(x)}Q)\Bigr).$

On cherche à déterminer des conditions assurant que les deux cônes T_xX et T'_xX sont égaux. L'intérêt d'une telle égalité est de simplifier le calcul du cône tangent ; le cône des contraintes linéarisées étant en effet plus simple à calculer que le cône tangent puisqu'il ne fait intervenir la contrainte que par sa dérivée.

Qualification de contrainte — Dans le cadre ci-dessus, on dit que la contrainte c est qualifiée en x si c est différentiable en x et si T_xX = T'_xX.

On montre aisément que le cône tangent est toujours inclus dans le cône des contraintes linéarisées.

Surestimation du cône tangent — Avec les notations ci-dessus et si c est différentiable en x, on a

$T_xX\subset T'_xX.$

La qualification est une propriété de la contrainte c, pas de l'ensemble X dont la définition utilise cette contrainte. On peut en effet définir l'ensemble X par diverses fonctions c, sans modifier donc le cône tangent T_xX, alors que T'_xX sera le plus souvent affecté par le changement de fonction c. Dès lors, cette notion de qualification permet de sélectionner les bonnes fonctions c, dans un sens qui dépend du contexte. En optimisation, par exemple, avoir des contraintes qualifiées en une solution d'un problème permet d'obtenir des multiplicateurs optimaux ou variables duales ; voir l'article sur les conditions d'optimalité des problèmes d'optimisation.

Qualification de contraintes d'égalité

L'ensemble X_E

On considère dans cette section que l'ensemble est décrit comme l'image réciproque d'un point par une application différentiable $c:\mathbb{E}\to\mathbb{F}$ entre deux espaces vectoriels de dimension finie $\mathbb{E}$ et $\mathbb{F}$ :

$X_E:=\{x\in \mathbb{E}:c(x)=0\}.$

Le point de $\mathbb{F}$ dont on prend l'image réciproque par c est l'origine ; c'est sans perte de généralité, car un autre point pourrait être intégré dans la fonction c.

Conditions suffisantes de qualification de la contrainte définissant X_E

D'après la formule générale de T'_xX ci-dessus, le cône tangent T_xX_E est inclus dans le cône suivant

$T'_xX_E:=\{d\in\mathbb{E}:c'(x)\cdot d = 0\}$

et on dit que la contrainte c définissant X_E est qualifiée en x si T_xX_E = T'_xX_E. Une condition suffisante de qualification est la suivante.

Condition suffisante de qualification de la contrainte de X_E — Si $c: \mathbb{E}\to\mathbb{F}$ est C¹ dans un voisinage de $x\in X_E$ et si c'(x) est surjective, alors c est qualifiée en x.

Qualification de contraintes d'égalité et d'inégalité

L'ensemble X_EI

On considère dans cette section que l'ensemble est décrit comme l'image réciproque d'un cône particulier $Q\in\mathbb{R}^m$ par une application $c:\mathbb{E}\to\mathbb{R}^m$ définie sur un espace vectoriel de dimension finie $\mathbb{E}$ :

$X_{EI}:=\{x\in \mathbb{E}:c_E(x)=0, c_I(x)\leqslant 0\}.$

On a noté E et I des ensembles d'indices formant une partition de l'ensemble des m premiers entiers $\{1, \ldots, m\}$ :

$E \cup I=\{1, \ldots, m\} \qquad\mbox{et}\qquad E \cap I = \varnothing.$

Les cardinaux de E et I sont notés respectivement

$m_E:=|E| \qquad\mbox{et}\qquad m_I:=|I|,$

si bien que m = m_E + m_I. Alors $c_E:\mathbb{E}\to\mathbb{R}^{m_E}$ désigne la fonction dont les composantes c_i sont celles de c avec $i\in E$. De même pour c_I. Le cône de $\mathbb{R}^m$ dont X_EI est l'image réciproque par c est donc

$Q=\{v\in\mathbb{R}^m:v_i=0~\mbox{si}~i\in E,~v_i\leqslant 0~\mbox{si}~i\in I\}.$

Son cône tangent en $y\in Q$ est donné par

$T_yQ=\{h\in\mathbb{R}^m:h_i=0~\mbox{si}~i\in E,~h_i\leqslant 0~\mbox{si}~i\in I~\mbox{et}~y_i=0\}.$

Conditions suffisantes de qualification de la contrainte définissant X_EI

D'après la formule générale de T'_xX et celle de T_yQ ci-dessus, le cône tangent T_xX_EI est inclus dans le cône suivant

$T'_xX_{EI}:=\{d\in\mathbb{E}:c'_E(x)\cdot d = 0, c'_{I^0(x)}(x)\cdot d\leqslant 0\},$

où on a noté

$I^0(x)\equiv I^0_x:= \{i \in I : c_i (x) = 0\}$

l'ensemble des indices des contraintes d'inégalité actives en x. On rappelle que la contrainte c définissant X_EI est dite qualifiée en x si T_xX_EI = T'_xX_EI. Vérifier que cette égalité a lieu est une tâche difficile car il faut calculer le cône tangent. On connaît un grand nombre de conditions assurant que cette qualification a lieu (des conditions suffisantes donc). Elles supposent toutes que les contraintes actives au point considéré sont différentiables en ce point, car les dérivées de ces contraintes interviennent dans la définition du cône des contraintes linéarisées. Voici les principales conditions suffisantes de qualification, donnant un petit aperçu de la galerie des conditions qui sont utilisées aujourd'hui.

Affinité locale (QC-A)

Cette condition suffisante de qualification est utilisée pour des contraintes linéaires (ou affines), comme en optimisation linéaire ou quadratique.

Affinité locale (QC-A) — $c_{E \cup I^0(x)}$ est affine dans un voisinage de $x\in X_{EI}$ et $c_{I \setminus I^0(x)}$ est continue en x.

Slater (QC-S)

Les conditions suffisantes de qualification de Slater^[1] sont essentiellement utilisées pour les ensembles définis par des contraintes convexes.

Slater (QC-S) — $c_{I \setminus I^0(x)}$ est continue en $x\in X_{EI}$ et

• c_E est une fonction affine avec c'_E surjective,
• les composantes de $c_{I^0(x)}$ sont convexes,
• on peut trouver un point $\hat{x}$ tel que $c_E(\hat{x})=0$ et $c_{I^0(x)}(\hat{x})<0.$

Indépendance linéaire (QC-IL)

Cette condition suffisante de qualification a bien des défauts mais elle a l'avantage de la simplicité et de n'utiliser qu'un concept d'algèbre linéaire.

Indépendance linéaire (QC-IL) — $c_{E \cup I^0(x)}$ est de classe C¹ dans un voisinage de $x\in X_{EI}$, $c_{I \setminus I^0(x)}$ est continue en x et l'une des conditions équivalentes suivantes est satisfaite :

1. les gradients des contraintes actives en x sont linéairement indépendants, c'est-à-dire $\sum_{i \in E \cup I^0(x)} \alpha_i \nabla c_i(x) = 0$ implique que α_i = 0 pour tout $i \in E \cup I^0(x),$
2. $c'_{E \cup I^0(x)}(x)$ est surjective,
3. quel que soit $g\in\mathbb{E}$, le sous-espace affine $\{\lambda\in\mathbb{R}^m: g+c'_{E \cup I^0(x)}(x)^*\lambda_{E \cup I^0(x)}=0,~\lambda_{I\setminus I^0(x)}=0\}$ est borné.

Au point 3, l'ensemble affine peut être vide (il est en réalité réduit à un point ou vide). Cette condition exprime de manière compliquée que $c'_{E \cup I^0(x)}(x)^*$ est injective ; cette affirmation a été mise sous cette forme pour la rapprocher de celle que l'on obtient (condition 4) avec (QC-MF) ci-dessous.

Mangasarian-Fromovitz (QC-MF)

Cette condition suffisante de qualification, qui fut trouvée assez tardivement (1967)^[2], est celle qui est la mieux adaptée aux problèmes avec contraintes d'inégalité non linéaires.

Mangasarian-Fromovitz (QC-MF) — $c_{E \cup I^0(x)}$ est différentiable en $x\in X_{EI},$ $c_{I \setminus I^0(x)}$ est continue en x et l'une des conditions équivalentes suivantes est satisfaite :

1. la condition $\sum_{i \in E \cup I^0(x)} \alpha_i \nabla c_i(x) = 0,~\mbox{avec}~\alpha_i \geqslant 0~\mbox{pour tout}~i \in I^0(x)$ implique que α_i = 0 pour tout $i \in E \cup I^0(x),$
2. pour tout $v\in\mathbb{R}^m$, il existe une direction $d\in\mathbb{E}$ telle que $c'_E(x)\cdot d=v_E$ et $c'_{I^0(x)}(x)\cdot d\leqslant v_{I^0(x)},$
3. c'_E(x) est surjective et il existe une direction $d\in\mathbb{E}$ telle que $c'_E(x)\cdot d=0$ et $c'_{I^0(x)}(x)\cdot d< 0,$
4. quel que soit $g\in\mathbb{E}$, le polyèdre convexe $\{\lambda\in\mathbb{R}^m:~g+c'_E(x)^*\lambda_E+c'_{I^0(x)}(x)^*\lambda_{I^0(x)}=0,~\lambda_{I^0(x)}\geqslant 0,~\lambda_{I\setminus I^0(x)}=0\}$ est borné.

La comparaison de la première condition de (QC-IL) et de la première condition de (QC-MF) montre clairement que l'on a

(QC-IL)   $\Longrightarrow$   (QC-MF).

La réciproque n'est pas vraie, comme le montre le cas de deux boules tangentes intérieurement : au point de tangence, (QC-MF) est vérifiée, mais pas (QC-IL).

La seconde condition de (QC-MF) est aussi clairement plus faible que la seconde condition de (QC-IL), puisqu'elle exprime une espèce de sous-surjectivité de la jacobienne $c'_{E \cup I^0(x)}(x)$.

L'expression duale 4 des conditions de Mangasarian-Fromovitz ci-dessus est due à Gauvin (1977)^[3] ; elle fait intervenir un produit scalaire sur $\mathbb{E}$ et l'adjoint des opérateurs dérivées. Appliquée à l'optimisation, cette expression implique que l'ensemble des multiplicateurs optimaux est borné si et seulement si (QC-MF) a lieu.

Examinons à présent les liens entre (QC-S) et (QC-MF).

(QC-S) et (QC-MF) — Si c_E est affine, si $c_{I^0(x)}$ est convexe et différentiable en $x\in X_{EI}$ et si $c_{I \setminus I^0(x)}$ est continue en x, alors

(QC-S)   $\Longleftrightarrow$   (QC-MF).

Annexes

Notes

1. ↑ (en) M. Slater (1950). Lagrange multipliers revisited: a contribution to non-linear programming. Cowles Commission Discussion Paper, Math. 403.
2. ↑ (en) O. L. Mangasarian, S. Fromovitz (1967), The Fritz John necessary optimality conditions in the presence of equality and inequality constraints, Journal of Mathematical Analysis and Applications, 17, 37–47.
3. ↑ (en) J. Gauvin (1977). A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming. Mathematical Programming, 12, 136–138.

Articles connexes

• Cône tangent
• Conditions d'optimalité (dimension finie)

Lien externe

• J. Ch. Gilbert, Éléments d'Optimisation Différentiable — Théorie et Algorithmes, syllabus de cours à l'ENSTA ParisTech, Paris.

Ouvrages généraux

• (en) J. F. Bonnans, A. Shapiro (2000). Perturbation Analysis of Optimization Problems. Springer Verlag, New York.
• J.-B. Hiriart-Urruty (1996). L’Optimisation. Que sais-je, n° 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.