Complémentarité linéaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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,

x^{\top} 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 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 2^n 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 x_i=0 n'est pas atteint, c'est-à-dire que x_i>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.

Le problème[modifier | modifier le code]

Quelques notations[modifier | modifier le code]

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

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

Définitions[modifier | modifier le code]

Étant donnés une matrice réelle carrée 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 \mbox{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 \mbox{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\}.

On note


\mbox{Sol}(M,q)

l'ensemble des solutions du problème de complémentarité linéaire \mbox{CL}(M,q) ; c'est une réunion de polyèdres convexes[1].

Liens avec l'optimisation quadratique[modifier | modifier le code]

Conditions d'optimalité et complémentarité[modifier | modifier le code]

Les 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


\left\{\begin{array}{l}
\textstyle\inf_{x\in\R^n}\,g^\top x+\frac{1}{2}\,x^\top Hx\\
Ax\geqslant b\\
x\geqslant0,
\end{array}\right.

g\in\R^n, H\in\R^{n\times n} est une matrice symétrique (non nécessairement semi-définie positive), A\in\R^{m\times n} et b\in\R^m. Ses conditions d'optimalité du premier ordre s'écrivent pour des multiplicateurs y\in\R^m et z\in\R^n :


\left\{\begin{array}{l}
g+Hx-A^\top y-z=0\\
0\leqslant y\perp (Ax-b)\geqslant0\\
0\leqslant z\perp x\geqslant0.
\end{array}\right.

En éliminant le multiplicateur z, on obtient un système formé de deux problèmes de complémentarité linéaire couplés


\left\{\begin{array}{l}
0\leqslant y\perp (Ax-b)\geqslant0\\
0\leqslant (g+Hx-A^\top y)\perp x\geqslant0.
\end{array}\right.

Celui-ci peut s'exprimer comme un unique problème de complémentarité linéaire :


0\leqslant
\begin{pmatrix}x\\y\end{pmatrix}
\perp
\begin{pmatrix}H&-A^\top\\A&0\end{pmatrix}
\begin{pmatrix}x\\y\end{pmatrix}+
\begin{pmatrix}g\\-b\end{pmatrix}
\geqslant0.

Par ailleurs, lorsque M\in\R^{n\times n} est symétrique semi-définie positive, le problème \operatorname{CL}(M,q) est équivalent au problème d'optimisation quadratique


\left\{\begin{array}{l}
\textstyle\inf_{x\in\R^n}\,q^\top x+\frac{1}{2}\,x^\top Mx\\
x\geqslant0.
\end{array}\right.

En effet, dans les conditions énoncées, le problème d'optimisation quadratique est équivalent à ses conditions d'optimalité du premier ordre : il existe (x,z)\in\R^n\times\R^n tel que


\left\{\begin{array}{l}
q+Mx-z=0\\
0\leqslant x\perp z\geqslant0.
\end{array}\right.

Après élimination du multiplicateur z, on obtient \operatorname{CL}(M,q).

Complémentarité linéaire comme problème d'optimisation quadratique[modifier | modifier le code]

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.

Si le problème de complémentarité linéaire \operatorname{CL}(M,q) est admissible, c'est-à-dire si \mbox{Adm}(M,q)\ne\varnothing, l'ensemble admissible du problème quadratique (\mbox{PQ}) 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


\mbox{Sta}(M,q)

l'ensemble des points stationnaires du problème d'optimisation quadratique (\mbox{PQ}). On a \mbox{Sol}(M,q)\subset\mbox{Sta}(M,q)\subset\mbox{Adm}(M,q) et, par le raisonnement précédent,


\mbox{Adm}(M,q)\ne\varnothing
\qquad\Longrightarrow\qquad
\mbox{Sta}(M,q)\ne\varnothing.

On a bien sûr

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

On peut exprimer le problème de complémentarité \mbox{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 \mbox{CL}(M,q) par le système d'équations non linéaires


F(x)=0,

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


F_i(x)= f(F_i(x),G_i(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[modifier | modifier le code]

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


f_{\min}(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 facilement 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(u_i,v_i) pour tout indice i.

La C-fonction de Fischer-Burmeister[modifier | modifier le code]

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

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 classes remarquables de matrices et les propriétés du problème de complémentarité linéaire \mbox{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.

  1. Les \mathbf{M}-matrices sont celles qui assurent l'existence et l'unicité de solution pour le problème \mbox{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 non dégénérées sont celles pour lesquelles, quel que soit q\in\R^n, toute solution éventuelle de \mbox{CL}(M,q) est localement unique.
  3. 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.
  4. 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).
  5. Les \mathbf{P}-matrices sont celles qui assurent l'existence et l'unicité de solution pour le problème \mbox{CL}(M,q), quel que soit q\in\R^n[8].
  6. Les \mathbf{Q}-matrices sont celles qui assurent l'existence de solution pour le problème \mbox{CL}(M,q), quel que soit q\in\R^n.
  7. Les \mathbf{Q_0}-matrices sont celles qui assurent que le problème \mbox{CL}(M,q) a une solution lorsqu'il est réalisable.
  8. Les \mathbf{R_0}-matrices sont celles qui assurent que x=0 est l'unique solution de \mbox{CL}(M,0).
  9. 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.
  10. Les \mathbf{Z}-matrices sont celles qui assurent l'existence d'un minimum (pour l'ordre \leqslant de \R^n) de \mbox{Adm}(M,q), qui est solution de \mbox{CL}(M,q), pour tout q rendant l'ensemble admissible \mbox{Adm}(M,q)\ne\varnothing.

Existence de solution[modifier | modifier le code]

On 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[modifier | modifier le code]

Dans 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 \mbox{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 \mathbf{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 s et z tels que


\left\{\begin{array}{ll}
(a) & (M+M^\top)x+q-s-M^\top z=0\\
(b) & 0\leqslant x \perp s\geqslant0\\
(c) & 0\leqslant(Mx+q)\perp z\geqslant0.
\end{array}\right.

Il suffit alors de montrer que z=x pour déduire de (c) que x est solution de \mbox{CL}(M,q). Par quelques manipulations algébriques astucieuses, on peut obtenir (x-z)\cdot M^\top(x-z)\leqslant0 qui implique que z=x grâce à la \mathbf{P}-matricité de M^\top, qui se déduit de celle de M.

Approche par point fixe[modifier | modifier le code]

Dans cette approche, on commence par introduire un problème de complémentarité linéaire augmenté \mbox{CL}(\tilde{M},\tilde{q}) défini par


\tilde{M}=\begin{pmatrix}M&p\\-p^\top&0\end{pmatrix}\in\R^{(n+1)\times(n+1)}
\qquad\mbox{et}\qquad
\tilde{q}=\begin{pmatrix}q\\r\end{pmatrix}\in\R^{n+1},

p\in\R^n et r\in\R. Ce problème s'écrit comme un système de deux problèmes de complémentarité linéaire couplés, l'un en x\in\R^n, l'autre en \alpha\in\R :


\left\{\begin{array}{ll}
(a) & 0 \leqslant x \perp (Mx+q+\alpha p) \geqslant 0\\
(b) & 0 \leqslant \alpha \perp (r-p^\top x) \geqslant 0.
\end{array}\right.

On voit que si l'on réussit à montrer que \mbox{CL}(\tilde{M},\tilde{q}) a une solution (x,\alpha) avec \alpha=0, x sera solution de \mbox{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é[modifier | modifier le code]

La première étape consiste donc à choisir p\in\R^n et r\in\R de telle sorte que le problème augmenté \mbox{CL}(\tilde{M},\tilde{q}) 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 \tilde{M} et \tilde{q} sont comme ci-dessus, avec p\in\R^n et r\in\R tels que x\mapsto\frac{1}{2} x^\top Mx+q^\top x est bornée inférieurement sur \{x\in\R^n:x\geqslant0, p^\top x\leqslant r\}\ne\varnothing, alors \operatorname{CL}(\tilde{M},\tilde{q}) a une solution.

La démonstration repose sur le fait que, dans les conditions énoncées, le problème d'optimisation quadratique


\left\{\begin{array}{l}
\textstyle\inf_x\,\frac{1}{2} x^\top Mx+q^\top x\\
x\geq0,\\
p^\top x\leq r,
\end{array}\right.

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 \operatorname{CL}(\tilde{M},\tilde{q}) comme un problème d'inéquation variationnelle \operatorname{IV}(F,K) dans lequel


F:\R^n\to\R^n:x\mapsto Mx+q
\qquad\mbox{et}\qquad
K:=\{x\in\R^n:x\geqslant0,~p^\top x\leqslant r\}.

Bien sûr K 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 p>0 et r\geqslant0. On obtient alors le résultat suivant.

Existence de solution du PCL augmenté — Si \tilde{M} et \tilde{q} sont donnés comme ci-dessus, avec p>0 et r\geqslant0, alors \operatorname{CL}(\tilde{M},\tilde{q}) a une solution.

Existence de solution du problème original[modifier | modifier le code]

La seconde étape consiste à donner des conditions permettant de trouver une solution de \operatorname{CL}(M,q) à partir d'une solution de \operatorname{CL}(\tilde{M},\tilde{q}). Le résultat suivant donne des conditions suffisantes pour que le multiplicateur \alpha dans (a) et (b) ci-dessus soit nul.

CS d'existence de solution du PCL — Soient M\in\R^{n\times n} et q\in\R^n. S'il existe un vecteur p>0 et un scalaire r>0 tels que la fonction quadratique x\mapsto x^\top(Mx+q) soit positive sur \{x\in\R^n:x\geq0, p^\top x=r\}, alors \operatorname{CL}(M,q) a une solution.

Dans les conditions nécessaires et suffisantes d'existence de solution du problème \operatorname{CL}(M,q) données ci-dessous, on ne peut garantir que \alpha=0 dans (a) et (b) ci-dessus, mais on suppose que des solutions (x_k,\alpha_k) d'une suite de problèmes augmentés \operatorname{CL}(\tilde{M},\tilde{q}_k), k\in\mathbb{N}, sont telles que zéro adhère à \{\alpha_k\}.

CNS d'existence de solution du PCL — Soient M\in\R^{n\times n}, q\in\R^n et p>0. Les propriétés suivantes sont équivalentes.

  1. Le problème \operatorname{CL}(M,q) a une solution.
  2. Pour toute suite non bornée \{r_k\}\subset\R_+, les problèmes \operatorname{CL}(\tilde{M},\tilde{q}_k), avec
    \tilde{M}:=\begin{pmatrix}M&p\\-p^\top&0\end{pmatrix}\in\R^{(n+1)\times(n+1)} \qquad\mbox{et}\qquad \tilde{q}_k:=\begin{pmatrix}q\\r_k\end{pmatrix}\in\R^{(n+1)},
    ont des solutions (x_k,\alpha_k) telles que zéro est un point d'accumulation de \{\alpha_k\}.
  3. Il existe un suite non bornée \{r_k\}\subset\R_+, telle que les problèmes \operatorname{CL}(\tilde{M},\tilde{q}_k), avec (\tilde{M},\tilde{q}_k) donné comme au point 2, ont des solutions (x_k,\alpha_k) avec \alpha_k\to0.

On peut utiliser ce résultat pour montrer que

Méthodes de résolution[modifier | modifier le code]

Comme 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[modifier | modifier le code]

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

Méthodes de points intérieurs[modifier | modifier le code]

Méthodes non lisses[modifier | modifier le code]

Méthodes non lisses brutes[modifier | modifier le code]

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.

Méthodes non lisses régularisées[modifier | modifier le code]

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

Complexité[modifier | modifier le code]

Annexes[modifier | modifier le code]

Notes[modifier | modifier le code]

  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. a, b et c (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) 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[modifier | modifier le code]

  • (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.