1 Introduction

The concept of a nonlinear complementarity function (NCP function, in short) was originally introduced by Mangasarian [1], and it has proved to be useful in computational optimization (see, e.g., [2, 3]). In the last few decades, a variety of NCP functions have been studied (see [4] and the references therein). In [5], Kanzow et al. proposed new NCP functions for the nonlinear complementarity problem and proved several properties of these functions. The nonlinear complementarity problem has a large number of important applications, and we refer the interested reader to the survey paper by Ferris and Pang [6]. In [4] and [7], some elementary properties of NCP functions have been studied. In particular, Galántai [4] developed several new methods for the construction of NCP functions. In the present paper, we focus on generalized convexity of NCP functions. We prove that, there is no pseudoconvex NCP function. Also, we prove that an NCP function cannot be both convex and differentiable. In addition, some properties of the homogeneous NCP functions are proved.

The organization of the paper is as follows. In Sect. 2, we deal with preliminaries. In Sect. 3, we prove that an NCP function cannot be pseudoconvex. In Sect. 4, we study the differentiability of homogeneous NCP functions. In Sect. 5, we investigate quasiconvex NCP functions. The paper is closed by conclusions in Sect. 6.

2 Preliminaries

In this section, we recall some definitions that will be used in the paper.

Definition 2.1

A function \(\varphi :\mathbb {R}^2 \rightarrow \mathbb {R}\) is called an NCP function iff it satisfies

$$\begin{aligned} \varphi (a,b)=0 \quad \Longleftrightarrow \quad a\geqslant 0, \;\;\; b\geqslant 0, \;\;\; ab=0. \end{aligned}$$
(1)

Definition 2.2

Let \(F:\mathbb {R}^n \rightarrow \mathbb {R}^n\) be continuously differentiable. The nonlinear complementarity problem consists in finding a vector \(\mathbf {x}\in \mathbb {R}^n\) such that

$$\begin{aligned} \mathbf {x}\geqslant 0, \quad F(\mathbf {x})\geqslant 0, \quad \langle \mathbf {x},F(\mathbf {x}) \rangle =0. \end{aligned}$$
(2)

One of the most popular approaches for solving the nonlinear complementarity problem, is to reformulate this problem as a system of nonlinear equations (see [1, 8]). For any NCP function \(\varphi \), (2) is equivalent with the equation

$$\begin{aligned} \Phi (\mathbf {x}) \mathrel {\mathop :}=[\varphi (x_1,F_1(\mathbf {x})),\ldots ,\varphi (x_n,F_n(\mathbf {x}))]^T=0, \end{aligned}$$

