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

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

x {\displaystyle 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-difficiles et donc difficiles à résoudre lorsque la dimension n {\displaystyle 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'é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 {\displaystyle x_{i}=0} n'est pas atteint, c'est-à-dire que x i > 0 {\displaystyle x_{i}>0} , l'équation ( M x + q ) i = 0 {\displaystyle (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 R n {\displaystyle v\in \mathbb {R} ^{n}} , la notation v 0 {\displaystyle v\geqslant 0} signifie que toutes les composantes v i {\displaystyle v_{i}} du vecteur sont positives ou nulles.

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

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

Définitions

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

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

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

x ( M x + q ) = 0 {\displaystyle x\cdot (Mx+q)=0}

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

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

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

Adm ( M , q ) := { x R n : x 0 ,   M x + q 0 } {\displaystyle {\mbox{Adm}}(M,q):=\{x\in \mathbb {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 Adm ( M , q ) {\displaystyle {\mbox{Adm}}(M,q)\neq \varnothing } . On montre facilement que

R + n M ( R + n ) = { q R n : Adm ( M , q ) } {\displaystyle \mathbb {R} _{+}^{n}-M(\mathbb {R} _{+}^{n})=\{q\in \mathbb {R} ^{n}:{\mbox{Adm}}(M,q)\neq \varnothing \}} .

On note

Sol ( M , q ) {\displaystyle {\mbox{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].

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

{ inf x R n g x + 1 2 x H x A x b x 0 , {\displaystyle \left\{{\begin{array}{l}\textstyle \inf _{x\in \mathbb {R} ^{n}}\,g^{\top }x+{\frac {1}{2}}\,x^{\top }Hx\\Ax\geqslant b\\x\geqslant 0,\end{array}}\right.}

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

{ g + H x A y z = 0 0 y ( A x b ) 0 0 z x 0. {\displaystyle \left\{{\begin{array}{l}g+Hx-A^{\top }y-z=0\\0\leqslant y\perp (Ax-b)\geqslant 0\\0\leqslant z\perp x\geqslant 0.\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

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

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

0 ( x y ) ( H A A 0 ) ( x y ) + ( g b ) 0. {\displaystyle 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}}\geqslant 0.}

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

{ inf x R n q x + 1 2 x M x x 0. {\displaystyle \left\{{\begin{array}{l}\textstyle \inf _{x\in \mathbb {R} ^{n}}\,q^{\top }x+{\frac {1}{2}}\,x^{\top }Mx\\x\geqslant 0.\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 ) R n × R n {\displaystyle (x,z)\in \mathbb {R} ^{n}\times \mathbb {R} ^{n}} tel que

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

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

Expression sous forme de problème d'optimisation quadratique

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

(PQ) { min x ( M x + q ) x 0 M x + q 0. {\displaystyle {\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 CL(M,q) est admissible, c'est-à-dire si Adm ( M , q ) {\displaystyle {\mbox{Adm}}(M,q)\neq \varnothing } , l'ensemble admissible du problème quadratique ( PQ ) {\displaystyle ({\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

Sta ( M , q ) {\displaystyle {\mbox{Sta}}(M,q)}

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

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

On a bien sûr

x Sol ( M , q ) x {\displaystyle 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 CL(M,q) 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 R n {\displaystyle \mathbb {R} ^{n}} est défini au moyen d'un produit scalaire , {\displaystyle \langle \cdot ,\cdot \rangle } sur R n {\displaystyle \mathbb {R} ^{n}} , d'un ensemble non vide K R n {\displaystyle K\subset \mathbb {R} ^{n}} et d'une fonction F : K R n {\displaystyle F:K\to \mathbb {R} ^{n}} . Il consiste à trouver un point x R n {\displaystyle x\in \mathbb {R} ^{n}} tel que

{ x K F ( x ) , y x 0 , y K . {\displaystyle \left\{{\begin{array}{l}x\in K\\\langle F(x),y-x\rangle \geqslant 0,\quad \forall y\in K.\end{array}}\right.}

Si le produit scalaire est le produit sclalaire euclidien u , v := u v {\displaystyle \langle u,v\rangle :=u^{\top }v} , si K {\displaystyle K} est l'orthant positif R + n {\displaystyle \mathbb {R} _{+}^{n}} et si F : x R + n ( M x + q ) R n {\displaystyle F:x\in \mathbb {R} _{+}^{n}\mapsto (Mx+q)\in \mathbb {R} ^{n}} , 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

On 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 f : R 2 R {\displaystyle f:\mathbb {R} ^{2}\to \mathbb {R} } est une C-fonction si

f ( a , b ) = 0 a b = 0 , a 0 , b 0. {\displaystyle 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 , {\displaystyle F(x)=0,}

F : R n R n {\displaystyle F:\mathbb {R} ^{n}\to \mathbb {R} ^{n}} a sa composante i {\displaystyle i} définie par

F i ( x ) = f ( F i ( x ) , G i ( x ) ) . {\displaystyle F_{i}(x)=f(F_{i}(x),G_{i}(x)).}

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

f min ( a , b ) = min ( a , b ) . {\displaystyle 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 , M x + q ) = 0 x Sol ( M , q ) , {\displaystyle \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 ) {\displaystyle \min(u,v)_{i}=\min(u_{i},v_{i})} pour tout indice i {\displaystyle i} .

La C-fonction de Fischer-Burmeister

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

f F B ( a , b ) = a 2 + b 2 ( a + b ) . {\displaystyle 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 ) {\displaystyle (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 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.

  1. 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 :
    x ¯ 1 Sol ( M , q 1 ) , x ¯ 2 Sol ( M , q 2 ) , q 1 q 2 x ¯ 1 x ¯ 2 . {\displaystyle {\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 R n {\displaystyle q\in \mathbb {R} ^{n}} , toute solution éventuelle de CL(M,q) est localement unique.
  3. Les matrices suffisantes en colonne sont celles qui assurent la convexité de l'ensemble des solutions Sol ( M , q ) {\displaystyle \operatorname {Sol} (M,q)} , quel que soit q R n {\displaystyle q\in \mathbb {R} ^{n}} .
  4. Les matrices suffisantes en ligne sont celles qui assurent que, quel que soit q R n {\displaystyle q\in \mathbb {R} ^{n}} , l'ensemble des solutions Sol ( M , q ) {\displaystyle \operatorname {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 CL(M,q), quel que soit q R n {\displaystyle q\in \mathbb {R} ^{n}} [8].
  6. Les Q-matrices sont celles qui assurent l'existence de solution pour le problème CL(M,q), quel que soit q R n {\displaystyle q\in \mathbb {R} ^{n}} .
  7. Les Q0-matrices sont celles qui assurent que le problème CL(M,q) a une solution lorsqu'il est réalisable.
  8. Les R0-matrices sont celles qui assurent que x = 0 {\displaystyle x=0} est l'unique solution de CL(M,q).
  9. Les S-matrices sont celles qui assurent que l'ensemble admissible Adm ( M , q ) {\displaystyle {\mbox{Adm}}(M,q)\neq \varnothing } , quel que soit q R n {\displaystyle q\in \mathbb {R} ^{n}} .
  10. Les Z-matrices sont celles qui assurent l'existence d'un minimum (pour l'ordre {\displaystyle \leqslant } de R n {\displaystyle \mathbb {R} ^{n}} ) de Adm(M,q), qui est solution de CL(M,q), pour tout q rendant l'ensemble admissible Adm ( M , q ) {\displaystyle {\mbox{Adm}}(M,q)\neq \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 q.

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[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 s {\displaystyle s} et z tels que

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

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

Approche par point fixe

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

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

p R n {\displaystyle p\in \mathbb {R} ^{n}} et r R {\displaystyle r\in \mathbb {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 R n {\displaystyle x\in \mathbb {R} ^{n}} , l'autre en α R {\displaystyle \alpha \in \mathbb {R} }  :

{ ( a ) 0 x ( M x + q + α p ) 0 ( b ) 0 α ( r p x ) 0. {\displaystyle \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 CL ( M ~ , q ~ ) {\displaystyle {\mbox{CL}}({\tilde {M}},{\tilde {q}})} a une solution ( x , α ) {\displaystyle (x,\alpha )} avec α = 0 {\displaystyle \alpha =0} , 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é

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

{ inf x 1 2 x M x + q x x 0 , p x r , {\displaystyle \left\{{\begin{array}{l}\textstyle \inf _{x}\,{\frac {1}{2}}x^{\top }Mx+q^{\top }x\\x\geq 0,\\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 CL ( M ~ , q ~ ) {\displaystyle \operatorname {CL} ({\tilde {M}},{\tilde {q}})} comme un problème d'inéquation variationnelle IV ( F , K ) {\displaystyle \operatorname {IV} (F,K)} dans lequel

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

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

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

Existence de solution du problème original

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

CS d'existence de solution du PCL — Soient M R n × n {\displaystyle M\in \mathbb {R} ^{n\times n}} et q R n {\displaystyle q\in \mathbb {R} ^{n}} . S'il existe un vecteur p > 0 {\displaystyle p>0} et un scalaire r > 0 {\displaystyle r>0} tels que la fonction quadratique x x ( M x + q ) {\displaystyle x\mapsto x^{\top }(Mx+q)} soit positive sur { x R n : x 0 {\displaystyle \{x\in \mathbb {R} ^{n}:x\geq 0} , p x = r } {\displaystyle p^{\top }x=r\}} , 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 α = 0 {\displaystyle \alpha =0} dans (a) et (b) ci-dessus, mais on suppose que des solutions ( x k , α k ) {\displaystyle (x_{k},\alpha _{k})} d'une suite de problèmes augmentés CL ( M ~ , q ~ k ) {\displaystyle \operatorname {CL} ({\tilde {M}},{\tilde {q}}_{k})} , k N {\displaystyle k\in \mathbb {N} } , sont telles que zéro adhère à { α k } {\displaystyle \{\alpha _{k}\}} .

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

  1. Le problème CL(M,q) a une solution.
  2. Pour toute suite non bornée { r k } R + {\displaystyle \{r_{k}\}\subset \mathbb {R} _{+}} , les problèmes CL ( M ~ , q ~ k ) {\displaystyle \operatorname {CL} ({\tilde {M}},{\tilde {q}}_{k})} , avec
    M ~ := ( M p p 0 ) R ( n + 1 ) × ( n + 1 ) et q ~ k := ( q r k ) R ( n + 1 ) , {\displaystyle {\tilde {M}}:={\begin{pmatrix}M&p\\-p^{\top }&0\end{pmatrix}}\in \mathbb {R} ^{(n+1)\times (n+1)}\qquad {\mbox{et}}\qquad {\tilde {q}}_{k}:={\begin{pmatrix}q\\r_{k}\end{pmatrix}}\in \mathbb {R} ^{(n+1)},}
    ont des solutions ( x k , α k ) {\displaystyle (x_{k},\alpha _{k})} telles que zéro est un point d'accumulation de { α k } {\displaystyle \{\alpha _{k}\}} .
  3. Il existe une suite non bornée { r k } R + {\displaystyle \{r_{k}\}\subset \mathbb {R} _{+}} , telle que les problèmes CL ( M ~ , q ~ k ) {\displaystyle \operatorname {CL} ({\tilde {M}},{\tilde {q}}_{k})} , avec ( M ~ , q ~ k ) {\displaystyle ({\tilde {M}},{\tilde {q}}_{k})} donné comme au point 2, ont des solutions ( x k , α k ) {\displaystyle (x_{k},\alpha _{k})} avec α k 0 {\displaystyle \alpha _{k}\to 0} .

On peut utiliser ce résultat pour montrer que

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

  • Algorithme de Lemke (en)
  • Algorithme d'entrecroisement (en)
  • Algorithme du pivot principal

Méthodes de points intérieurs

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
  • Méthodes affines
  • Méthodes de réduction du potentiel
  • Méthodes de trajectoire centrale de type primal-dual

Méthodes non lisses

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

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.

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[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

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Complexité

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Annexes

Notes

  1. (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.
  2. a b et c (en) M. Frank et P. Wolfe, « An algorithm for quadratic programming », Naval Research Logistics Quarterly, vol. 3,‎ , p. 95–110.
  3. Facchinei et Pang (2003), proposition 9.1.1.
  4. (en) M. Kostreva, Direct Algorithms for Complementarity Problems. Ph.D. thesis., Troy, New York, Rensselaer Polytechnic Institute, .
  5. (en) O. Mangasarian, « Solution of symmetric linear complementarity problems by iterative methods », Journal of Optimization Theory and Applications, vol. 22,‎ , p. 465–485.
  6. (en) A. Fischer, « A special Newton-type optimization method », Optimization, vol. 24,‎ , p. 269–284.
  7. (en) A. Fischer, « A Newton-type method for positive semidefinite linear complementarity problems », Journal of Optimization Theory and Applications, vol. 86,‎ , p. 585–608.
  8. (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.
  9. (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

  • (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
  • icône décorative Portail des mathématiques