On regularity conditions for complementarity problems

Abstract

In the context of complementarity problems, various concepts of solution regularity are known, each of them playing a certain role in the related theoretical and algorithmic developments. Despite the existence of rich literature on this subject, it appears that the exact relations between some of these regularity concepts remained unknown. In this note, we not only summarize the existing results on the subject but also establish the missing relations filling all the gaps in the current understanding of how different regularity concepts relate to each other. In particular, we demonstrate that strong regularity is in fact equivalent to nonsingularity of all matrices in the natural outer estimates of the generalized Jacobians of the most widely used residual mappings for complementarity problems. On the other hand, we show that CD-regularity of the natural residual mapping does not imply even BD-regularity of the Fischer–Burmeister residual mapping. As a result, we provide the complete picture of relations between the most important regularity conditions for mixed complementarity problems, with a special emphasis on those conditions used to justify the related numerical methods. A special attention is paid to the particular cases of a nonlinear complementarity problem and of a Karush–Kuhn–Tucker system.

1 Introduction

We consider the mixed complementarity problem (MCP), which is the variational inequality on the generalized box:

$$ z\in[\ell, u],\qquad \bigl\langle\varPhi(z), y-z\bigr\rangle\ge0 \quad \forall y\in[\ell, u]. $$

(1.1)

Here $\varPhi\colon\mathbb{R}^{s}\to\mathbb{R}^{s}$ is a given mapping, and

$$[\ell, u]= \bigl\{ z\in\mathbb{R}^s\bigm| \ell_i \le z_i \le u_i, i = 1, \ldots, s \bigr \}, $$

with some $\ell_{i}\in\mathbb{R}\cup\{-\infty\}$, $u_{i}\in\mathbb{R}\cup\{+\infty\}$, ℓ _i <u _i , i=1,…,s. Equivalently, the MCP can be stated as follows:

$$ z\in[\ell, u],\qquad \varPhi_i(z) \begin{cases} \ge0 & \mbox{if } z_i = \ell_i,\\ = 0 & \mbox{if } z_i \in(\ell_i, u_i),\\ \le0 & \mbox{if } z_i = u_i, \end{cases} \quad i = 1, \ldots, s. $$

(1.2)

The MCP format covers many important applications and problem settings [9, 11, 12], and perhaps the most well-known among them are the (usual) nonlinear complementarity problem (NCP)

$$ z\ge0,\qquad \varPhi(z)\ge0,\qquad \bigl\langle z, \varPhi(z) \bigr\rangle=0, $$

(1.3)

corresponding to the case when ℓ _i =0, u _i =+∞, i=1,…,s, and the Karush–Kuhn–Tucker (KKT) system

$$ \begin{aligned} &F(x)+\bigl(h'(x) \bigr)^{\mathrm{T}}\lambda+\bigl(g'(x)\bigr)^{\mathrm{T}}\mu= 0, \quad h(x)=0, \\ &\mu\ge0,\qquad g(x)\le0,\qquad\bigl\langle\mu, g(x) \bigr\rangle= 0, \end{aligned} $$

(1.4)

in unknown $(x, \lambda, \mu)\in\mathbb{R}^{n}\times\mathbb {R}^{l}\times\mathbb{R}^{m}$. Here $F\colon\mathbb{R}^{n}\to\mathbb{R}^{n}$ , $h\colon\mathbb {R}^{n}\to\mathbb{R}^{l}$ and $g\colon \mathbb{R}^{n}\to\mathbb{R}^{m}$ are given mappings, and the last two are assumed differentiable. Indeed, (1.4) can be written in the form of (1.2) by setting s=n+l+m,

$$\begin{aligned} &\ell_i=-\infty,\quad i=1, \ldots, n+l,\qquad \ell_i = 0,\quad i=n+l+1, \ldots, n+l+m, \\ &u_i = +\infty,\quad i=1, \ldots, n+l+m, \\ &\varPhi(z) = \bigl(G(x, \lambda, \mu), h(x), -g(x)\bigr),\qquad z=(x, \lambda, \mu), \end{aligned}$$

with $G\colon\mathbb{R}^{n}\times\mathbb{R}^{l}\times\mathbb{R}^{m}\to \mathbb{R}^{n}$ defined by

$$G(x, \lambda, \mu) = F(x) + \bigl(h'(x) \bigr)^{\mathrm{T}}\lambda+ \bigl(g'(x)\bigr)^{\mathrm{T}}\mu . $$

The MCP (1.1) with Φ(z)=φ′(z), $z\in \mathbb{R}^{s}$, gives the primal first-order optimality condition for the optimization problem

$$\begin{array}{l@{\quad}l} \mbox{minimize} &\varphi(z)\\ \mbox{subject to} &z\in[\ell, u], \end{array} $$

where $\varphi:\mathbb{R}^{s}\to\mathbb{R}$ is a given smooth objective function. On the other hand, the KKT system (1.4) with F(x)=f′(x), $x\in\mathbb{R}^{n}$, characterizes stationary points and the associated Lagrange multipliers of the mathematical programming problem

$$\begin{array}{l@{\quad}l} \mbox{minimize} &f(x)\\ \mbox{subject to} &h(x)=0,\qquad g(x)\le0, \end{array} $$

where $f:\mathbb{R}^{n}\to\mathbb{R}$ is a given smooth objective function.

Another well known fact (see, e.g., [1, 10]) is that the MCP can be equivalently reformulated as a system of nonlinear equations employing a complementarity function, that is, a function $\psi\colon\mathbb{R}^{2}\to\mathbb{R}$ satisfying

$$\psi(a, b) = 0 \quad\Longleftrightarrow\quad a \ge0,\qquad b \ge0,\qquad ab = 0. $$

Assuming the additional properties

$$ \psi(a, b) < 0\quad\forall a > 0, b < 0,\qquad \psi(a, b) > 0\quad\forall a > 0, b > 0, $$

(1.5)

from the equivalent formulation (1.2) of the MCP (1.1) it can be seen that solutions of this problem coincide with solutions of the equation

$$ \varPsi(z) = 0, $$

(1.6)

where $\varPsi\colon\mathbb{R}^{s}\to\mathbb{R}^{s}$ is given by

$$ \varPsi_i(z) = \begin{cases} \varPhi_i(z)& \mbox{if } i\in I_\varPhi,\\ \psi(z_i - l_i, \varPhi_i(z)) & \mbox{if } i\in I_\ell,\\ -\psi(u_i - z_i, -\varPhi_i(z)) & \mbox{if } i\in I_u,\\ \psi(z_i - l_i, -\psi(u_i - z_i, -\varPhi_i(z))) & \mbox{if } i\in I_{\ell u}, \end{cases} $$

