# LE PROBLÈME DE COMPLÉMENTARITÉ LINÉAIRE SEMI-DÉFINI

MOHAMED ACHACHE*, NAIMA BOUDIAF† and ABDELKARIM KERAGHEL*

**Abstract.** Dans cet article on présente une synthèse sur les principaux travaux liés au problème de complémentarité linéaire semi-défini. La présentation est donnée de façon à rendre le bagage utilisé pour ce problème comprehensible et permettant de nouveaux développements.

MSC 2000. 90C33.

**Keywords.** Problème de complémentarité linéaire semi-défini.

## 1. INTRODUCTION

Soit $S^n$ l'espace des matrices symétriques d'ordre $n$ et $S_+^n$ le cône des matrices semi-définies positives de $S^n$. Etant donné une transformation linéaire $L: S^n \to S^n$ et une matrice $Q$ de $S^n$, le problème de complémentarité linéaire semi-défini associé à $(L, Q)$ (abbréviation SDLCP$(L, Q)$) est défini comme suit:
Trouver une matrice $X \in S_+^n$ telle que :

$$L(X) + Q \in S_+^n, \text{ et } \langle X, L(X) + Q \rangle = \operatorname{tr}(X(L(X) + Q)) = 0.$$

Autrement dit SDLCP$(L, Q)$ est équivalent à trouver un couple de matrices $(X, Y) \in \mathcal{F}$ tel que :

$$X, Y \in S_+^n, \quad Y - L(X) = Q \quad \text{et} \quad \langle X, Y \rangle = \operatorname{tr}(XY) = 0.$$

Ici $\langle X, Y \rangle$ désigne le produit scalaire défini sur $S^n$ par :

$$\langle X, Y \rangle = \operatorname{tr}(XY) = \sum_{i=1}^{n} \sum_{j=1}^{n} X_{ij}Y_{ij},$$

où $\operatorname{tr}(A)$ désigne la trace de la matrice $A = (a_{ij})$ d'ordre $n$ définie par $\operatorname{tr}(A) = \sum_{i=1}^{n} a_{ii}$, et

$$\mathcal{F} = \{(X, Y) \in S^n \times S^n : Y - L(X) = Q\}$$

<footnote>* Laboratoire de Mathématiques fondamentales et Numériques, Université Ferhat Abbas de Sétif 19000, Algérie, e-mail: {achache_m, a_keragheldz}@yahoo.fr.</footnote>

<footnote>† Université El'hadj Lakhdar, Batna 05000, Algérie, e-mail: benhassinen13@yahoo.fr.</footnote>
est un sous ensemble affine de $S^n \times S^n$ de dimension $\frac{n(n+1)}{2}$. Cette forme de SDLCP est traitée par beaucoup de chercheurs (voir [4, 5, 6, 7, 12, 13]). Ce problème a fait l'objet de nombreuses études de recherche ces dernières années, son importance grandissante peut être mesurée par les différentes applications qu'il couvre, en l'occurrence : la théorie du contrôle, la programmation semi-définie, les systèmes linéaires et bilinéaires, l'optimisation combinatoire et structurelle et l'analyse du facteur minimum de trace. On mentionne aussi que des résultats classiques de Lyapunov et Stein (le théorème de stabilité de Lyapunov et de Stein pour les problèmes différentiels dynamiques continus et discrets) sont aussi démontrés en utilisant la notion de complémentarité linéaire semi-définie. SDLCP est aussi un cas particulier des problèmes de complémentarité défini sur les cônes convexes fermés par : Trouver $x \in H$ tel que $x \in K$, $y = L(x) + q \in K^*$, et $\langle x, y \rangle_K = 0$, où $H$ est un espace de Hilbert muni d'un produit scalaire $\langle \cdot, \cdot \rangle_K$ et $K$ est un cône convexe fermé auto-adjoint ($K = K^*$), $K^*$ est le dual de $K$ dans $H$ défini par :

$$K^* = \{y \in H : \langle y, x \rangle \ge 0, \forall x \in K\}.$$

Pour $H = S^n$, $K = S_+^n$, $K^* = S_+^n$, $\langle X, Y \rangle = \text{tr}(XY)$, on trouve SDLCP, qui est à son tour un cas particulier du problème variationnel suivant : soit $H$ un espace de Hilbert muni d'un produit scalaire $\langle \cdot, \cdot \rangle$, et $K$ un convexe fermé dans $H$ alors le problème des inégalités variationnelles (VIP) est de trouver $x \in K$ tel que :

$$\langle f(x), y - x \rangle \ge 0, \forall y \in K,$$

où $f : H \to H$ est une fonction donnée. Si $K$ est un cône, alors (VIP) est un problème de complémentarité. Si $H = S^n$, $K = S_+^n$ et $f$ est une fonction affine, on retrouve SDLCP.

Si de plus $K = \mathbb{R}_+^n$ l'orthant positif de $\mathbb{R}^n$, alors on obtient le problème de complémentarité linéaire (LCP) : Trouver $x, y \in \mathbb{R}_+^n$ tels que :

