\(^{\ast }\)Department of Mathematics, Faculty of Science, University Ferhat Abbas of Setif, 19000, Algeria, Laboratory of Fundamental and Numerical Mathematics,
e-mail: achache_m@yahoo.fr.

\(^{\S }\)Department of Mathematics, Faculty of Science, University El Hadj Lakhdar, Batna 05000, Algeria, e-mail: benhassinen13@yahoo.fr.

1 Introduction

Let\(\, \, \mathbb {S}^{n}\) be the space of all real symmetric matrices of order \(n\), \(\mathbb {S}_{+}^{n}\) be the cone of positive semidefinite matrices in \(\mathbb {S}^{n}\)and \(\mathbb {S}_{++}^{n}\)is the cone formed by all symmetric positive definite matrices. The expression \(X\succeq 0\, (X\succ 0)\) means that \(X\in \mathbb {S}_{+}^{n}(X\in \mathbb {S}_{++}^{n})\). Let \(L\) :\(~ \mathbb {S}^{n}\longrightarrow \mathbb {S}^{n}\) be a given linear transformation and \(Q\in \mathbb {S}^{n}\). The semidefinite linear complementarity problem (SDLCP) is to find a couple of matrices \((X,Y)\) \(\in \) \(\mathcal{A}\) such that:

where

is an affine subset of \(\mathbb {S}^{n}.\)

This problem has made the object of many studies of research this last years. Its growing importance can be measured by its different applications in control theory and various areas of optimization problems. This problem can be also viewed as a generalization of the standard linear complementarity
problem (LCP) and also included the geometric monotone semi-definite linear complementarity introduced by Kojima et al., [ 9 ] and which contains the pair of primal-dual semidefinite programming problems (SDP). For more details on (SDLCP) we refer the reader to the references [6-8, 11] and the thesis of Phd of Song [20]. Moreover it turns out that primal-dual path-following interior point algorithms can solve efficiently many problems such as linear, semidefinite programming, convex quadratic programming, conic and complementarity problems. These algorithms have polynomial complexity and numerical efficiency (see[1-4, 9, 10, 12-19, 21, 22]). It has been shown that most primal-dual (IPMs) algorithms and their analysis can be extended naturally from linear programming to (SDP) and so to more general context of (SDLCP).

The goal of this paper is to analyze the polynomial complexity of a primal-dual path-following interior-point algorithm for solving (SDLCP). Here, we reconsider the analysis used by Peng et al., (Ref. [17]) for (SDP) and we make it suiting to (SDLCP) case. The algorithm uses at each interior point iteration a full Nesterov-Todd (NT) step and a suitable proximity for tracing approximately the central-path. We provide also an unified analysis for both long and small-update primal-dual algorithms. Finally, the total iteration bounds for these algorithms are obtained. These polynomial complexity are analogous to such methods for linear, quadratic, semidefinite programming, conic and complementarity problems.

The rest of the paper is as follows. In section 2, the central path with its properties and Nesterov-Todd search directions are discussed. In section 3, the algorithm and its complexity analysis are stated. In section 4, a conclusion and future researches are given.

Throughout the paper we use the following notation.\(\, \mathbb {R}^{n\times n}\, \)is the space of all real \(n\times n~ \)matrices,\(\, \left\Vert .\right\Vert \) denotes the Frobenius norm of matrices. For a given matrix \(A\in \mathbb {R}^{n\times n}\), det\(\, A\) denotes its determinant if in addition \(A\) is nonsingular then \(A^{-1}\) denotes its inverse whereas \(A^{T}\, \)is the transpose of \(A\). Let \(X\in \mathbb {R}_{+}^{n},\) \(X^{1/2}\) represents its square root matrix. The trace of a matrix \(A\ \)is the sum of its diagonal entries and it is denoted by \(\operatorname {Tr}(A).\) Recall that for any two matrices \(A~ =(a_{ij})\ \)and \(B=(b_{ij})\ \)in \(\mathbb {R}^{n\times n},\, \)their inner product (trace) is defined by: \(\langle A,B\rangle :=\operatorname {Tr}(A^{T}B)={\textstyle \sum _{i,j}} a_{ij}b_{ij}.\, \)The identity matrix of order \(n\) is denoted by \(I\). Finally, \(g(t)=O(f(t))\) if and only if \(g(t)\leq kf(t)\) for some positive constant \(k\) where \(f(t)\) and \(g(t)\) are two real valued functions and \(t{\gt}0\).

2 Central path and Nesterov-Todd search directions for SDLCP

In this section we define the central path for SDLCP and its properties and we determine Nesterov-Todd search directions.

The feasible set and the strict feasible set of (1) are subsets of \(\mathbb {R}^{n\times n}\):

In the sequel we do the following hypothesis.

Hypothesis 1. The linear transformation \(L\) is monotone [6, 20] i.e.

Hypothesis 2. \(\mathcal{F}^{0}\neq \emptyset \).
Underour hypothesis it is shown that the set