(1.7)

with

$$\begin{aligned} I_\varPhi =& \{i=1, \ldots, s \mid\ell_i=-\infty, u_i=+\infty\}, \\ I_\ell =& \{i=1, \ldots, s \mid\ell_i>-\infty, u_i=+\infty\}, \\ I_u =& \{i=1, \ldots, s \mid\ell_i=-\infty, u_i<+\infty\}, \\ I_{\ell u} =& \{i=1, \ldots, s \mid\ell_i>-\infty, u_i<+\infty\}. \end{aligned}$$

The two most widely used complementarity functions, both satisfying (1.5), are the natural residual (or minimum) function

$$\psi(a, b) = \min\{a, b\} , $$

and the Fischer–Burmeister function

$$\psi(a, b) = a + b - \sqrt{a^2+b^2}. $$

(We changed the sign in the customary definition of the Fischer–Burmeister function [9] in order to satisfy (1.5) which is needed for the reformulation (1.6), (1.7) to take effect when the set I _lu is nonempty.) The corresponding instances of the mapping Ψ in (1.7) will be denoted by Ψ _NR and Ψ _FB , respectively. At the time, solving the equation (1.6) with Ψ=Ψ _NR or Ψ=Ψ _FB by some generalized Newton-type methods is among the most well-established numerical strategies for complementarity problems.

For a given solution $\bar{z}\in\mathbb{R}^{s}$ of the MCP (1.1) (equivalently, of (1.2)), define the index sets

$$\begin{aligned} I_+ =& I_+(\bar{z}) = \bigl\{i=1, \ldots, s \mid \varPhi_i(\bar{z})=0, \bar{z}_i\in(\ell_i, u_i)\bigr\}, \\ I_0 =& I_0(\bar{z}) = \bigl \{i=1, \ldots, s \mid\varPhi_i(\bar{z})=0,\ \bar{z}_i\in \{ \ell_i, u_i\}\bigr\}, \\ N =& N(\bar{z}) = \bigl\{i=1, \ldots, s \mid\varPhi_i( \bar{z})\neq0\bigr\}. \end{aligned}$$

Observe that no matter how smooth the underlying mapping Φ is, if the strict complementarity condition I ₀=∅ is violated then both mappings Ψ=Ψ _NR and Ψ=Ψ _FB are not necessarily differentiable at $\bar{z}$. At the same time, they are locally Lipschitz-continuous at $\bar{z}$ provided Φ possesses this property. The relevant generalized differential objects for these mappings are therefore the B-differential