$$y = Mx + q \text{ et } x^Ty = 0,$$

où $M$ est une matrice donnée dans $\mathbb{R}^{n \times n}$, $q$ un vecteur donné dans $\mathbb{R}^n$ et $x^Ty$ est le produit scalaire usuel défini sur $\mathbb{R}^n$ par :

$$x^Ty = \sum_{i=1}^{n} x_i y_i.$$

Pour plus de détails sur ce problème le lecteur consultera les références [1, 3, 8]. De ce fait, LCP peut servir de base pour développer une véritable méthodologie pour SDLCP. Cependant, l'extension directe des résultats d'existence et
d'unicité de LCP à SDLCP n'est pas immédiate. Deux problèmes sont ren-
contrés, d'une part le cône $S_+^n$ n'est pas polyédrique et d'autre part, le pro-
duit de deux matrices symétriques n'est pas commutatif. De plus les notions
utilisées dans LCP doivent être reconsidérées pour les besoins de SDLCP.

Dans cet article on présente une synthèse des principaux travaux liés à
ce problème. La présentation est donnée de façon à rendre le bagage utilisé
comprehensible et conduisant à de nouveaux développements.

L'article est organisé comme suit. La section 2, contient les notations et les
notions de base de la théorie des matrices. Dans la section 3, on donne des
exemples de SDLCP. La section 4, décrit des propriétés importantes pour les
transformations liées à l'étude de ce problème. Dans la section 5, on étudie
l'existence et l'unicité de la solution de SDLCP. Dans la section 6, on étudie les
problèmes de complémentarité linéaire semi-défini issus des transformations de
Lyapunov, Stein et Two-sided. La section 7, contient une conclusion.

## 2. NOTATIONS ET NOTIONS DE BASE

Dans toute la suite, $\mathbb{R}^n$ désigne l'espace vectoriel réel sur le corps $\mathbb{R}$, et $\mathbb{R}_+^n$ l'orthant positif de $\mathbb{R}^n$. $S^n$ désigne l'espace des matrices symétriques et $S_+^n$ le cône des matrices symétriques semi-définies positives. $S^n$ est un espace de Hilbert muni du produit scalaire (trace) défini par :

$$
\langle A, B \rangle = \operatorname{tr}(AB) = \sum_{i=1}^{n} \sum_{j=1}^{n} A_{ij} B_{ij}.
$$

Pour toute matrice $A \in \mathbb{R}^{n \times n}$, où $\mathbb{R}^{n \times n}$ est l'ensemble des matrices carrées d'ordre $n$, $\operatorname{tr}(A) = \sum_{i=1}^{n} a_{ii} = \sum_{i=1}^{n} \lambda_i$ où $a_{ii}$ désignent les éléments diagonaux de $A$ et $\lambda_i(i = 1, 2, \dots, n)$ sont ses valeurs propres. La norme de Frobénius de $A$ est donnée par :

$$
\|A\|_F = \sqrt{\operatorname{tr}(A^2)}.
$$

L'écriture $X \succeq (\succ) 0$, où $X \in S^n$, signifie que $X$ est semi-définie positive (définie positive), et $x * y = (x_i y_i)_{i=1}^n$ désigne le produit de Hadamard (composante par composante) de $x \in \mathbb{R}^n$ par $y \in \mathbb{R}^n$.

On cite maintenant quelques notions de base de la théorie des matrices qui
seront utiles par la suite (voir [4, 13, 15]).

1) $A \in \mathbb{R}^{n \times n}$ est dite une matrice normale si $AA^T = A^T A$ (où $A^T$ désigne la transposée de $A$). Si de plus $AA^T = I$, où $I$ est la matrice identité d'ordre $n$, alors $A$ est dite orthogonale.

2) Toute matrice $X \in S^n$ est diagonalisable c-à-d il existe une matrice or-
thogonale $U$ telle que $X = UDU^T$ avec $D = \text{diag}(d_1, d_2, \dots, d_n)$ où $d_i$ sont les
valeurs propres de $X$.

3) $X \ge 0 \Rightarrow U X U^T \ge 0$ pour toute matrice orthogonale $U$.

4) $X \ge 0, Y \ge 0 \Rightarrow \langle X, Y \rangle \ge 0$.

5) $X \ge 0, Y \ge 0, \langle X, Y \rangle = 0 \Rightarrow [XY = 0 \Leftrightarrow YX = 0]$.

6) $X \in S^n, \langle X, Y \rangle \ge 0 \forall Y \ge 0 \Rightarrow X \ge 0$. Dans ce cas le cône $S_+^n$ est dit auto-adjoint.

7) $X, Y \in S^n$ avec $XY = YX$, c-à-d $X$ et $Y$ sont des matrices commutatives, alors il existe une matrice orthogonale $U$, et deux matrices diagonales $E$ et $D$ telles que : $X = UDU^T$ et $Y = UEU^T$.

