A New Smooth NCP Function for Solving Semidefinite Nonlinear Complementarity Problems

Abstract

In this paper, we propose to solve semidefinite nonlinear complementarity problems (NCP) associated to a nonlinear matrix function , by a quasi-Newton method. For this, we reformulate this problem as a smooth nonlinear matrix equation by using a new smooth NCP matrix function, then we apply a quasi-Newton method for solving this matrix equation. We prove the local superlinear convergence of our algorithm and we give some numerical examples to illustrate the efficiency of the proposed method.

1 Introduction

Let ${\mathcal {S}}^{n}$ and ${\mathcal {S}}_{+}^{n}$ denote the space of $n\times n$ symmetric matrices, and the cone of symmetric positive semidefinite matrices respectively. We endow ${\mathcal {S}}^{n}$ with the inner product and the Frobenius norm defined by

$$\begin{aligned} \left\langle X,S\right\rangle =\text {Tr}(XS)\quad \text {and}\quad \left\| X\right\| _{F}=\sqrt{\left\langle X,X\right\rangle }, \end{aligned}$$

where $X,S\in {\mathcal {S}}^{n}$ and Tr(·) stands for the trace of a matrix.

The notation $A\succeq 0$ and $A\succ 0$ means that A is symmetric positive semidefinite and symmetric positive definite, respectively.

Let $F:{\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}$ be a continuously differentiable function. The Semidefinite Nonlinear Complementarity Problem associated to F (SDNCP(F)) is defined as follows:

Find $X\in {\mathcal {S}}^{n}$ such that:

$$\begin{aligned} X\in {\mathcal {S}}_{+}^{n},Y=F(X)\in {\mathcal {S}}_{+}^{n},\quad \text {and}\quad \left\langle X,Y\right\rangle =\text {Tr}(XY)=0. \end{aligned}$$

(1.1)

If F is an affine function of the form $F(X)=L(X)+Q$ where $L:{\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}$ is a linear operator and $Q\in {\mathcal {S}}^{n}$, then SDNCP(F) is called a semidefinite linear complementarity problem (SDLCP(F), for short).

Note that the SDNCP(F) is a generalization of the nonnegative orthant nonlinear complementarity problem (NCP) defined by: Find $x\in {\mathbb {R}} ^{n}$ such that:

$$\begin{aligned} x\ge 0,f(x)\ge 0,\quad \text {and}\quad x^{\mathrm{T}}f(x)=0, \end{aligned}$$

(1.2)

where f :  ${\mathbb {R}} ^{n}\rightarrow {\mathbb {R}} ^{n}$ is continuously differentiable vector function.

This problem arises naturally in the optimality conditions of semidefinite programming problems (SDP) involving inequality constraints and has wide applications in engineering, economics, management sciences and other fields (see [10, 12], for example). Some methods have been proposed to solve the SDNCP(F) problems, for example, interior-point methods and merit function methods in [11]. Chen and Tseng [13] proposed a so-called exact non-interior continuation (or smoothing-type Newton) method to solve SDNCP(F).

Another approach to solve the problem (SDNCP(F)) is to reformulate it as a matrix equation $H\left( X,S\right) =0$ where $H:{\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}$ is defined by

$$\begin{aligned} H\left( X,S\right) =\left( \begin{array}{c} \phi \left( X,S\right) \\ F(X)-S \end{array} \right) , \end{aligned}$$

(1.3)

and $\phi :{\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}$ is an NCP function, that is:

$$\begin{aligned} \phi \left( X,S\right) =0\Leftrightarrow X\in {\mathcal {S}}_{+}^{n},S\in {\mathcal {S}}_{+}^{n},\quad \text {and}\quad XS=0. \end{aligned}$$

(1.4)

Most reformulations of the SDNCP(F) problem use nonsmooth NCP functions and the most popular NCP functions are Fischer–Burmeister function [6, 7, 9], defined by

$$\begin{aligned} \phi _{\mathrm{FB}}\left( X,S\right) =X+S-\sqrt{X^{2}+S^{2}}, \end{aligned}$$

(1.5)

and the natural residual function [2], defined by

$$\begin{aligned} \phi _{\mathrm{NR}}\left( X,S\right)= & {} \min \left( X,S\right) =\frac{1}{2}\left( X+S- \sqrt{\left( X-S\right) ^{2}}\right) . \nonumber \\= & {} \frac{1}{2}\left( X+S-\left| X-S\right| \right) , \end{aligned}$$

(1.6)

where the matrix valued functions square root, min and absolute value are defined in the following section.

It is shown in [4], that the functions $\phi _{\mathrm{FB}}$ and $\phi _{\min }$ are not differentiable everywhere, but only strongly semismooth functions. To overcome the nonsmoothness, many authors [8, 13, 14] used smooth approximations of these functions. Smooth approximations of $\phi _{\mathrm{FB}}$ and $\phi _{\min }$ [2, 8, 13, 15], are given for a parameter $\mu \in {\mathbb {R}} _{+}^{*}$, respectively by:

$$\begin{aligned} \phi _{\mathrm{FB}}^{\mu }\left( X,S\right) =X+S-\sqrt{X^{2}+S^{2}+2\mu ^{2}I}, \end{aligned}$$

(1.7)

and

$$\begin{aligned} \phi _{\mathrm{NR}}^{\mu }\left( X,S\right) =\frac{1}{2}\left( X+S-\sqrt{\left( X-S\right) ^{2}+4\mu ^{2}I}\right) . \end{aligned}$$

(1.8)

In this paper, we propose a new NCP function to give a smooth reformulation of the SDNCP(F) problem. This new NCP function is continuously differentiable and is defined by $\phi _{\alpha }:{\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}$ where

$$\begin{aligned} \phi _{\alpha }\left( X,S\right) =XS+SX-\frac{1}{\alpha }\left[ \min \left( 0,X+S\right) \right] ^{2},\quad 0<\alpha \le 1. \end{aligned}$$

(1.9)

The rest of the paper is organized as follows. In Sect. 2, we recall some useful preliminaries that will be needed in the sequel. We study some properties of the NCP function $\phi _{\alpha }$ in Sect. 3. In Sect. 4, we develop our algorithm for solving the SDNCP(F) using the NCP function $\phi _{\alpha }$ and a quasi-Newton method. For the sake of illustrating the effectiveness of our algorithm, some numerical experiments are reported in Sect. 5. We draw conclusions in Sect. 6.

2 Preliminaries

In this section, we recall the spectral definition of matrix valued function associated to a given real valued function and we present a classical result about its differentiability.

For any $X\in {\mathcal {S}}^{n}$, let $\lambda _{1}\left( X\right) \le \lambda _{2}\left( X\right) \le \cdots \le \lambda _{n}\left( X\right)$ be eigenvalues of X,  then X admits a spectral decomposition of the form $X=PD_{X}P^{\mathrm{T}}$ for some $P\in {\mathcal {O}}^{n}$, where ${\mathcal {O}}^{n}$ denotes the set of $P\in \mathcal { {\mathbb {R}} }^{n\times n}$ that are orthogonal and $D_{X}=\hbox {diag}[\lambda _{1}\left( X\right) ,\ldots ,\lambda _{n}\left( X\right) ]$ denotes the $n\times n$ diagonal matrix where $\lambda _{i}\left( X\right)$ are diagonal elements.

Let $f: {\mathbb {R}} \rightarrow {\mathbb {R}}$. We can define a corresponding matrix valued function $F:{\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}$ by

$$\begin{aligned} X \rightarrow F\left( X\right) =P\hbox {diag}\left( f\left( \lambda _{1}\left( X\right) \right) ,f\left( \lambda _{2}\left( X\right) \right) ,\ldots ,f\left( \lambda _{n}\left( X\right) \right) \right) P^{\mathrm{T}}, \end{aligned}$$

(2.1)

where $X=PD_{X}P^{\mathrm{T}}$ is the spectral decomposition of X.

Example 2.1

• (1) For $f(t)=\sqrt{t},$ the corresponding function $F:{\mathcal {S}}_{+}^{n}\rightarrow {\mathcal {S}}_{+}^{n}$ is defined by

  $$\begin{aligned} F(X)=\sqrt{X}=P\hbox {diag}\left( \sqrt{ \lambda _{1}\left( X\right) },\ldots ,\sqrt{\lambda _{n}\left( X\right) }\right) P^{\mathrm{T}}. \end{aligned}$$

  is called square root function.

• (2) For $f(t)=\min \left( 0,t\right) ,$ the corresponding function $F:{\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}$ is defined by

  $$\begin{aligned} F(X)=\min (0,X)=P\hbox {diag}\left( \min \left( 0,\lambda _{1}\left( X\right) \right) ,\ldots ,\min \left( 0,\lambda _{n}\left( X\right) \right) \right) P^{\mathrm{T}}. \end{aligned}$$

  is called the min function.

• (3) For $f(t)=\left| t\right| ,$ the corresponding function $F:{\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}$ is defined by

  $$\begin{aligned} F(X)=\left| X\right| =P\text {diag}\left( \left| \lambda _{1}\left( X\right) \right| ,\ldots ,\left| \lambda _{n}\left( X\right) \right| \right) P^{\mathrm{T}}, \end{aligned}$$

  (2.2)

is called the absolute value function.

Remark 2.2

Note that the definition of absolute value function given by (2.2) is not applicable to the vectors, since here the absolute value is applied to the eigenvalues and not the entries of a matrix. Furthermore, we have

$$\begin{aligned} \left| X \right| =\sqrt{X^{2}} \quad \text {and}\quad \left| X \right| ^{2}=X^{2}. \end{aligned}$$

It is proved in [5, 7, 14] that the matrix valued function F inherited all topological properties of the function f,  in particular we have:

Proposition 2.3

(See [7, 14] for the proof) Let $f:{\mathbb {R}} \rightarrow {\mathbb {R}}$ and $F:{\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}$ be the corresponding matrix valued function. Let $X=PD_{X}P^{\mathrm{T}}$ be the spectral decomposition of X. Then

F is (continuously) differentiable at an $X\in {\mathcal {S}}^{n}$ with eigenvalues $\lambda _{1}\left( X\right) ,\ldots ,\lambda _{n}\left( X\right)$ if and only if f is (continuously) differentiable at $\lambda _{1}\left( X\right) ,\ldots ,\lambda _{n}\left( X\right) .$ Moreover,  $F^{\prime }\left( X\right)$ is an operator given by

$$\begin{aligned} F^{\prime }\left( X\right) \left( H\right) =P\left[ f^{\left[ 1\right] }\left( D_{X}\right) \circ \left( PHP^{\mathrm{T}}\right) \right] P^{\mathrm{T}}, \end{aligned}$$

(2.3)

where $\circ$ is the Hadamard product and $f^{\left[ 1\right] }\left( D_{X}\right)$ is the matrix whose elements are:

$$\begin{aligned} \left[ f^{\left[ 1\right] }\left( D_{X}\right) \right] _{ij}=\left\{ \begin{array}{ll} \frac{f\left( \lambda _{i}\right) -f\left( \lambda _{j}\right) }{\lambda _{i}-\lambda _{j}}, &{}\quad \text {if}\ i\ne j\in \left\{ 1,2,\ldots ,n\right\} \\ f^{\prime }\left( \lambda _{i}\right) &{}\quad \text {if}\ i=j\in \left\{ 1,2,\ldots ,n\right\} \end{array} \right. . \end{aligned}$$

(2.4)

3 Properties of the Function $\phi _{\alpha }$

In this section, we state some properties of the function $\phi _{\alpha }$ given by (1.9). In particular, we show that this function is an NCP function, that is continuously differentiable and we calculate its derivative.

First, we remark that our new function $\phi _{\alpha }$ can be expressed equivalently as follows:

$$\begin{aligned} \phi _{\alpha }\left( X,S\right) =XS+SX-\frac{1}{4\alpha }\left( X+S-\left| X+S\right| \right) ^{2},\quad 0<\alpha \le 1, \end{aligned}$$

(3.1)

or by the form:

$$\begin{aligned} \phi _{\alpha }\left( X,S\right) =XS+SX-\frac{1}{\alpha }P\text {diag}(f(\lambda _{1}),\ldots f(\lambda _{n}))P^{\mathrm{T}},\quad 0<\alpha \le 1, \end{aligned}$$

(3.2)

with $f(\cdot )=\min ^{2}(0,\cdot )$ and $X+S=PDP^{\mathrm{T}}$ is the spectral decomposition of the symmetric matrix $X+S$.

Proposition 3.1

The function $\phi _{\alpha }$ defined in (1.9) is an NCP function for all $0<\alpha \le 1,$ i.e.:

$$\begin{aligned} X\in {\mathcal {S}}_{+}^{n},S\in {\mathcal {S}}_{+}^{n},\quad \text {and}\quad \text {Tr}(XS)=0\Leftrightarrow \phi _{\alpha }\left( X,S\right) =0. \end{aligned}$$

Proof

Let $0<\alpha \le 1.$

(1) Suppose that $X\in {\mathcal {S}}_{+}^{n},$ $S\in {\mathcal {S}}_{+}^{n}$, and $\text {Tr}(XS)=0,$ then

$$\begin{aligned} \ XS=SX=0\Rightarrow XS+SX=0, \end{aligned}$$

and

$$\begin{aligned} X+S\in {\mathcal {S}}_{+}^{n}\Rightarrow \min \left( 0,X+S\right) =0. \end{aligned}$$

Obviously, this implies that$\ \phi _{\alpha }\left( X,S\right) =0$

(2) Conversely, suppose that $\phi _{\alpha }\left( X,S\right) =0$. Using the form (3.1) of the function $\phi _{\alpha }$ and the fact that $\phi _{\alpha }\left( X,S\right) =0,$ it follows that

$$\begin{aligned} \ XS+SX-\frac{1}{ 4\alpha }\left( X+S-\left| X+S\right| \right) ^{2}=0. \end{aligned}$$

So,

$$\begin{aligned} \ 4\alpha \left( XS+SX\right) =\left( X+S-\left| X+S\right| \right) ^{2}, \end{aligned}$$

(3.3)

then $XS+SX\in {\mathcal {S}}_{+}^{n}$.

Next, by expanding the right-hand side of (3.3) we obtain

$$\begin{aligned} \ 4\alpha \left( XS+SX\right) =2\left( X+S\right) ^{2}-\left( X+S\right) \left| X+S\right| -\left| X+S\right| \left( X+S\right) , \end{aligned}$$

since $\left| X+S\right| ^{2}= \left( X+S\right) ^{2}$.

So, for all $0<\alpha \le 1$, we get

$$\begin{aligned}&\left( X+S\right) \left| X+S\right| +\left| X+S\right| \left( X+S\right) \\= & {} 2\left( X+S\right) ^{2}-4\alpha \left( XS+SX\right) \\= & {} 2X^{2}+2S^{2}+\left( 2-4\alpha \right) \left( XS+SX\right) \\= & {} 2X^{2}+2S^{2}-2\left( XS+SX\right) +\left( 4-4\alpha \right) \left( XS+SX\right) \\= & {} 2\left( X-S\right) ^{2}+\left( 4-4\alpha \right) \left( XS+SX\right) \in {\mathcal {S}}_{+}^{n} \end{aligned}$$

and then

$$\begin{aligned} \left( X+S\right) \left| X+S\right| +\left| X+S\right| \left( X+S\right) \in {\mathcal {S}}_{+}^{n}. \end{aligned}$$

Let $X+S=PDP^{\mathrm{T}}$ be the spectral decomposition of $X+S,$ where $D=\text {diag}\left( \lambda _{1},\ldots ,\lambda _{n}\right) ,$ then

$$\begin{aligned}&\left( X+S\right) \left| X+S\right| +\left| X+S\right| \left( X+S\right) =PDP^{\mathrm{T}}\left| PDP^{\mathrm{T}}\right| +\left| PDP^{\mathrm{T}}\right| PDP^{\mathrm{T}}\\&\quad = PD\left| D\right| P^{\mathrm{T}}+PD\left| D\right| P^{\mathrm{T}} (since \left| PDP^{\mathrm{T}}\right| =P\left| D\right| P^{\mathrm{T}}) \\&\quad = 2P\text {diag}\left( \lambda _{i}\left| \lambda _{i}\right| \right) P^{\mathrm{T}}\in {\mathcal {S}}_{+}^{n}, \end{aligned}$$

then for all $i=1,2,\ldots ,n,$ we have

$$\begin{aligned} \lambda _{i}\left| \lambda _{i}\right| \ge 0\Rightarrow \lambda _{i}\ge 0,\quad \forall i=1,2,\ldots ,n, \end{aligned}$$

therefore, $X+S\in {\mathcal {S}}_{+}^{n}$ which implies that $\min \left( 0,X+S\right) =0$, i.e: the eigenvalues of $X+S$ are all nonnegative

Next, since $\phi _{\alpha }\left( X,S\right) =0$ we get

$$\begin{aligned} \ XS+SX=0. \end{aligned}$$

So, we have shown that

$$\begin{aligned} XS+SX=0\quad \text {and}\quad X+S\in {\mathcal {S}}_{+}^{n}. \end{aligned}$$

Now, it remains to be shown that

$$\begin{aligned} X\in {\mathcal {S}}_{+}^{n},S\in {\mathcal {S}}_{+}^{n},\quad \text {and}\quad \left\langle X,S\right\rangle =\text {Tr}(XS)=0. \end{aligned}$$

(3.4)

The proof of (3.4) can be given by two methods:

Method 1:

Since $XS+SX=0$ and $X+S\in {\mathcal {S}}_{+}^{n}$, then:

$$\begin{aligned} \ XS+SX=0\Rightarrow \left( X+S\right) ^{2}=X^{2}+S^{2}, \end{aligned}$$

so

$$\begin{aligned} X+S=\sqrt{X^{2}+S^{2}},\quad (\left| X+S\right| =X+S, because X+S\in {\mathcal {S}}_{+}^{n}), \end{aligned}$$

hence

$$\begin{aligned} \ X+S-\sqrt{X^{2}+S^{2}} =0\Leftrightarrow \phi _{\mathrm{FB}}\left( X,S\right) =0. \end{aligned}$$

It is known that $\phi _{\mathrm{FB}}$ is an NCP function [2], then

$$\begin{aligned} X\in {\mathcal {S}}_{+}^{n},S\in {\mathcal {S}}_{+}^{n} \quad and \quad \left\langle X,S\right\rangle =\text {Tr}(XS)=0. \end{aligned}$$

Method 2:

(1) Let $X=LD_{X}L^{\mathrm{T}}$ be the spectral decomposition of X, where L is an orthogonal matrix and $D_{X}=\text {diag}(\lambda _{1}\left( X\right) ,\ldots \lambda _{n}\left( X\right) ).$

Since $XS+SX=0$ and $X+S\in {\mathcal {S}}_{+}^{n},$ we get

$$\begin{aligned} LD_{X}L^{\mathrm{T}}S+SLD_{X}L^{\mathrm{T}}=0 \quad \text {and} \quad LD_{X}L^{\mathrm{T}}+S\in {\mathcal {S}}_{+}^{n}, \end{aligned}$$

(3.5)

next, since $L\,L^{\mathrm{T}}=L^{\mathrm{T}}\,L=I_n$, it follows from relations (3.5) that

$$\begin{aligned} D_{X}L^{\mathrm{T}}SL+L^{\mathrm{T}}SLD_{X}=0 \quad \text {and} \quad D_{X}+L^{\mathrm{T}}SL\in {\mathcal {S}}_{+}^{n}. \end{aligned}$$

Set $B=(b_{ij})=L^{\mathrm{T}}SL$. Since $D_{X}B+BD_{X}=0$, it follows that

$$\begin{aligned} \left( \lambda _{i}\left( X\right) +\lambda _{j}\left( X\right) \right) b_{ij}=0 \quad \text {for all } i,j=1,2,\ldots ,n, \end{aligned}$$

in particular if we take $i=j$, we obtain

$$\begin{aligned} 2\lambda _{i}\left( X\right) b_{ii}=0, \quad \text {for all } i=1,2,\ldots ,n. \end{aligned}$$

Next, since $D_{X}+B\in {\mathcal {S}}_{+}^{n}$ then it follows that

$$\begin{aligned} \lambda _{i}\left( X\right) +b_{ii}\ge 0, \quad \text {for all } i=1,2,\ldots ,n. \end{aligned}$$

so, for all $i=1,2,\ldots ,n$, we have

$$\begin{aligned} 2\lambda _{i}\left( X\right) b_{ii}=0 \quad \text {and}\quad \lambda _{i}\left( X\right) +b_{ii}\ge 0. \end{aligned}$$

Obviously, this implies

$$\begin{aligned} \lambda _{i}\left( X\right) \ge 0,\quad \text {for all } i=1,2,\ldots ,n, \end{aligned}$$

then X is positive semidefinite matrix.

(2) In the same way, we prove that S is positive semidefinite matrix.

(3) We have $\text {Tr}(XS)=\frac{1}{2}\text {Tr}(XS+SX)$, then $\text {Tr}(XS)=0.$

Therefore, we obtain

$$\begin{aligned} \phi _{\alpha }\left( X,S\right) =0\Rightarrow X\in {\mathcal {S}}_{+}^{n},S\in {\mathcal {S}}_{+}^{n}, \text { et }\left\langle X,S\right\rangle =\text {Tr}(XS)=0. \end{aligned}$$

$\square$

Proposition 3.2

(Differentiability of the function $\phi _{\alpha })$ The function $\phi _{\alpha }$ defined by (1.9) is continuously differentiable everywhere and its derivative is given by : 

$$\begin{aligned} \phi _{\alpha }^{\prime }\left( X,S\right) \left( U,V\right)= & {} US+SU+XV+VX\nonumber \\&- \frac{1}{\alpha }P\left[ f^{\left[ 1\right] }\left( D\right) \circ \left( P\left( U+V\right) P^{\mathrm{T}}\right) \right] P^{\mathrm{T}}. \end{aligned}$$

(3.6)

for all $U,V\in {\mathcal {S}}^{n},$ where $X+S=PDP^{\mathrm{T}}$ is the spectral decomposition of $X+S$ and : 

$$\begin{aligned} \left[ f^{\left[ 1\right] }\left( D\right) \right] _{ij}=\left\{ \begin{array}{ll} \frac{\min ^{2}\left( 0,\lambda _{i}\right) -\min ^{2}\left( 0,\lambda _{j}\right) }{\lambda _{i}-\lambda _{j}}&{}\quad \text {if }i\ne j\in \left\{ 1,\ldots ,n\right\} \\ 2\min \left( 0,\lambda _{i}\right) &{}\quad \text {if }i=j\in \left\{ 1,\ldots ,n\right\} \end{array} \right. . \end{aligned}$$

(3.7)

Proof

From formula (1.9), we have

$$\begin{aligned} \phi _{\alpha }\left( X,S\right) =\psi _{1}\left( X,S\right) -\frac{1}{\alpha } \psi _{2}\left( X,S\right) , \end{aligned}$$

where $\psi _{1}\left( X,S\right) =XS+SX$ and

$$\begin{aligned} \psi _{2}\left( X,S\right) =\frac{1}{\alpha }P\text {diag}(f(\lambda _{1}),\ldots f(\lambda _{n}))P^{\mathrm{T}}, \end{aligned}$$

with $f(\cdot )=\min ^{2}(0,\cdot ).$

It is clear that $\psi _{1}$ is continuously differentiable everywhere. Now, by using the Proposition 2.3 and the fact that f is continuously differentiable everywhere, then the function $\psi _{2}$ is continuously differentiable everywhere. Hence $\phi _{\alpha }$ is continuously differentiable since it is the sum of two continuously differentiable functions. Now, we calculate the derivative of $\phi _{\alpha }$

(a) It is clear that

$$\begin{aligned} \psi _{1}^{\prime }\left( X,S\right) \left( U,V\right) =US+SU+XV+VX, \end{aligned}$$

for all $U,V\in {\mathcal {S}}^{n}.$

(b) We compute the derivative of $\psi _{2}$ in the following way

$$\begin{aligned} \psi _{2}\left( X,S\right)= & {} [min ( 0,X+S)]^{2} \\= & {} P\text {diag}(f(\lambda _{1}),\ldots f(\lambda _{n}))P^{\mathrm{T}}. \end{aligned}$$

We put

$$\begin{aligned} \psi _{2}\left( X,S\right) =\left( \theta \circ \Sigma \right) \left( X,S\right) , \end{aligned}$$

where

$$\begin{aligned} \Sigma :{\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\rightarrow & {} {\mathcal {S}}^{n} \\ \left( X,S\right)\rightarrow & {} \Sigma \left( X,S\right) =X+S, \end{aligned}$$

and

$$\begin{aligned} \theta :{\mathcal {S}}^{n}\rightarrow & {} {\mathcal {S}}^{n} \\ \ Z\rightarrow & {} \theta \left( Z\right) =\ [ \ min ( 0,Z)]^{2} , \end{aligned}$$

then:

$$\begin{aligned} \psi _{2}^{\prime }\left( X,S\right) (\cdot ,\cdot )=\theta ^{\prime }\left( \Sigma \left( X,S\right) \right) \circ \left( \Sigma ^{\prime }\left( X,S\right) (\cdot ,\cdot )\right) . \end{aligned}$$

It is clear that the derivative of $\Sigma$ at $\left( X,S\right)$ is

$$\begin{aligned} \Sigma ^{\prime }\left( X,S\right) :{\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\rightarrow & {} {\mathcal {S}}^{n} \\ \left( U,V\right)\rightarrow & {} \Sigma ^{\prime }\left( X,S\right) \left( U,V\right) =U+V, \end{aligned}$$

for the derivative of $\theta \left( Z\right) :$

$$\begin{aligned} \theta ^{\prime }\left( Z\right) :{\mathcal {S}}^{n}\rightarrow & {} {\mathcal {S}}^{n} \\ K\rightarrow & {} \theta ^{\prime }\left( Z\right) \left( K\right) , \end{aligned}$$

we have

$$\begin{aligned} \theta \left( Z\right)= & {} \ [ \ min ( 0,Z)]^{2} =P\text {diag}\left( f\left( \lambda _{1}\left( Z\right) \right) ,\ldots ,f\left( \lambda _{n}\left( Z\right) \right) \right) \\= & {} P\text {diag}\left( \min \left( 0,\lambda _{1}\left( Z\right) \right) ^{2} ,\ldots ,\min \left( 0,\lambda _{n}\left( Z\right) \right) ^{2} \right) P^{\mathrm{T}}, \end{aligned}$$

where $Z=PD_{Z}P^{\mathrm{T}}$ and $D_{Z}=\text {diag}\left( \lambda _{1}\left( Z\right) ,\ldots ,\lambda _{n}\left( Z\right) \right) ,$ $i=1,\ldots ,n$.

According to Proposition 2.3, the derivate of $\theta$ is given by

$$\begin{aligned} \theta ^{\prime }\left( Z\right) \left( K\right) =P\left[ f^{\left[ 1\right] }\left( D_{Z}\right) \circ \left( PKP^{\mathrm{T}}\right) \right] P^{\mathrm{T}}. \end{aligned}$$

Next, using the chain rule formula, we obtain

$$\begin{aligned} \psi _{2}^{\prime }\left( X,S\right) (\cdot ,\cdot )=\theta ^{\prime }\left( \Sigma \left( X,S\right) \right) \circ \left( \Sigma ^{\prime }\left( X,S\right) (\cdot ,\cdot )\right) , \end{aligned}$$

that is

$$\begin{aligned} \psi _{2}^{\prime }\left( X,S\right) \left( U,V\right) =\theta ^{\prime }\overset{Z}{\overbrace{\left( X+S\right) }}\overset{K}{\overbrace{\left( U+V\right) }}. \end{aligned}$$

Hence, the derivative of $\psi _{2}$ is given by

$$\begin{aligned} \psi _{2}^{\prime }\left( X,S\right) \left( U,V\right) =P\left[ f^{\left[ 1\right] }\left( D\right) \circ \left( P\left( U+V\right) P^{\mathrm{T}}\right) \right] P^{\mathrm{T}}, \end{aligned}$$

where $X+S=PDP$ is the spectral decomposition of $X+S$ and

$$\begin{aligned} \left[ f^{\left[ 1\right] }\left( D\right) \right] _{ij}= & {} \left\{ \begin{array}{ll} \frac{\min ^{2}\left( 0,\lambda _{i}\right) -\min ^{2}\left( 0,\lambda _{j}\right) }{\lambda _{i}-\lambda _{j}},&{}\quad \text {if}\ i\ne j\in \left\{ 1,\ldots ,n\right\} \\ 2\min \left( 0,\lambda _{i}\right) &{}\quad \text {if}\ i=j\in \left\{ 1,\ldots ,n\right\} . \end{array} \right. \end{aligned}$$

Finally, the derivate of the function $\phi _{\alpha }$ is given by

$$\begin{aligned} \phi _{\alpha }^{\prime }\left( X,S\right) \left( U,V\right)= & {} US+SU+XV+VX\\&-\frac{1}{\alpha }P\left[ f^{\left[ 1\right] }\left( D\right) \circ \left( P\left( U+V\right) P^{\mathrm{T}}\right) \right] P^{\mathrm{T}} \end{aligned}$$

for all $U,V\in {\mathcal {S}}^{n}.$ $\square$

Remark 3.3

We can give the matrix function $f^{\left[ 1\right] }\left( D\right)$ by the form

$$\begin{aligned} \left[ f^{\left[ 1\right] }\left( D\right) \right] _{ij}=\left\{ \begin{array}{ll} 0&{}\quad \text {if}\ \lambda _{i}\ge 0\text { and }\lambda _{j}\ge 0 \\ \frac{- \lambda _{j}^{2}}{\lambda _{i}-\lambda _{j}}&{}\quad \text {if}\ \lambda _{i}>0\text { and }\lambda _{j}<0 \\ \frac{\lambda _{i}^{2}}{\lambda _{i}-\lambda _{j}}&{}\quad \text {if}\ \lambda _{i}<0\text { and }\lambda _{j}>0 \\ \lambda _{i}+\lambda _{j}&{}\quad \text {if}\ \lambda _{i}<0\text { and } \lambda _{j}<0, \end{array} \right. \quad \forall i,j\in \left\{ 1,2,\ldots ,n\right\} , \end{aligned}$$

then we obtain

$$\begin{aligned} \left[ f^{\left[ 1\right] }\left( D\right) \right] _{ij}=\left\{ \begin{array}{ll} =0&{}\quad \text {if}\ X+S\succeq 0(\lambda _{i}\ge 0 \text { and }\lambda _{j}\ge 0)\\<0&{}\quad \text {if not}\ \left( \text {i.e. }\lambda _{i}<0 \text { or }\lambda _{j}<0\right) \end{array} \right. . \end{aligned}$$

4 On the Applicability of Newton’s Method for Solving the SDNCP

Solving the SDNCP(F) problem comes back to solving the smooth equation $H_{\alpha }\left( X,S\right) =0$, where

$$\begin{aligned} H_{\alpha }\left( X,S\right) =\left( \begin{array}{c} \phi _{\alpha }\left( X,S\right) \\ F(X)-S \end{array} \right) , \end{aligned}$$

(4.1)

and $\phi _{\alpha }\left( X,S\right)$ is defined by (1.9).

Since the functions $\phi _{\alpha }$ and F are continuously differentiable then $H_{\alpha }$ is a continuously differentiable function. Moreover, based on Proposition 3.2, the derivative (or Jacobian) operator $H_{\alpha }^{\prime }\left( X,S\right)$ of $H_{\alpha }$ at $\left( X,S\right)$ is given by:

$$\begin{aligned} H_{\alpha }^{\prime }\left( X,S\right) \left( U,V\right) =\left( \begin{array}{c} \left( \begin{array}{c} US+SU+XV+VX \\ -\frac{1}{\alpha }P\left[ f^{\left[ 1\right] }\left( D\right) \circ \left( P\left( U+V\right) P^{\mathrm{T}}\right) \right] P^{\mathrm{T}} \end{array} \right) \\ \left( F^{^{\prime }}(X)U-V\right) \end{array} \right) , \end{aligned}$$

(4.2)

for all $U,V\in {\mathcal {S}}^{n}$, where $X+S=PDP^{\mathrm{T}}$ is the spectral decomposition of $X+S.$

To solve the equation $H_{\alpha }(X,S)=0$ by Newton’s method, we must study the invertibility property of $H_{\alpha }^{\prime }\left( X,S\right)$ at all $\left( X,S\right)$ in ${\mathcal {S}}^{n}\times {\mathcal {S}}^{n}$ near the solution. We need the following lemma:

Lemma 4.1

• (i) The operator of Lyapunov $L_{A}:{\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n},$ defined by

  $$\begin{aligned} \ L_{A}(X)=XA+AX, \end{aligned}$$

  is monotone (resp. strongly monotone) operator if $A\succeq 0$ (resp. $A\succ 0).$

• (ii) If $X,S\succ 0,$ then $L_{X}$, $L_{S}$ and $L_{S}\circ L_{X}$ are strongly monotone and $L_{X}$ and $L_{S}$ are self-adjoint.

• (iii) Let $B:{\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}$ be the operator defined by

  $$\begin{aligned} \ B\left( U\right) =- \frac{1}{\alpha }P\left[ f^{\left[ 1\right] }\left( D\right) \circ \left( P\left( U\right) P^{\mathrm{T}}\right) \right] P^{\mathrm{T}}, \end{aligned}$$

  where $X+S=PDP^{\mathrm{T}}$ is the spectral decomposition of $X+S$. Then $B=0$ if $X+S\succeq 0,$ and B is strongly monotone operator if not.

Proof

For the proof of (i) and (ii) see Lemma 4.2 in [2].

(iii) According to Remark 3.3, it follows that

• (1) If $X+S\succeq 0$, then

  $$\begin{aligned} \left[ f^{\left[ 1\right] }\left( D\right) \right] _{ij}=0, \end{aligned}$$

  for all $i,j=1,2,\ldots ,n.$ So,

  $$\begin{aligned} B=0. \end{aligned}$$

• (2) If $X+S\nsucceq 0$, then

  $$\begin{aligned} \ \left[ f^{\left[ 1\right] }\left( D\right) \right] _{ij}<0, \end{aligned}$$

  for all $i,j=1,2,\ldots ,n.$

We have

$$\begin{aligned} B is strongly monotone \Leftrightarrow \langle U,B(U)\rangle >0 , \end{aligned}$$

so, for all $U\in {\mathcal {S}}^{n}$ $\left( U\ne 0\right)$, we have

$$\begin{aligned} \left\langle U,B\left( U\right) \right\rangle= & {} \left\langle U,-\frac{1}{\alpha }P\left[ f^{\left[ 1\right] }\left( D\right) \circ \left( PUP^{\mathrm{T}}\right) \right] P^{\mathrm{T}}\right\rangle \\= & {} \text {Tr}\left( U\left( -\frac{1}{\alpha }P\left[ f^{\left[ 1\right] }\left( D\right) \circ \left( PUP^{\mathrm{T}}\right) \right] P^{\mathrm{T}}\right) \right) \\= & {} - \frac{1}{\alpha }\text {Tr}\left( UP\left[ f^{\left[ 1\right] }\left( D\right) \circ \left( PUP^{\mathrm{T}}\right) \right] P^{\mathrm{T}}\right) . \end{aligned}$$

Now, since

$$\begin{aligned} \text {Tr}(X)=\text {Tr}(P^{\mathrm{T}}XP), \quad \forall P\in {\mathcal {O}}^{n}, \end{aligned}$$

then

$$\begin{aligned} \left\langle U,B\left( U\right) \right\rangle= & {} - \frac{1}{\alpha }\text {Tr}\left( P^{\mathrm{T}}\left( UP\left[ f^{\left[ 1\right] }\left( D\right) \circ \left( PUP^{\mathrm{T}}\right) \right] P^{\mathrm{T}}\right) P\right) \\= & {} - \frac{1}{\alpha }\text {Tr}\left( \left( P^{\mathrm{T}}U P\right) f^{\left[ 1\right] }\left( D\right) \circ \left( PUP^{\mathrm{T}}\right) \right) . \end{aligned}$$

From the commutativity of the Hadamard product, we get

$$\begin{aligned} \left\langle U,B\left( U\right) \right\rangle= & {} - \frac{1}{\alpha }\text {Tr}\left( \left( P^{\mathrm{T}}UP\right) ^{2}\circ f^{\left[ 1\right] }\left( D\right) \right) \\= & {} - \frac{1}{\alpha }\sum _{i,j=1}^{n} \left( \left( P^{\mathrm{T}}UP\right) _{ij}^{2} \left( f^{\left[ 1\right] }\left( D\right) \right) _{ij}\right) >0. \end{aligned}$$

Then, the operator B is strongly monotone. $\square$

Proposition 4.2

(Invertibility of the derivative operator $H_{\alpha }^{\prime }\left( X,S\right)$ for the monotone case) Suppose that F is a monotone function.

Then for all $S\succ 0$ and $X\succ 0,$ the derivative operator $H_{\alpha }^{\prime }\left( X,S\right)$ defined by formula (4.2) is strongly monotone (so,  invertible).

Proof

$H_{\alpha }^{\prime }\left( X,S\right)$ is invertible operator $\Leftrightarrow \! \left[ H_{\alpha }^{\prime }\left( X,S\right) \left( U,V\right) =\!0\Rightarrow \left( U,V\right) =\left( 0,0\right) \right]$

$$\begin{aligned} \ H_{\alpha }^{\prime }\left( X,S\right) \left( U,V\right) =0\Leftrightarrow & {} \left( \begin{array}{c} \left( \begin{array}{c} US+SU+XV+VX \\ -\frac{1}{\alpha }P\left[ f^{\left[ 1\right] }\left( D\right) \circ \left( P\left( U+V\right) P^{\mathrm{T}}\right) \right] P^{\mathrm{T}} \end{array} \right) \\ \left[ F^{^{\prime }}(X)U-V\right] \end{array} \right) =\left( \begin{array}{c} 0 \\ 0 \end{array} \right) \\\Leftrightarrow & {} \left( \begin{array}{c} L_{S}\left( U\right) +L_{X}\left( V\right) +B\left( U\right) +B\left( V\right) \\ F^{^{\prime }}(X)U-V \end{array} \right) =\left( \begin{array}{c} 0 \\ 0 \end{array} \right) \\\Leftrightarrow & {} \left\{ \begin{array}{c} L_{S}\left( U\right) +L_{X}\left( V\right) +B\left( U\right) +B\left( V\right) =0 \\ V=F^{^{\prime }}(X)U. \end{array} \right. \end{aligned}$$

we replace $V=F^{^{\prime }}(X)U$ in the first equation:

$$\begin{aligned}&L_{S}\left( U\right) +L_{X}\left( F^{^{\prime }}(X)U\right) +B\left( U\right) +B\left( F^{^{\prime }}(X)U\right) =0\\&\quad \Leftrightarrow L_{S}\left( U\right) +\left( L_{X}\circ F^{^{\prime }}(X)\right) \left( U\right) +B\left( U\right) +\left( B\circ F^{^{\prime }}(X)\right) \left( U\right) =0 \\&\quad \Leftrightarrow \overset{A}{ \overbrace{\left( L_{S}+\left( L_{X}\circ F^{^{\prime }}(X)\right) +B+\left( B\circ F^{^{\prime }}(X)\right) \right) }}\left( U\right) =0. \end{aligned}$$

To show that the operator $H_{\alpha }^{\prime }\left( X,S\right)$ is strongly monotone (invertible), just show that the operator A is strongly monotone.

We have $S\succ 0$ and $X\succ 0$, then $S+X\succ 0.$ So, by Lemma 4.1 we have

$$\begin{aligned} B\left( U\right) =0 \quad and \quad \left( B\circ F^{^{\prime }}(X)\right) \left( U\right) =0, \end{aligned}$$

hence,

$$\begin{aligned} \ A=L_{S} + L_{X}\circ F^{^{\prime }}(X) , \end{aligned}$$

since $L_{X}$ is strongly monotone, we put $D=L_{X}^{-1}(U)$, then $U=L_{X}(D)$

$$\begin{aligned} A(U)= & {} (L_{S}+L_{X}\circ F^{^{\prime }}(X))(U) \\= & {} (L_{S}\circ L_{X}+L_{X}\circ F^{\prime }(X)\circ L_{X})(D) \\= & {} L_{S}\circ L_{X}(D)+L_{X}\circ F^{\prime }(X)\circ L_{X}(D). \end{aligned}$$

Now, by using Lemma 4.1 (property (i) and (ii)) we have $L_{X}$, $L_{S}$ and $L_{S}\circ L_{X}$ are strongly monotone and $L_{X}$ and $L_{S}$ are self-adjoint.

To show that A is strongly monotone we need to show that $L_{X}\circ F^{\prime }(X)\circ L_{X})$ is at least monotone. Then for all $D\in S^{n}$ ($D\ne 0$), we have

$$\begin{aligned} \langle L_{X}\circ F^{\prime }(X)\circ L_{X})(D),(D) \rangle= & {} \langle F^{\prime }(X)\circ L_{X})(D),L_{X}(D) \rangle ,\ \\&(\text {since}\ L_{X}\ \text {is self-adjoint}) \\= & {} \langle F^{\prime }(X)( L_{X}(D)),L_{X}(D) \rangle . \end{aligned}$$

By the fact that $F^{\prime }(X)$ is a monotone operator, we have

$$\begin{aligned} \langle F^{\prime }(X)(L_{X}(D)),L_{X}(D) \rangle \ge 0, \end{aligned}$$

then, $L_{X}\circ F^{\prime }(X)\circ L_{X}$ is monotone.

So, A is strongly monotone (sum of strongly monotone and monotone operator), so it is invertible. Consequently, the operator $H_{\alpha }^{\prime }\left( X,S\right)$ is strongly monotone, so it is invertible. $\square$

Remark 4.3

If $S\nsucc 0$ or $X\nsucc 0,$ the derivative operator $H_{\alpha }^{\prime }\left( X,S\right)$ may be not invertible. The following counter-example shows it.

Let $F:{\mathcal {S}}^{2}\rightarrow {\mathcal {S}}^{2}$ be the function defined by

$$\begin{aligned} \ F(X)=\left( \begin{array}{cc} 2x_{11} &{} x_{12} \\ x_{12} &{} x_{22}^{3}+x_{22} \end{array} \right) . \end{aligned}$$

By using theorem 2.5 in [3], we have

$$\begin{aligned} F^{\prime }(X)U=\left( \begin{array}{cc} 2u_{11} &{} u_{12} \\ u_{12} &{} \left( 3x_{22}^{2}+1\right) u_{22} \end{array} \right) ,\quad \text {for all }U=\left( \begin{array}{cc} u_{11} &{} u_{12} \\ u_{12} &{} u_{22} \end{array} \right) \in {\mathcal {S}}^{2}. \end{aligned}$$

It is clear that F is a strongly monotone function since $F^{\prime }(X)$ is a strongly monotone operator that is

$\left\langle F^{\prime }(X)U,U\right\rangle >0$, for all $U\in {\mathcal {S}}^{2}.$

Let $X_{0}=\left( \begin{array}{cc} -1 &{} 0 \\ 0 &{} 2 \end{array} \right)$ and $S_{0}=\left( \begin{array}{cc} 2 &{} 0 \\ 0 &{} -3 \end{array} \right)$ which are indefined matrices.

$X_{0}+S_{0}=\left( \begin{array}{cc} 1 &{} 0 \\ 0 &{} -1 \end{array} \right) =PDP^{\mathrm{T}}$, where $P=I_{2}$ and $D=\left( \begin{array}{cc} 1 &{} 0 \\ 0 &{} -1 \end{array} \right) .$

Let $\left( U,V\right) =\left( \left( \begin{array}{cc} u_{11} &{} u_{12} \\ u_{12} &{} u_{22} \end{array} \right) ,\left( \begin{array}{cc} v_{11} &{} v_{12} \\ v_{12} &{} v_{22} \end{array} \right) \right)$, then

$$\begin{aligned} \ H_{\alpha }^{\prime }\left( X_{0},S_{0}\right) \left( U,V\right) =\left( \begin{array}{c} \left( \begin{array}{c} US+SU+XV+VX \\ -\frac{1}{\alpha }P\left[ f^{\left[ 1\right] }\left( D\right) \circ \left( P\left( U+V\right) P^{\mathrm{T}}\right) \right] P^{\mathrm{T}} \end{array} \right) \\ \left( F^{^{\prime }}(X)U-V\right) \end{array} \right) , \end{aligned}$$

then for $\alpha =1$,

$$\begin{aligned} \ H_{\alpha }^{\prime }\left( X_{0},S_{0}\right) \left( U,V\right) =\left( \begin{array}{c} \left( \begin{array}{cc} 4u_{11}-2v_{11} &{} 1.5v_{12}-0.5u_{12} \\ 1.5v_{12}-0.5u_{12} &{} 2v_{22}-8u_{22} \end{array} \right) \\ \left( \begin{array}{cc} 2u_{11}-v_{11} &{} u_{12}-v_{12} \\ u_{12}-v_{12} &{} 13z-v_{22} \end{array} \right) \end{array} \right) , \end{aligned}$$

then

$$\begin{aligned} \ H_{\alpha }^{\prime }\left( X_{0},S_{0}\right) \left( U,V\right) = \overset{M}{\overbrace{\left( \begin{array}{cccccc} 4 &{} 0 &{} 0 &{} -2 &{} 0 &{} 0 \\ 0 &{} -0.5 &{} 0 &{} 0 &{} 1.5 &{} 0 \\ 0 &{} 0 &{} -8 &{} 0 &{} 0 &{} 2 \\ 2 &{} 0 &{} 0 &{} -1 &{} 0 &{} 0 \\ 0 &{} 1 &{} 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 0 &{} 13 &{} 0 &{} 0 &{} -1 \end{array} \right) }}\left( \begin{array}{c} u_{11} \\ u_{12} \\ u_{22} \\ v_{11} \\ v_{12} \\ v_{22} \end{array} \right) . \end{aligned}$$

Since $\det \left( M\right) =0$, then the operator $H^{\prime }\left( X_{0},S_{0}\right)$ is not invertible for $X_{0}$ and $S_{0}.$

Remark 4.4

Since we can not guarantee the invertibility of $H_{\alpha }^{\prime }\left( X_{k},S_{k}\right)$ at each iteration k, we can’t apply Newton’s method for solving the equation $H_{\alpha }\left( X,S\right) =0.$ To avoid the inversion and the computation of the Jacobian of $H_{\alpha }$ at each iteration, we propose to use a quasi-Newton method in Hilbertian space as defined in [1].

Recall that, quasi-Newton’s method for solving nonlinear equation

$$\begin{aligned} G(Z)=0, \end{aligned}$$

where ${\normalsize G:}\mathcal {X\rightarrow Y}$ is a Frechet-differentiable function and ${\mathcal {X}}$,${\mathcal {Y}}$ are two Hilbert spaces, is defined by:

$$\begin{aligned} Z_{k+1}=Z_{k}-B_{k}^{-1}\left( G\left( Z_{k}\right) \right) , \end{aligned}$$

where the operators $B_{k}$ are invertibles and approximate $G^{\prime }\left( Z_{k}\right)$ at each iteration k.

In this paper, we use the Broyden’s method [1], to update $B_{k}$ at each iteration, where the update formula is:

$$\begin{aligned} B_{k+1}=B_{k}+\frac{\left( Y_{k}-B_{k}\left( W_{k}\right) \right) \otimes W_{k}}{\left\langle W_{k}{,}W_{k}\right\rangle }, \end{aligned}$$

where $W_{k}=Z_{k+1}-Z_{k},$ $Y_{k}=G\left( Z_{k+1}\right) -G\left( Z_{k}\right)$ and $\otimes$ is the dyadic product operator defined by

$$\begin{aligned} \left( A\otimes C\right) \left( \cdot \right) =\left\langle C,\left( \cdot \right) \right\rangle A,\quad A\otimes C\in L\left( {\mathcal {X}}, {\mathcal {Y}}\right) . \end{aligned}$$

(4.3)

Remark 4.5

The notation $\otimes$ is used in the literature for the Kronecker product, but here it is used for the dyadic (or tensor) operator defined by (4.3).

Note also that for all $A, B \in {\mathcal {S}}^{n}$, the dyadic operator $A\otimes C$ is a linear operator, but the Kronecker product of matrices A and B, ($\text {Kron}(A,B)$ in Matlab notation) is a matrix of order $n^{2}\times n^{2}$. The relation between the dyadic operator and the Kronecker product is given in [1, Prop. 13].

In the space of symmetric matrices $({\mathcal {X}}={\mathcal {Y}}= {\mathcal {S}}^{n})$, the dyadic operator is given by

$$\begin{aligned} \left( A\otimes C\right) \left( M \right) =\left\langle C,M \right\rangle A=\text {Tr}(CM)A,\quad \forall M \in {\mathcal {S}}^{n} \end{aligned}$$

The following theorem shows that Broyden’s method converges superlinearly to the solution of the equation of $G(Z)=0.$

Theorem 4.6

(See [1] and references therein) Let ${\normalsize G:}{\mathcal {X}}\rightarrow {\mathcal {Y}}$ a continuously differentiable function in $D\subset {\mathcal {X}},$ where D is a convex,  open set. Assume that $Z^{*}\in D$ is a zero point of G that $G^{\prime }(Z^{*})\in L({\mathcal {X}},{\mathcal {Y}})$ is inversible and that $G^{\prime }(\cdot )$ satisfies the Lipchitz condition : 

$$\begin{aligned} \left\| G(Z)-G^{\prime }(Z^{*})\right\| \le L\left\| Z-Z^{*}\right\| , \end{aligned}$$

for each $Z\in D$.

Then,  if $Z_{0}\in D$ and $B_{0}\in L({\mathcal {X}}$,${\mathcal {Y}})$ are near $Z^{*}$ and $G^{\prime }(Z^{*})$ respectively,  we have : 

(1) the sequence $\left\{ Z_{k}\right\}$ defined by the Broyden’s method is well-defined and converges superlinearly to the solution $Z^{*}.$

(2) Furthermore,  $B_{k}^{-1}$ exists for each k and the sequences $\left\{ \left\| B_{k}\right\| \right\}$ and $\left\{ \left\| B_{k}^{-1}\right\| \right\}$ are bounded.

In practical implementation, we use the Broyden’s method in the form

$$\begin{aligned} \left\{ \begin{array}{c} B_{k}\left( W_{k}\right) =-G\left( Z_{k}\right) \\ Z_{k+1}=Z_{k}+W_{k}. \end{array} \right. \end{aligned}$$

Now, we apply the Broyden’s method to solve the equation $H_{\alpha }\left( X,S\right) =0$ defined by (4.1). This method is defined by

$$\begin{aligned} \left\{ \begin{array}{c} B_{k}\left( U_{k},V_{k}\right) =-H_{\alpha }\left( X_{k},S_{k}\right) \\ \left( X_{k+1},S_{k+1}\right) =\left( X_{k},S_{k}\right) +\left( U_{k},V_{k}\right) , \end{array} \right. \end{aligned}$$

where $B_{k}$ is updated by the following formula :

$$\begin{aligned} B_{k+1}=B_{k}+\frac{\left( Y_{k}-B_{k}\left( W_{k}\right) \right) \otimes W_{k}}{\left\langle W_{k}{,}W_{k}\right\rangle }, \end{aligned}$$

where $W_{k}=\left( X_{k+1},S_{k+1}\right) -\left( X_{k},S_{k}\right)$ and $Y_{k}=H_{\alpha }\left( X_{k+1},S_{k+1}\right) -H_{\alpha }\left( X_{k},S_{k}\right) .$

Lemma 4.7

The operator $B_{k}$ can be define by the formula

$$\begin{aligned} \!\!\!\! \ B_{k+1}\left( \cdot ,\cdot \right) =B_{k}\left( \cdot ,\cdot \right) +\beta _{k} \left( \left\langle U_{k}{,\cdot } \right\rangle +\left\langle V_{k}{,\cdot }\right\rangle \right) \left( \phi _{\alpha }\left( X_{k+1},S_{k+1}\right) ,\!F(X_{k+1})-S_{k+1}\right) ,\nonumber \\ \end{aligned}$$

(4.4)

where $\beta _{k} =\frac{{1}}{\left\langle {U}_{{k}} {,U}_{{k}}\right\rangle +\left\langle {V}_{{k}} {,V}_{{k}}\right\rangle }$.

Proof

We have

$$\begin{aligned} \ B_{k+1}=B_{k}+\frac{\left( {Y}_{{k}}-{B}_{{k} }\left( {W}_{{k}}\right) \right) \otimes {W}_{{k} }}{\left\langle {W}_{{k}}{,W}_{{k}}\right\rangle }, \end{aligned}$$

and $B_{k}\left( W_{k}\right) =-H_{\alpha }\left( X_{k},S_{k}\right)$, then

$$\begin{aligned} \ B_{k+1}=B_{k}+\frac{\left( {Y}_{{k}}+{H}_{\alpha }\left( {X}_{{k}}{,S}_{{k}}\right) \right) \otimes {W}_{{k}}}{\left\langle {W}_{{k}}{,W}_{{k}}\right\rangle }, \end{aligned}$$

where $Y_{k}=H_{\alpha }\left( X_{k+1},S_{k+1}\right) -H_{\alpha }\left( X_{k},S_{k}\right)$ and $W_{k}=\left( U_{k},V_{k}\right) .$

Hence, we obtain

$$\begin{aligned} \ B_{k+1}=B_{k}+\frac{{H}_{\alpha }{\left( X_{k+1},S_{k+1}\right) }\otimes \left( {U}_{{k}}{,V}_{ {k}}\right) }{\left\langle {U}_{{k}}{,U}_{ {k}}\right\rangle +\left\langle {V}_{{k}}{,V}_{ {k}}\right\rangle }, \end{aligned}$$

but $H_{\alpha }\left( X_{k+1},S_{k+1}\right) =\left( \phi _{\alpha }\left( X_{k+1},S_{k+1}\right) ,F(X_{k+1})-S_{k+1}\right)$, then

$$\begin{aligned} B_{k+1}=B_{k}+\frac{{1}}{\left\langle U_{k}{,} U_{k}\right\rangle +\left\langle V_{k}{,}V_{k}\right\rangle }\left( \phi _{\alpha }\left( X_{k+1},S_{k+1}\right) ,F(X_{k+1})-S_{k+1}\right) \otimes \left( U_{k},V_{k}\right) . \end{aligned}$$

Let $(U,V)\in {\mathcal {S}}^{n}\times {\mathcal {S}}^{n},$ by the definition of the dyadic product operator we have

$$\begin{aligned}&(\left( \phi _{\alpha }\left( X_{k+1},S_{k+1}\right) ,F(X_{k+1})-S_{k+1}\right) \otimes \left( U_{k},V_{k}\right) )\left( U,V\right) \\&\quad = \left\langle \left( U_{k},V_{k}\right) ,\left( U,V\right) \right\rangle \left( \phi _{\alpha }\left( X_{k+1},S_{k+1}\right) ,F(X_{k+1})-S_{k+1}\right) , \end{aligned}$$

then $B_{k+1}\left( U,V\right) =B_{k}\left( U,V\right) +\frac{\left\langle {U}_{ {k}}{,U}\right\rangle +\left\langle {V}_{{k}} {,V}\right\rangle }{\left\langle {U}_{{k}}{,U}_{ {k}}\right\rangle +\left\langle {V}_{{k}}{,V}_{ {k}}\right\rangle }\big ( \phi _{\alpha }\left( X_{k+1},S_{k+1}\right) ,F(X_{k+1})-S_{k+1}\big ) ,$

we put $\beta =\frac{{1}}{\left\langle {U}_{{k}}{,U}_{{k}}\right\rangle +\left\langle {V}_{{k}}{,V }_{{k}}\right\rangle }$, then

$B_{k+1}\left( U,V\right) =B_{k}\left( U,V\right) +\beta \left( \left\langle U_{k} {,}U\right\rangle +\left\langle V_{k}{,}V\right\rangle \right) \big ( \phi _{\alpha }\left( X_{k+1},S_{k+1}\right) ,F(X_{k+1})-S_{k+1}\big ) .$ $\square$

The following algorithm represents the quasi-Newton method applied to the equation $H_{\alpha }\left( X,S\right) =0.$

Algorithm 1: (Quasi-Newton’s method for SDNLCP(F))
Step 1: Initialization
Input a parameter $\alpha \in (0,1]$ and a tolerance $\varepsilon >0.$ Set $k=0.$
Initialize $X_{0},S_{0}\in {\mathcal {S}}^{n}$ and $B_{0}\in L\left( {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\right)$ be invertible.
Step 2: Stopping criteria
If $\left\| H_{\alpha }\left( X_{k},S_{k}\right) \right\| _{F}<\varepsilon$, stop. Otherwise go to Step 3.
Step 3: Compute the matrices$U_{k},V_{k}\ \in {\mathcal {S}}^{n}$
Find the solution $\left( U_{k},V_{k}\right) \in {\mathcal {S}}^{n}$ of the linear system:
$\ B_{k}\left( U_{k},V_{k}\right) =-H_{\alpha }\left( X_{k},S_{k}\right)$ .
Step 4: Updating formula.
Compute $B_{k+1}\in L\left( {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\right)$ by using formula (4.4).
Set $\left( X_{k+1},S_{k+1}\right) =\left( X_{k},S_{k}\right) +\left( U^{k},V^{k}\right) .$
Set $k=k+1$ and go to Step 2.

Remark 4.8

Since we must choose the operator $B_{0}$ invertible (to guarantee that $B_{k}$ is invertible for each iteration k), one possible choice is $B_{0}=I$ (the identity operator in $L\left( {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\right) )$ or $B_{0}=H_{\alpha }^{\prime }\left( X_{0},S_{0}\right)$ for $S_{0}\succ 0$ and $X_{0}\succ 0$ (cf. Proposition 4.2).

Now, we will show the convergence of the Broyden’s method for the equation $H_{\alpha }\left( X,S\right) =0$ defined by (4.1).

Theorem 4.9

(The convergence of Broyden’s method for the function $H_{\alpha })$ Let $H_{\alpha }:{\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}$ be the function defined by (4.1). Suppose that Eq. (4.1) admits a strict solution denoted by $\left( X^{*},S^{*}\right) ,$ i.e. ($X^{*}\succ 0,$ $S^{*}\succ 0$ and $H_{\alpha }\left( X^{*},S^{*}\right) =0).$

If $\left( X_{0},S_{0}\right) \in {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}$ and $B_{0}\in L\left( {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\right)$ are chosen near $\left( X^{*},S^{*}\right)$ and $H_{\alpha }^{\prime }\left( X^{*},S^{*}\right)$ respectively such that $B_{0}$ is invertible,  then : 

• (1) the sequence $\left\{ \left( X_{k},S_{k}\right) \right\}$ defined by the Broyden’s method is well-defined and converges super-linearly to the solution $\left( X^{*},S^{*}\right) .$

• (2) the operator $B_{k}^{-1}$ exists for all $k\ge 0,$ and the sequences $\left\{ \left\| B_{k}\right\| \right\}$ and $\left\{ \left\| B_{k}^{-1}\right\| \right\}$ are bounded.

Proof

The proof is based on Theorem 4.6. We have

(1) $H_{\alpha }^{\prime }\left( X^{*},S^{*}\right) \in L\left( {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\right)$ is an invertible operator, since $H_{\alpha }^{\prime }\left( X^{*},S^{*}\right)$ is invertible for any $X^{*}\succ 0$ and $S^{*}\succ 0$ (Proposition 4.2).

(2) $H_{\alpha }^{\prime }\left( X,S\right)$ is a Lipchitz operator for all $\left( X,S\right) \in {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}$ , since $H_{\alpha }^{\prime }\left( X,S\right)$ is a Lipchitz operator everywhere. $\square$

4.1 Smoothing Newton’s Method for Solving SDNCP$\left( F\right)$

In this subsection, we develop the smoothing Newton’s method for solving SDNCP$\left( F\right)$ problem.

Solving the SDNCP(F) problem by smoothing Newton’s method comes back to solving the smooth equation $H_{\mu }\left( X,S\right) =0$ where $H_{\mu }:{\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\times {\mathbb {R}} \rightarrow {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}$ is defined by

$$\begin{aligned} H_{\mu }\left( X,S\right)= & {} \left( \begin{array}{c} \phi _{\mathrm{FB}}^{\mu }\left( X,S\right) \\ F(X)-S \end{array} \right) \end{aligned}$$

(4.5)

$$\begin{aligned}= & {} \left( \begin{array}{c} X+S-\sqrt{X^{2}+S^{2}+2\mu ^{2}I} \\ F(X)-S \end{array} \right) . \end{aligned}$$

(4.6)

Smoothing Newton’s method applied to the equation $H_{\mu }\left( X,S\right) =0$ is defined by

$$\begin{aligned} \left( X_{k+1},S_{k+1}\right) =\left( X_{k},S_{k}\right) -\left( H_{\mu _{k}}^{\prime }\left( X_{k},S_{k}\right) \right) ^{-1}\left( H_{\mu _{k}}\left( X_{k},S_{k}\right) \right) \end{aligned}$$

where $H_{\mu _{k}}^{\prime }\left( X_{k},S_{k}\right)$ is the derivative operator of $H_{\mu _{k}}$ at $\left( X_{k},S_{k}\right) .$

In practical implementation, we use the smoothing Newton’s method in the form

$$\begin{aligned} \left\{ \begin{array}{c} H_{\mu _{k}}^{\prime }\left( X_{k},S_{k}\right) \left( U_{k},V_{k}\right) =-H_{\mu _{k}}\left( X_{k},S_{k}\right) \\ \left( X_{k+1},S_{k+1}\right) =\left( X_{k},S_{k}\right) +\left( U_{k},V_{k}\right) . \end{array} \right. \end{aligned}$$

(4.7)

So, at each iteration k of the smoothing Newton’s method we need to solve the system of linear equations defined in (4.7), where $\left( \mu _{k}\right)$ is a decreasing sequence of positive numbers that tends to 0.

From [13, Lemma 2(c)], The derivative of $\phi _{\mathrm{FB}}^{\mu }$ defined by (1.7) is given by

$$\begin{aligned} \left( \ \phi _{\mathrm{FB}}^{\mu }\right) ^{\prime }\left( X,S\right) \left( U,V\right) =U+V-L_{C}^{-1}[XU+UX+SV+VS] \end{aligned}$$

(4.8)

where $C=\sqrt{X^{2}+S^{2}+2\mu ^{2}I}$ and $L_{C}$ is a Lyapunov operator associated to C defined by

$L_{C}\left( X\right) =CX+XC$

Consequently the derivative of $H_{\mu }$ is given by

$$\begin{aligned} H_{\mu }^{\prime }\left( X,S\right) \left( U,V\right)= & {} \left( \begin{array}{c} \left( \ \phi _{\mathrm{FB}}^{\mu }\right) ^{\prime }\left( X,S\right) \left( U,V\right) \\ F^{\prime }(X)U-V \end{array} \right) \nonumber \\= & {} \left( \begin{array}{c} U+V-L_{C}^{-1}[XU+UX+SV+VS]. \\ F^{\prime }(X)U-V \end{array} \right) . \end{aligned}$$

(4.9)

In [13, Lemma 7], it is proved that if F is monotone then the operator $H_{\mu }^{\prime }\left( X,S\right)$ is nonsingular for all $\left( X,S\right) \in {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}$ and $\mu \in {\mathbb {R}} _{++}.$

Now, for each iteration, the system of linear equations defined in (4.7 ) equivalent to

$$\begin{aligned} U_{k}+V_{k}-L_{C_{k}}^{-1}[X_{k}U_{k}+U_{k}X_{k}+S_{k}V_{k}+V_{k}S_{k}]=-\ \phi _{\mathrm{FB}}^{\mu _{k}}\left( X_{k},S_{k}\right) \end{aligned}$$

(4.10)

and

$$\begin{aligned} F^{\prime }(X_{k})U_{k}-V_{k}=-(F(X_{k})-S_{k}). \end{aligned}$$

(4.11)

By applying $L_{C_{k}}$ to (4.10), we obtain

$$\begin{aligned} L_{C_{k}}\left( U_{k}+V_{k}\right) -[X_{k}U_{k}+U_{k}X_{k}+S_{k}V_{k}+V_{k}S_{k}]=-\ L_{C_{k}}\left( \phi _{\mathrm{FB}}^{\mu _{k}}\left( X_{k},S_{k}\right) \right) \end{aligned}$$

then

$$\begin{aligned} L_{C_{k}-X_{k}}\left( U_{k}\right) +L_{C_{k}-S_{k}}\left( V_{k}\right) =-\ L_{C_{k}}\left( \phi _{\mathrm{FB}}^{\mu _{k}}\left( X_{k},S_{k}\right) \right) \end{aligned}$$

(4.12)

and by (4.11), we have

$$\begin{aligned} V_{k}=F^{\prime }(X_{k})U_{k}+F(X_{k})-S_{k} \end{aligned}$$

(4.13)

substituting (4.13) in (4.12), we have

$$\begin{aligned}&L_{C_{k}-X_{k}}\left( U_{k}\right) +L_{C_{k}-S_{k}}\left( F^{\prime }(X_{k})U_{k}\right) \nonumber \\&\quad =-\ L_{C_{k}}\left( \phi _{\mathrm{FB}}^{\mu _{k}}\left( X_{k},S_{k}\right) \right) -L_{C_{k}-S_{k}}\left( F(X_{k})-S_{k}\right) . \end{aligned}$$

(4.14)

Algorithm 2: (Smoothing Newton’s method for SDNLCP(F))
Step 1: Initialization
Input a tolerance $\varepsilon >0.$ Set $k=0.$
Initialize $X_{0},S_{0}\in {\mathcal {S}}^{n}$ and $\mu _{0}>0$.
Step 2: Stopping criteria
If $\left\| H_{\mu _{k}}\left( X_{k},S_{k}\right) \right\| _{F}<\varepsilon$, stop. Otherwise go to Step 3.
Step 3: Compute $\left( U_{k},V_{k}\right)$ as follows:
Find the solution $U_{k}\in S^{n}$ of linear system (4.14)
Compute the matrix $V_{k}\in S^{n}$ by the relation (4.13)
Step 4: Updating formula.
Set $\left( X_{k+1},S_{k+1}\right) =\left( X_{k},S_{k}\right) +\left( U^{k},V^{k}\right) .$
Set $k=k+1$ and go to Step 2.

5 Numerical Experiments

In this section, some numerical experiments are given to show the performance of Algorithm 1 and the Smoothing Newton’s method (SNM for short) for solving SDNCP(F). We used a personal computer with 8.0 GB for random memory and Intel(R) core(TM) i7-4600M CPU 2.90 GHz to perform all numerical experiments. We used Windows 8 as operating system and Matlab R2017a to write the computer codes. For all examples, the stop criterion used in Algorithm 1 and SNM is $er_1:=\Vert H_{\alpha }(X,S)\Vert _{F}<\varepsilon =10^{-10}$ and $er_2:=\Vert H_{\mu }(X,S)\Vert _{F}<10^{-10}$ respectively or if the number of iterations is greater than 1000.

Example 5.1

Let $F:S^{4}\rightarrow S^{4}$ be the function defined by

$$\begin{aligned} F(X)=\left( \begin{array}{lccl} 2x_{11}-2 &{} \ x_{12} &{} \ x_{13} &{} x_{14} \\ x_{12} &{} \ x_{22}^{3}+x_{22}-2 &{} \ x_{23} &{} x_{24} \\ x_{13} &{} \ x_{23} &{} \ x_{33}^{3}-1 &{} x_{34} \\ x_{14} &{} \ x_{24} &{} \ x_{34} &{} x_{44}-1 \end{array} \right) ,\quad \text {for all}\ X=(x_{ij})\in S^{4}. \end{aligned}$$

We can verify that the exact solution of the SDNCP(F) associated to this function is $(X^{*},S^{*})=(I_{4},0_{4})$. Furthermore, for all $X=(x_{ij}),\,U=(u_{ij})\in S^{4}$, we have

$$\begin{aligned} F^{\prime }(X)U=\left( \begin{array}{lccl} 2u_{11} &{} \ u_{12} &{} \ u_{13} &{} u_{14} \\ u_{12} &{} \ (3x_{22}^{2}+1)\,u_{22} &{} \ u_{23} &{} u_{24} \\ u_{13} &{} \ u_{23} &{} \ 3x_{33}^{2}\,u_{33} &{} u_{34} \\ u_{14} &{} \ u_{24} &{} \ u_{34} &{} u_{44} \end{array} \right) \end{aligned}$$

Hence, for all $U\in S^{4}$ such that $U\ne 0_{4}$, we have

$$\begin{aligned} \langle <F^{\prime }(X)U,U\rangle= & {} \text {Tr}(F^{\prime }(X)U.U)\, \\= & {} 2 \sum _{j=1}^{4}u_{1j}^{2}+2(u_{23}^{2}+u_{24}^{2}+u_{34}^{2})+(3x_{22}^{2}+1)u_{22}^{2}\\&+3x_{33}^{2}u_{33}^{2}+u_{44}^{2}>0. \end{aligned}$$

So, F is strongly monotone function since $F^{\prime }(X)$ is strongly monotone operator.

Table 1 Iterations, CPU time and ${\Vert H}_{\alpha }(X_{k}{,S}_{k})\Vert$ for different initial guesses

Table 2 Iterations, CPU time and $er_2(k)$ for different initial guesses

We apply Algorithm 1 and SNM to solve the SDNCP(F), with $\alpha =1$, $B_{0}=H^{\prime }(X_{0},S_{0})$, $\mu _k=(0.85)^k$, for different choices of initial guess $(X_{0},S_{0})$. The number of iterations k , CPU time in seconds and the values $er1(k):=\Vert H_{\alpha }(X_{k},S_{k})\Vert$ and $er2(k):=\Vert H_{\mu _k}(X_{k},S_{k})\Vert$ are listed in Tables 1 and 2.

Table 3 Approximate solution ($X_{k} {,S} _{k}$) for different initial guesses

Fig. 1

Convergence of Algorithms 1 and SNM for some choices of $(X_0 ,S_0)$

The values of approximate solutions $(X_{k},S_{k})$ corresponding to different initial guesses $(X_{0},S_{0})$ finded using Algorithm 1 are shown in Table 3 (Fig. 1).

where

$$\begin{aligned} D_{1}= & {} \left( \begin{array}{llll} 0.0184 &{} -0.1242 &{} 0.0267 &{} 0.0033 \\ -0.1242 &{} -0.0251 &{} -0.0424 &{} -0.1572 \\ 0.0267 &{} -0.0424 &{} 0.0386 &{} -0.0059 \\ 0.0033 &{} -0.1572 &{} -0.0059 &{} -0.0303 \end{array} \right) ,\\ Z_{1}= & {} \left( \begin{array}{llll} 0.0369 &{} -0.1242 &{} 0.0267 &{} 0.0033 \\ -0.1242 &{} -0.2131 &{} -0.0424 &{} -0.1572 \\ 0.0267 &{} -0.0424 &{} 0.1208 &{} -0.0059 \\ 0.0033 &{} -0.1572 &{} -0.0059 &{} -0.0303 \end{array} \right) ;\\ D_{2}= & {} \left( \begin{array}{llll} 0.291 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0.1453 &{} 0 &{} 0 \\ 0 &{} 0 &{} -0.1158 &{} 0 \\ 0 &{} 0 &{} 0 &{} -0.0631 \end{array} \right) ,\\ Z_{2}= & {} \left( \begin{array}{llll} 0.0581 &{} 0 &{} 0 &{} 0 \\ 0 &{} -0.1726 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0.1740 &{} 0 \\ 0 &{} 0 &{} 0 &{} -0.0631 \end{array} \right) ;\\ D_{3}= & {} \left( \begin{array}{llll} 0.0144&{} -0.1070 &{} 0.0951 &{} 0.0106\\ -0.1070 &{} -0.0256 &{} 0.0051 &{} -0.0339\\ 0.0951 &{} 0.0051 &{} 0.0315 &{} 0.0316\\ 0.0106 &{}-0.0339 &{} 0.0316 &{} 0.0037 \end{array} \right) ,\\ Z_{3}= & {} \left( \begin{array}{llll} 0.0288 &{} -0.1070 &{} 0.0951 &{} 0.0106\\ -0.1070 &{} -0.1310 &{} 0.0051 &{} -0.0339\\ 0.0951 &{} 0.0051 &{} 0.0714 &{} 0.0316\\ 0.0106 &{} -0.0339 &{} 0.0316 &{} 0.0037 \end{array} \right) . \end{aligned}$$

Example 5.2

Let n be a positive integer and let $a_{1},b_{1},a_{2},b_{2},\dots ,a_{n},b_{n}$ be a fixed real parameters such that

$$\begin{aligned} a_{2i}=0,\quad a_{2i+1}>0,\ b_{2i}>0,\ \text {and}\ b_{2i+1}=0. \end{aligned}$$

We define a function $F:{\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}$ by

$$\begin{aligned} F(X)=\text {diag}(P_{1}(X),\dots ,P_{n}(X)) \end{aligned}$$

where for all $X=(x_{ij})\in {\mathcal {S}}^{n}$,

$$\begin{aligned} P_{i}(X)=x_{ii}^{2}-a_{i}\,x_{ii}+b_{i},\quad i\in \{1,2,\dots ,n\}. \end{aligned}$$

By a simple verification, the exact solution of SDNCP(F) associated to function F is $(X^{*},S^{*})$, where

$$\begin{aligned} X^{*}=\text {diag}(a_{1},0,a_{3},0,\dots ,a_{n}),\quad S^{*}=\text {diag}(0,b_{2},0,b_{4},\dots ,b_{n}). \end{aligned}$$

Using the definition of differentiability, we can prove that for all $X=(x_{ij})$, $U=(u_{ij})\in {\mathcal {S}}^{n}$, we have

$$\begin{aligned} F^{\prime }(X)U=\text {diag}((2x_{11}-a_{1})\,u_{11},\dots ,(2x_{nn}-a_{n})\,u_{nn}). \end{aligned}$$

Now, we take for example

$$\begin{aligned} a_{2i}=0,\quad a_{2i+1}=\frac{2i+1}{2i+2},\ b_{2i}=\frac{2i+1}{2i},\ \text {and}\ b_{2i+1}=0. \end{aligned}$$

Table 4 Performance of Algorithm 1 and SNM for $n=8, 20, 40, 60$

Fig. 2

Convergence of Algorithm 1 and SNM for $(X_0 ,S_0)=(I_{n} , I_{n})$ where $n=20, 60$

We apply Algorithm 1 and SNM to solve the SDNCP(F), with $\alpha =0.85$, $\mu _k=\frac{1}{2^{k+1}}$, $(X_{0},S_{0})=(I_{n},I_{n})$ (for both Algorithm 1 and SNM) and $B_{0}=H^{\prime }(X_{0},S_{0})$ for different values of dimension n. The number of iterations k , CPU time in seconds and the values $er_1(k):=\Vert H_{\alpha }(X_{k},S_{k})\Vert$ and $er_2(k):=\Vert H_{\mu }(X_{k},S_{k})\Vert$ are listed in Table 4. (Fig 2).

In the case $n=8$, the approximate solution $(X_{32},S_{32})$ is

$$\begin{aligned} X_{32}= & {} \text {diag}(5.0,-4.21\times 10^{-14},0.750,3.73\times 10^{-13},0.83,\\&-7.28\times 10^{-13},0.875 , 6.78\times 10^{-13}); \end{aligned}$$

and

$$\begin{aligned} S_{32}= & {} \text {diag}(2.18\times 10^{-13},1.50,-1.30\times 10^{-12},1.25,\\&-2.87\times 10^{-12},1.16,5.46\times 10^{-12},1.125). \end{aligned}$$

Note that, in this case $(n=8),$ the exact solution of SDNCP(F) is

$$\begin{aligned} X^{*}=\text {diag}\left( \frac{1}{2},0,\frac{3}{4},0,\frac{5}{6},0,\frac{7}{8} ,0\right) ,\quad S^{*}=\text {diag}\left( 0,\frac{3}{2},0,\frac{5}{4},0,\frac{7}{6} ,0,\frac{9}{8}\right) . \end{aligned}$$

Now, we repeat the same experiment with fixed dimension $n=30$ and $(X_{0},S_{0})=(\lambda *\text {diag}(a),I_{n})$ where $\lambda \in \{ 0.55 , 1 , 1.25 \}$, we get the results showing in Table 5 (Figs. 2, 3).

Table 5 Performance of Algorithm 1 and SNM for $\lambda =0.55, 0.70, 1.25$

Fig. 3

Convergence of Algorithms 1 and NM for $(X_0 ,S_0)=(\lambda *\hbox {diag}(a) , I_{30})$ where $\lambda =0.7 , 1.25$

Example 5.3

Let $Q\in S_{+}^{n}$ , $n\ge 1$. We define a function $F:{\mathcal {S}}^{n}\rightarrow {\mathcal {S}}^{n}$ by $F(X)=X^{2}-Q$. It is clear that $(X^{*},S^{*})=(Q^{\frac{1 }{2}},0_{n})$ is the exact solution of SDNCP(F) associated to function F, where $Q^{\frac{1}{2}}$ is the square root of the matrix Q.The function F is derivable on ${\mathcal {S}}^{n}$, and for all $(X,U)\in {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}$, we have

$$\begin{aligned} F^{\prime }(X)U=XU+UX. \end{aligned}$$

According to Lemma 4.1, $F^{\prime }(X)$ is strongly monotone. So F is also strongly monotone.

Now, we consider the following two choices of the matrix Q

$$\begin{aligned} Q_{1}=\text {diag}(1,2,\dots ,10),\ Q_{2}=M^{2}; \end{aligned}$$

where

$$\begin{aligned} M=\left( \begin{array}{cccccccccc} 3 &{} 2 &{} 2 &{} 1 &{} 2 &{} 2 &{} 2 &{} 2 &{} 2 &{} 2 \\ 2 &{} 2 &{} 2 &{} 1 &{} 2 &{} 2 &{} 2 &{} 2 &{} 2 &{} 2 \\ 2 &{} 2 &{} 3 &{} 1 &{} 2 &{} 2 &{} 2 &{} 2 &{} 2 &{} 2 \\ 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 \\ 2 &{} 2 &{} 2 &{} 1 &{} 3 &{} 2 &{} 2 &{} 2 &{} 2 &{} 2 \\ 2 &{} 2 &{} 2 &{} 1 &{} 2 &{} 3 &{} 2 &{} 2 &{} 2 &{} 2 \\ 2 &{} 2 &{} 2 &{} 1 &{} 2 &{} 2 &{} 3 &{} 2 &{} 2 &{} 2 \\ 2 &{} 2 &{} 2 &{} 1 &{} 2 &{} 2 &{} 2 &{} 3 &{} 2 &{} 2 \\ 2 &{} 2 &{} 2 &{} 1 &{} 2 &{} 2 &{} 2 &{} 2 &{} 3 &{} 2 \\ 2 &{} 2 &{} 2 &{} 1 &{} 2 &{} 2 &{} 2 &{} 2 &{} 2 &{} 3 \end{array} \right) \in S_{+}^{10}. \end{aligned}$$

We remark that when $Q=Q_{1}$, the exact solution of the SDNCP(F) is

$$\begin{aligned} (X^{*},S^{*})=(\text {diag}(1,\sqrt{2},\sqrt{3},\dots ,\sqrt{10}),0_{10}); \end{aligned}$$

and when $Q=Q_{2}$, then the exact solution of the SDNCP(F) is $(X^{*},S^{*})=(M,0_{10})$. We apply Algorithm 1 to solve the SDNCP(F), with $n=10$, for the two choices $Q=Q_{1}$ and $Q=Q_{2}$ and different values of parameter $\alpha \in \Omega :=\{0.10,0.25,0.50,0.75,1\}.$

First case : $Q=Q_{1}$. In the case, we take the initial guess $(X_{0},S_{0})=(2*I_{10},0.1*I_{10})$ and $B_{0}=H^{\prime }(X_{0},S_{0})$ . We get the results listed in Table 6.

Table 6 Iterations, CPU time and $\Vert H_{\alpha }(X_{k},S_{k})\Vert \text {for different values of }\alpha$

From Table 6, we remark that for all $\alpha \in \Omega$, we need 20 iterations to get desired approximate solution $(X_{20},S_{20})$, where

$$\begin{aligned} X_{20}= & {} diag(1.0,1.4142,1.7321,2.0,2.2361,2.4495,2.6458,2.8284,3.0,3.1623),\\ S_{20}= & {} 10^{-10} \,diag(-0.0533,0.1041,-0.0285,0.0153,\\&-0.0165,0.0244,-0.0039,-0,0,-0). \end{aligned}$$

However, the optimal value of $\alpha$ from $\Omega$, which makes Algorithm more faster is 0.5.

Second case : $Q=Q_{2}$. In the case, we take the initial guess $(X_{0},S_{0})=(2*M,0.1*I_{10})$ and $B_{0}=H^{\prime }(X_{0},S_{0})$.

Table 7 Iterations, CPU time and $\Vert H_{\alpha } (X_{k},S_{k})\Vert \text { for different values of}\alpha$.

From Table 7, we remark that Algorithm 1 has the same behavior for all $\alpha \in \Omega$. We need 24 iterations to get desired approximate solution $(X_{24},S_{24})=(M+10^{-11}Z_{1}\,,\,10^{-11}Z_{2})$, where

$$\begin{aligned} {\small Z_{1}= \left( \begin{array}{cccccccccc} -0.0386 &{} -0.0095 &{} 0.0303 &{} 0.0235 &{} 0.0301 &{} 0.0303 &{} 0.0303 &{} 0.0301 &{} 0.0302 &{} 0.0301 \\ -0.0095 &{} 0.2692 &{} -0.0090 &{} -0.0327 &{} -0.0093 &{} -0.0092 &{} -0.0091 &{} -0.0088 &{} -0.0093 &{} -0.0089 \\ 0.0303 &{} -0.0090 &{} -0.0387 &{} 0.0235 &{} 0.0303 &{} 0.0300 &{} 0.0301 &{} 0.0302 &{} 0.0301 &{} 0.0302 \\ 0.0235 &{} -0.0327 &{} 0.0235 &{} -0.1474 &{} 0.0235 &{} 0.0235 &{} 0.0235 &{} 0.0234 &{} 0.0235 &{} 0.0236 \\ 0.0301 &{} -0.0093 &{} 0.0303 &{} 0.0235 &{} -0.0388 &{} 0.0302 &{} 0.0304 &{} 0.0302 &{} 0.0302 &{} 0.0302 \\ 0.0303 &{} -0.0092 &{} 0.0300 &{} 0.0235 &{} 0.0302 &{} -0.0390 &{} 0.0301 &{} 0.0303 &{} 0.0304 &{} 0.0304 \\ 0.0303 &{} -0.0091 &{} 0.0301 &{} 0.0235 &{} 0.0304 &{} 0.0301 &{} -0.0389 &{} 0.0301 &{} 0.0302 &{} 0.0302 \\ 0.0301 &{} -0.0088 &{} 0.0302 &{} 0.0234 &{} 0.0302 &{} 0.0303 &{} 0.0301 &{} -0.0387 &{} 0.0301 &{} 0.0301 \\ 0.0302 &{} -0.0093 &{} 0.0301 &{} 0.0235 &{} 0.0302 &{} 0.0304 &{} 0.0302 &{} 0.0301 &{} -0.0386 &{} 0.0302 \\ 0.0301 &{} -0.0089 &{} 0.0302 &{} 0.0236 &{} 0.0302 &{} 0.0304 &{} 0.0302 &{} 0.0301 &{} 0.0302 &{} -0.0390 \end{array} \right) } \end{aligned}$$

and

$$\begin{aligned} {\small Z_{2}=\left( \begin{array}{cccccccccc} 0.0974 &{} -0.0821 &{} -0.1103 &{} -0.0150 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} -0.1103 \\ -0.0821 &{} -0.0325 &{} -0.0822 &{} -0.0672 &{} -0.0821 &{} -0.0822 &{} -0.0822 &{} -0.0822 &{} -0.0822 &{} -0.0822 \\ -0.1103 &{} -0.0822 &{} 0.0974 &{} -0.0150 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} -0.1103 \\ -0.0150 &{} -0.0672 &{} -0.0150 &{} -0.3824 &{} -0.0150 &{} -0.0150 &{} -0.0150 &{} -0.0150 &{} -0.0150 &{} -0.0150 \\ -0.1103 &{} -0.0821 &{} -0.1103 &{} -0.0150 &{} 0.0974 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} -0.1103 \\ -0.1103 &{} -0.0822 &{} -0.1103 &{} -0.0150 &{} -0.1103 &{} 0.0974 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} -0.1103 \\ -0.1103 &{} -0.0822 &{} -0.1103 &{} -0.0150 &{} -0.1103 &{} -0.1103 &{} 0.0974 &{} -0.1103 &{} -0.1103 &{} -0.1103 \\ -0.1103 &{} -0.0822 &{} -0.1103 &{} -0.0150 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} 0.0974 &{} -0.1103 &{} -0.1103 \\ -0.1103 &{} -0.0822 &{} -0.1103 &{} -0.0150 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} 0.0974 &{} -0.1103 \\ -0.1103 &{} -0.0822 &{} -0.1103 &{} -0.0150 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} -0.1103 &{} 0.0974 \end{array} \right) } \end{aligned}$$

Example 5.4

We show here an example in which Algorithm 1 converge while SNM diverge. Let n be a positive integer. Consider the problem posed in Example 4 such that $Q=(P' P)^2\in {\mathcal {S}}^{n}_{+}$ where $P=(p_{ij} )_{1\le i,j \le n}$ and

$$\begin{aligned} p_{ij}=\frac{\vert i-j \vert }{i+j} \end{aligned}$$

It is clear that the exact solution of the SDNCP(F) is $(X^{*},S^{*})=(P'P,0_{n})$. We apply Algorithm 1 and SNM to solve the SDNCP(F), with initial guess $(X_{0},S_{0})=(1.25* P'P,0.1*I_{n})$ which is closed to $(X^{*},S^{*})$ and $\alpha =0.5$ and $\mu _k=\frac{1}{2^{k+1}}$. For different values of n we obtain results showing in Table 8.

Table 8 Convergence of Algorithm 1 and divergence of SNM for $n=4, 10, 15$

For $n=4$ we get using Algorithm 1 the following approximation $(X_{28} , S_{28})$ of exact solution $(P'P,0_{n})$ :

$$\begin{aligned} X_{28}= \left( \begin{array}{cccc} 0.7211 &{} 0.3000 &{} 0.1524 &{} 0.1825\\ 0.3000 &{} 0.2622 &{} 0.2143 &{} 0.2286\\ 0.1524 &{} 0.2143 &{} 0.3104 &{} 0.3667\\ 0.1825 &{} 0.2286 &{} 0.3667 &{} 0.4915 \end{array} \right) \end{aligned}$$

and

$$\begin{aligned} S_{28}=10^{-9}*\left( \begin{array}{cccc} 0.0023 &{}-0.0117 &{} 0.0306 &{} -0.0198\\ -0.0117 &{} 0.0404 &{} -0.1048 &{} 0.0653\\ 0.0306 &{} -0.1048 &{} 0.2031 &{} -0.1177\\ -0.0198 &{} 0.0653 &{} -0.1177&{} 0.0649 \end{array} \right) \end{aligned}$$

6 Conclusion

In this paper, we proposed a new smooth NCP matrix function and studied various properties of this function. Using these properties, we reformulated the SDNCP(F) problem as a smooth equation. We proved that Newton’s method can not be applied to solve this matrix equation since we can not guarantee that its Jacobian operator is invertible at each iteration. So, we applied a quasi-Newton’s method and proved that the convergence is superlinear. Also we give some developments of the smoothing Newton’s method for solving this problem. We concluded this paper by some numerical tests which confirm the theoretical results and demonstrate the efficiency of the proposed method, and we compared between the both methods.