$$\partial_B\varPsi(\bar{z})=\bigl\{ J\in\mathbb{R}^{s\times s}\bigm| \exists \bigl\{ z^k\bigr\} \subset{\mathcal{S}}_ \varPsi\mbox{ such that } \bigl\{ z^k\bigr\} \to\bar{z}, \bigl\{ \varPsi'\bigl(z^k\bigr)\bigr\} \to J\bigr\}, $$

where ${\mathcal{S}}_{\varPsi}$ is the set of points at which Ψ is differentiable (by the Rademacher theorem, ${\mathcal{S}}_{\varPsi}$ is a full Lebesgue measure set around $\bar{z}$), and Clarke’s generalized Jacobian

$$\partial\varPhi(\bar{z}) = \mathop{\mathrm{conv}}\partial_B\varPhi( \bar{z}), $$

where conv stands for the convex hull (see [3, Sect. 2.6.1], [9, Sect. 7.1]).

Assume that Φ is differentiable near $\bar{z}$, with its derivative being continuous at $\bar{z}$ (implying local Lipschitz continuity of Φ at $\bar{z}$). The following upper estimate of $\partial_{B}\varPsi_{NR} (\bar{z})$ (see, for example, [15]) can be derived immediately by the definition of Ψ _NR : the rows of any matrix $J\in\partial_{B}\varPsi_{NR}(\bar{z})$ satisfy

$$ J_i \begin{cases} =\varPhi_i'(\bar{z}) & \mbox{if } i \in I_+, \\ \in\{\varPhi_i'(\bar{z}), e^i \} & \mbox{if } i \in I_0,\\ =e^i & \mbox{if } i \in N, \end{cases} $$

(1.8)

where e ⁱ is the i-th row of the s×s unit matrix, i=1,…,s. The set of matrices in $\mathbb{R}^{s\times s}$ with rows satisfying (1.8) will be denoted by $\varDelta_{NR}(\bar{z})$. Therefore, $\partial_{B}\varPsi_{NR}(\bar{z})\subset\varDelta_{NR}(\bar{z} )$.

The upper estimate of $\partial\varPsi_{FB}(\bar{z})$ has been obtained in [1]. We are not aware of any reference for the proof of the corresponding upper estimate for $\partial_{B}\varPsi_{FB}(\bar{z} )$, but it can be easily derived directly from the definitions. Specifically, the rows of any matrix $J\in\partial_{B}\varPsi_{FB}(\bar{z})$ satisfy

$$ J_i = \begin{cases} \varPhi_i'(\bar{z}) & \mbox{if } i \in I_+, \\ \alpha_i\varPhi_i'(\bar{z}) + \beta_i e^i & \mbox{if } i \in I_0,\\ e^i & \mbox{if } i \in N, \end{cases} $$

(1.9)

where $(\alpha_{i}, \beta_{i})\in\mathbb{R}\times\mathbb{R}$ belongs to the set

$$ S = \bigl\{ (a, b)\in\mathbb{R}^2 \bigm|(a-1)^2+(b-1)^2=1 \bigr\} $$

(1.10)

for each i∈I ₀. The set of matrices with rows satisfying (1.9) with some (α _i ,β _i )∈S, i∈I ₀, will be denoted by $\varDelta_{FB}(\bar{z})$. With this notation, $\partial_{B}\varPsi _{FB}(\bar{z})\subset\varDelta_{FB}(\bar{z})$.

One of the referees of this paper conjectured that our smoothness hypothesis regarding Φ could actually be somewhat relaxed: it would be enough to assume that Φ is strictly differentiable at $\bar{z}$. This is indeed the case: all the constructions and conclusions of this work would remain valid under this weaker assumption. Most importantly, the sets $\varDelta _{NR}(\bar{z})$ and $\varDelta_{FB}(\bar{z})$ defined above would still serve as outer estimates of $\partial_{B}\varPsi_{NR}(\bar{z})$ and $\partial_{B}\varPsi_{FB}(\bar{z})$, respectively. This follows from [22, Lemma 5.1] which claims that in the case of strict differentiability of Φ at $\bar{z}$, the derivative Φ′ is continuous at $\bar{z}$ with respect to its domain.

The rest of the paper is organized as follows. In Sect. 2 we recall the most important and widely used regularity conditions for the MCP, including those related to the generalized differential objects defined above. We also specify which relations between these conditions have not been established so far. In Sect. 3 we fill those gaps (corresponding to the question marks in Table 1 below) and establish the complete picture of relations between these regularity conditions for the general MCP and for the NCP. Section 4 is concerned with the specificities of the KKT systems. The specific new results of this paper are those contained in Sect. 3.2 (Proposition 3.1, Lemma 3.1, Proposition 3.2, and Example 3.5) and Proposition 4.1. Overall, the main contribution of this paper is the complete flowchart of relations in Fig. 2.

Table 1 Regularity conditions for MCP: known relations

Anticipating our exposition below, we mention that each of the regularity concepts that we consider in this note is of great importance, in particular, because each of them is a key assumption in local convergence analysis of the related numerical methods for complementarity and optimization problems. Not surprisingly, these conditions have been intensively studied in the literature for many years; see [9] for an excellent summary of these studies. Nevertheless, the relationships between some of these conditions have not been fully clarified so far. This paper gives the ultimate answers to the remaining open questions of this kind.

Apart from its clear methodological value, the full picture of relations between various regularity concepts helps to clarify the relations between various convergence theories established for various methods under various sets of assumptions. For example, in order to apply the semismooth Newton method to the MCP, one has first to select a complementarity function to be used in (1.7), and the needed regularity condition is CD-regularity of the corresponding mapping Ψ. It is known that CD-regularity of Ψ _FB does not imply CD-regularity of Ψ _NR , and one might conjecture that local superlinear convergence of the method employing the Fischer–Burmeister complementarity function is established under the assumptions weaker than those needed for the natural residual. The results of this paper demonstrate that this is not the case: for the general MCP, CD-regularity of Ψ _NR does not imply CD-regularity of Ψ _FB as well, while in the case of the KKT systems these conditions are equivalent.

As another example, let us mention that in practice, computation of matrices belonging to the true ∂ _B Ψ _FB (∂ _B Ψ _NR ) or ∂Ψ _FB (∂Ψ _NR ) can require some uneasy auxiliary procedures. Quite a common strategy is to use (readily computable) matrices from Δ _FB (Δ _NR ) or convΔ _FB (convΔ _NR ) instead. Local superlinear convergence of the corresponding versions of the semismooth Newton method can be expected assuming nonsingularity of all matrices in these Δ-sets at the solution. On the other hand, these assumptions serve as verifiable sufficient conditions for the corresponding BD and CD-regularity conditions. However, our results below demonstrate that nonsingularity of Δ _FB , nonsingularity of convΔ _FB , and nonsingularity of convΔ _NR are actually very strong assumptions: they are all equivalent to strong regularity. One particular consequence of this is that, e.g., the Josephy–Newton method [2, 14] possesses local superlinear convergence under the assumptions weaker than those needed for these versions of the semismooth Newton method.

2 Regularity conditions for MCP

We will be saying that a set of square matrices is nonsingular if every matrix in this set is nonsingular. The following regularity conditions play a central role in justification of local superlinear convergence of semismooth Newton methods applied to (1.6) with a locally Lipschitzian mapping on the left-hand side (see [17, 18, 23, 24] and [9, Sect. 7.5]).

Definition 2.1

A mapping $\varPsi\colon\mathbb{R}^{s}\to\mathbb{R}^{s}$ is said to be BD-regular (CD-regular) at $\bar{z}\in\mathbb{R}^{s}$ if the set $\partial_{B}\varPsi(\bar{z})$ ($\partial\varPsi(\bar{z})$) is nonsingular.

Assuming again that $\bar{z}\in\mathbb{R}^{s}$ is a solution of the MCP (1.1), and employing the upper estimates of $\partial _{B}\varPsi_{NR}(\bar{z})$ and $\partial_{B}\varPsi_{FB}(\bar{z})$ discussed in the previous section, we conclude that BD-regularity of Ψ _NR (of Ψ _FB ) at $\bar{z}$ is implied by nonsingularity of $\varDelta_{NR}(\bar{z})$ (of $\varDelta_{FB}(\bar{z})$), while CD-regularity of Ψ _NR (of Ψ _FB ) at $\bar{z}$ is implied by nonsingularity of $\mathop{\mathrm{conv}}\varDelta_{NR}(\bar{z})$ (of $\mathop{\mathrm{conv}} \varDelta_{FB}(\bar{z})$).

Define the sets

$$\varSigma=\bigl\{ (a, b)\in\mathbb{R}^2\bigm| a+b=1, a\ge0, b\ge0 \bigr\} , $$

and

$$B=\mathop{\mathrm{conv}}S=\bigl\{ (a, b)\in\mathbb{R}^2\bigm| (a-1)^2+(b-1)^2\le1\bigr\} . $$

From the definition of $\varDelta_{NR}(\bar{z})$ by the standard tools of convex analysis it readily follows that $\mathop{\mathrm {conv}}\varDelta_{NR}(\bar{z} )$ consists of all matrices $J\in\mathbb{R}^{s\times s}$ with rows satisfying (1.9) with some (α _i ,β _i )∈Σ, i∈I ₀. Similarly, since J _i in (1.9) depends linearly on (α _i ,β _i ), by the standard tools of convex analysis it immediately follows that $\mathop{\mathrm{conv}}\varDelta_{FB}(\bar{z})$ consists of all matrices $J\in\mathbb{R} ^{s\times s}$ with rows satisfying (1.9) with some (α _i ,β _i )∈B, i∈I ₀.

In the case of the NCP (1.3), nonsingularity of $\varDelta_{NR}(\bar{z})$ is known under the name of b-regularity of solution $\bar{z}$ [21]. This condition amounts to the following: the matrix

$$\left (\begin{array}{c@{\quad}c} (\varPhi'(\bar{z}))_{I_+I_+} & (\varPhi'(\bar{z}))_{I_+K}\\ (\varPhi'(\bar{z}))_{KI_+} & (\varPhi'(\bar{z}))_{KK} \end{array} \right ) $$

is nonsingular for any index set K⊂I ₀. Here and throughout by $M_{K_{1}K_{2}}$ we denote the submatrix of a matrix M corresponding to row numbers i∈K ₁ and column numbers j∈K ₂.

In the case of the KKT system (1.4), nonsingularity of $\varDelta_{NR}(\bar{z})$ is known as quasi-regularity of solution $\bar{z}=(\bar{x}, \bar{\lambda}, \bar{\mu})\in\mathbb{R}^{n}\times \mathbb{R}^{l}\times\mathbb{R}^{m}$ [8]. Assume that F is differentiable near $\bar{x}$, with its derivative being continuous at $\bar{x}$, and h and g are twice differentiable near $\bar{x}$, with their second derivatives being continuous at $\bar{x}$, and define the index sets

$$\begin{aligned} A_+ =& A_+(\bar{x}, \bar{\mu}) = \bigl\{i=1, \ldots, m \mid\bar{\mu}_i > g_i(\bar{x}) = 0\bigr\}, \\ A_0 =& A_0(\bar{x}, \bar{\mu}) = \bigl\{i=1, \ldots, m \mid\bar{\mu}_i = g_i(\bar{x}) = 0\bigr\}. \end{aligned}$$

Quasi-regularity amounts to saying that the matrix

$$\left ( \begin{array}{c@{\quad}c@{\quad}c} \frac{\partial G}{\partial x} (\bar{x}, \bar{\lambda}, \bar{\mu})&(h'(\bar{x}))^{\mathrm{T}} &(g_{A_+\cup K}'(\bar{x}))^{\mathrm{T}}\\ h'(x)&0&0\\ g_{A_+\cup K}'(\bar{x})&0&0 \end{array} \right ) $$

is nonsingular for any index set K⊂A ₀, where by y _K we mean the subvector of y with components y _i , i∈K.

Getting back to the general MCP, in addition to the regularity conditions mentioned above, we will consider the following two properties.

Definition 2.2

A solution $\bar{z}$ of the MCP (1.1) is referred to as strongly regular if for each $r\in\mathbb{R}^{s}$ close enough to 0 the perturbed linearized MCP

$$z\in[\ell, u],\qquad \bigl\langle\varPhi(\bar{z})+\varPhi'(\bar{z}) (z-\bar{z})-r, y-z\bigr\rangle\ge 0\quad \forall y\in[\ell, u], $$

has near $\bar{z}$ the unique solution z(r) and the mapping z(⋅) is locally Lipschitz-continuous at 0.

The concept of strong regularity is due to [25], and it keeps playing an important role in modern variational analysis (see, e.g., [9, Chap. 5], [6, Chap. 2], and bibliographical comments therein). In particular, it appears as a key assumption in local convergence analysis of various iterative methods for variational problems; see [6, Chap. 6].

A simple algebraic characterization of strong regularity for the NCP was obtained in [25], and was extended to the MCP in [7]. Recall that a square matrix M is referred to as a P-matrix if all its principal minors are positive. Solution $\bar{z}$ is strongly regular if, and only if, $(\varPhi'(\bar{z}))_{I_{+}I_{+}}$ is a nonsingular matrix, and its Schur complement

$$\bigl(\varPhi'(\bar{z})\bigr)_{I_0I_0}-\bigl( \varPhi'(\bar{z})\bigr)_{I_0I_+}\bigl(\varPhi'(\bar{z} )\bigr)^{-1}_{I_+I_+}\bigl(\varPhi'(\bar{z}) \bigr)_{I_+I_0} $$

in the matrix

$$\left (\begin{array}{c@{\quad}c} (\varPhi'(\bar{z}))_{I_+I_+} & (\varPhi'(\bar{z}))_{I_+I_0}\\ (\varPhi'(\bar{z}))_{I_0I_+} & (\varPhi'(\bar{z}))_{I_0I_0} \end{array} \right ) $$

is a P-matrix.

The following weaker regularity concept was introduced in [2] as the main ingredient of sharp local convergence analysis of Newton-type methods for variational problems. Other applications of this property are concerned with sensitivity and error bounds [9, Sects. 5.3, 6.2].

Definition 2.3

A solution $\bar{z}$ of the MCP (1.1) is referred to as semistable if there exists C>0 such that for any $r\in\mathbb {R}^{s}$, any solution z(r) of the perturbed MCP

$$z\in[\ell, u],\qquad \bigl\langle\varPhi(z)-r, y-z\bigr\rangle\ge0\quad \forall y\in[\ell, u], $$

close enough to $\bar{z}$, satisfies the estimate

$$\bigl \Vert z(r)-\bar{z}\bigr \Vert \le C\|r\|. $$

3 Relations between regularity conditions

3.1 Known relations

In this section we recall the relations between the regularity properties stated above, which we consider to be known, or at least well-understood.

We start with some relations between BD-regularity and CD-regularity. It is evident that $\varDelta_{NR}(\bar{z})\subset \varDelta_{FB}(\bar{z})$, implying also the inclusion for the convex hulls $\mathop{\mathrm{conv}}\varDelta_{NR}(\bar{z})\subset\mathop {\mathrm{conv}}\varDelta_{FB}(\bar{z})$. In particular, nonsingularity of $\varDelta_{FB}(\bar{z})$ implies nonsingularity of $\varDelta_{NR}(\bar{z})$.

The converse implication is not true, in general; moreover, nonsingularity of $\varDelta_{NR}(\bar{z})$ does not necessarily imply neither CD-regularity of Ψ _NR at $\bar{z}$, nor BD-regularity of Ψ _FB at $\bar{z}$, as demonstrated by the following example taken from [19, Example 2.1].

Example 3.1

Let s=2 and consider the NCP (1.3) with Φ(z)=(−z ₁+z ₂,−z ₂). The point $\bar{z}=0$ is the unique solution of this NCP.

It can be directly checked that

$$\partial_B\varPsi_{NR}(\bar{z})=\varDelta_{NR}( \bar{z})=\left \{ \left ( \begin{array}{c@{\quad}c} 1&0\\ 0&1 \end{array} \right ), \left ( \begin{array}{c@{\quad}c} -1&1\\ 0&1\\ \end{array} \right ) \right \} , $$

and therefore, $\varDelta_{NR}(\bar{z})$ is nonsingular. On the other hand,

$$\frac{1}{2} \left ( \begin{array}{c@{\quad}c} 1&0\\ 0&1 \end{array} \right ) + \frac{1}{2} \left ( \begin{array}{c@{\quad}c} -1&1\\ 0&1\\ \end{array} \right ) =\left ( \begin{array}{c@{\quad}c} 0&1/2\\ 0&1\\ \end{array} \right ) $$

is a singular matrix, and hence, Ψ _NR is not CD-regular at $\bar{z}$.

For each k=1,2,…, set z ^k=(1/k,2/k). Then Ψ _FB is differentiable at z ^k,

$$\varPsi_{FB}'\bigl(z^k\bigr)=\left ( \begin{array}{c@{\quad}c} 0&1-1/\sqrt{2} \\ 0&-\sqrt{2} \end{array} \right ), $$

and the sequence {z ^k} converges to $\bar{z}$. Therefore, the singular matrix on the right-hand side of the last relation belongs to $\partial_{B}\varPsi_{FB}(\bar{z})$, and hence, Ψ _FB is not BD-regular at $\bar{z}$.

The next example, taken from [5, Example 2], demonstrates that $\partial_{B}\varPsi_{FB}(\bar{z})$ can be smaller than $\varDelta_{FB}(\bar{z})$. Moreover, Ψ _NR and Ψ _FB can be both CD-regular at $\bar{z}$ when both $\varDelta_{NR}(\bar{x})$ and $\varDelta_{FB}(\bar{x})$ contain singular matrices.

Example 3.2

Let s=2, Φ(z)=((z ₁+z ₂)/2,(z ₁+z ₂)/2). Then $\bar{z}=0$ is the unique solution of the NCP (1.3).

It can be directly checked that

$$\partial_B\varPsi_{NR}(\bar{z})=\left \{ \left ( \begin{array}{c@{\quad}c} 1&0\\ 1/2&1/2 \end{array} \right ), \left ( \begin{array}{c@{\quad}c} 1/2&1/2\\ 0&1\\ \end{array} \right ) \right \} , $$

and hence,

$$\partial\varPsi_{NR}(\bar{z})= \left \{ \left ( \begin{array}{c@{\quad}c} t+(1-t)/2&(1-t)/2\\ t/2&(1-t)+t/2 \end{array} \right ) \Big| t\in[0, 1] \right \} . $$

By direct computation, detJ=1/2 for all $J\in\partial\varPsi _{NR}(\bar{z} )$, implying CD-regularity (and hence BD-regularity) of Ψ _NR at $\bar{z}$. At the same time,

$$\varDelta_{NR}(\bar{z})=\left \{ \left ( \begin{array}{c@{\quad}c} 1&0\\ 0&1 \end{array} \right ), \left ( \begin{array}{c@{\quad}c} 1&0\\ 1/2&1/2 \end{array} \right ), \left ( \begin{array}{c@{\quad}c} 1/2&1/2\\ 0&1\\ \end{array} \right ), \left ( \begin{array}{c@{\quad}c} 1/2&1/2\\ 1/2&1/2\\ \end{array} \right ) \right \} , $$

where the matrix

$$ J_0=\left ( \begin{array}{c@{\quad}c} 1/2&1/2\\ 1/2&1/2 \end{array} \right ) $$

(3.1)

is singular.

Furthermore, $\varDelta_{FB}(\bar{z})$ consists of matrices of the form

$$ J=J(\alpha, \beta)=\left ( \begin{array}{c@{\quad}c} \alpha_1/2+\beta_1&\alpha_1/2\\ \alpha_2/2&\alpha_2/2+\beta_2 \end{array} \right ) $$

(3.2)

for all (α _i ,β _i )∈S, i=1,2. By direct computation,

$$\det J(\alpha, \beta)=\frac{1}{2} (\alpha_1 \beta_2+\alpha _2\beta_1+2 \beta_1\beta _2). $$

Since the inclusion (α _i ,β _i )∈S implies that α _i ≥0, β _i ≥0 for i=1,2, this determinant equals zero only provided

$$\alpha_1\beta_2=0,\qquad \alpha_2 \beta_1=0,\qquad \beta_1\beta_2=0, $$

and hence, α ₁=α ₂=1, β ₁=β ₂=0, implying that J ₀ defined in (3.1) is the only singular matrix which belongs $\varDelta_{FB}(\bar{z})$. Moreover, employing the above characterization of the structure of $\mathop{\mathrm{conv}}\varDelta_{FB}(\bar{z})$, it is evident that J ₀ is the only singular matrix in this set. However, it can be directly checked that this matrix does not belong to $\partial_{B}\varPsi_{FB}(\bar{z})$. This further implies that it does not belong to $\partial\varPsi_{FB}(\bar{z})$ as well, since from (3.2) it can be easily seen that J ₀ cannot be a non-extreme point of $\partial\varPsi_{FB}(\bar{z})$. Therefore, Ψ _FB is CD-regular (and hence BD-regular) at $\bar{z}$.

One might conjecture that BD-regularity (or at least CD-regularity) of Ψ _FB at $\bar{z}$ implies CD-regularity (or at least BD-regularity) of Ψ _NR at $\bar{z}$, but this is also not the case as demonstrated by the following example taken from [4].

Example 3.3

Let s=2, Φ(z)=(z ₂,−z ₁+z ₂). Then $\bar{z}=0$ is the unique solution of the NCP (1.3), and it can be seen that $\partial_{B}\varPsi_{NR}(\bar{z})$ contains the singular matrix

$$\left ( \begin{array}{c@{\quad}c} 0&1 \\ 0&1 \end{array} \right ), $$

while Ψ _FB is CD-regular at $\bar{z}$: it can be readily seen that the specified matrix is the only singular matrix in $\mathop{\mathrm {conv}}\varDelta _{FB}(\bar{z})$, and that it does not belong to $\partial_{B}\varPsi_{FB}(\bar{z})$; furthermore, it does not belong to $\partial\varPsi_{FB}(\bar{z})$ because this matrix cannot be a non-extreme point of this $\partial\varPsi_{FB}(\bar{z})$.

It is also known that BD-regularity of Ψ _FB at $\bar{z}$ does not imply CD-regularity of Ψ _FB at $\bar{z}$. This can be seen from the following simple example.

Example 3.4

Let s=1, Φ(z)=−z. Then $\bar{z}=0$ is the unique solution of the NCP (1.3).

Obviously, $\varPsi_{FB}(z)=-\sqrt{2} |z|$, $\partial_{B}\varPsi_{FB}(\bar{z})=\{ -\sqrt{2}, \sqrt{2}\}$, implying BD-regularity of Ψ _FB at $\bar{z}$. At the same time, $\partial\varPsi_{FB}(\bar{z})=\varDelta_{FB}(\bar{z})=[-\sqrt{2}, \sqrt {2} ]$ contains 0.

Finally, we summarize the known relations concerning semistability and strong regularity.

In [5] it has been shown that BD-regularity of either Ψ _NR or Ψ _FB at $\bar{z}$ implies semistability. The converse implication is not true. This can be seen from Examples 3.1 and 3.2.

As for strong regularity, the proof in [10, Theorem 1] implies the following: if $\bar{z}$ is a strongly regular solution of the MCP (1.1) then $\mathop{\mathrm{conv}}\varDelta _{FB}(\bar{z})$ (and hence, $\mathop{\mathrm{conv}}\varDelta_{NR}(\bar{z})$) is nonsingular. In particular, strong regularity cannot be implied by any of the conditions not implying nonsingularity of $\mathop{\mathrm{conv}}\varDelta_{FB}(\bar{z})$.

Table 1 summarizes the relations discussed in this section. Plus (minus) in each cell means that the property in the title of the row implies (does not imply) the property in the title of the column. Question mark means that to the best of our knowledge, the presence or the absence of the corresponding implications has been unknown so far.

3.2 Remaining relations

We now fill the gaps in Table 1. We begin with the following fact.

Proposition 3.1

For a solution $\bar{z}$ of the MCP (1.1) the following properties are equivalent:

• (a) $\mathop{\mathrm{conv}}\varDelta_{NR}(\bar{z})$ is nonsingular.

• (b) $\varDelta_{FB}(\bar{z})$ is nonsingular.

• (c) $\mathop{\mathrm{conv}}\varDelta_{FB}(\bar{z})$ is nonsingular.

Proof

A key observation is the following: for any point (a,b)∈B there exists t _Σ >0 such that (t _Σ a,t _Σ b)∈Σ, and there exists t _S >0 such that (t _S a,t _S b)∈S (see Fig. 1). This implies that any matrix J defined in (1.9) with (α _i ,β _i )∈B for all i∈I ₀, can be transformed into matrices of the same form but with (α _i ,β _i )∈Σ and (α _i ,β _i )∈S, respectively, for all i∈I ₀, and this transformation can be achieved by multiplication of some rows of J by appropriate positive numbers. In particular, such matrices are nonsingular only simultaneously, which gives the needed equivalence.

Fig. 1

Sets Σ, S and B

 □

Furthermore, any of the equivalent properties (a)–(c) in Proposition 3.1 implies strong regularity of $\bar{z}$, as we show next. We first prove the following lemma closely related to [16, Proposition 2.7] (see also [10, Proposition 4]).

Lemma 3.1

If $M\in\mathbb{R}^{p\times p}$ is not a P-matrix then there exist $\alpha, \beta\in\mathbb{R}^{p}$ such that (α _i ,β _i )∈S for all i=1,…,p, where S is defined in (1.10), and the matrix

$$ M(\alpha, \beta)=\mathop{\mathrm{diag}}(\alpha)M+ \mathop {\mathrm{diag}}(\beta) $$

(3.3)

is singular.

Here and in the sequel diag(α) is the diagonal matrix with diagonal elements equal to the components of the vector α.

Proof

We argue by induction. If p=1 then the assumption that M is not a P-matrix means that M is a nonpositive scalar. It follows that the circle S in (α,β)-plane always has a nonempty intersection with the straight line given by the equation diag(α)M+diag(β)=0. The points in this intersection are the needed pairs (α,β).

Suppose now that the assertion is valid for any matrix in $\mathbb{R} ^{(p-1)\times (p-1)}$, and suppose that the matrix $M\in\mathbb{R}^{p\times p}$ with elements m _i,j , i,j=1,…,p, has a nonpositive principal minor. If the only such minor is detM then set α _i =1, β _i =0, i=2,…,p, and compute

$$\begin{aligned} \det M(\alpha, \beta) =&\det \left ( \begin{array}{c@{\quad}c@{\quad}c@{\quad}c} \alpha_1m_{11}+\beta_1&\alpha_1m_{12}&\ldots&\alpha_1m_{1p}\\ m_{21}&m_{22}&\ldots&m_{2p}\\ \cdots&\cdots&\cdots&\cdots\\ m_{p1}&m_{p2}&\ldots&m_{pp}\\ \end{array} \right ) \\ =&\alpha_1\det M+\beta_1\det M_{\{ 2, \ldots, p\} \{ 2, \ldots, p\}}, \end{aligned}$$

where the last equality can be obtained by expanding the determinant by the first row. Since detM≤0 and detM _{{2,…,p}{2,…,p}}>0, we again obtain that the circle S in (α ₁,β ₁)-plane always has a nonempty intersection with the straight line given by the equation detM(α,β)=0 with respect to (α ₁,β ₁), and we again get the needed α and β.

It remains to consider the case of existence of an index set K⊂{1,…,p} such that detM _KK ≤0, and there exists k∈{1,…,p}∖K. Removing the k-th row and column from M, we then get the matrix $\tilde{M}\in\mathbb{R}^{(p-1)\times(p-1)}$ with a nonpositive principal minor. By the hypothesis of the induction there exist $\tilde{\alpha}=(\alpha_{1}, \ldots, \alpha_{k-1}, \alpha _{k+1}, \ldots, \alpha_{p})\in\mathbb{R} ^{p-1}$, $\tilde{\beta}=(\beta_{1}, \ldots, \beta_{k-1}, \beta _{k+1}, \ldots, \beta_{p})\in\mathbb{R} ^{p-1}$ such that (α _i ,β _i )∈S for all i=1,…,p, $i\not=k$, and the matrix $\mathop{\mathrm{diag}}(\tilde{\alpha})\tilde{M}+\mathop{\mathrm {diag}}(\tilde{\beta})$ is singular. Setting α _k =0, β _k =1, we again obtain the needed α and β. □

Proposition 3.2

For a solution $\bar{z}$ of the MCP (1.1), if $\varDelta_{FB}(\bar{z})$ is nonsingular then $\bar{z}$ is strongly regular.

Proof

Nonsingularity of all matrices in $\varDelta_{FB}(\bar{z})$ is equivalent to saying that the matrix

$$ D(\alpha, \beta)=\left ( \begin{array}{c@{\quad}c} (\varPhi'(\bar{z}))_{I_+I_+}&(\varPhi'(\bar{z}))_{I_+I_0}\\ \mathop{\mathrm{diag}}(\alpha)(\varPhi'(\bar{z}))_{I_0I_+}&\mathop {\mathrm{diag}}(\alpha)(\varPhi'(\bar{z} ))_{I_0I_0}+\mathop{\mathrm{diag}}(\beta) \end{array} \right ) $$

(3.4)

is nonsingular for all α=(α _i ,i∈I ₀) and β=(β _i ,i∈I ₀) satisfying (α _i ,β _i )∈S, i∈I ₀. Taking α _i =0, β _i =1, i∈I ₀, we immediately obtain that $(\varPhi'(\bar{z}))_{I_{+}I_{+}}$ is nonsingular.

Suppose that $\bar{z}$ is not strongly regular. Then nonsingularity of $(\varPhi'(\bar{z}))_{I_{+}I_{+}}$ implies that

$$\bigl(\varPhi'(\bar{z})\bigr)_{I_0I_0}-\bigl( \varPhi'(\bar{z})\bigr)_{I_0I_+}\bigl(\bigl( \varPhi'(\bar{z} )\bigr)_{I_+I_+}\bigr)^{-1}\bigl( \varPhi'(\bar{z})\bigr)_{I_+I_0} $$

is not a P-matrix. Therefore, by Lemma 3.1 we obtain the existence of α=(α _i ,i∈I ₀) and β=(β _i ,i∈I ₀) satisfying (α _i ,β _i )∈S, i∈I ₀, and such that the matrix

$$\mathop{\mathrm{diag}}(\alpha) \bigl(\bigl(\varPhi'(\bar{z}) \bigr)_{I_0I_0}-\bigl(\varPhi '(\bar{z})\bigr)_{I_0I_+} \bigl(\bigl(\varPhi '(\bar{z})\bigr)_{I_+I_+} \bigr)^{-1}\bigl(\varPhi'(\bar{z} )\bigr)_{I_+I_0} \bigr)+\mathop{\mathrm{diag}}(\beta) $$

is singular. But this matrix is the Schur complement of the nonsingular matrix $(\varPhi'(\bar{z} ))_{I_{+}I_{+}}$ in D(α,β), and therefore, we conclude that D(α,β) is also singular (see, e.g., [20, Theorem 2.1]). □

Combining Propositions 3.1 and 3.2 with the known fact that strong regularity of $\bar{z}$ implies nonsingularity of $\mathop{\mathrm{conv}}\varDelta _{FB}(\bar{z})$, we finally obtain that any of the equivalent properties (a)–(c) in Proposition 3.1 is further equivalent to strong regularity.

Now the only thing to clarify is whether CD-regularity of Ψ _NR at $\bar{z}$ implies CD-regularity or (at least BD-regularity) of Ψ _FB at $\bar{z}$. The next example demonstrates that this is not the case; moreover, even a combination of CD-regularity of Ψ _NR at $\bar{z}$ and nonsingularity of $\varDelta_{NR}(\bar{z})$ does not imply BD-regularity (and even less so CD-regularity) of Ψ _FB at $\bar{z}$.

Example 3.5

Let n=2, $\varPhi(z)=(-z_{1}+3z_{2}/(2\sqrt{2} ), 2z_{1}+(1-3/(2\sqrt{2} ))z_{2})$. Then $\bar{z}=0$ is the unique solution of the corresponding NCP.

Consider any sequence $\{ z^{k}\} \subset\mathbb{R}^{2}$ such that $z_{1}^{k}<0$, $z_{2}^{k}=0$ for all k, and $z_{1}^{k}$ tends to 0 as k→∞. Then for all k it holds that Ψ _FB is differentiable at z ^k, and

$$\begin{aligned} \varPsi_{FB} '\bigl(z^k\bigr) =&\left ( \begin{array}{c@{\quad}c} -\frac{2z_1^k}{\sqrt{2(z_1^k)^2} } & \frac{3}{2\sqrt{2} } (1+\frac{z_1^k}{\sqrt {2(z_1^k)^2} } )\\ 2 (1-\frac{2z_1^k}{\sqrt{(2z_1^k)^2} } )& 1+ ( 1-\frac{3}{2\sqrt{2} } ) (1-\frac {2z_1^k}{\sqrt{(2z_1^k)^2} } ) \end{array} \right ) \\ =&\left ( \begin{array}{c@{\quad}c} \sqrt{2} &\frac{3}{2\sqrt{2} } (1-\frac {1}{\sqrt{2} } )\\ 4&1+2 ( 1-\frac{3}{2\sqrt{2} } ) \end{array} \right ), \end{aligned}$$

and therefore, the singular matrix on the right-hand side belongs to $\partial_{B}\varPsi_{FB}(\bar{z})$.

At the same time, it can be directly checked that

$$\partial_B\varPsi_{NR}(\bar{z})=\left \{ \left ( \begin{array}{c@{\quad}c} 1&0\\ 2&1-\frac{3}{2\sqrt{2} } \end{array} \right ), \left ( \begin{array}{c@{\quad}c} -1&\frac{3}{2\sqrt{2} } \\ 0&1\\ \end{array} \right ) \right \} , $$

and hence,

$$\partial\varPsi_{NR}(\bar{z})= \left \{ \left ( \begin{array}{c@{\quad}c} t-(1-t)&(1-t)\frac{3}{2\sqrt{2} } \\ 2t&t (1-\frac{3}{2\sqrt{2} } )+(1-t) \end{array} \right )\bigg \vert t\in[0, 1] \right \} . $$

By direct computation, for any matrix J(t) on the right-hand side of the last relation we have

$$\det J(t)= \biggl(2- \frac{3}{2\sqrt{2} } \biggr)t-1\le1-\frac {3}{2\sqrt{2} }<0\quad \forall t\in[0, 1], $$

implying CD-regularity of Ψ _NR at $\bar{z}$.

Observe also that

$$\begin{aligned} &\varDelta_{NR}(\bar{z}) \\ &\quad=\left \{ \left ( \begin{array}{c@{\quad}c} 1&0\\ 0&1 \end{array} \right ), \left ( \begin{array}{c@{\quad}c} 1&0\\ 2&1-\frac{3}{2\sqrt{2} } \end{array} \right ), \left ( \begin{array}{c@{\quad}c} -1&\frac{3}{2\sqrt{2} } \\ 0&1\\ \end{array} \right ), \left ( \begin{array}{c@{\quad}c} -1&\frac{3}{2\sqrt{2} } \\ 2&1-\frac{3}{2\sqrt{2} } \end{array} \right ) \right \} , \end{aligned}$$

and it is evident that $\varDelta_{NR}(\bar{z})$ is nonsingular, that is, $\bar{z}$ is a b-regular solution.

Example 3.5 shows that replacing $\partial_{B}\varPsi _{NR}(\bar{z})$ by its convexification $\partial\varPsi_{NR}(\bar{z})$, or by its different enlargement $\varDelta_{NR}(\bar{z})$, and assuming nonsingularity of all matrices in the resulting set does not imply even BD-regularity of Ψ _FB at $\bar{z}$. However, by Propositions 3.1 and 3.2, applying both these enlargements together (that is, assuming nonsingularity of all matrices in $\mathop{\mathrm{conv}}\varDelta _{NR}(\bar{z})$) implies strong regularity of $\bar{z}$.

4 KKT systems

Some implications that are not valid for the general MCP turn out to be true for the special case of the KKT system.

The key observation is that unlike the case of the NCP, for the KKT systems formula (1.8) gives not only an outer estimate of the B-differential of Ψ _NR but its exact characterization: for any solution $\bar{z}=(\bar{x}, \bar{\lambda}, \bar{\mu})$ of the KKT system (1.4) it holds that $\partial_{B}\varPsi _{NR}(\bar{z}) = \varDelta_{NR}(\bar{z})$, implying also the equality $\partial \varPsi_{NR}(\bar{z}) = \mathop{\mathrm{conv}}\varDelta_{NR}(\bar{z})$. This is due to the fact that the primal variable x and the dual variable μ are “decoupled” in the arguments of the natural residual complementarity function, and for any $J\in\varDelta_{NR}(\bar{z})$, one can readily construct a sequence $\{ z^{k}\} \subset{\mathcal{S}}_{\varPsi _{NR}}$ such that $\{ z^{k}\} \to\bar{z}$ and $\{ \varPsi_{NR}'(z^{k})\} \to J$.

Therefore, in the case of the KKT system BD-regularity of Ψ _NR at $\bar{z}$ is equivalent to nonsingularity of $\varDelta_{NR}(\bar{z})$ (that is, to quasi-regularity of this solution), while CD-regularity of Ψ _NR at $\bar{z}$ is equivalent to nonsingularity of $\mathop{\mathrm{conv}}\varDelta _{NR}(\bar{z})$.

As for Ψ _FB , it can be seen that the formula (1.9) gives the exact characterization of the B-differential of this mapping at $\bar{z}$ provided that the gradients $g_{i}'(\bar{x})$, i∈A ₀, are linearly independent. We next show that the latter condition is automatically satisfied at any solution $\bar{z}$ of the KKT system such that Ψ _FB is BD-regular at this solution.

Proposition 4.1

Let $F\colon\mathbb{R}^{n}\to\mathbb{R}^{n}$ be differentiable in a neighborhood of $\bar{x} \in\mathbb{R}^{n}$, with its derivative being continuous at $\bar{x}$, and let $h\colon\mathbb{R}^{n}\to\mathbb{R}^{l}$ and $g\colon\mathbb {R}^{n}\to\mathbb{R}^{m}$ be twice differentiable in a neighborhood of $\bar{x}$, with their second derivatives being continuous at $\bar{x}$. Let $\bar{z}=(\bar{x}, \bar{\lambda}, \bar{\mu})$ with some $(\bar{\lambda}, \bar{\mu})\in\mathbb{R}^{l}\times \mathbb{R}^{m}$ be a solution of the KKT system (1.4).

If Ψ _FB is BD-regular at $\bar{z}$ then $\bar{x}$ satisfies the linear independence constraint qualification: the gradients $h'_{j}(\bar{x})$, j=1,…,l, $g_{i}'(\bar{x})$, i∈A=A ₊∪A ₀, are linearly independent.

Proof

Fix any sequence $\{ \mu^{k}\} \subset\mathbb{R}^{m}$ such that $\mu_{A}^{k}>0$, $\mu_{\{ 1, \ldots, m\} \setminus A}^{k}=0$ for all k, and $\{ \mu_{A}^{k}\} \to\bar{\mu}_{A}$. Then the sequence $\{ (\bar{x}, \bar{\lambda}, \mu^{k})\}$ converges to $(\bar{x}, \bar{\lambda}, \bar{\mu})$, and it can be easily seen that for any k the mapping Ψ _FB is differentiable at $(\bar{x}, \bar{\lambda}, \mu^{k})$, and the sequence of its Jacobians converges to the matrix

$$\left ( \begin{array}{c@{\quad}c@{\quad}c@{\quad}c} \frac{\partial G}{\partial x} (\bar{x}, \bar{\lambda}, \bar{\mu})&(h'(\bar{x}))^{\mathrm{T}}& (g_A'(\bar{x}))^{\mathrm{T}}&(g_{\{ 1, \ldots, m\} \setminus A}'(\bar{x}))^{\mathrm{T}}\\ h'(\bar{x})&0&0&0\\ -g_A'(\bar{x})&0&0&0\\ 0&0&0&I \end{array} \right ) $$

(perhaps after an appropriate re-ordering of rows and columns), where I stands for the identity matrix of the appropriate size. The needed result is now evident. □

From this proposition and the preceding discussion it follows that for the KKT system BD-regularity of Ψ _FB at $\bar{z}$ implies nonsingularity of $\varDelta_{FB}(\bar{z})$, and hence, by Proposition 3.1, nonsingularity of $\mathop{\mathrm{conv}}\varDelta_{FB}(\bar{z})$ (which in its turn implies CD-regularity of Ψ _FB at $\bar{z}$). Also, it now becomes evident, that CD-regularity of Ψ _FB at a solution $\bar{z}$ of the KKT system implies nonsingularity of $\varDelta_{FB}(\bar{z})$.

Therefore, for the KKT systems, we have three groups of equivalent conditions. The first group consists of BD-regularity of Ψ _FB at $\bar{z}$, CD-regularity of Ψ _NR at $\bar{z}$, CD-regularity of Ψ _FB at $\bar{z}$, nonsingularity of $\varDelta_{FB}(\bar{z})$, nonsingularity of $\mathop{\mathrm {conv}}\varDelta_{NR}(\bar{z})$, nonsingularity of $\mathop{\mathrm{conv}}\varDelta_{FB}(\bar{z})$, and strong regularity of $\bar{z}$. The second group consists of BD-regularity of Ψ _NR at $\bar{z}$, and of nonsingularity of $\varDelta_{NR}(\bar{z})$. The last group consists of semistability. Conditions in the first group imply conditions in the second, and conditions in the second imply semistability.

The absence of converse implications is well-understood. The NCP in Example 3.4 corresponds to the primal first-order optimality conditions for the optimization problem

$$\begin{array}{l@{\quad}l} \mbox{minimize} &-\dfrac{1}{2} x^2\\ \mbox{subject to} &x\ge0. \end{array} $$

The unique solution of the corresponding KKT system is $\bar{z}=(\bar{x} , \bar{\mu})=(0, 0)$, and it can be readily seen that this solution is quasi-regular, but $\varDelta_{FB}(\bar{z})$ contains a singular matrix.

The fact that semistability does not necessarily imply BD-regularity of Ψ _NR is demonstrated. e.g., by [13, Example 1].

In conclusion we present all the relations between regularity conditions in question in the form of a flowchart in Fig. 2. The solid arrows correspond to implications valid for the general MCP, while the dashed arrows show the additional implications valid for the KKT systems. The diagram is complete: if two blocks in it are not connected by (a sequence of) arrows, it means the absence of the corresponding implication, even for the particular cases of the NCP or the KKT system (observe that all counterexamples presented in Sect. 3 are the NCPs).

Fig. 2

Regularity conditions: complete flowchart of relations