8) Pour toutes matrices $A, B \in \mathbb{R}^{n \times n} : \text{tr}(AB) = \text{tr}(BA)$.

9) Le rayon spectral de $A$, $\rho(A)$ est défini par :

$$ \rho(A) = \max \{ |\lambda| : \lambda \in \sigma(A) \}, $$

où

$$ \sigma(A) = \{ \lambda : \lambda \text{ valeur propre de } A \} $$

désigne le spectre de la matrice $A$.

10) Une matrice $A \in \mathbb{R}^{n \times n}$ est dite :

• Positivement stable si chaque valeur propre $\lambda$ de $A$ possède une partie réelle strictement positive ($\text{Re}(\lambda) > 0$).

• Schur stable si $\rho(A) < 1$, c-à-d toutes les valeurs propres se trouvent dans le disque unité du plan complexe.

Selon la propriété 5, SDLCP devient : Trouver le couple $(X, Y) \in S^n \times S^n$ tel que :

$$ (1) \qquad X, Y \in S_+^n, Y - L(X) = Q \text{ et } XY = 0. $$

La propriété (5), s'appelle condition de complémentarité.

### 3. EXEMPLES DE SDLCP

Dans cette section on donne six exemples du problème complémentaire linéaire semi-défini. Les trois premiers problèmes sont cités dans la thèse de Y.Song [13] tels que le problème de complémentarité linéaire standard (LCP), SDLCP géométrique [10] et SDLCP par bloc, les trois derniers exemples sont donnés dans la thèse de Master de J. Krislock [11] dans le traitement de trois types de problèmes d'optimisation de moindre carrés à savoir le problème de moindre carrés semi-défini (SDLS), le problème de moindre carrés semi-défini non
symétrique (NS-SDLS) et le problème de moindre carrés semi-défini avec contraintes dit aussi le problème de moindre carrés semi-défini d'inégalités matricielles linéaires (LMI-LS).

**3.1. Problème de complémentarité linéaire (LCP).** Reprenons le problème de complémentarité linéaire (LCP) : Trouver $x$ et $y \in \mathbb{R}_+^n$ tels que :

$$y = Mx + q \in \mathbb{R}_+^n \text{ et } x^T y = 0.$$

En effet, LCP est un SDLCP car si on se donne une matrice $M \in \mathbb{R}^{n \times n}$ et un vecteur $q \in \mathbb{R}^n$ et que nous définissons la transformation linéaire $L : S^n \to S^n$ par :

$$L(X) := \text{Diag}(M \text{diag}(X)),$$

où diag($X$) est un vecteur dont les composantes sont les éléments diagonaux de la matrice $X$ et Diag($x$) est une matrice diagonale dont les éléments sont les composantes du vecteur $x$ on trouve le problème de complémentarité linéaire semi-défini SDLCP($L$, Diag($q$)) : Trouver $X \in S^n$ tel que :

$$X \in S_+^n, Y = L(X) + \text{Diag}(q) \text{ et } \langle X, Y \rangle = 0.$$

Alors on a le résultat suivant : $X$ est une solution de SDLCP($L$, Diag($q$)), si et seulement si diag($X$) est une solution de LCP($M$, $q$).

**3.2. SDLCP géométrique.** SDLCP($\mathcal{F}$) géométrique est apparu pour la première fois dans les travaux de Kojima, Shindoh et Hara en (1997) sous le nom du problème complémentaire linéaire semi-défini géométrique car dans ce cas le sous ensemble affine est quelconque de $S^n \times S^n$ et de dimension $\frac{n(n+1)}{2}$ au lieu de $\mathcal{F}$. C'est à dire $L$ n'est pas donnée explicitement. Il est donc défini comme suit : Trouver un couple $(X, Y) \in S^n \times S^n$ tel que :

$$(X, Y) \in \mathcal{F} \cap S^n \times S^n \text{ et } \langle X, Y \rangle = 0.$$

Cette version de SDLCP inclut le programme primal-dual semi-défini. En effet, soit le programme primal semi-défini sous forme standard :

$$(\text{SDP}) \quad \min_X \operatorname{tr}(CX) \quad \text{sujet à : } \langle A_k, X \rangle = b_k, k = 1, 2, \dots, m, X \in S_+^n,$$

où $b \in \mathbb{R}^m$, $C \in S^n$ et $A_k \in S^n$, $k = 1, 2, \dots, m$, et son dual :

$$\max_{(y,Z)} b^T y \quad \text{sujet à :} \quad \sum_{i=1}^{m} y_i A_i + Z = C, \ Z \in S_{+}^{n}.$$
Alors le programme primal-dual semi-défini est équivalent à un SDLCP avec l'ensemble affine $\mathcal{F}$ est donné par :

$$ \mathcal{F} = \left\{ (X, Z) \in S^n \times S^n, \text{ tel que : } \exists y \in \mathbb{R}^m, \sum_{i=1}^{n} y_i A_i + Z = C, \right. \\ \left. \langle A_i, X \rangle = b_i, \, i = 1, \dots, m \right\} $$

