Complémentarité linéaire

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 M\in\R^{n\times n} et d'un vecteur q\in\R^n et consiste à trouver un vecteur x\in\R^n tel que ses composantes et celles de y: = Mx + q soient positives et tel que x et y soient orthogonaux pour le produit scalaire euclidien de \R^n :

x\geqslant 0,\qquad (Mx+q)\geqslant 0 \qquad\mbox{et}\qquad x^{\!\top}(Mx+q)=0,

où x^{\top} désigne le vecteur x transposé.

Ces problèmes sont souvent NP ardus (en) et donc difficiles à résoudre lorsque la dimension n 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'équation 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 xi = 0 n'est pas atteint, c'est-à-dire que xi > 0, l'équation (Mx + q)i = 0 est active. Les exemples de problèmes modélisés par complémentarité sont nombreux ; citons les problèmes de contact, les problèmes d'apparition et de disparition de phases dans les écoulements multiphasiques, les problèmes de précipitation-dissolution en chimie, en météorologie, etc.

Sommaire

Le problème

Quelques notations

Pour un vecteur v\in\R^n, la notation v\geqslant 0 signifie que toutes les composantes vi du vecteur sont positives.

On note \R^n_+:=\{x\in\R^n:x\geqslant 0\} l'orthant positif de \R^n.

Définitions

Étant donnés une matrice réelle carrée d'ordre M\in\R^{n\times n}, non nécessairement symétrique, et un vecteur q\in\R^n, un problème de complémentarité linéaire consiste à trouver un vecteur x\in\R^n tel que

x\geqslant 0,\qquad Mx+q\geqslant 0\qquad\mbox{et}\qquad x^{\!\top}(Mx+q)=0.

Le symbole {}^{\top} ci-dessus est utilisé pour désigner la transposition du vecteur à sa gauche. Dès lors, l'orthogonalité requise de x et de Mx + q revient à demander que le produit de Hadamard de ces deux vecteurs soit nul :

x\cdot(Mx+q)=0

On écrit souvent ce problème de manière concise comme suit :

\mbox{CL}(M,q):\qquad 0\leqslant x\perp(Mx+q)\geqslant 0.

Un point x vérifiant x\geqslant 0 et Mx+q\geqslant 0 est dit admissible pour le problème CL(M,q) et l'ensemble

\mbox{Adm}(M,q):=\{x\in\R^n: x\geqslant 0,~Mx+q\geqslant 0\}

est appelé l'ensemble admissible de ce problème. On dit que le problème CL(M,q) est réalisable si \mbox{Adm}(M,q)\ne\varnothing. On montre facilement que

\R^n_+-M(\R^n_+)=\{q\in\R^n:\mbox{Adm}(M,q)\ne\varnothing\},

où \R^n_+:=\{x\in\R^n:x\geqslant 0\}.

On note

Sol(M,q)

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].

Lien avec l'optimisation quadratique

Considérons le problème d'optimisation quadratique en x\in\R^n suivant :