where \(F_i(\mathbf {x})\) and \(x_i\) denote the \(i\)th components of \(F(\mathbf {x})\) and \(\mathbf {x}\), respectively. Many NCP functions have been proposed in the literature. We list below some well-known NCP functions and their sources:

  • \(\varphi _{min}(a,b)= \min \{a,b\}\)    (Pang [9]),

  • \(\varphi _{FB}(a,b) = \sqrt{a^2+b^2}-(a+b)\)    (Fischer [10]),

  • \(\varphi _{W}(a,b)= (a-b)^{+}-a\)    (Wierzbicki [11]),

  • \(\varphi _{MS}(a,b)=ab+\frac{1}{2\lambda } \Big \{\Big [{(a-\lambda b)}^+ \Big ]^2-a^2+\Big [{(b-\lambda a)}^+\Big ]^2-b^2 \Big \}\)    (\(\lambda >1\))    (Mangasarian and Solodov [12]),

  • \(\varphi _{p}(a,b) = ||(a,b)||_p-(a+b)\)    (\(p>1\))    (Chen and Pan [13]),

  • \(\varphi _{YFB}(a,b)= \varphi _{FB}^2(a,b)\)    (Yamashita [14]),

  • \(\varphi _{\theta p}(a,b)=\root p \of {\theta (|a|^p+|b|^p)+(1-\theta )|a-b|^p}-(a+b)\)    (\(\theta \in ]0,1], \; p>1\))    (Hu, Huang and Chen [15]),

  • \(\varphi _{SW}(a,b) ={\left\{ \begin{array}{ll} \varphi _{FB}^2(a,b) &{} a\geqslant 0,\;b\geqslant 0\\ (a^-)^2+(b^-)^2 &{} \text {otherwise} \end{array}\right. }\)    (Sun and Womersley [16]),

where \(x^{+}=\max \{x,0\}\) and \(x^{-}=\min \{x,0\}\) for any real number \(x\), and \(||.||_p\) denotes the \(p\)-norm on \(\mathbb {R}^2\).

Remark 2.1

Note that \(\varphi _{FB}\) is a special case of \(\varphi _p\) with \(p=2\), and \(\varphi _p\) is a special case of \(\varphi _{\theta p}\) with \(\theta =1\).

Remark 2.2

From Definition 2.1, it is clear that if \(\varphi \) is an NCP function, then \(c\varphi \) is also an NCP function for each \(c\in \mathbb {R}{\setminus }\{0\}\), and \(\varphi ^k\) is an NCP function for any \(k \in \mathbb {N}\).

3 Nonexistence of Pseudoconvex NCP Functions

Pseudoconvexity is a desirable property in various areas of mathematical programming. In this section we prove that, unfortunately, there is no pseudoconvex NCP function.

Definition 3.1

Let \(f:\mathbb {R}^n \rightarrow \mathbb {R}\) be differentiable on \(\mathbb {R}^n\). The function \(f\) is said to be pseudoconvex iff, for each \(\mathbf {x}\), \(\mathbf {y}\in \mathbb {R}^n\) with \(f(\mathbf {x}) < f(\mathbf {y})\), we have \({\nabla f(\mathbf {y})}^{T}(\mathbf {x}-\mathbf {y}) < 0\).

In order to reach our goals in this section, we need the following lemma.

Lemma 3.1

Let \(\varphi \) be an NCP function. If the first order partial derivatives of \(\varphi \) exist at the origin, then \(\nabla \varphi (0,0)=(0,0)^T\).

Proof

Since \(\varphi \) is an NCP function, we have \(\varphi (a,0)=0\) for each \(a \geqslant 0\). Therefore,

$$\begin{aligned} \frac{\partial \varphi }{\partial a}(0,0)=\lim _{a \rightarrow 0^{+}}{\frac{\varphi (a,0)-\varphi (0,0)}{a-0}}=0. \end{aligned}$$

Similarly, it can be seen that \(\frac{\partial \varphi }{\partial b}(0,0)=0\). \(\square \)

Theorem 3.1

There is no pseudoconvex NCP function.

Proof

Assume by contradiction that \(\varphi \) is a pseudoconvex NCP function. Let \(c>0\), by definition we know that \(\varphi (c,c) \ne 0\). If \(\varphi (c,c) < 0\), then we have \(\varphi (c,c) < \varphi (0,0)\). So, by pseudoconvexity of \(\varphi \) we obtain that \({\nabla \varphi (0,0)}^{T}\begin{pmatrix} c\\ c \end{pmatrix} < 0\). But this is a contradiction, because differentiability of \(\varphi \), together with Lemma 3.1 implies that \(\nabla \varphi (0,0)=\begin{pmatrix} 0\\ 0 \end{pmatrix}\). Therefore, \(0 < \varphi (c,c) \). Now, since \(\varphi (2c,0)= 0 < \varphi (c,c)\), from pseudoconvexity of \(\varphi \), we have

$$\begin{aligned} {\nabla \varphi (c,c)}^{T}\begin{pmatrix} c\\ -c \end{pmatrix} < 0. \end{aligned}$$
(3)

On the other hand, because \(\varphi (0,2c)= 0 < \varphi (c,c)\), then by pseudoconvexity of \(\varphi \) we obtain that \({\nabla \varphi (c,c)}^{T}\begin{pmatrix} c\\ -c \end{pmatrix} > 0.\) This is a contradiction with (3), and the proof is completed. \(\square \)

As a direct consequence of Theorem 3.1, the following corollary shows that an NCP function cannot be both convex and differentiable.

Corollary 3.1

Every convex NCP function is nondifferentiable.

Proof

It follows from Theorem 3.1 and the fact that every differentiable convex function is pseudoconvex. \(\square \)

Example 3.1

\(\varphi _{W}\) and \(\varphi _{\theta p}\) are two examples of convex NCP functions [11, 15]. It is easy to see that these NCP functions are not differentiable, as predicted by Corollary 3.1. On the other hand \(\varphi _{MS}\), \(\varphi _{YFB}\) and \(\varphi _{SW}\) are differentiable [12, 14, 16], so Corollary 3.1 implies that these NCP functions are not convex.

4 Differentiability of Homogeneous NCP Functions

Most of the well-known NCP functions are homogeneous. In this section, we study the differentiability of homogeneous NCP functions.

Definition 4.1

Let \(C\) be a cone in \(\mathbb {R}^n\). A function \(f:C \rightarrow \mathbb {R}\) is said to be homogeneous of degree \(\alpha \in \mathbb {R}\) iff, it satisfies \(f(t \mathbf {x})=t^\alpha f(\mathbf {x})\), for each \(\mathbf {x}\in C\) and each \(t>0\). In particular, a function \(f\) is said to be linearly homogeneous iff, it is homogeneous of degree one.

To prove our theorems in this section, we shall need the following two lemmas. The first lemma relates the homogeneity of a function to the homogeneity of its partial derivatives.

Lemma 4.1

Let \(C\) be an open cone in \(\mathbb {R}^n\). Suppose that \(f:C \rightarrow \mathbb {R}\) is continuously differentiable and homogeneous of degree \(\alpha \). Then its first order partial derivatives are homogeneous of degree \(\alpha -1\).

Proof

See [17]. \(\square \)

Lemma 4.2

Suppose that NCP function \(\varphi \) is homogeneous of degree \(\alpha \). Then, the first order partial derivatives of \(\varphi \) exist at the origin if and only if \(\alpha >1\).

Proof

We have

$$\begin{aligned} \frac{\partial \varphi }{\partial a^-}(0,0)&=\lim _{a \rightarrow 0^{-}}{\frac{\varphi (a,0)-\varphi (0,0)}{a-0}}=\lim _{a \rightarrow 0^{-}}{\frac{\varphi (a,0)}{a}} =\lim _{a \rightarrow 0^{-}}{\frac{(-a)^\alpha \varphi (-1,0)}{a}} \nonumber \\&=-\varphi (-1,0) \lim _{a \rightarrow 0^{-}}{(-a)^{\alpha -1}}. \end{aligned}$$
(4)

Since \(\varphi (-1,0) \ne 0\), we have from (4) that

$$\begin{aligned} \frac{\partial \varphi }{\partial a^-}(0,0)=0 \quad \text {if and only if} \quad \alpha >1. \end{aligned}$$
(5)

On the other hand, since \(\varphi (a,0)=0\) for each \(a \geqslant 0\), we know that \(\frac{\partial \varphi }{\partial a^+}(0,0)=0\). Therefore, we can conclude from (5) that

$$\begin{aligned} \frac{\partial \varphi }{\partial a^-}(0,0)=\frac{\partial \varphi }{\partial a^+}(0,0) \quad \text {if and only if} \quad \alpha >1, \end{aligned}$$

i.e., \(\frac{\partial \varphi }{\partial a}(0,0)\) exists if and only if \(\alpha >1\). Similarly, we can prove that \(\frac{\partial \varphi }{\partial b}\) exists at the origin if and only if \(\alpha >1\). \(\square \)

Theorem 4.1

Suppose that NCP function \(\varphi \) is homogeneous of degree \(\alpha >1\). Then \(\varphi \) is continuously differentiable if and only if the first order partial derivatives of \(\varphi \) exist on \(\mathbb {R}^2 {\setminus }\{(0,0)\}\) and are continuous.

Proof

If \(\varphi \) is continuously differentiable, then we know that it has continuous partial derivatives everywhere in the plane. To prove the converse, it is sufficient to show that the partial derivatives of \(\varphi \) exist and are continuous at the origin.

Notice that, from Lemma 4.2, it follows that the partial derivatives of \(\varphi \) exist at the origin. Thus, by Lemma 3.1, we have \(\frac{\partial \varphi }{\partial a}(0,0)=\frac{\partial \varphi }{\partial b}(0,0)=0\). Now, let \(S\) be the unit sphere in \(\mathbb {R}^2\), i.e., \(S=\{(a,b) \in \mathbb {R}^2 \,:\; ||(a,b)||=1\}\). Since \(S\) is a compact set and \(\frac{\partial \varphi }{\partial a}\) is continuous on \(S\), it is bounded on this set. Thus, there exists \(M>0\) such that \(|\frac{\partial \varphi }{\partial a}(a,b)| \leqslant M\), for all \((a,b) \in S\). On the other hand, by using Lemma 4.1 we know that \(\frac{\partial \varphi }{\partial a}\) is homogeneous of degree \(\alpha -1\). So, for each \((a,b)\ne (0,0)\),

$$\begin{aligned} \left| {\frac{\partial \varphi }{\partial a}(a,b)}\right| \;=\;\left| { \frac{\partial \varphi }{\partial a}(\frac{||(a,b)||}{||(a,b)||}(a,b))}\right|&= ||(a,b)||^{\alpha -1} \; | \frac{\partial \varphi }{\partial a}(\frac{1}{||(a,b)||}(a,b))| \\&\leqslant ||(a,b)||^{\alpha -1} M. \end{aligned}$$

Hence, we have \(\frac{\partial \varphi }{\partial a}(a,b) \rightarrow 0\) as \((a,b) \rightarrow (0,0)\). This means that \(\frac{\partial \varphi }{\partial a}\) is continuous at the origin. Similarly, it can be shown that \(\frac{\partial \varphi }{\partial b}\) is continuous at the origin. \(\square \)

Theorem 4.2

Suppose that NCP function \(\varphi \) is homogeneous of degree \(\alpha >0\) and its partial derivatives exist and are continuous on \(\mathbb {R}^2 {\setminus }\{(0,0)\}\). Let \(k \in \mathbb {N}\), then \(\varphi ^{k}\) is a continuously differentiable NCP function if and only if \(k>\frac{1}{\alpha }\).

Proof

It is easy to see that \(\varphi ^{k}\) is a homogeneous NCP function of degree \(k\alpha \). If \(\varphi ^{k}\) is continuously differentiable then by Lemma 4.2 we have \(k\alpha >1\), and so it follows that \(k>\frac{1}{\alpha }\). The proof of converse statement is a direct consequence of Theorem 4.1.\(\square \)

As a direct result of Theorem 4.2, we have the following corollary:

Corollary 4.1

Suppose that NCP function \(\varphi \) is homogeneous of degree \(\alpha \geqslant 1\) and its partial derivatives exist and are continuous on \(\mathbb {R}^2 {\setminus }\{(0,0)\}\). Then \(\varphi ^{k}\) is a continuously differentiable NCP function, for each \(k \in \{2,3,4, \ldots \}\).

Example 4.1

One can easily see that \(\varphi _{\theta p}\) is linearly homogeneous, for all \(\theta \in ]0,1]\) and all \(p>1\). So, by Lemma 4.2, the partial derivatives of \(\varphi _{\theta p}\) do not exist at the origin. It has been proved in [15] that \(\varphi _{\theta p}\) is continuously differentiable on \(\mathbb {R}^2 {\setminus }\{(0,0)\}\). Hence, Corollary 4.1 implies that \(\varphi _{\theta p}^k\) is a continuously differentiable NCP function, for each \(k \in \{2,3,4, \ldots \}\). As a special case, it follows that \(\varphi _{YFB}= \varphi _{FB}^2\) is a continuously differentiable NCP function.