$A_i, C \in S^n, b \in \mathbb{R}^m$.

SDP est un problème très important car d'une part il contient la programmation linéaire (LP) et d'autre part il a beaucoup d'applications telles que la théorie du contrôle, la chimie quantique et l'optimisation combinatoire. Pour plus de détails sur SDP (voir les références [2, 14]).

Il est clair que SDLCP est un SDLCP géométrique. Réciproquement, considérons un sous ensemble affine $\mathcal{F}$ de $S^n \times S^n$ de dimension $\frac{n(n+1)}{2}$ et le problème SDLCP($\mathcal{F}$) géométrique associé à $\mathcal{F}$. On suppose sans perte de généralité que :

$$ \mathcal{F} = \{(X, Y) \in S^n \times S^n : L_1(X) + L_2(Y) = B\} $$

où $L_1$ et $L_2$ sont des transformations linéaires de $S^n$ dans lui même et $B$ une matrice de $S^n$. On définit $L : S^{3n} \to S^{3n}$ et $Q \in S^{3n}$ par :

$$ L \left( \begin{bmatrix} X & * & * \\ * & Y & * \\ * & * & Z \end{bmatrix} \right) = \begin{bmatrix} Y & 0 & 0 \\ 0 & L_1(X) + L_2(Y) & 0 \\ 0 & 0 & -L_1(X) - L_2(Y) \end{bmatrix}, $$

$$ Q = \begin{bmatrix} 0 & 0 & 0 \\ 0 & -B & 0 \\ 0 & 0 & B \end{bmatrix}. $$

Donc, si l'on pose :

$$ W = \begin{pmatrix} X & * & * \\ * & Y & * \\ * & * & Z \end{pmatrix}, $$

alors il est facile de vérifier que si $W$ est une solution de SDLCP, elle est aussi solution de SDLCP($\mathcal{F}$). D'autre part, si $(X, Y)$ est une solution du SDLCP($\mathcal{F}$) géométrique, alors

$$ W = \begin{pmatrix} X & * & * \\ * & Y & * \\ * & * & 0 \end{pmatrix} $$

est une solution du SDLCP.

Finalement, on déduit que la résolution de SDLCP($\mathcal{F}$) est équivalente à celle de SDLCP.
**3.3. SDLCP par bloc.** Soient $n_1, n_2, \dots, n_k$ des nombres fixés et $S^{n_i}$ l'ensemble des matrices réelles d'ordre $n_i, i = 1, \dots, k$. Soit $S$ l'ensemble de toutes les matrices diagonales par bloc $X_i \in S_i^n$, $i = 1, \dots, k$, c-à-d :

$$S := \left\{ X = \begin{pmatrix} X_1 & 0 & \dots & 0 \\ 0 & X_2 & \ddots & \vdots \\ \vdots & 0 & \ddots & 0 \\ 0 & 0 & 0 & X_k \end{pmatrix} : X_i \in S^{n_i}, i = 1, \dots, k \right\}.$$

Donc $S$ est un espace de Hilbert muni du produit scalaire :

$$\langle X, Y \rangle = \operatorname{tr}(XY) = \sum_{i=1}^{n} \operatorname{tr}(X_i Y_i).$$

Soit $S_+$ le cône convexe fermé des matrices positives semi définies dans $S$. Considérons le problème suivant : Soit $\mathcal{L}: S \to S$ une transformation linéaire donnée et $Q$ une matrice de $S$, trouver $X \in S$ telle que :

$$(2) \qquad X \in S_+, Y = \mathcal{L}(X) + Q \in S_+ \text{ et } \langle X, Y \rangle = 0,$$

ce problème inclut LCP si on prend $n_i = 1$, pour tout $i$. De plus notre SDLCP est un cas particulier de ce problème.

Réciproquement, on peut formuler (2) comme un SDLCP. En effet, soit $m = n_1 + n_2 + \dots + n_k$ et supposons qu'une transformation linéaire $L$ et une matrice $Q$ sont données. Alors pour chaque $i = 1, 2, \dots, k$, il existe une transformation $L_i$ on $S^m$ avec $L_i(X_i)$ sont les matrices bloc de la matrice $\mathcal{L}(X)$. Définissons maintenant une transformation $L$ on $S^m$ par :

$$L \begin{pmatrix} X_1 & * & \dots & * \\ * & X_2 & \ddots & \vdots \\ \vdots & * & \ddots & * \\ * & * & * & X_k \end{pmatrix} = \begin{pmatrix} L_1(X_1) & * & \dots & * \\ * & L_2(X_2) & \ddots & \vdots \\ \vdots & * & \ddots & * \\ * & * & * & L_k(X_k) \end{pmatrix}.$$

Pour une matrice $Q \in S$, si $X$ est une solution de (2), alors $X$ est une solution de SDLCP($L, Q$) donnée par (1). Soit maintenant $X \in S^m$ une solution de SDLCP($L, Q$), donc la matrice

