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 \mathbb {R} ^{n\times n}$ et d'un vecteur $q\in \mathbb {R} ^{n}$ et consiste à trouver un vecteur $x\in \mathbb {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 $\mathbb {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é. Ce problème peut être vu comme un cas particulier d'inéquation variationnelle.

Ces problèmes sont souvent NP-difficile 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

Quelques notations

Pour un vecteur $v\in \mathbb {R} ^{n}$ , la notation $v\geqslant 0$ signifie que toutes les composantes $v_{i}$ du vecteur sont positives ou nulles.

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

Pour deux parties $A$ et $B$ 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 \mathbb {R} ^{n\times n}$ , non nécessairement symétrique, et un vecteur $q\in \mathbb {R} ^{n}$ , un problème de complémentarité linéaire consiste à trouver un vecteur $x\in \mathbb {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 \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 ${\mbox{CL}}(M,q)$ est réalisable si ${\mbox{Adm}}(M,q)\neq \varnothing$ . On montre facilement que

\mathbb {R} _{+}^{n}-M(\mathbb {R} _{+}^{n})=\{q\in \mathbb {R} ^{n}:{\mbox{Adm}}(M,q)\neq \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].

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

$\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.$

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

$\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

$\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\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\in \mathbb {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 \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)\in \mathbb {R} ^{n}\times \mathbb {R} ^{n}$ tel que

$\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 $\operatorname {CL} (M,q)$ .

Expression sous forme de problème d'optimisation quadratique

Considérons le problème d'optimisation quadratique en $x\in \mathbb {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)\neq \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)\neq \varnothing \qquad \Longrightarrow \qquad {\mbox{Sta}}(M,q)\neq \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.

Cas particulier d'inéquation variationnelle

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

$\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 ${\displaystyle \langle u,v\rangle$ , si $K$ est l'orthant positif $\mathbb {R} _{+}^{n}$ et si $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 ${\mbox{CL}}(M,q)$ .

Reformulations au moyen d'équations

On peut exprimer le problème de complémentarité linéaire ${\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:\mathbb {R} ^{2}\to \mathbb {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,$

où $F:\mathbb {R} ^{n}\to \mathbb {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

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

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

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}.$
Les matrices non dégénérées sont celles pour lesquelles, quel que soit $q\in \mathbb {R} ^{n}$ , toute solution éventuelle de ${\mbox{CL}}(M,q)$ est localement unique.
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 \mathbb {R} ^{n}$ .
Les matrices suffisantes en ligne sont celles qui assurent que, quel que soit $q\in \mathbb {R} ^{n}$ , l'ensemble des solutions $\operatorname {Sol} (M,q)$ est identique à l'ensemble des points stationnaires du problème quadratique associé (PQ).
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 \mathbb {R} ^{n}$ [8].
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 \mathbb {R} ^{n}$ .
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.
Les $\mathbf {R_{0}}$ -matrices sont celles qui assurent que $x=0$ est l'unique solution de ${\mbox{CL}}(M,0)$ .
Les $\mathbf {S}$ -matrices sont celles qui assurent que l'ensemble admissible ${\mbox{Adm}}(M,q)\neq \varnothing$ , quel que soit $q\in \mathbb {R} ^{n}$ .
Les $\mathbf {Z}$ -matrices sont celles qui assurent l'existence d'un minimum (pour l'ordre $\leqslant$ de $\mathbb {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)\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 ${\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\geqslant 0\\(c)&0\leqslant (Mx+q)\perp z\geqslant 0.\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)\leqslant 0$ 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

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 \mathbb {R} ^{(n+1)\times (n+1)}\qquad {\mbox{et}}\qquad {\tilde {q}}={\begin{pmatrix}q\\r\end{pmatrix}}\in \mathbb {R} ^{n+1},$

où $p\in \mathbb {R} ^{n}$ et $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\in \mathbb {R} ^{n}$ , l'autre en $\alpha \in \mathbb {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é

La première étape consiste donc à choisir $p\in \mathbb {R} ^{n}$ et $r\in \mathbb {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 \mathbb {R} ^{n}$ et $r\in \mathbb {R}$ tels que $x\mapsto {\frac {1}{2}}x^{\top }Mx+q^{\top }x$ est bornée inférieurement sur $\{x\in \mathbb {R} ^{n}:x\geqslant 0$ , $p^{\top }x\leqslant r\}\neq \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\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 $\operatorname {CL} ({\tilde {M}},{\tilde {q}})$ comme un problème d'inéquation variationnelle $\operatorname {IV} (F,K)$ dans lequel

$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$ 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\geqslant 0$ . 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\geqslant 0$ , alors $\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 $\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 \mathbb {R} ^{n\times n}$ et $q\in \mathbb {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 \mathbb {R} ^{n}:x\geq 0$ , $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 \mathbb {R} ^{n\times n}$ , $q\in \mathbb {R} ^{n}$ et $p>0$ . Les propriétés suivantes sont équivalentes.

Le problème $\operatorname {CL} (M,q)$ a une solution.
Pour toute suite non bornée $\{r_{k}\}\subset \mathbb {R} _{+}$ , les problèmes $\operatorname {CL} ({\tilde {M}},{\tilde {q}}_{k})$ , avec
${\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},\alpha _{k})$ telles que zéro est un point d'accumulation de $\{\alpha _{k}\}$ .
Il existe une suite non bornée $\{r_{k}\}\subset \mathbb {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}\to 0$ .

On peut utiliser ce résultat pour montrer que

les matrices strictement copositives sont des Q-matrices,
un problème $\operatorname {CL} (M,q)$ avec $M$ copositive et $q\in \{x\in \mathbb {R} _{+}^{n}:x^{\top }Mx=0,~Mx\geqslant 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).

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

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

Annexes

Notes

(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.
(en) M. Frank, P. Wolfe (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3, 95–110.
Facchinei et Pang (2003), proposition 9.1.1.
(en) M. Kostreva (1976). Direct Algorithms for Complementarity Problems. Ph.D. thesis, Rensselaer Polytechnic Institute, Troy, New York.
(en) O. Mangasarian (1977). Solution of symmetric linear complementarity problems by iterative methods. Journal of Optimization Theory and Applications, 22, 465–485.
(en) A. Fischer (1992). A special Newton-type optimization method. Optimization, 24, 269–284.
(en) A. Fischer (1995). A Newton-type method for positive semidefinite linear complementarity problems. Journal of Optimization Theory and Applications, 86, 585–608.
(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.
(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 et R. E. Stone, The Linear Complementarity Problem, Philadelphia, PA, SIAM, coll. « Classics in Applied Mathematics » (n^o 60), 2009
(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 », 2003
(en) K. G. Murty, Linear Complementarity, Linear and Nonlinear Programming, Berlin, Heldermann Verlag, coll. « Sigma Series in Applied Mathematics » (n^o 3), 1988 (ISBN 978-3-88538-403-8), téléchargeable sur le site de l'auteur

Portail des mathématiques

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

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

[frank-wolfe-1956-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) C. Chen, O.L. Mangasarian (1995). Smoothing methods for convex inequalities and linear complementary problems. Mathematical Programming, 71, 1–112. doi