\mbox{(PQ)}\qquad \left\{\begin{array}{l} \min\;x^{\!\top}(Mx+q)\\ x\geqslant 0\\ Mx+q\geqslant 0. \end{array}\right.

Comme le coût de ce problème est borné inférieurement sur l'ensemble admissible (il y est positif), ce problème a toujours une solution (Frank et Wolfe, 1956[2]). On en déduit alors que

x\in\operatorname{Sol}(M,q)\quad\Longleftrightarrow\quad x est solution de (PQ) avec un coût optimal nul.

On notera cependant que (PQ) est, en général, un problème non convexe, si bien que la résolution de \operatorname{CL}(M,q) passant par celle de (PQ) n'est guère aisée.

Formulations au moyen d'équations

On peut exprimer le problème de complémentarité 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 f:\R^2\to\R est une C-fonction si

f(a,b)=0 \qquad\Longleftrightarrow\qquad ab=0,\quad a\geqslant 0,\quad b\geqslant 0.

Une C-fonction permet donc de remplacer le problème CL(M,q) par le système d'équations non linéaires

F(x) = 0,

où F:\R^n\to\R^n a sa composante i définie par

Fi(x) = f(Fi(x),Gi(x)).

On n'a pas intérêt à avoir des C-fonctions f différentiables, car alors F'(x) 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

La C-fonction la plus simple est la fonction min :

fmin (a,b) = min(a,b).

Elle semble avoir été proposée pour la première fois par Kostreva (1976)[4] et Mangasarian (1977)[5]. On montre fcilement qu'il s'agit bien d'une C-fonction. Dès lors

\min(x,Mx+q)=0 \qquad\Longleftrightarrow\qquad x\in\mbox{Sol}(M,q),

où la fonction min agit composante par composante : min(u,v)i = min(ui,vi) pour tout indice i.

La C-fonction de Fischer-Burmeister

La fonction de Fischer-Burmeister [6],[7] est définie par :

f_{\rm\scriptscriptstyle FB}(a,b)=\sqrt{a^2+b^2}-(a+b).

On montre facilement qu'il s'agit d'une C-fonction, convexe, différentiable partout sauf en (0,0) et que son carré est continûment différentiable.

Galerie de matrices adaptées

Les 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 grandes classes de matrices et les propriétés de CL(M,q) qui y sont associées.

  1. Les \mathbf{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 :

    \bar{x}^1\in\operatorname{Sol}(M,q^1),\quad\bar{x}^2\in\operatorname{Sol}(M,q^2),\quad q^1\leqslant q^2\quad\Longrightarrow\quad\bar{x}^1\geqslant\bar{x}^2.

  2. Les matrices suffisantes en colonne sont celles qui assurent la convexité de l'ensemble des solutions \operatorname{Sol}(M,q), quel que soit q\in\R^n.
  3. Les matrices suffisantes en ligne sont celles qui assurent que, quel que soit q\in\R^n, l'ensemble des solutions \operatorname{Sol}(M,q) est identique à l'ensemble des points stationnaires du problème quadratique associé (PQ).
  4. Les \mathbf{P}-matrices sont celles qui assurent l'existence et l'unicité de solution pour le problème CL(M,q), quel que soit q\in\R^n[8].
  5. Les \mathbf{Q_0}-matrices sont celles qui assurent que le problème CL(M,q) a une solution lorsqu'il est réalisable.
  6. Les \mathbf{R_0}-matrices sont celles qui assurent que x = 0 est l'unique solution de CL(M,0).
  7. Les \mathbf{S}-matrices sont celles qui assurent que l'ensemble admissible \mbox{Adm}(M,q)\ne\varnothing, quel que soit q\in\R^n.
  8. Les \mathbf{Z}-matrices sont celles qui assurent l'existence d'un minimum (pour l'ordre \leqslant de \R^n) de Adm(M,q), qui est solution de CL(M,q), pour tout q rendant l'ensemble admissible \mbox{Adm}(M,q)\ne\varnothing.

Méthodes de résolution

Comme toujours, 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

Les 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).

  • Algorithme de Lemke (en)
  • Algorithme du pivot principal

Méthodes de points intérieurs

Méthodes non lisses

La 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.

Algorithme de Newton-min

L'algorithme consiste à résoudre \operatorname{CL}(M,q), au moyen d'itérations de Newton semi-lisse[9], l'équation équivalente, formulée au moyen de la C-fonction min :

F_{\min}(x)\equiv\min(x,Mx+q)=0.

L'algorithme de Newton-min est bien défini si M est non dégénérée, c'est-à-dire si toutes ses sous-matrices principales sont inversibles.

Algorithme de Newton-min — On se donne un point/itéré initial x^0\in\R^n et un seuil de tolérance \varepsilon\geqslant 0. L'algorithme de Newton-min définit une suite d'itérés x^1, x^2, \ldots \in\R^n, jusqu'à ce qu'un test d'arrêt soit satisfait. Il passe de xk à xk + 1 par les étapes suivantes.

  1. Test d'arrêt : si \min(x^k,Mx^k+q) \leqslant \varepsilon, arrêt.
  2. Sélection d'indices :
    A_k:=\{i:x^k_i\leqslant(Mx^k+q)_i\}\qquad\mbox{et}\qquad I_k:=\{i:x^k_i>(Mx^k+q)_i\}
  3. Nouvel itéré :
    x^{k+1}_{A_k} = 0\qquad\mbox{et}\qquad (Mx^{k+1}+q)_{I_k}=0.

En pratique, il faut prendre ε > 0 ; la valeur nulle de cette tolérance est admise uniquement pour simplifier l'expression des résultats de convergence ci-dessous. Il s'agit donc d'une méthode de Newton semi-lisse dans laquelle le système linéaire à résoudre à chaque itération est posé en utilisant une pseudo-jacobienne de Fmin  en x. On a choisi de mettre dans Ak tous les indices i pour lesquels x^k_i=(Mx^k+q)_i, appelés indices actifs, dans le but de minimiser l'ordre | Ik | du système linéaire à résoudre à l'étape 3 de chaque itération.

Les premières traces de cet algorithme se trouvent chez Chandrasekaran (1970[10]), mais il semble bien que ce soit Aganagić (1984[11]) qui l'ait clairement présenté et étudié, d'ailleurs sous une forme un peu plus générale que celle présentée ici. Il fut ensuite redécouvert et généralisé aux problèmes de commande optimale quadratiques par Bergounioux, Ito et Kunisch (1999[12]).

Voici quelques résultats connus pour cet algorithme en fonction de la classe de matrices à laquelle M appartient (on suppose ci-dessous que ε = 0).

  • Si M est non dégénérée et si \operatorname{CL}(M,q) a une solution, l'algorithme converge localement, en un nombre fini d'étapes[13].
  • Si M est une \mathbf{P}-matrice, la convergence locale est superlinéaire[14] et la convergence globale est assurée si n = 1 ou n = 2, mais ne l'est pas nécessairement pour n\geqslant 3 (il existe des contre-exemples)[15].
  • Si M est suffisamment proche d'une \mathbf{M}-matrice, l'algorithme converge globalement, avec \{\textstyle\sum_ix^k_i\} croissante[14].
  • Si M est une \mathbf{M}-matrice, l'algorithme converge globalement, avec {xk} croissante dès la seconde itération (pour l'ordre de \R^n induit par \leqslant)[11] et en au plus n itérations[16].

L'algorithme de Newton-min est difficile à globaliser, car la direction xk + 1 − xk n'est pas nécessairement une direction de descente en xk de la fonction de mérite naturelle pour cette approche, à savoir

x\mapsto\frac{1}{2}\|\min(x,Mx+q)\|^2_2.

Un meilleur choix des indices actifs allant dans Ak ou Ik permettrait de générer des directions de descente, mais un bon choix est de nature combinatoire ; il peut par exemple être déterminé en résolvant un problème de complémentarité[17], ce qui n'est guère séduisant lorsque l'on veut justement résoudre un tel problème.

Algorithme de Newton-Fischer-Burmeister

Méthodes non lisses régularisées

On 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[18]). Cette approche est reliée à celle par points intérieurs.