$$\begin{pmatrix} X_1 & 0 & \dots & 0 \\ 0 & X_2 & \ddots & \vdots \\ \vdots & 0 & \ddots & 0 \\ 0 & 0 & 0 & X_k \end{pmatrix}$$
est une solution de (2) où $X_i$ sont des sous matrices de $X$ dont les lignes et les colonnes sont indexées sur l'ensemble $\{n_{i-1} + 1, \dots, n_{i-1} + n_i\}$.

**3.4. SDLS est un SDLCP.** Le problème de moindre carrés semi-défini est un problème d'optimisation convexe défini par :

$$ (\text{SDLS}) \quad \min_{\text{s.à. } X \in S_+^n} \frac{1}{2} \|AX - B\|_F^2, $$

où $A, B \in \mathbb{R}^{m \times n}$ et $X \in S^n$. Il est démontré que si la matrice $A$ est de plein rang (voir [11]), le problème (SDLS) admet un minimiseur global unique donné par les équations de Karush-Kuhn-Tucker (K.K.T) suivantes :

$$ \left. \begin{array}{l} A^T(AX - B) = Z, \\ \frac{1}{2}(Z + Z^T) = Y, \\ \langle X, Y \rangle = 0, \ X, Y \succeq 0. \end{array} \right\} $$

Soit maintenant la transformation $L: S^n \to S^n$ définie par :

$$ L(X) = \frac{1}{2}(A^T A X + X A^T A) $$

et

$$ Q = -\frac{1}{2}(A^T B + B^T A) $$

et soit l'ensemble affine :

$$ \mathcal{F} = \{ (X, Y) \in S^n \times S^n : Y - L(X) = Q \}. $$

Alors $(X, Y)$ satisfait les équations dans (3) si $(X, Y)$ satisfait le problème SDLCP suivant :

$$ (X, Y) \in \mathcal{F}, \ X \succeq 0, \ Y \succeq 0, \ \text{et} \ \langle X, Y \rangle = 0. $$

Il est facile de vérifier que la transformation $L$ est linéaire sur $S^n$ d'où en effet (SDLS) est un (SDLCP).

**3.5. NS-SDLS est un SDLCP.** Le problème de moindre carrés semi-défini non symétrique est aussi un problème d'optimisation convexe défini comme suit :

$$ (\text{NS-SDLS}) \quad \min_{\text{s.à. } X \in D} \frac{1}{2} \|AX - B\|_F^2, $$

où

$$ D = \{ X \in \mathbb{R}^{n \times n} : X \text{ est une matrice semi-définie} \} $$

et $A, B \in \mathbb{R}^{m \times n}$.
Ce problème admet un minimiseur unique sur l'ensemble D si la matrice A est de plein rang et dans ce cas (NS-SDLS) est équivalent à trouver les matrices symétriques X et Y qui satisfont les équations de (K.K.T) suivantes :

$$ (4) \qquad \left. \begin{array}{l} A^T(AX - B) = Z, \\ \frac{1}{2}(X + X^T) = Y, \\ \langle Z, Y \rangle = 0, \quad Z, Y \succeq 0. \end{array} \right\} $$

Alors (4) est équivalent au SDLCP suivant : Trouver le couple $(Z, Y)$ tel que $(Z, Y) \in \mathcal{F}, Z \succeq 0, Y \succeq 0$, et $\langle Z, Y \rangle = 0$ avec

$$ \mathcal{F} = \{ (Z, Y) \in S^n \times S^n : Y - L(Z) = Q \}, $$

où

$$ L(Z) = \frac{1}{2}((A^T A)^{-1} Z + Z(A^T A)^{-1}) $$

et

$$ Q = \frac{1}{2}((A^T A)^{-1} A^T B + B^T A (A^T A)^{-1}). $$

Il est aussi facile de vérifier que $L$ est une transformation linéaire de $S^n$ dans lui même.

**3.6. LMI-LS est un SDLCP.** Le problème de moindre carrés d'inégalités matricielles linéaires est aussi un problème d'optimisation convexe défini par :

$$ (\text{LMI-LS}) \qquad \min_{\mathcal{K}, x \preceq C} \frac{1}{2} \|Ax - b\|_2 $$

où

$$ \mathcal{K}x = \sum_{i=1}^{n} x_i K_i, $$

$K_i$, $(i = 1, \dots, n)$, $C \in S^n$, $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^m$ et $x \in \mathbb{R}^n$.

Sous les conditions suivantes :

* A est de plein rang

* L'ensemble des points strictement réalisables

$$ \{x \in \mathbb{R}^n : \mathcal{K}x \prec C\} $$

est non vide, LMI-LS admet un minimiseur unique $x$ caractérisé par le système d'équations de (K.K.T) suivant :

$$ (5) \qquad A^T(Ax - b) + \mathcal{K}^*Z = 0, \mathcal{K}x + Y = C, \langle Y, Z \rangle = 0, Z, Y \succeq 0, $$

