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

$x⩾0,Mx+q⩾0\text{et}{x}^{\mathrm{\top }}(Mx+q)=0,$

où $x^{\mathrm{\top }}$ désigne le vecteur Modèle:Mvar 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 $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 Modèle:Math 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 Modèle:Mvar et de Modèle:Mvar, 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 : 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

Notations préliminaires

Pour un vecteur $v\in {ℝ}^n$, la notation $v⩾0$ signifie que toutes les composantes $v_i$ du vecteur sont positives ou nulles.

On note ${ℝ}_{+}^n:=\{x\in {ℝ}^n:x⩾0\}$ l'orthant positif de ${ℝ}^n$.

Pour deux parties Modèle:Mvar et Modèle:Mvar d'un espace vectoriel, $A+B$ désigne leur somme de Minkowski, qui est l'ensemble $A+B:=\{x+y:x\in A,y\in B\}$.

Définitions

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

$x⩾0,Mx+q⩾0\text{et}{x}^{\mathrm{\top }}(Mx+q)=0.$

Le symbole ${}^{\mathrm{\top }}$ ci-dessus est utilisé pour désigner la transposition du vecteur à sa gauche. Dès lors, l'orthogonalité requise de Modèle:Mvar 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 :

Un point Modèle:Mvar vérifiant $x⩾0$ et $Mx+q⩾0$ est dit admissible pour le problème Modèle:Math l'ensemble

$\text{Adm}(M,q):=\{x\in {ℝ}^n:x⩾0,Mx+q⩾0\}$

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

On note

$\text{Sol}(M,q)$

l'ensemble des solutions du problème de complémentarité linéaire Modèle:Math ; c'est une réunion de polyèdres convexes.

Liens avec d'autres problèmes

Conditions d'optimalité d'un problème d'optimisation quadratique

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