5 Quasiconvexity of NCP Functions

In this section, we prove some properties of the quasiconvex NCP functions. In particular, we generalize a theorem by Galántai [4], to quasiconvex NCP functions.

Definition 5.1

A function \(f:\mathbb {R}^n \rightarrow \mathbb {R}\) is said to be quasiconvex iff, for every \(\mathbf {x}\), \(\mathbf {y}\in \mathbb {R}^n\) and every \(\lambda \in [0,1]\),

$$\begin{aligned} f(\lambda \mathbf {x}+(1-\lambda ) \mathbf {y}) \leqslant \max \{f(\mathbf {x}), f(\mathbf {y})\}. \end{aligned}$$

Here we prove a generalization of Corollary 2 in [4]. To prove this Theorem we need the following lemma.

Lemma 5.1

For any continuous NCP function \(\varphi \), the following cases are possible:

  1. 1.

    \(\varphi (a,b) \geqslant 0\) everywhere on \(\mathbb {R}^2\);

  2. 2.

    \(\varphi (a,b) \leqslant 0\) everywhere on \(\mathbb {R}^2\);

  3. 3.

    \(\varphi (a,b) < 0\) if and only if \(a,b>0\);

  4. 4.

    \(\varphi (a,b) > 0\) if and only if \(a,b>0\).