Autres méthodes

Complexité

Annexes

Notes

  1. ↑ (en) M.J.M. Janssen (1983). On the structure of the solution set of a linear complementarity problem. Cahiers Centre Études Rech. Opér., 25, 41–48.
  2. ↑ (en) M. Frank, P. Wolfe (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3, 95–110.
  3. ↑ Facchinei et Pang (2003), proposition 9.1.1.
  4. ↑ (en) M. Kostreva (1976). Direct Algorithms for Complementarity Problems. Ph.D. thesis, Rensselaer Polytechnic Institute, Troy, New York.
  5. ↑ (en) O. Mangasarian (1977). Solution of symmetric linear complementarity problems by iterative methods. Journal of Optimization Theory and Applications, 22, 465–485.
  6. ↑ (en) A. Fischer (1992). A special Newton-type optimization method. Optimization, 24, 269–284.
  7. ↑ (en) A. Fischer (1995). A Newton-type method for positive semidefinite linear complementarity problems. Journal of Optimization Theory and Applications, 86, 585–608.
  8. ↑ (en) H. Samelson, R.M. Thrall, O. Wesler (1958). A partition theorem for the Euclidean n-space. Proceedings of the American Mathematical Society, 9, 805–807.
  9. ↑ (en) L. Qi, J. Sun (1993). A nonsmooth version of Newton’s method. Mathematical Programming, 58, 353–367.
  10. ↑ (en) R. Chandrasekaran (1970). A special case of the complementary pivot problem. Opsearch, 7, 263–268.
  11. ↑ a et b (en) M. Aganagić (1980). Newton’s method for linear complementarity problems. Mathematical Programming, 28, 349–362 (1984).
  12. ↑ (en) M. Bergounioux, K. Ito, K. Kunisch (1999). Primal-dual strategy for constrained optimal control problems. SIAM Journal on Control and Optimization, 37, 1176–1194.
  13. ↑ (en) A. Fischer, C. Kanzow (1996). On finite termination of an iterative method for linear complementarity problems. Mathematical Programming, 74, 279–292.
  14. ↑ a et b (en) M. Hintermuüller, K. Ito, K. Kunisch (2003). The primal-dual active set strategy as a semismooth Newton method. SIAM Journal on Optimization, 13, 865–888.
  15. ↑ (en) I. Ben Gharbia, J.Ch. Gilbert (2011). Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix. Mathematical Programming (à paraître). doi
  16. ↑ (en) Ch. Kanzow (2004). Inexact semismooth Newton methods for large-scale complementarity problems. Optimization Methods and Software, 19, 309–325.
  17. ↑ (en) P.T. Harker, J.-S. Pang (1990). A damped-Newton method for the linear complementarity problem. In E.L. Allgower, K. Georg (éditeurs), Computational Solution of Nonlinear Systems of Equations, Lecture in Applied Mathematics 26. AMS, Providence, RI.
  18. ↑ (en) C. Chen, O.L. Mangasarian (1995). Smoothing methods for convex inequalities and linear complementary problems. Mathematical Programming, 71, 1–112. doi

Ouvrages généraux

  • (en) R. W. Cottle, J.-S. Pang, R. E. Stone (2009). The linear complementarity problem. Classics in Applied Mathematics 60. SIAM, Philadelphia, PA, USA.
  • (en) F. Facchinei, J.-S. Pang (2003). Finite-Dimentional Variational Inequalities and Complementarity Problems (2 volumes). Springer Series in Operations Research. Springer-Verlag, New York.
  • (en) K.G. Murty (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics, 3. Heldermann Verlag, Berlin. ISBN 978-3-88538-403-8. Téléchargeable sur le site de l'auteur.

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Programmation non linéaire — Optimisation (mathématiques) En mathématiques, l optimisation est l’étude des problèmes qui sont de la forme : Étant donné : une fonction d’un ensemble A dans l ensemble des nombre réels Rechercher : un élément x0 de A tel que pour …   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

  • Matrice suffisante — En mathématiques, les termes suffisante en colonne, suffisante en ligne et suffisante qualifient des matrices carrées réelles apportant des propriétés particulières aux problèmes de complémentarité linéaire. Brièvement, une matrice est dite… …   Wikipédia en Français

  • P-matrice — En mathématiques, une matrice est une matrice carrée réelle dont les mineurs principaux sont strictement positifs. Ces matrices interviennent dans l étude des problèmes de complémentarité linéaire. Une notion voisine est celle des matrices.… …   Wikipédia en Français

  • M-matrice — En mathématiques, une matrice est une matrice carrée réelle qui est à la fois une matrice et une matrice, ce qui signifie que tous ses mineurs principaux sont strictement positifs et que ses éléments extra diagonaux sont négatifs. D autres… …   Wikipédia en Français

  • Z-matrice — En mathématiques, une matrice est une matrice carrée réelle dont les éléments extra diagonaux sont négatifs. Ces matrices apportent des propriétés particulières aux problèmes de complémentarité linéaire. Sommaire 1 Définitions 2 Propriété …   Wikipédia en Français

  • Q0-matrice — En mathématiques, une matrice est une matrice carrée réelle apportant des propriétés particulières aux problèmes de complémentarité linéaire. Ce sont celles qui assurent l existence d une solution dès que le problème est réalisable. Sommaire 1… …   Wikipédia en Français

  • R0-matrice — En mathématiques, une matrice est une matrice carrée réelle apportant des propriétés particulières aux problèmes de complémentarité linéaire. Ces propriétés, difficilement exprimables en quelques mots, sont décrites dans la définition donnée ci… …   Wikipédia en Français

  • S-matrice — En mathématiques, une matrice est une matrice carrée réelle dont l image de l orthant positif intersecte l intérieur de cet orthant. Ces matrices apportent des propriétés particulières aux problèmes de complémentarité linéaire. Sommaire 1… …   Wikipédia en Français

  • Optimisation (mathématiques) — L optimisation est une branche des mathématiques, cherchant à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à déterminer le meilleur élément d un ensemble, au sens d un critère quantitatif donné. Ce mot vient …   Wikipédia en Français

Share the article and excerpts

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