Qualification de contraintes

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

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

Sommaire

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

TxX,

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 TxX 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 TxX = 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 TxX, 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 TxXE 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 XE est qualifiée en x si TxXE = T'xXE. Une condition suffisante de qualification est la suivante.

Condition suffisante de qualification de la contrainte de XE — Si c: \mathbb{E}\to\mathbb{F} est C1 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 = mE + mI. Alors c_E:\mathbb{E}\to\mathbb{R}^{m_E} désigne la fonction dont les composantes ci sont celles de c avec i\in E. De même pour cI. Le cône de \mathbb{R}^m dont XEI 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 TyQ ci-dessus, le cône tangent TxXEI 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 XEI est dite qualifiée en x si TxXEI = T'xXEI. 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

  • cE 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 C1 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 cE 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

Lien externe

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.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Qualification de contraintes de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Conditions d'optimalité (dimension finie) — En optimisation mathématique, les conditions d optimalité sont un ensemble d équations, d inéquations (i.e., des inégalités) et d expressions diverses (e.g., la semi définie positivité de matrices sur des cônes) vérifiées par une solution d un… …   Wikipédia en Français

  • Cône tangent — En mathématiques, le cône tangent est l approximation au premier ordre d un ensemble en un point, comme l application dérivée d une fonction est son approximation au premier ordre en un point. Cette notion est, par exemple, utilisée en… …   Wikipédia en Français

  • Optimisation linéaire — En optimisation, qui est une branche des mathématiques, un problème d optimisation linéaire est un problème d optimisation dans lequel on minimise une fonction linéaire sur un polyèdre convexe. La fonction coût et les contraintes peuvent donc… …   Wikipédia en Français

  • PROGRAMMATION MATHÉMATIQUE — La programmation mathématique consiste à chercher, parmi tous les points x vérifiant certaines conditions du type: celui ou ceux qui rendent minimal (ou maximal, suivant le cas) un certain critère f (x ), qui sera interprété comme un gain dans le …   Encyclopédie Universelle

  • DÉVELOPPEMENT ÉCONOMIQUE ET SOCIAL - Économie — Le terme de développement n’est usité dans son acception économique que depuis les années cinquante. Mais l’idée est plus ancienne. Elle constitue le thème central du livre d’Adam Smith, Recherches sur la nature et les causes de la richesse des… …   Encyclopédie Universelle

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Satellite artificiel — Pour les articles homonymes, voir satellite et Sat. Le satellite de météorologie GOES O avant son lancement en orbite géostationnaire …   Wikipédia en Français

  • Satellite d'astronomie — Satellite artificiel Pour les articles homonymes, voir satellite et Sat. Le satellite de météorologie GOES O avant son lancement en …   Wikipédia en Français

  • Satellite scientifique — Satellite artificiel Pour les articles homonymes, voir satellite et Sat. Le satellite de météorologie GOES O avant son lancement en …   Wikipédia en Français

  • Satellites artificiels — Satellite artificiel Pour les articles homonymes, voir satellite et Sat. Le satellite de météorologie GOES O avant son lancement en …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”