où $\mathcal{K}^*$ : $S^k \to \mathbb{R}^n$ est la transformation adjointe de $\mathcal{K}$ définie par $\langle Y, \mathcal{K}x \rangle = \langle \mathcal{K}^*Y, x \rangle$.
Alors les équations dans (5) définissent un SDLCP comme suit : Trouver le couple de matrices $(Z, Y)$ tel que : $(Z, Y) \in \mathcal{F}, Z \succeq 0, Y \succeq 0$, et $\langle Z, Y \rangle = 0$, où

$$ \mathcal{F} = \{(Z, Y) \in S^n \times S^n : Y = L(Z) + Q\} $$

avec

$$ L(Z) = \mathcal{K}(A^T A)^{-1} \mathcal{K}^* Z $$

et

$$ Q = C - \mathcal{K}(A^T A)^{-1} A^T b. $$

On vérifie facilement que L est une transformation linéaire de $S^n$.

Dans la section suivante, on donne les définitions de quelques propriétés liées à la transformation qui sont utiles dans l'étude d'existence et (d'unicité) de la solution du SDLCP.

## 4. DÉFINITIONS ET QUELQUES PROPRIÉTÉS

DÉFINITION 4.1. Soit : $L : S^n \to S^n$ une transformation linéaire alors :
1- $L$ est une $P$-transformation si :

$$ [X \in S^n, XL(X) = L(X)X \preceq 0] \Rightarrow X = 0. $$

2- $L$ est une $P_0$-transformation si $(L+\varepsilon I)$ est une $P$-transformation pour tout $\varepsilon > 0$, où $I$ est la transformation identité dans $S^n$.

3- $L$ est une $P_1$-transformation si :

$$ [XL(X) + L(X)X \preceq 0] \Rightarrow X = 0. $$

4- $L$ est une $P_2$-transformation si :

$$ [X \succeq 0, Y \succeq 0, (X - Y) [L(X) - L(Y)] (X + Y) \preceq 0] \Rightarrow X = Y. $$

5- $L$ est une transformation monotone (strictement monotone) si :

$$ \langle L(X), X \rangle \geq 0 (> 0), $$

pour tout $0 \neq X \in S^n$.

6- $L$ est une super $P$-transformation si pour toute matrice $U$ orthogonale, la transformation linéaire $\tilde{L} : S^n \to S^n$ définie par : $\tilde{L}(X) = U^T L(UXU^T)U$, est une $P$-transformation.
DÉFINITION 4.2. $L$ est strictement semi-monotone (où $L$ est dite E-transformation) si :

$$[X \geq 0, XL(X) = L(X)X \leq 0] \Rightarrow X = 0.$$

Si $(L + \varepsilon I)$ est strictement semi-monotone pour tout $\varepsilon > 0$, alors $L$ est dite semi-monotone (où $L$ est une $E_0$-transformation).

Le concept des propriétés $\mathbf{R}_0$ et $\mathbf{Q}_0$, est similaire à celui de LCP, et on a pour le SDLCP$(L, Q)$, les définitions suivantes :

DÉFINITION 4.3. Soit $L: S^n \to S^n$ une transformation linéaire.

1) $L$ possède la propriété $\mathbf{R}_0$ si la matrice nulle est la seule solution du problème SDLCP$(L, 0)$.

2) $L$ possède la propriété $\mathbf{Q}$ si pour toute matrice $Q \in S^n$, SDLCP$(L, Q)$ admet une solution.

DÉFINITION 4.4. $L$ possède la (globaly uniquely solvable) (GUS)-propriété si pour toute matrice $Q \in S^n$, SDLCP$(L, Q)$ admet une solution unique.

DÉFINITION 4.5. Soit $L: S^n \to S^n$ une transformation linéaire. On dit que :

1) $L$ est une transformation de CS (column sufficient) si : $\forall Q \in S^n$, l'ensemble des solutions de SDLCP$(L, Q)$ est convexe (peut être vide).

2) $L$ possède la propriété de CC (cross commutative) si : $\forall Q \in S^n$ et $X_1, X_2$ sont deux solutions de SDLCP$(L, Q)$ alors : $X_1Y_2 = Y_2X_1$ et $X_2Y_1 = Y_1X_2$, où $Y_i = L(X_i) + Q, i = 1, 2$.

DÉFINITION 4.6. Soit $L: S^n \to S^n$ une transformation linéaire. Alors la transposée de $L, L^T: S^n \to S^n$ est définie par :

$$\langle L(X), Y \rangle = \langle X, L^T(Y) \rangle \text{ pour tout } X, Y \in S^n.$$

De plus, on dit que $L$ est une transformation auto-adjointe sur $S^n$ si $L = L^T$ et normale si $LL^T = L^TL$.

## 5. EXISTENCE ET UNICITÉ DE LA SOLUTION DE SDLCP

L'existence de la solution de SDLCP est donnée par le théorème dû à Kara-mardian [9].