$\{\begin{array}{c}\underset{x\in {ℝ}^n}{\inf }{g}^{\mathrm{\top }}x+\frac{1}{2}{x}^{\mathrm{\top }}Hx\\ Ax⩾b\\ x⩾0,\end{array}$

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

$\{\begin{array}{c}g+Hx-A^{\mathrm{\top }}y-z=0\\ 0⩽y\perp (Ax-b)⩾0\\ 0⩽z\perp x⩾0.\end{array}$

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

$\{\begin{array}{c}0⩽y\perp (Ax-b)⩾0\\ 0⩽(g+Hx-A^{\mathrm{\top }}y)\perp x⩾0.\end{array}$

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

$0⩽\left(\begin{array}{c}x\\ y\end{array}\right)\perp \left(\begin{array}{cc}H& -A^{\mathrm{\top }}\\ A& 0\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)+\left(\begin{array}{c}g\\ -b\end{array}\right)⩾0.$

Par ailleurs, lorsque $M\in {ℝ}^{n\times n}$ est symétrique semi-définie positive, le problème Modèle:Math est équivalent au problème d'optimisation quadratique

$\{\begin{array}{c}\underset{x\in {ℝ}^n}{\inf }{q}^{\mathrm{\top }}x+\frac{1}{2}{x}^{\mathrm{\top }}Mx\\ x⩾0.\end{array}$

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 {ℝ}^n\times {ℝ}^n$ tel que

$\{\begin{array}{c}q+Mx-z=0\\ 0⩽x\perp z⩾0.\end{array}$

Après élimination du multiplicateur Modèle:Mvar, on obtient Modèle:Math.

Expression sous forme de problème d'optimisation quadratique

Considérons le problème d'optimisation quadratique en $x\in {ℝ}^n$ suivant :

Modèle:Ancre $\text{(PQ)}\{\begin{array}{c}\min x^{\mathrm{\top }}(Mx+q)\\ x⩾0\\ Mx+q⩾0.\end{array}$

Si le problème de complémentarité linéaire Modèle:Math est admissible, c'est-à-dire si $\text{Adm}(M,q)\ne \varnothing$, l'ensemble admissible du problème quadratique $(\text{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) et donc des points stationnaires. On note

$\text{Sta}(M,q)$

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

$\text{Adm}(M,q)\ne \varnothing ⟹\text{Sta}(M,q)\ne \varnothing .$

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 Modèle:Math passant par celle de (PQ) n'est guère aisée.

Cas particulier d'inéquation variationnelle

Un problème d'inéquation variationnelle sur ${ℝ}^n$ est défini au moyen d'un produit scalaire $⟨\cdot ,\cdot ⟩$ sur ${ℝ}^n$, d'un ensemble non vide $K\subset {ℝ}^n$ et d'une fonction $F:K\to {ℝ}^n$. Il consiste à trouver un point $x\in {ℝ}^n$ tel que

$\{\begin{array}{c}x\in K\\ ⟨F(x),y-x⟩⩾0,\mathrm{\forall }y\in K.\end{array}$

Si le produit scalaire est le produit sclalaire euclidien $⟨u,v⟩:=u^{\mathrm{\top }}v$, si $K$ est l'orthant positif ${ℝ}_{+}^n$ et si $F:x\in {ℝ}_{+}^n\mapsto (Mx+q)\in {ℝ}^n$, le problème d'inéquation variationnelle ci-dessus n'est autre que le problème de complémentarité linéaire Modèle:Math.

Reformulations au moyen d'équations

On peut exprimer le problème de complémentarité linéaire Modèle:Math 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:{ℝ}^2\to ℝ$ est une C-fonction si

$f(a,b)=0⟺ab=0,a⩾0,b⩾0.$

Une C-fonction permet donc de remplacer le problème Modèle:Math par le système d'équations non linéaires

$F(x)=0,$

où $F:{ℝ}^n\to {ℝ}^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^{\prime }(x)$ n'est pas inversible en une solution dégénérée Modèle:Mvar (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 :

$f_{\min }(a,b)=\min (a,b).$

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

$\min (x,Mx+q)=0⟺x\in \text{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

La fonction de Fischer-BurmeisterModèle:, est définie par :

$f_{\mathrm{F}\mathrm{B}}(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 Modèle:Mvar. 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 Modèle:Math 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 M-matrices sont celles qui assurent l'existence et l'unicité de solution pour le problème Modèle:Math, avec la propriété de monotonie suivante :Modèle:Saut${\overline{x}}^1\in \mathrm{Sol}(M,q^1),{\overline{x}}^2\in \mathrm{Sol}(M,q^2),q^1⩽q^2⟹{\overline{x}}^1⩾{\overline{x}}^2.$Modèle:Saut
2. Les matrices non dégénérées sont celles pour lesquelles, quel que soit $q\in {ℝ}^n$, toute solution éventuelle de Modèle:Math est localement unique.
3. Les matrices suffisantes en colonne sont celles qui assurent la convexité de l'ensemble des solutions $\mathrm{Sol}(M,q)$, quel que soit $q\in {ℝ}^n$.
4. Les matrices suffisantes en ligne sont celles qui assurent que, quel que soit $q\in {ℝ}^n$, l'ensemble des solutions $\mathrm{Sol}(M,q)$ est identique à l'ensemble des points stationnaires du problème quadratique associé (PQ).
5. Les P-matrices sont celles qui assurent l'existence et l'unicité de solution pour le problème Modèle:Math, quel que soit $q\in {ℝ}^n$.
6. Les Q-matrices sont celles qui assurent l'existence de solution pour le problème Modèle:Math, quel que soit $q\in {ℝ}^n$.
7. Les [[Q0-matrice|QModèle:Ind-matrices]] sont celles qui assurent que le problème Modèle:Math a une solution lorsqu'il est réalisable.
8. Les [[R0-matrice|RModèle:Ind-matrices]] sont celles qui assurent que $x=0$ est l'unique solution de Modèle:Math.
9. Les S-matrices sont celles qui assurent que l'ensemble admissible $\text{Adm}(M,q)\ne \varnothing$, quel que soit $q\in {ℝ}^n$.
10. Les Z-matrices sont celles qui assurent l'existence d'un minimum (pour l'ordre $⩽$ de ${ℝ}^n$) de Modèle:Math, qui est solution de Modèle:Math, pour tout Modèle:Mvar rendant l'ensemble admissible $\text{Adm}(M,q)\ne \varnothing$.

Existence de solution

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 Modèle:Mvar.

Approche par l'optimisation

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), celle-ci est alors solution du problème de complémentarité linéaire Modèle:Math.

Par exemple, pour montrer que le problème de complémentarité linéaire a une solution dans le cas où Modèle:Mvar est une P-matrice, on écrit les conditions d'optimalité de (PQ) en une solution Modèle:Mvar : comme les contraintes sont qualifiées, il existe des multiplicateurs optimaux $s$ et Modèle:Mvar tels que

$\{\begin{array}{cc}(a)& (M+M^{\mathrm{\top }})x+q-s-M^{\mathrm{\top }}z=0\\ (b)& 0⩽x\perp s⩾0\\ (c)& 0⩽(Mx+q)\perp z⩾0.\end{array}$

Il suffit alors de montrer que $z=x$ pour déduire de (c) que Modèle:Mvar est solution de Modèle:Math. Par quelques manipulations algébriques astucieuses, on peut obtenir $(x-z)\cdot M^{\mathrm{\top }}(x-z)⩽0$ qui implique que $z=x$ grâce à la P-matricité de $M^{\mathrm{\top }}$, qui se déduit de celle de Modèle:Mvar.

Approche par point fixe

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

$\tilde{M}=\left(\begin{array}{cc}M& p\\ -p^{\mathrm{\top }}& 0\end{array}\right)\in {ℝ}^{(n+1)\times (n+1)}\text{et}\tilde{q}=\left(\begin{array}{c}q\\ r\end{array}\right)\in {ℝ}^{n+1},$

où $p\in {ℝ}^n$ et $r\in ℝ$. 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 {ℝ}^n$, l'autre en $\alpha \in ℝ$ :

$\{\begin{array}{cc}(a)& 0⩽x\perp (Mx+q+\alpha p)⩾0\\ (b)& 0⩽\alpha \perp (r-p^{\mathrm{\top }}x)⩾0.\end{array}$

On voit que si l'on réussit à montrer que $\text{CL}(\tilde{M},\tilde{q})$ a une solution $(x,\alpha )$ avec $\alpha =0$, Modèle:Mvar sera solution de Modèle:Math (par le problème Modèle:Math ci-dessus). Le plus souvent, on n'obtiendra ces circonstances qu'après un passage à la limite.

Existence de solution du problème augmenté

La première étape consiste donc à choisir $p\in {ℝ}^n$ et $r\in ℝ$ de telle sorte que le problème augmenté $\text{CL}(\tilde{M},\tilde{q})$ ait une solution. Voici deux résultats, le premier suppose que Modèle:Mvar est symétrique, le second pas.

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

$\{\begin{array}{c}\underset{x}{\inf }\frac{1}{2}{x}^{\mathrm{\top }}Mx+q^{\mathrm{\top }}x\\ x\ge 0,\\ p^{\mathrm{\top }}x\le r,\end{array}$

a une solution (Frank et Wolfe, 1956). Celle-ci vérifie les conditions d'optimalité du premier ordre, qui ne sont autres que les conditions Modèle:Math et Modèle:Math ci-dessus.

Lorsque Modèle:Mvar n'est pas symétrique, on exprime $\mathrm{CL}(\tilde{M},\tilde{q})$ comme un problème d'inéquation variationnelle $\mathrm{IV}(F,K)$ dans lequel

$F:{ℝ}^n\to {ℝ}^n:x\mapsto Mx+q\text{et}K:=\{x\in {ℝ}^n:x⩾0,p^{\mathrm{\top }}x⩽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⩾0$. On obtient alors le résultat suivant.

Existence de solution du problème original

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

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

On peut utiliser ce résultat pour montrer que

• les matrices strictement copositives sont des Q-matrices,
• un problème Modèle:Math avec Modèle:Mvar copositive et $q\in \{x\in {ℝ}_{+}^n:x^{\mathrm{\top }}Mx=0,Mx⩾0{\}}^{+}$ (dual positif) a une solution.

Méthodes de résolution

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

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

• Modèle:Lien
• Modèle:Lien
• Algorithme du pivot principal

Méthodes de points intérieurs

• Méthodes affines
• Méthodes de réduction du potentiel
• Méthodes de trajectoire centrale de type primal-dual

Méthodes non lisses

Méthodes non lisses brutes

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

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

Annexes

Ouvrages généraux

• Modèle:Ouvrage
• Modèle:Ouvrage
• Modèle:Ouvrage, téléchargeable sur le site de l'auteur