Proof

See [4]. \(\square \)

Theorem 5.1

Let \(\varphi \) be a continuous and quasiconvex NCP function. Then \(\varphi (a,b)<0\) if and only if \(a,b>0\).

Proof

Since \(\varphi \) is quasiconvex, then for each \(c>0\) we can write

$$\begin{aligned} \varphi \Big (\frac{1}{2}(2c,0)+\frac{1}{2}(0,2c)\Big ) \leqslant \max \{\varphi (2c,0),\varphi (0,2c)\}=0. \end{aligned}$$

Therefore, we have \(\varphi (c,c) \leqslant 0\), and this implies that \(\varphi (c,c) < 0\). So, \(\varphi \) belongs to neither case 1 nor case 4 in Lemma 5.1. On the other hand, we have

$$\begin{aligned} \varphi (0,0)=\varphi \Big (\frac{1}{2}(c,c)+\frac{1}{2}(-c,-c)\Big ) \leqslant \max \{\varphi (c,c),\varphi (-c,-c)\}, \end{aligned}$$

i.e.,

$$\begin{aligned} 0 \leqslant \max \{\varphi (c,c),\varphi (-c,-c)\}. \end{aligned}$$

This last inequality together with \(\varphi (c,c) < 0\) concludes that \(\varphi (-c,-c) \geqslant 0\), which implies that \(\varphi (-c,-c) > 0\). Thus, \(\varphi \) does not belong to the case 2 in Lemma 5.1, this means that \(\varphi \) belongs to the case 3, as desired. \(\square \)