THÉORÈME 5.1. Soit $L: S^n \to S^n$ une transformation linéaire. Si les deux problèmes SDLCP$(L, 0)$ et SDLCP$(L, E)$, $E$ étant une matrice définie positive de $S^n$, ont chacun une solution unique (éventuellement la solution zéro), alors pour toute matrice $Q \in S^n$, SDLCP$(L, Q)$ admet une solution.
Ce théorème est donné dans un cadre plus générale c-à-d la transformation $L$ est définie sur des cônes quelconques $K$ qui sont convexes fermés auto-adjoints. Alors le théorème précédent est restreint uniquement au cône $K = S_+^n$.

Maintenant, on donne quelques résultats d'existence et d'unicité de la solution de SDLCP associé à des transformations qui vérifient la P-propriété et la (GUS)-propriété.

Dans la théorie de LCP, l'existence et l'unicité de la solution de LCP pour tout $q \in \mathbb{R}^n$, est présentée dans le cadre de ce résultat :

1- chaque mineur principal de la matrice $M$ est positif.

2- pour tout $x \in \mathbb{R}^n (x \neq 0)$, il existe un indice $i$ tel que $x_i(Mx)_i > 0$.

3- l'implication $[x \in \mathbb{R}^n, x * Mx \leq 0] \Rightarrow x = 0$ est satisfaite.

4- pour tout $q \in \mathbb{R}^n$, LCP($M$, $q$), admet une solution unique.

On rapelle qu'une matrice $M \in \mathbb{R}^{n \times n}$ est une P-matrice (où $M$ a la propriété $P$) si l'une des conditions 1 ou 2 et 3 est satisfaite. Alors l'unicité de la solution dans LCP($M$, $q$) est décrite par la propriété $P$ de la matrice $M$.

Tandis que si la matrice $M$ est semi-définie positive, alors dans ce cas le LCP($M$, $q$) est dit monotone, de plus si son ensemble de points strictement realisables :

$$ \mathcal{F}_{str} = \{(x, y) \in \mathbb{R}^{2n} : x > 0, y = Mx + q > 0\} $$

est non vide, alors l'ensemble de ces solutions est un convexe non vide.

De la condition (4), LCP est dit (globaly uniquely solvable) où (GUS)-propriété.

**THÉORÈME 5.2.** [4, 13] *Supposons que $L : S_+^n \to S_+^n$ possède la P-propriété. Donc pour toute matrice $Q \in S^n$, SDLCP($L$, $Q$) admet une solution.*

**REMARQUE 5.3.** La P-propriété de la transformation $L$ assure l'existence de la solution mais non l'unicité. (voir un contre-exemple donné par Gowda & al [4]). Contrairement à LCP où la P-propriété assure l'existence et l'unicité de la solution. □

Le théorème prochain assure le résultat d'unicité dans le SDLCP($L$, $Q$).

**THÉORÈME 5.4.** *Soit $L : S^n \to S^n$ une transformation linéaire. Les asséritions suivantes sont équivalentes:*

a) Pour toute matrice $Q \in S^n$, SDLCP($L$, $Q$) admet au plus une solution;

b) $L$ possède la P-propriété et la cross-commutativité;

c) $L$ possède la (GUS)-propriété.

Introduisons maintenant des résultats pour les transformations linéaires monotones.
### THÉORÈME 5.5. Soit $L: S^n \to S^n$ une transformation linéaire. Alors si $L$ est monotone, l'ensemble des solutions du problème SDLCP($L, Q$) est un convexe peut être vide pour toute matrice $Q \in S^n$.

### COROLLAIRE 1. Si $L: S^n \to S^n$ est une transformation linéaire monotone, alors

$$GUS = P.$$

Dans ce qui se suit on donne les conditions suffisantes pour qu'une transformation $L$ possède la (GUS)-propriété. (Voir [13]).

### THÉORÈME 5.6. (Suffisance) Si $L$ est une transformation strictement monotone, alors elle possède la GUS-propriété.

### THÉORÈME 5.7. Pour une transformation linéaire $L: S^n \to S^n$, les implications suivantes sont vérifiées :

$$(6) \qquad \text{stricte monotone} \Rightarrow P_2 \Rightarrow \text{GUS}.$$

On donne maintenant un résultat qui inverse les implications du résultat (6).

### THÉORÈME 5.8. Soit $L: S^n \to S^n$ une transformation qui possède la $P$-propriété. Si $L$ est auto-adjointe, alors elle est strictement monotone et les implications inverses suivantes sont satisfaites :

$$\text{stricte monotonie} \Leftrightarrow P_2 \Leftrightarrow \text{GUS}.$$

## 6. ETUDE DE QUELQUES FORMES DE SDLCP

### 6.1. La forme de Lyapunov.
La transformation de Lyapunov associée à une matrice carrée $A$ est définie par :

$$L_A(X) = AX + XA^T.$$

La caractérisation de (GUS)-propriété est donnée dans le cadre du théorème suivant.

