Complémentarité linéaire
En mathématiques, et plus spécialement en recherche opérationnelle et en optimisation, un problème de complémentarité linéaire est défini par la donnée d'une matrice et d'un vecteur et consiste à trouver un vecteur tel que ses composantes et celles de soient positives et tel que x et y soient orthogonaux pour le produit scalaire euclidien de :
où désigne le vecteur x transposé. Ce problème peut être vu comme un cas particulier d'inéquation variationnelle.
Ces problèmes sont souvent NP-difficiles et donc difficiles à résoudre lorsque la dimension du problème devient grande. La combinatoire du problème vient du fait qu'il faut déterminer quelles sont les composantes de la solution qui sont nulles et il y a 2n possibilités de réaliser cela.
Les problèmes de complémentarité se sont d'abord manifestés dans les conditions d'optimalité des problèmes d'optimisation, les conditions de Karush, Kuhn et Tucker. Elles permettent de modéliser des problèmes décrits par plusieurs systèmes d'équations qui sont en quelque sorte en compétition ; celui qui est actif en un endroit et temps donnés, correspondant à un indice commun de x et de y, dépend de seuils qui sont ou non atteints : si le seuil n'est pas atteint, c'est-à-dire que , l'équation est active. Les exemples de problèmes modélisés par complémentarité sont nombreux : problèmes de contact, problèmes d'apparition et de disparition de phases dans les écoulements multiphasiques, problèmes de précipitation-dissolution en chimie, en météorologie, etc.
Problème
modifierNotations préliminaires
modifierPour un vecteur , la notation signifie que toutes les composantes du vecteur sont positives ou nulles.
On note l'orthant positif de .
Pour deux parties A et B d'un espace vectoriel, désigne leur somme de Minkowski, qui est l'ensemble .
Définitions
modifierÉtant donnés une matrice réelle carrée , non nécessairement symétrique, et un vecteur , un problème de complémentarité linéaire consiste à trouver un vecteur tel que
Le symbole ci-dessus est utilisé pour désigner la transposition du vecteur à sa gauche. Dès lors, l'orthogonalité requise de x et de revient à demander que le produit de Hadamard de ces deux vecteurs soit nul :
On écrit souvent ce problème de manière concise comme suit :
Un point x vérifiant et est dit admissible pour le problème CL(M,q) l'ensemble
est appelé l'ensemble admissible de ce problème. On dit que le problème CL(M,q) est réalisable si . On montre facilement que
On note
l'ensemble des solutions du problème de complémentarité linéaire CL(M,q) ; c'est une réunion de polyèdres convexes[1].
Liens avec d'autres problèmes
modifierConditions d'optimalité d'un problème d'optimisation quadratique
modifierLes conditions d'optimalité d'un problème d'optimisation quadratique peuvent s'exprimer comme un problème de complémentarité linéaire. En effet, considérons le problème d'optimisation quadratique générique
où , est une matrice symétrique (non nécessairement semi-définie positive), et . Ses conditions d'optimalité du premier ordre s'écrivent pour des multiplicateurs et :
En éliminant le multiplicateur z, on obtient un système formé de deux problèmes de complémentarité linéaire couplés
Celui-ci peut s'exprimer comme un unique problème de complémentarité linéaire :
Par ailleurs, lorsque est symétrique semi-définie positive, le problème CL(M,q) est équivalent au problème d'optimisation quadratique
En effet, dans les conditions énoncées, le problème d'optimisation quadratique est équivalent à ses conditions d'optimalité du premier ordre : il existe tel que
Après élimination du multiplicateur z, on obtient CL(M,q).
Expression sous forme de problème d'optimisation quadratique
modifierConsidérons le problème d'optimisation quadratique en suivant :
Si le problème de complémentarité linéaire CL(M,q) est admissible, c'est-à-dire si , l'ensemble admissible du problème quadratique est non vide. Dans ce cas, ce problème quadratique a une solution (car son coût est borné inférieurement sur l'ensemble admissible - il y est positif, voir Frank et Wolfe, 1956[2]) et donc des points stationnaires. On note
l'ensemble des points stationnaires du problème d'optimisation quadratique . On a et, par le raisonnement précédent,
On a bien sûr
On notera cependant que (PQ) est, en général, un problème non convexe, si bien que la résolution de CL(M,q) passant par celle de (PQ) n'est guère aisée.
Cas particulier d'inéquation variationnelle
modifierUn problème d'inéquation variationnelle sur est défini au moyen d'un produit scalaire sur , d'un ensemble non vide et d'une fonction . Il consiste à trouver un point tel que
Si le produit scalaire est le produit sclalaire euclidien , si est l'orthant positif et si , le problème d'inéquation variationnelle ci-dessus n'est autre que le problème de complémentarité linéaire CL(M,q).
Reformulations au moyen d'équations
modifierOn peut exprimer le problème de complémentarité linéaire CL(M,q) au moyen d'équations, en général non lisses, c'est-à-dire non différentiables. Les fonctions qui interviennent dans cette formulation et dont on cherche un zéro sont appelées des C-fonctions (C pour complémentarité). Cette formulation est utilisée par des algorithmes de résolution.
On dit que est une C-fonction si
Une C-fonction permet donc de remplacer le problème CL(M,q) par le système d'équations non linéaires
où a sa composante définie par
On n'a pas intérêt à avoir des C-fonctions différentiables, car alors n'est pas inversible en une solution dégénérée x[3] (et donc l'algorithme de Newton ne fonctionne pas). Il semblerait que des C-fonctions non lisses conduisent à des algorithmes plus efficaces.
On trouvera ci-après quelques exemples de C-fonctions et leurs propriétés.
La C-fonction min
modifierLa C-fonction la plus simple est la fonction min :
Elle semble avoir été proposée pour la première fois par Kostreva (1976)[4] et Mangasarian (1977)[5]. On montre facilement qu'il s'agit bien d'une C-fonction. Dès lors
où la fonction min agit composante par composante : pour tout indice .
La C-fonction de Fischer-Burmeister
modifierLa fonction de Fischer-Burmeister[6],[7] est définie par :
On montre facilement qu'il s'agit d'une C-fonction, convexe, différentiable partout sauf en et que son carré est continûment différentiable.
Galerie de matrices adaptées
modifierLes propriétés des problèmes de complémentarité linéaire dépendent, bien sûr, de celles de la matrice M. Ces propriétés sont très variées et ne dépendent pas d'un seul type de matrices. La situation est donc beaucoup plus complexe et très différente de celle rencontrée dans la résolution d'un système d'équations linéaires, dont les propriétés dépendent pour beaucoup de l'inversibilité de la matrice définissant le système. Nous énumérons ci-dessous quelques classes remarquables de matrices et les propriétés du problème de complémentarité linéaire CL(M,q) qui y sont associées. Ces classes de matrices ont souvent (mais pas toujours) des caractérisations algébriques qui permettent de reconnaître leurs membres.
- Les M-matrices sont celles qui assurent l'existence et l'unicité de solution pour le problème CL(M,q), avec la propriété de monotonie suivante :
- Les matrices non dégénérées sont celles pour lesquelles, quel que soit , toute solution éventuelle de CL(M,q) est localement unique.
- Les matrices suffisantes en colonne sont celles qui assurent la convexité de l'ensemble des solutions , quel que soit .
- Les matrices suffisantes en ligne sont celles qui assurent que, quel que soit , l'ensemble des solutions est identique à l'ensemble des points stationnaires du problème quadratique associé (PQ).
- Les P-matrices sont celles qui assurent l'existence et l'unicité de solution pour le problème CL(M,q), quel que soit [8].
- Les Q-matrices sont celles qui assurent l'existence de solution pour le problème CL(M,q), quel que soit .
- Les Q0-matrices sont celles qui assurent que le problème CL(M,q) a une solution lorsqu'il est réalisable.
- Les R0-matrices sont celles qui assurent que est l'unique solution de CL(M,q).
- Les S-matrices sont celles qui assurent que l'ensemble admissible , quel que soit .
- Les Z-matrices sont celles qui assurent l'existence d'un minimum (pour l'ordre de ) de Adm(M,q), qui est solution de CL(M,q), pour tout q rendant l'ensemble admissible .
Existence de solution
modifierOn recense (au moins) deux stratégies pour démontrer qu'un problème de complémentarité linéaire a une solution. La première passe par le problème quadratique associé (PQ) et ses conditions d'optimalité. La seconde repose sur le théorème du point fixe de Brouwer. On ne pense pas aujourd'hui (2013) avoir fait le tour de la question, en particulier, parce qu'on ne sait pas décrire algébriquement la classe des Q-matrices, celles qui assurent l'existence d'une solution quel que soit le vecteur q.
Approche par l'optimisation
modifierDans cette approche, on cherche à montrer que le problème quadratique (PQ) a une valeur optimale nulle. Comme ce problème quadratique a une solution (Frank et Wolfe, 1956[2]), celle-ci est alors solution du problème de complémentarité linéaire CL(M,q).
Par exemple, pour montrer que le problème de complémentarité linéaire a une solution dans le cas où M est une P-matrice, on écrit les conditions d'optimalité de (PQ) en une solution x : comme les contraintes sont qualifiées, il existe des multiplicateurs optimaux et z tels que
Il suffit alors de montrer que pour déduire de (c) que x est solution de CL(M,q). Par quelques manipulations algébriques astucieuses, on peut obtenir qui implique que grâce à la P-matricité de , qui se déduit de celle de M.
Approche par point fixe
modifierDans cette approche, on commence par introduire un problème de complémentarité linéaire augmenté défini par
où et . Ce problème s'écrit comme un système de deux problèmes de complémentarité linéaire couplés, l'un en , l'autre en :
On voit que si l'on réussit à montrer que a une solution avec , x sera solution de CL(M,q) (par le problème (a) ci-dessus). Le plus souvent, on n'obtiendra ces circonstances qu'après un passage à la limite.
Existence de solution du problème augmenté
modifierLa première étape consiste donc à choisir et de telle sorte que le problème augmenté ait une solution. Voici deux résultats, le premier suppose que M est symétrique, le second pas.
Existence de solution du PCL augmenté avec M symétrique — Si M est symétrique et si et sont comme ci-dessus, avec et tels que est bornée inférieurement sur , , alors a une solution.
La démonstration repose sur le fait que, dans les conditions énoncées, le problème d'optimisation quadratique
a une solution (Frank et Wolfe, 1956[2]). Celle-ci vérifie les conditions d'optimalité du premier ordre, qui ne sont autres que les conditions (a) et (b) ci-dessus.
Lorsque M n'est pas symétrique, on exprime comme un problème d'inéquation variationnelle dans lequel
Bien sûr est convexe et fermé. Pour le rendre non vide et borné (afin d'appliquer le théorème d'existence de solution d'une IV), il est naturel de prendre et . On obtient alors le résultat suivant.
Existence de solution du PCL augmenté — Si et sont donnés comme ci-dessus, avec et , alors a une solution.
Existence de solution du problème original
modifierLa seconde étape consiste à donner des conditions permettant de trouver une solution de CL(M,q) à partir d'une solution de . Le résultat suivant donne des conditions suffisantes pour que le multiplicateur dans (a) et (b) ci-dessus soit nul.
CS d'existence de solution du PCL — Soient et . S'il existe un vecteur et un scalaire tels que la fonction quadratique soit positive sur , , alors CL(M,q) a une solution.
Dans les conditions nécessaires et suffisantes d'existence de solution du problème CL(M,q) données ci-dessous, on ne peut garantir que dans (a) et (b) ci-dessus, mais on suppose que des solutions d'une suite de problèmes augmentés , , sont telles que zéro adhère à .
CNS d'existence de solution du PCL — Soient , et . Les propriétés suivantes sont équivalentes.
- Le problème CL(M,q) a une solution.
- Pour toute suite non bornée , les problèmes , avec
ont des solutions telles que zéro est un point d'accumulation de . - Il existe une suite non bornée , telle que les problèmes , avec donné comme au point 2, ont des solutions avec .
On peut utiliser ce résultat pour montrer que
- les matrices strictement copositives sont des Q-matrices,
- un problème CL(M,q) avec M copositive et (dual positif) a une solution.
Méthodes de résolution
modifierComme on peut s'y attendre, il n'y a pas d'algorithme idéal pour résoudre un problème de complémentarité linéaire, mais un ensemble d'algorithmes qui sont, par leurs caractéristiques, plus ou moins adaptés à des classes particulières de problèmes.
Méthodes de pivotage
modifierLes méthodes de pivotage ont une complexité pire-cas exponentielle. Pour une description des approches algorithmiques de ce type, voir Murty (1988), Cottle et Pang (2009).
Méthodes de points intérieurs
modifier- Méthodes affines
- Méthodes de réduction du potentiel
- Méthodes de trajectoire centrale de type primal-dual
Méthodes non lisses
modifierMéthodes non lisses brutes
modifierLa stratégie suivie ici consiste à exprimer le problème de complémentarité linéaire au moyen d'une C-fonction et à résoudre le système non lisse résultant par des itérations apparentées à celles de Newton.
Méthodes non lisses régularisées
modifierOn exprime le problème de complémentarité linéaire comme une équation non lisse à résoudre (voir la section Méthodes non lisses) et on régularise celle-ci. Cette régularisation dépend d'un paramètre que l'on réduit au cours des itérations. Voir par exemple, la contribution de Chen et Mangasarian (1995[9]).
Cette approche est apparentée à celle par points intérieurs. Leur analyse conduit à des résultats de convergence globale et locale rapide, sans résultat de complexité (contrairement aux algorithmes de points intérieurs).
Autres méthodes
modifierComplexité
modifierAnnexes
modifierNotes
modifier- (en) M.J.M. Janssen, « On the structure of the solution set of a linear complementarity problem », Cahiers Centre Études Rech. Opér., vol. 25, , p. 41–48.
- (en) M. Frank et P. Wolfe, « An algorithm for quadratic programming », Naval Research Logistics Quarterly, vol. 3, , p. 95–110.
- Facchinei et Pang (2003), proposition 9.1.1.
- (en) M. Kostreva, Direct Algorithms for Complementarity Problems. Ph.D. thesis., Troy, New York, Rensselaer Polytechnic Institute, .
- (en) O. Mangasarian, « Solution of symmetric linear complementarity problems by iterative methods », Journal of Optimization Theory and Applications, vol. 22, , p. 465–485.
- (en) A. Fischer, « A special Newton-type optimization method », Optimization, vol. 24, , p. 269–284.
- (en) A. Fischer, « A Newton-type method for positive semidefinite linear complementarity problems », Journal of Optimization Theory and Applications, vol. 86, , p. 585–608.
- (en) H. Samelson, R.M. Thrall et O. Wesler, « A partition theorem for the Euclidean n-space », Proceedings of the American Mathematical Society, vol. 9, , p. 805–807.
- (en) C. Chen et O.L. Mangasarian, « Smoothing methods for convex inequalities and linear complementary problems », Mathematical Programming, vol. 71, , p. 1–112 (DOI 10.1007/BF01592244)
Ouvrages généraux
modifier- (en) R. W. Cottle, J.-S. Pang et R. E. Stone, The Linear Complementarity Problem, Philadelphia, PA, SIAM, coll. « Classics in Applied Mathematics » (no 60),
- (en) F. Facchinei et J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems (2 vol.), New York, Springer-Verlag, coll. « Springer Series in Operations Research »,
- (en) K. G. Murty, Linear Complementarity, Linear and Nonlinear Programming, Berlin, Heldermann Verlag, coll. « Sigma Series in Applied Mathematics » (no 3), (ISBN 978-3-88538-403-8), téléchargeable sur le site de l'auteur