of solutions of (1) is compact and non empty [6, 20].

In addition (1) is equivalent to the following optimization problem:

Hence solving (1) is equivalent to find the minimizer of (2) with its objective value is zero.

Now to introduce an interior point method for solving (2) we use the technique of the logarithmic barrier approach. So for (2) we associate with it the following minimization problem:

where \(\mu {\gt}0\, \)is the barrier parameter and \(\log \det (XY)\, \, \)is the logarithmic barrier function associated with (2), [4].

Under our hypothesis we deduce the following useful properties for (3).

• (OP)\(_{\mu }\) is a convex optimization problem.

• (OP)\(_{\mu }\) has a unique solution (\(X(\mu ),Y(\mu ))\) for all \(\mu {\gt}0\).

• If \(\mathcal{A}\neq \emptyset \). Then \(\lim _{\mu \mapsto 0}\)\((X(\mu ),\, Y(\mu ))=(X^{\ast },Y^{\ast })\, \)is a solution of (1), [9].

• The solution \((X(\mu ),Y(\mu ))\, \)is characterized by the first-order necessary and sufficient optimality conditions called conditions of Karush-Kuhn-Tucker of (OP)\(_{\mu }\) given by the following nonlinear system of equations:

  \begin{equation} \left\{ \begin{array}[l]{l}Y-L(X)=Q,\\ XY=\mu I,\, \, X\succ 0,Y\succ 0. \end{array} \right. \end{equation}

  4

• Hence solving (OP)\(_{\mu }\) is equivalent to solve (4).

• The set

  \[ \left\{ (X(\mu ),Y(\mu ))\, :\mu {\gt}0\right\} \]

  of solutions of the system (4) defines the central-path which is a smooth curve.

For solving (4) we use primal-dual path-following (IPMs) algorithms. The basic ideas behind these algorithms is to follow the central path approximately and to approach the solution of (4) as \(\mu \ \)goes to zero by using Newton step. Suppose now that we have \((X,Y)\in \)\(\mathcal{F}^{0}\). Applying Newton method for the system (4) we obtain a class of search directions given by the following linear system of equations:

Note that the system (5) has a unique solution \((\Delta X,\Delta Y) \)but unfortunately this last it is not symmetric. To remedy this default many works have been done in literature for symmetrizing the second equation in (5). In most suggestions used by researchers in this domain is to introduce a scaling and invertible matrix \(P\) and to consider the following linear transformation \(H_{P}\) given by:

Then the second equation in system (5) becomes:

Now we give some popular directions used in IPMs. For \(P=I\) we get the Alizadeh-Haerberly-Overton (A.H.O) direction and for \(P=\)\(Y^{1/2}\) or \(P=X^{1/2}\) it defines the so-called (H.K.M) direction.

Here we use the Nesterov-Todd (NT) direction where \(P\, \)is given by \(P=D^{-1/2}\) and \(D=X^{1/2}(X^{1/2}YX^{1/2})^{-1/2}X^{1/2}=Y^{-1/2}(Y^{1/2}XY^{1/2})^{1/2}Y^{-1/2}.\)

The role of the symmetric and positive definite matrix\(\, D\) is to rescale the two matrices \(X\, \, \)and \(Y\, \)to the same symmetric and positive definite matrix\(\, V\, \) given by:

Then the scaling Newton directions are:

Hence using (7) and (8) the system (6) can be written as:

where

and \(\bar{L}\, \)is given by:

The linear transformation \(\bar{L}\, \)is also monotone on \(\mathbb {S}^{n}\). Under our hypothesis the new linear system in (9)has a unique symmetric solution \((D_{X},D_{Y})\). Furthermore these directions satisfy:

This inequality shows that the Newton directions in the primal-dual space are not orthogonal in contrast to SDP case. Thus makes the analysis of the complexity a little different to SDP. As mentioned before the proximity used here is defined as:

One can easily verify that:

3 The algorithm and its complexity analysis

In this section we present the algorithm and we study its complexity and we compute the total number of iterations produced by it. We start to state some technical results that are needed for the analysis of the algorithm. Let\(\, A\, \, \)be a given matrix in \(\mathbb {R}^{n\times n}\). We decompose \(A\, \)in its symmetric part \(\overline{A}\) and its skew-symmetric part \(\widetilde{A}\). Thus we have

Now the generic form of this algorithm is stated as follows.

3.1 The Algorithm

(Generic primal-dual algorithm for (SDLCP))

Input:

an accuracy parameter \(\epsilon ;\)

an update parameter \(\theta ,0\) \({\lt}\theta {\lt}1;\)

a proximity parameter \(\tau ;\)

a feasible step size \(\alpha ;\)

a strictly feasible point \((X^{0},Y^{0})\, \)and \(\mu ^{0}= {\tfrac 1n\operatorname {Tr}(X^{0}Y^{0})}\) s.t. \(\delta (X^{0}Y^{0},\mu ^{0})\leq \tau ;\)

begin

set \(X:=X^{0};\; Y:=Y^{0};\; \mu :=\mu ^{0};\)

while \(n\mu \geq \epsilon \, \, \)do

  begin

   \(\mu :=(1-\theta )\mu ;\)

   while \(\delta (XY,\mu )\geq \tau ~ \) do

    begin

     compute \((\Delta X,\Delta Y)\, \; \)via (9);

     set \(\; X:=X+\alpha \Delta X;\; Y:=Y+\alpha \Delta Y;\)

    end

end

end.

3.2 Complexity analysis

Defining the symmetric matrix

Since \(\widetilde{D}\, \, \)is symmetric then its eigenvalues \(\lambda _{i}(\widetilde{D})\, \)are real for all \(i\in I=\left\{ 1,2,\ldots ,n\right\} \) and due to (11) there exist two nonnegative numbers (Ref. [18]) such that:

where

and

are index sets.

For the right hand of it since \(\widetilde{D\, \, }\)is symmetric then it is diagonalizable and there exists an orthogonal matrix \(Q_{\widetilde{D}}\, \)such that:

and let

Since the matrix

is positive semi-definite it holds that:

and

On the other hand the matrix

is also positive semi-definite whence

and

and together leads to

Thus gives

For the last result it follows from (11) and (15) that:

Then using (10) and (14) we deduce:

It completes the proof.

Next we want to estimate the quantity \(\delta _{+}^{2}-\delta ^{2}\) i.e. the effect of a damped Newton iteration on the proximity. Here \(\delta _{+}\, \)denotes the proximity after a stepsize \(\alpha \). Let

First we start to give a result for \(\delta _{+}\).

since \(\operatorname {Tr}(VD_{X})=\operatorname {Tr}(D_{X}V)\) and \(\operatorname {Tr}(VD_{Y})=\operatorname {Tr}(D_{Y}V).\)

Now substituting \(D_{X}\),\(~ D_{Y}\), \(D_{V}\, \, \)by their values and by (11) we deduce:

For the quantity \(\operatorname {Tr}((X^{+})^{-1}(Y^{+})^{-1})\) we have by a simple calculus and using Lemma 3.1 that:

Now for the last term in the right hand side of the above inequality and if \(0{\lt}\alpha {\lt}1\), is sufficiently small such that the matrix \((I+\alpha \widetilde{D})\) is positive definite, then by Lemma 3.2 we get:

It completes the proof of the lemma.

Now by Lemma 3.3 \(\lambda _{i}(\widetilde{D})\) the eigenvalues of \(\widetilde{D}\, \)satisfy \(\left\vert \lambda _{i}(\widetilde{D})\right\vert \leq \sigma \leq 2\delta ^{2}\) for all \(i\in I\, \) where \(\sigma =\sigma _{+}\) since \(\operatorname {Tr}(\widetilde{D})\geq 0,\) it implies \(\sigma _{+}\geq \sigma _{-},\) then the following result holds.

and

Now using the fact that \(\sigma \leq 2\delta ^{2}\) and \(\sigma _{-}\leq \sigma .\) We deduce:

and

It completes the proof of the theorem.

then the step size is strictly feasible and by Theorem 3.2 it follows that

This completes the proof of the theorem.

Now we are ready to compute the iteration bounds of the algorithm.

3.3 Iteration bounds

Then every damped Newton step decreases \(\delta ^{2}\) by at least \(\tfrac {5}{24}\). Hence after at most

iterations the proximity will have passed the threshold value \(\tau \). This completes the proof of the lemma.

Consequently we have the following theorem.

Multiplication of this number by the bound in Lemma 3.5 yields the theorem. Omitting the round-off brackets in Theorem 3.4 (this does not change the order of magnitude of the iteration bound) our algorithm does not exceed the following upper bound of iterations

Thus if \(\theta =\tfrac {1}{2}\) and \(\tau =1\) the bound becomes:

which is the bound complexity of such long-update primal-dual algorithms. Meanwhile if \(\theta =n^{-\tfrac {1}{2}}\) and \(\tau =1\) we obtain the best well-known iteration bound for small-update primal-dual algorithms, namely:

It completes the proof of the theorem.

4 Conclusion and future research

In this paper we have extended the study of complexity analysis of a primal-dual path-following algorithm designed for (SDP) to monotone (SDLCP). We have succeed to give an unified analysis for its polynomial complexity. For long-update algorithm we have \(O\big(n\log \tfrac {n\mu ^{0}}{\epsilon }\big)\) iteration bound. This complexity is similar to such primal-dual (IPMs) methods. For small-update algorithm the iteration bound is \(O\big(\sqrt{n}\log \tfrac {n\mu ^{0}}{\epsilon }\big)\) which is the best known iteration bound. Finally, an important topic for further research is the numerical implementation of this algorithm and to extend it for other optimization problems.