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 (on simplifie un peu, voir ci-dessous pour une définition précise). 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 analyse, pour établir des bornes d'erreur,
en optimisation pour établir les conditions d'optimalité, pour passer à la limite dans les conditions d'optimalité de problèmes voisins, etc,
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.

Introduction

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

$\operatorname {T} _{x}X,$

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 \mathbb {E} :c(x)\in G\}\equiv c^{-1}(G),$

où $G$ 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 linéarisant

$\operatorname {T} _{x}'X:=\{d\in \mathbb {E} :c'(x)\cdot d\in \operatorname {T} _{c(x)}G\}\equiv c'(x)^{-1}(\operatorname {T} _{c(x)}G).$

On montre facilement que

\operatorname {T} _{x}X\subset \operatorname {T} _{x}'X.

On n'a pas nécessairement l'égalité entre les deux cônes $\operatorname {T} _{x}X$ et $\operatorname {T} '_{x}X$ , car $\operatorname {T} '_{x}X$ peut être convexe (c'est le cas si $G$ est convexe) alors que $\operatorname {T} _{x}X$ ne l'est pas nécessairement. En optimisation (et c'est avec ce point de vue que cet article est écrit), c'est gênant, car c'est le cône tangent $\operatorname {T} _{x}X$ qui intervient dans la condition nécessaire d'optimalité générique de Peano-Kantorovitch alors que le cône linéarisant $\operatorname {T} '_{x}X$ a l'avantage d'avoir une expression analytique que l'on aimerait pouvoir exploiter. La notion de qualification des contraintes définissant $X$ 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 cherche à montrer que le gradient $\nabla f(x_{*})$ 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,
le fait de pouvoir se passer de la prise de l'adhérence après application du lemme de Farkas.

Le second point est à l'origine de la seconde condition ci-dessous.

Qualification de contrainte — Dans le cadre ci-dessus, on dit que la contrainte $c:\mathbb {E} \to \mathbb {F}$ est qualifiée en $x\in X$ pour représenter $X$ si $c$ est dérivable en $x$ et si les deux conditions suivantes sont vérifiées :

{\begin{array}{c}\operatorname {T} _{x}X=\operatorname {T} '_{x}X,\\c'(x)^{*}[(\operatorname {T} _{c(x)}G)^{+}]~{\mbox{est fermé,}}\end{array}}

où $c'(x)^{*}:\mathbb {F} \to \mathbb {E}$ l'opérateur linéaire adjoint de $c'(x):\mathbb {E} \to \mathbb {F}$ .

La seconde condition est immédiatement vérifiée si $G$ est un polyèdre convexe, car alors le cône tangent $\operatorname {T} _{x}G$ est aussi un polyèdre convexe et son dual $(\operatorname {T} _{x}G)^{+}$ également ; il en résulte que $c'(x)^{*}[(\operatorname {T} _{c(x)}G)^{+}]$ est un polyèdre convexe et donc un fermé. Cette condition de polyédricité sera vérifiée pour les ensembles $X_{E}$ et $X_{EI}$ ci-dessous.

La qualification est une propriété de la fonction $c$ , pas de l'ensemble $X$ dont la définition utilise cette fonction. On peut en effet définir l'ensemble $X$ par diverses fonctions $c$ , sans modifier donc le cône tangent $\operatorname {T} _{x}X$ , alors que $\operatorname {T} _{x}'X$ 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.

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 $\operatorname {T} _{x}'X$ ci-dessus, le cône tangent $\operatorname {T} _{x}X_{E}$ est inclus dans le cône suivant

$\operatorname {T} _{x}'X_{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 $\operatorname {T} _{x}X_{E}=\operatorname {T} _{x}'X_{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^{1}$ 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 $G\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

$G=\{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 G$ est donné par

$\operatorname {T} _{y}G=\{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 $\operatorname {T} _{x}'X$ et celle de $\operatorname {T} _{y}G$ ci-dessus, le cône tangent $\operatorname {T} _{x}X_{EI}$ est inclus dans le cône suivant

$\operatorname {T} _{x}'X_{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_{x}^{0}:=\{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 $\operatorname {T} _{x}X_{EI}=\operatorname {T} _{x}'X_{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 linéarisant. 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^{1}$ 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 :

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 $\alpha _{i}=0$ pour tout $i\in E\cup I^{0}(x),$
$c'_{E\cup I^{0}(x)}(x)$ est surjective,
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 :

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 $\alpha _{i}=0$ pour tout $i\in E\cup I^{0}(x),$
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)},$
$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,$
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).

Qualification de contraintes générales

L'ensemble X_G

Dans cette section, on suppose que l'ensemble $X\equiv X_{G}$ est défini comme dans l'introduction de cet article, à savoir

X_{G}:=\{x\in \mathbb {E} :c(x)\in G\}=c^{-1}(G),

où $c:\mathbb {E} \to \mathbb {F}$ est une fonction et $G$ est un convexe fermé non vide de l'espace euclidien $\mathbb {F}$ . Le produit scalaire des espaces euclidiens $\mathbb {E}$ et $\mathbb {F}$ sont tous deux notés $\langle \cdot ,\cdot \rangle$ .

Condition suffisante de qualification de Robinson

La condition suffisante de qualification de Robinson[4] est une généralisation à l'ensemble $X_{G}$ de la condition de Mangasarian-Fromovitz de l'ensemble $X_{EI}$ .

(QC-R) — La condition de qualification de Robinson a lieu en $x\in X_{G}$ si $c$ est différentiable en $x$ et si

\operatorname {(QC-R)} \qquad 0\in \operatorname {int} (c(x)+c'(x)\mathbb {E} -G).

Dans (QC-R), l'écriture $c'(x)\mathbb {E}$ est une autre manière de désigner ${\mathcal {R}}(c'(x))$ , l'image de l'opérateur linéaire $c'(x)$ . Cette condition (QC-R) n'est pas simple ; elle est difficile à décrire géométriquement et à mémoriser. Lorsqu'elle est écrite en $x=x_{0}$ , il est sans doute utile (et c'est comme cela qu'elle intervient dans son analyse) de la voir comme l'image de la multifonction «linéarisée»

T_{0}:\mathbb {E} \multimap \mathbb {F} :x\in \mathbb {E} \mapsto c(x_{0})+c'(x_{0})(x-x_{0})-G.

Cette dernière multifonction est en effet une espèce de linéarisation en $x_{0}$ de la multifonction

T:\mathbb {E} \multimap \mathbb {F} :x\in \mathbb {E} \mapsto c(x)-G,

qui a tout son sens dans l'analyse de $X_{G}$ puisque $x\in X_{G}$ si, et seulement si, $0\in T(x)$ .

Le résultat de qualification précis est le suivant ; il demande un peu plus de régularité pour $c$ en $x$ .

Condition suffisante de qualification de Robinson — Si $c:\mathbb {E} \to \mathbb {F}$ est $C^{1}$ dans un voisinage de $x\in X_{G}$ et si (QC-R) a lieu en $x$ , alors $c$ est qualifiée en $x$ pour représenter $X_{G}.$

La condition de Robinson peut s'écrire sous les différentes formes ci-dessous ; on y a noté $\operatorname {T} _{c(x)}^{a}G:=\mathbb {R} _{+}(G-c(x))$ le cône des directions admissibles de $G$ en $c(x)$ .

Autres formes de (QC-R) — Si $c:\mathbb {E} \to \mathbb {F}$ est différentiable en $x\in X_{G}$ , alors les propriétés suivantes sont équivalentes :

$0\in \operatorname {int} (c(x)+c'(x)\mathbb {E} -G)$ ,
$c'(x)\mathbb {E} -\operatorname {T} _{c(x)}^{a}G=\mathbb {F}$ ,
$c'(x)\mathbb {E} -\operatorname {T} _{c(x)}G=\mathbb {F}$ ,
${\overline {c'(x)\mathbb {E} -\operatorname {T} _{c(x)}G}}=\mathbb {F}$ .

La condition de Robinson a essentiellement un lien avec la stabilité de $X_{G}$ pour de petites perturbations $y$ de $G$ , dans le sens où l'on a la caractérisation suivante.

(QC-R) et régularité métrique — Si $c:\mathbb {E} \to \mathbb {F}$ est $C^{1}$ en $x_{0}\in X_{G}$ , alors les propriétés suivantes sont équivalentes :

(QC-R) a lieu en $x=x_{0}$ ,
il existe une constante $\mu >0$ telle que pour tout $(x,y)$ proche de $(x_{0},0)$ , on a $\operatorname {dist} (x,c^{-1}(y+G))\leqslant \mu \operatorname {dist} (c(x),y+G).$

Le point 2 de ce résultat est équivalent à la régularité métrique en $(x_{0},0)$ de la multifonction $T:\mathbb {E} \multimap \mathbb {F}$ définie en $x\in \mathbb {E}$ par $T(x)=c(x)-G$ parce qu'avec cette multifonction, on a $\operatorname {dist} (x,c^{-1}(y+G))=\operatorname {dist} (x,T^{-1}(y))$ et $\operatorname {dist} (c(x),y+G)=\operatorname {dist} (y,T(x))$ . Ce qu'affirme ce point 2 est la propriété suivante : pour tout $x$ proche de $x_{0}$ et pour toute petite perturbation $y$ de $G$ , la distance de $x$ à la perturbation $c^{-1}(y+G)$ de $X_{G}$ reste contrôlable par la distance de $c(x)$ à la perturbation $y+G$ de $G$ .

Maintenant, le membre de droite de l'inégalité du point 2 est toujours fini ( $G$ est non vide), si bien que le membre de gauche l'est aussi; ce qui a pour conséquence que la perturbation $c^{-1}(y+G)$ de $X_{G}$ est non vide lorsque $y$ est suffisamment petit.

Corollaire 1: stabilité de $X_{G}$ — Si

c:\mathbb {E} \to \mathbb {F}

est

C^{1}

x_{0}\in X_{G}

et si (QC-R) a lieu en

x=x_{0}

, alors pour tout

y\in \mathbb {F}

petit

\{x\in \mathbb {E} :c(x)\in y+G\}\neq \varnothing .

Un autre corollaire est obtenu en prenant $y=0$ dans le point 2 : on obtient alors une borne d'erreur pour $G$ .

Corollaire 2: borne d'erreur pour $X_{G}$ — Si

c:\mathbb {E} \to \mathbb {F}

est

C^{1}

x_{0}\in X_{G}

et si (QC-R) a lieu en

x=x_{0}

, alors il existe une constante

\mu >0

telle que pour tout

x

proche de

x_{0}

, on a

\operatorname {dist} (x,X_{G})\leqslant \mu \operatorname {dist} (c(x),G).

Annexes

Notes

(en) M. Slater (1950). Lagrange multipliers revisited: a contribution to non-linear programming. Cowles Commission Discussion Paper, Math. 403.
(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.
(en) J. Gauvin (1977). A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming. Mathematical Programming, 12, 136–138.
(en) S.M. Robinson (1976). Stability theory for systems of inequalities, part II: differentiable nonlinear systems. SIAM Journal of Numerical Analysis, 13, 487-513.

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.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.