Theorem 5.2

Suppose that NCP function \(\varphi \) is continuous and quasiconvex. If \(\varphi \) is homogeneous of degree \(\alpha >0\), then it has no local minimum (or maximum).

Proof

By contradiction, suppose that \(\varphi \) has a local minimum at \(\mathbf {x}^*={(a^*,b^*)}^T\), i.e., there exists \(r>0\) such that

$$\begin{aligned} ||\mathbf {x}-\mathbf {x}^*||<r \quad \Longrightarrow \quad \varphi (\mathbf {x}) \geqslant \varphi (\mathbf {x}^*). \end{aligned}$$
(6)

If we define the function \(g:]0,+\infty [ \rightarrow \mathbb {R}\) by

$$\begin{aligned} g(t) \mathrel {\mathop :}=\varphi (t \mathbf {x}^*)=t^\alpha \varphi (\mathbf {x}^*), \end{aligned}$$

then \(g\) has a local minimum at \(t=1\). So, we have

$$\begin{aligned} g'(1)=\alpha \varphi (\mathbf {x}^*)=0, \end{aligned}$$

and hence \(\varphi (\mathbf {x}^*)=0\). It follows from the fact that \(\varphi \) is an NCP function that

$$\begin{aligned} a^* \geqslant 0 ,\quad b^* \geqslant 0 ,\quad a^*b^*=0. \end{aligned}$$

Now, if we set \(a=a^*+\frac{r}{2}\), \(b=b^*+\frac{r}{2}\) and \(\mathbf {x}={(a,b)}^T\), then since \(a,b>0\) by Theorem 5.1, we obtain that \(\varphi (\mathbf {x})<0\). On the other hand, we have

$$\begin{aligned} ||\mathbf {x}-\mathbf {x}^*||=||(\frac{r}{2},\frac{r}{2})^T||=\frac{r}{\sqrt{2}}<r. \end{aligned}$$

Thus, from (6) it follows that \(\varphi (\mathbf {x}) \geqslant \varphi (\mathbf {x}^*) = 0\). This is a contradiction and completes the proof. In a similar way, it can be proved that \(\varphi \) has no local maximum. \(\square \)

6 Conclusions

We showed in this paper that an NCP function cannot be pseudoconvex, and as a consequence of this, that every convex NCP function is nondifferentiable. Some properties of quasiconvex NCP functions are proved. Also, a characterization of continuously differentiable NCP functions is given.