### THÉORÈME 6.1. Considérons la transformation de Lyapunov $L_A$ avec $A$ une matrice donnée dans $\mathbb{R}^{n \times n}$. Alors les assertions suivantes sont équivalentes :
1) $L_A$ possède la GUS-propriété;

2) $A$ est positivement stable et semi-définie positive.

### THÉORÈME 6.2. $L_A$ possède la $P_2$-propriété si et seulement si $A$ est une matrice définie positive.
### THÉORÈME 6.3. Supposons que $A$ est une matrice normale. Alors on a pour la transformation $L_A$,

$$ \text{stricte monotonie} = GUS = P. $$

## 6.2. La forme de Stein.
Cette transformation est donnée par :

$$ S_A(X) = X - AXA^T $$

pour toute matrice $A$ dans $\mathbb{R}^{n \times n}$.

On a les résultats suivants pour $S_A$.

### THÉORÈME 6.4. Soit $A \in \mathbb{R}^{n \times n}$ une matrice normale. Alors on a pour la transformation $S_A$,

$$ \text{stricte monotonie} = GUS = P. $$

### REMARQUE 6.5. La caractérisation de la GUS-propriété pour la transformation de Stein reste un problème ouvert. □

## 6.3. La forme de Two-sided.
Cette transformation est donnée par :

$$ M_A(X) = AXA^T $$

pour une matrice $A$ donnée dans $\mathbb{R}^{n \times n}$, et on a aussi les résultats suivants :

### THÉORÈME 6.6. Pour la transformation $M_A$ on a :

1) $M_A$ possède la GUS-propriété;

2) La matrice $A$ est définie positive ou bien définie négative.

### REMARQUE 6.7. Pour cette transformation on a :

$$ GUS = P. $$

□

Pour plus de détails sur les démonstrations des théorèmes précédents, voir les références [4, 5, 6, 12] et la référence [13].

Finalement, on mentionne que les formes de SDLCP données par les trois derniers exemples [3.4, 3.5, 3.6] sont strictement monotones car leurs transformations sont strictement monotones. Alors elles possèdent la GUS-propriété.

# 7. CONCLUSION

Dans cet article on a présenté sommairement les principaux travaux liés au problème complémentaire linéaire semi-défini. Cela facilite la comprehension de ce problème et conduisant à des nouveaux développement dans ce domaine.
REFERENCES

[1] ACHACHE, M., *Multidimensional primal-dual path-following interior point methods for linear programming and linear complementarity problems*, Thèse de Doctorat d'Etat, Université Ferhat Abbas de Sétif 19000, Algérie, 2005.

[2] ALIZADEH, F., HAEBERLY, J.A. and OVERTON, O., *Primal-dual interior point methods for semidefinite programming*, Convergence rates, stability and numerical results, SIAM J. Optimization, **8**, pp. 746-768, 1998.

[3] COTTLE, R.W., PANG, J.S. and STONE, R., *The linear complementarity problem*, Academic Press, Boston, 1992.

[4] GOWDA, M.S. and SONG, Y., *On semidefinite linear complementarity problem. Mathematical Programming*, Series A, **88**, pp. 575-587, 2000.

[5] GOWDA, M.S., SONG, Y. and RAVINDRAN, G., *Some interconnections between strong monotonicity, GUS and P properties in semidefinite linear complementarity problems*, Linear algebras and its applications, **370**, pp. 355-386, 2003.

[6] GOWDA, M.S. and SONG, Y., *Some new results for the semidefinite linear complementarity problem*, SIAM Journal on Matrix Analysis and Applications, **24** (1) pp. 25-39, 2003.

[7] MALIK, M. and MOHAN, S.R., *Some geometrical aspects of semidefinite linear complementarity problems*, Linear and multilinear algebras, **54** (1), pp. 55-70, 2006.

[8] MURTY, K.G., *Linear complementarity, linear and nonlinear programming*, Heldermann Verlag, Berlin, 1988.

[9] KARAMARDIAN, S., *The complementarity problem*, Mathematical Programming, **2**, pp. 107-129, 1972.

[10] KOJIMA, M., SHINDOH, M. and HARA, S., *Interior point methods for the monotone semidefinite linear complementarity in symmetric matrices*, SIAM J. Optimization, **7**, pp. 86-125, 1997.

[11] KRISLOCK, J., *Numerical solution of semidefinite constrained least squares problems*, Master thesis, the university of british columbia, Canada, 2003.

[12] PARTHASARTHY, T., RAMAN, D.S. and SRIPARNA, B., *Relationship between strong monotonicity property, P2-property, and the GUS-property in semidefinite linear complementarity problems*, Mathematics of Operations Research, **27** (2) pp. 326-331, 2002.

[13] SONG, Y, *The P and globally uniquely solvable properties in semidefinite linear complementarity problems*, PhD thesis, University of Maryland, USA, 2002.

[14] VANDENBERGHE, L. and BOYED, S., *Semidefinite programming*, SIAM Review, **38**, pp. 49-95, 1996.

[15] ZHANG, F., *Matrix theory*, Springer-Verlag, New-York, 1999.