Aller au contenu

Qualification de contraintes

Un article de Wikipédia, l'encyclopédie libre.

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

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

[modifier | modifier le code]

Soient un espace normé, une partie de et un point de . On s'intéresse au calcul du cône tangent à en , que l'on note

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

est une partie d'un espace normé , est une fonction différentiable, que l'on appelle contrainte, et l'exposant «» est utilisé pour désigner l'image réciproque. On introduit le cône linéarisant

On montre facilement que

On n'a pas nécessairement l'égalité entre les deux cônes et , car peut être convexe (c'est le cas si est convexe) alors que 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 qui intervient dans la condition nécessaire d'optimalité générique de Peano-Kantorovitch alors que le cône linéarisant a l'avantage d'avoir une expression analytique que l'on aimerait pouvoir exploiter. La notion de qualification des contraintes définissant 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 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 est qualifiée en pour représenter si est dérivable en et si les deux conditions suivantes sont vérifiées :

l'opérateur linéaire adjoint de .

La seconde condition est immédiatement vérifiée si est un polyèdre convexe, car alors le cône tangent est aussi un polyèdre convexe et son dual également ; il en résulte que est un polyèdre convexe et donc un fermé. Cette condition de polyédricité sera vérifiée pour les ensembles et ci-dessous.

La qualification est une propriété de la fonction , pas de l'ensemble dont la définition utilise cette fonction. On peut en effet définir l'ensemble par diverses fonctions , sans modifier donc le cône tangent , alors que sera le plus souvent affecté par le changement de fonction . Dès lors, cette notion de qualification permet de sélectionner les bonnes fonctions , dans un sens qui dépend du contexte.

Qualification de contraintes d'égalité

[modifier | modifier le code]

L'ensemble XE

[modifier | modifier le code]

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 entre deux espaces vectoriels de dimension finie et  :

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

Conditions suffisantes de qualification de la contrainte définissant XE

[modifier | modifier le code]

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

et on dit que la contrainte définissant est qualifiée en si Une condition suffisante de qualification est la suivante.

Condition suffisante de qualification de la contrainte de  — Si est dans un voisinage de et si est surjective, alors est qualifiée en

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

[modifier | modifier le code]

L'ensemble XEI

[modifier | modifier le code]

On considère dans cette section que l'ensemble est décrit comme l'image réciproque d'un cône particulier par une application définie sur un espace vectoriel de dimension finie  :

On a noté et des ensembles d'indices formant une partition de l'ensemble des premiers entiers  :

Les cardinaux de et sont notés respectivement

si bien que Alors désigne la fonction dont les composantes sont celles de avec . De même pour . Le cône de dont est l'image réciproque par est donc

Son cône tangent en est donné par

Conditions suffisantes de qualification de la contrainte définissant XEI

[modifier | modifier le code]

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

où on a noté

l'ensemble des indices des contraintes d'inégalité actives en On rappelle que la contrainte définissant est dite qualifiée en si 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)

[modifier | modifier le code]

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) —  est affine dans un voisinage de et est continue en

Slater (QC-S)

[modifier | modifier le code]

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

Slater (QC-S) —  est continue en et

  • est une fonction affine avec surjective,
  • les composantes de sont convexes,
  • on peut trouver un point tel que et

Indépendance linéaire (QC-IL)

[modifier | modifier le code]

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) —  est de classe dans un voisinage de , est continue en et l'une des conditions équivalentes suivantes est satisfaite :

  1. les gradients des contraintes actives en sont linéairement indépendants, c'est-à-dire
    implique que pour tout
  2. est surjective,
  3. quel que soit , le sous-espace affine
    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 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)

[modifier | modifier le code]

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) —  est différentiable en est continue en et l'une des conditions équivalentes suivantes est satisfaite :

  1. la condition
    implique que pour tout
  2. pour tout , il existe une direction telle que et
  3. est surjective et il existe une direction telle que et
  4. quel que soit , le polyèdre convexe
    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)      (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 .

L'expression duale 4 des conditions de Mangasarian-Fromovitz ci-dessus est due à Gauvin (1977)[3] ; elle fait intervenir un produit scalaire sur 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 est affine, si est convexe et différentiable en et si est continue en , alors

(QC-S)      (QC-MF).

Qualification de contraintes générales

[modifier | modifier le code]

L'ensemble XG

[modifier | modifier le code]

Dans cette section, on suppose que l'ensemble est défini comme dans l'introduction de cet article, à savoir

est une fonction et est un convexe fermé non vide de l'espace euclidien . Le produit scalaire des espaces euclidiens et sont tous deux notés .

Condition suffisante de qualification de Robinson

[modifier | modifier le code]

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

(QC-R) — La condition de qualification de Robinson a lieu en si est différentiable en et si

Dans (QC-R), l'écriture est une autre manière de désigner , l'image de l'opérateur linéaire . Cette condition (QC-R) n'est pas simple ; elle est difficile à décrire géométriquement et à mémoriser. Lorsqu'elle est écrite en , 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»

Cette dernière multifonction est en effet une espèce de linéarisation en de la multifonction

qui a tout son sens dans l'analyse de puisque si, et seulement si, .

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

Condition suffisante de qualification de Robinson — Si est dans un voisinage de et si (QC-R) a lieu en , alors est qualifiée en pour représenter

La condition de Robinson peut s'écrire sous les différentes formes ci-dessous ; on y a noté le cône des directions admissibles de en .

Autres formes de (QC-R) — Si est différentiable en , alors les propriétés suivantes sont équivalentes :

  1. ,
  2. ,
  3. ,
  4. .

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

(QC-R) et régularité métrique — Si est en , alors les propriétés suivantes sont équivalentes :

  1. (QC-R) a lieu en ,
  2. il existe une constante telle que pour tout proche de , on a

Le point 2 de ce résultat est équivalent à la régularité métrique en de la multifonction définie en par parce qu'avec cette multifonction, on a et . Ce qu'affirme ce point 2 est la propriété suivante : pour tout proche de et pour toute petite perturbation de , la distance de à la perturbation de reste contrôlable par la distance de à la perturbation de .

Maintenant, le membre de droite de l'inégalité du point 2 est toujours fini ( est non vide), si bien que le membre de gauche l'est aussi; ce qui a pour conséquence que la perturbation de est non vide lorsque est suffisamment petit.

Corollaire 1: stabilité de  — Si est en et si (QC-R) a lieu en , alors pour tout petit

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

Corollaire 2: borne d'erreur pour  — Si est en et si (QC-R) a lieu en , alors il existe une constante telle que pour tout proche de , on a
  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.
  4. (en) S.M. Robinson (1976). Stability theory for systems of inequalities, part II: differentiable nonlinear systems. SIAM Journal of Numerical Analysis, 13, 487-513.

Articles connexes

[modifier | modifier le code]

Lien externe

[modifier | modifier le code]

Ouvrages généraux

[modifier | modifier le code]
  • (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.