Error Bounds of Regularized Gap Functions for Polynomial Variational Inequalities

Abstract

This paper is devoted to presenting new error bounds of regularized gap functions for polynomial variational inequalities with exponents explicitly determined by the dimension of the underlying space and the number/degree of the involved polynomials. The main techniques are based on semialgebraic geometry and variational analysis, which allow us to establish a nonsmooth extension of the seminal Łojasiewicz gradient inequality to regularized gap functions with explicitly calculated exponents.

1 Introduction

In the finite-dimensional setting, suppose that a cost map and a constraint set are given. We study the variational inequality problem in which a point in the constraint set is sought such that the negative of the cost map at this point is a normal vector to the constraint set at that point. It is well known that when the constraint set is the nonnegative orthant, the variational inequality problem reduces to the nonlinear complementarity problem.

Variational inequalities and related problems have been widely studied in various fields such as mathematical programming, game theory, and economics. There is a large literature on all aspects of the theory and applications of variational inequalities; for more details, we refer the reader to the survey by Harker and Pang [11] and the comprehensive monograph by Facchinei and Pang [8] with the references therein for the scalar variational inequalities and [3, 12] for the vector variational inequalities.

Many fruitful approaches to both theoretical and numerical treatment of variational inequalities make use of merit (gap) functions. Among these merit functions, regularized gap functions are particularly interesting because they cast variational inequality problems as equivalent constrained optimization problems ( [1, 8, 9, 29,30,31]). Furthermore, regularized gap functions have remarkable properties, which are basic for development of iterative algorithms for solving variational inequalities.

On the other hand, the theory of error bounds provides a useful aid for understanding the connection between a merit function and the actual distance to its zero set and hence plays an important role in convergence analysis and stopping criteria for many iterative algorithms; for more details, see [8, Chapter 6] and references therein. Therefore, it would be interesting and useful to investigate error bounds for regularized gap functions associated with variational inequalities.

Assume that the cost mapping is strongly monotone and smooth and that the constraint set is closed convex. By virtue of the consideration of differentials, Wu et al. [31], Yamashita and Fukushima [32], and Huang and Ng [15] showed that the regularized gap function of the corresponding variational inequality problem has an error bound with a certain non-unit exponent and thereby established convergence results of sequences obtained by an algorithm of Armijo type. These results are extended by Ng and Tan [26] to cover the case where the cost map is not necessarily smooth; see also [17, 18, 29, 33, 34] for related works. As the reader can see, the monotonicity of the cost map and the convexity of the constraint set play a crucial role in establishing these results.

At this point, we would like to mention that error bound results with explicit exponents are indeed important for both theory and applications since they can be used, e.g., to establish explicit convergence rates of iterative algorithms. On the other hand, as explained by Luo et al. [23], exponents in error bound results are, in general, difficult to determine.

In this paper, we study error bounds of regularized gap functions associated with variational inequalities with polynomial data. Namely, assume that the cost map is a polynomial map and the constraint set is a closed set defined by finitely many polynomial equalities and inequalities, our contribution is as follows:

• 1. We establish a nonsmooth version of the seminal Łojasiewicz gradient inequality to the regularized gap function with an explicitly calculated exponent (see Theorem 3.1).

• 2. We propose new error bounds for the regularized gap function with explicitly calculated exponents (see Theorems 4.1 and 4.2 ).

In fact, the exponents in these results are determined by the dimension of the underlying space and the number/degree of the involved polynomials.

Note that we do not require that the cost map is (strongly) monotone or the restriction of the cost map on the constraint set satisfies regularity conditions at infinity or the constraint set is convex. A motivation for studying such a problem is that Nash–Cournot oligopolistic equilibrium models involving concave cost [25], in some cases, can be reformulated in this form. On the other hand, our proof is similar in spirit to that of [27] (see also [6, 16, 19,20,21] for related works); in particular, the techniques used here are largely based on semialgebraic geometry and variational analysis. Furthermore, while all results are stated for regularized gap functions, we believe analogous results can be obtained for D-gap functions; for the definition and properties of these functions, we refer to [8]. However, to lighten the exposition, we do not pursue this idea here.

The rest of the paper is organized as follows: In Sect. 2, we review some preliminaries from variational analysis and semialgebraic geometry that will be used later. Given a polynomial variational inequality, in Sect. 3, we provide a nonsmooth version of the Łojasiewicz gradient inequality to the regularized gap function, and in Sect. 4, we establish some error bounds for the regularized gap function.

2 Preliminaries

Throughout this work, we deal with the Euclidean space ${\mathbb {R}}^n$ equipped with the usual scalar product $\langle \cdot , \cdot \rangle$ and the corresponding Euclidean norm $\Vert \cdot \Vert .$ The distance from a point $x \in {\mathbb {R}}^n$ to a nonempty set $A \subset {\mathbb {R}}^n$ is defined by

$$\begin{aligned} \mathrm {dist}(x, A) := \inf _{y\in A} \Vert x - y\Vert . \end{aligned}$$

By convention, the distance to the empty set is equal to infinity. We write ${\mathrm {conv}}A$ for the convex hull of A. We denote by ${\mathbb {B}}_r(x)$ the closed ball centered at x with radius r;  we also use the notations ${\mathbb {B}}_r$ for ${\mathbb {B}}_r(0)$ and ${\mathbb {B}}$ for the closed unit ball. For each real number r,  we put $[r]_+ := \max \{r, 0\}.$

2.1 Some Subdifferentials

We first recall the notions of subdifferentials, which are crucial for our considerations. For nonsmooth analysis, we refer the reader to the comprehensive texts [5, 24, 28].

Definition 2.1

Let $f :{\mathbb {R}}^n \rightarrow {\mathbb {R}}$ be a lower semicontinuous function and $x \in {\mathbb {R}}^n$.

• (i) The Fréchet subdifferential ${\hat{\partial }} f(x)$ of f at x is given by

  $$\begin{aligned} {\hat{\partial }} f(x) := \left\{ v \in {\mathbb {R}}^n \ : \ \liminf _{\Vert h \Vert \rightarrow 0, \ h \ne 0} \frac{f(x + h) - f(x) - \langle v, h \rangle }{\Vert h \Vert } \ge 0 \right\} . \end{aligned}$$

• (ii) The limiting (known also as basic, Mordukhovich) subdifferential of f at x,  denoted by ${\partial } f(x),$ is the set of all cluster points of sequences $\{v^k\}$ such that $v^k\in {\hat{\partial }} f(x^k)$ and $(x^k, f(x^k)) \rightarrow (x, f(x))$ as $k \rightarrow \infty .$

• (iii) Assume that f is locally Lipschitz. By Rademacher’s theorem, f has at almost all points $x \in {\mathbb {R}}^n$ a gradient, which we denote $\nabla f(x).$ Then, the Clarke (or convexified) subdifferential ${\partial }^\circ f(x)$ of f at x is defined by

  $$\begin{aligned} {\partial }^\circ f(x) := {\mathrm {conv}}\{\lim \nabla f(x^k) \ : \ x^k\rightarrow x\}. \end{aligned}$$

Remark 2.1

It is well known from variational analysis (see e.g., [5, 28]) that

• (i) ${\hat{\partial }} f(x)$ (and a fortiori $\partial f(x)$) is nonempty in a dense subset of the domain of f.

• (ii) If f is locally Lipschitz, then ${\partial }^\circ (-f)(x)=-{\partial }^\circ f(x)$ and

  $$\begin{aligned} {\hat{\partial }}f(x)\subset {\partial }f(x)\subset {\partial }^\circ f(x) = {\mathrm {conv}} {\partial } f(x). \end{aligned}$$

2.2 Semialgebraic Geometry

In this subsection, we recall some notions and results of semialgebraic geometry, which can be found in [2] or [10, Chapter 1].

Definition 2.2

• (i) A subset of ${\mathbb {R}}^n$ is called semialgebraic if it is a finite union of sets of the form

  $$\begin{aligned} \{x \in {\mathbb {R}}^n \ : \ f_i(x) = 0, i = 1, \ldots , k; f_i(x) > 0, i = k + 1, \ldots , p\} \end{aligned}$$

  where all $f_{i}$ are polynomials.

• (ii) Let $A \subset \mathbb {R}^n$ and $B \subset \mathbb {R}^p$ be semialgebraic sets. A map $f :A \rightarrow B$ is said to be semialgebraic if its graph

  $$\begin{aligned} \{(x, y) \in A \times B \ : \ y = f(x)\} \end{aligned}$$

  is a semialgebraic subset of $\mathbb {R}^n\times \mathbb {R}^p.$

The class of semialgebraic sets is closed under taking finite intersections, finite unions, and complements; furthermore, a Cartesian product of semialgebraic sets is semialgebraic. A major fact concerning the class of semialgebraic sets is given by the following seminal result of semialgebraic geometry.

Theorem 2.1

(Tarski–Seidenberg theorem) Images of semialgebraic sets under semialgebraic maps are semialgebraic.

Remark 2.2

As an immediate consequence of Tarski–Seidenberg Theorem, we get semialgebraicity of any set $\{ x \in A : \exists y \in B, (x, y) \in C \},$ provided that A, B,  and C are semialgebraic sets in the corresponding spaces. It follows that also $\{ x \in A : \forall y \in B, (x, y) \in C \}$ is a semialgebraic set as its complement is the union of the complement of A and the set $\{ x \in A : \exists y \in B, (x, y) \not \in C \}.$ Thus, if we have a finite collection of semialgebraic sets, then any set obtained from them with the help of a finite chain of quantifiers is also semialgebraic.

Theorem 2.2

(the classical Łojasiewicz inequality) Let $f :{\mathbb {R}}^n \rightarrow {\mathbb {R}}$ be a continuous semialgebraic function. For each compact subset K of $\mathbb {R}^n$ with $K \cap f^{-1}(0) \ne \emptyset ,$ there exist constants $c>0$ and $\alpha > 0$ satisfying the following inequality

$$\begin{aligned} c\, \mathrm {dist}(x, f^{-1}(0))\le & {} |f(x)|^\alpha \quad \text { for all } \quad x \in K. \end{aligned}$$

We also need another fundamental result taken from [6, Theorem 4.2], which provides an exponent estimate in the Łojasiewicz gradient inequality for polynomials.

Theorem 2.3

(the Łojasiewicz gradient inequality) Let $f :{\mathbb {R}}^n \rightarrow {\mathbb {R}}$ be a polynomial of degree $d \ge 1$ and let ${\bar{x}} \in {\mathbb {R}}^n.$ Then, there exist positive constants c and $\epsilon$ such that

$$\begin{aligned} \Vert \nabla f(x)\Vert \ge c|f(x) - f({{\bar{x}}})|^{1 - \frac{1}{{\mathcal {R}}(n, d)}} \quad \text { for all } \quad x \in {\mathbb {B}}_\epsilon ({{\bar{x}}}). \end{aligned}$$

Here and in the following, we put

$$\begin{aligned} {\mathcal {R}}(n, d) := {\left\{ \begin{array}{ll} d(3d - 3)^{n - 1} &{}\ \mathrm{if} \ d \ge 2, \\ 1 &{}\ \mathrm{if} \ d = 1. \end{array}\right. } \end{aligned}$$

(1)

3 The Łojasiewicz Gradient Inequality for the Regularized Gap Function

In this section, we establish a nonsmooth version of the Łojasiewicz gradient inequality with explicitly calculated exponents to regularized gap functions of polynomial variational inequalities.

From now on, let $F :{\mathbb {R}}^n \rightarrow {\mathbb {R}}^n$ be a polynomial map of degree at most $d \ge 1.$ Let $g_i, h_j :{\mathbb {R}}^n \rightarrow {\mathbb {R}}$ for $i=1, \ldots , r$ and $j=1, \ldots , s$ be polynomial functions of degree at most d,  and assume that the set

$$\begin{aligned} \varOmega:= & {} \{x \in {\mathbb {R}}^n \ : \ g_i(x) \le 0, \ i=1, \ldots , r, \ h_j(x) = 0, \ j=1, \ldots , s\} \end{aligned}$$

is (not necessarily convex or bounded) nonempty. Recall the variational inequality formulated in the introduction section: find a point $x \in \varOmega$ such that

$$\begin{aligned} \langle F(x), y - x \rangle \ge 0 \quad \text { for all } \quad y \in \varOmega . \end{aligned}$$

(VI)

Fix a positive real number $\rho$ and define the function $\phi :{\mathbb {R}}^n \times {\mathbb {R}}^n \rightarrow {\mathbb {R}}, (x, y) \mapsto \phi (x, y),$ by

$$\begin{aligned} \phi (x, y):= & {} \langle F(x), x - y \rangle - \frac{\rho }{2} \Vert x - y\Vert ^2. \end{aligned}$$

By definition, $\phi$ is a polynomial in 2n variables of degree at most $d + 1.$ Furthermore, for each $x \in {\mathbb {R}}^n$ we have $\lim _{\Vert y\Vert \rightarrow \infty } \phi (x, y) = - \infty ,$ and so the regularized gap function (see [9]) associated with the problem (VI):

$$\begin{aligned} \psi :{\mathbb {R}}^n \rightarrow {\mathbb {R}}, \quad x \mapsto \sup _{y \in \varOmega } \phi (x, y), \end{aligned}$$

is well defined. We will write

$$\begin{aligned} \varOmega (x) := \{y \in \varOmega \ : \ \psi (x) = \phi (x, y)\} \quad \text { for } \quad x \in {\mathbb {R}}^n. \end{aligned}$$

Lemma 3.1

The following statements hold

• (i) For each $x \in {\mathbb {R}}^n,$ $\varOmega (x)$ is a nonempty compact set.

• (ii) Let ${\bar{x}} \in {\mathbb {R}}^n.$ For any $\epsilon > 0,$ there exists a constant $R > 0$ such that

  $$\begin{aligned} \varOmega (x) \subset \{y \in {\mathbb {R}}^n : \Vert y \Vert < R \} \quad \text { for all } \quad x \in {\mathbb {B}}_\epsilon ({\bar{x}}). \end{aligned}$$

Proof

• (i) This follows immediately from the fact that for each $x \in {\mathbb {R}}^n,$

  $$\begin{aligned} \lim _{\Vert y\Vert \rightarrow \infty } \phi (x, y) = - \infty . \end{aligned}$$

• (ii) Let ${\bar{x}} \in {\mathbb {R}}^n$ and $\epsilon > 0.$ By contradiction, suppose that there exist sequences $\{x^k\} \subset {\mathbb {B}}_\epsilon ({\bar{x}})$ and $\{y^k\}$ with $y^k \in \varOmega (x^k)$ such that $\lim _{k \rightarrow \infty } \Vert y^k\Vert = +\infty .$ Passing to a subsequence if necessary, we can assume that $x^k$ converges to a point $x^* \in {\mathbb {B}}_\epsilon ({\bar{x}})$ (since ${\mathbb {B}}_\epsilon ({\bar{x}})$ is closed).

Take $y^* \in \varOmega (x^*).$ Then,

$$\begin{aligned} \phi (x^k, y^*) \le \sup _{y \in \varOmega } \phi (x^k, y) = \phi (x^k, y^k). \end{aligned}$$

It is clear that

$$\begin{aligned} \phi (x^k, y^k)&\le \Vert F(x^k)\Vert \Vert x^k -y^k \Vert - \frac{\rho }{2} \Vert x^k - y^k\Vert ^2 \\&= -\Vert x^k -y^k \Vert \left( \frac{\rho }{2} \Vert x^k - y^k\Vert - \Vert F(x^k)\Vert \right) . \end{aligned}$$

Hence,

$$\begin{aligned} \phi (x^k, y^*) \le -\Vert x^k -y^k \Vert \left( \frac{\rho }{2} \Vert x^k - y^k\Vert - \Vert F(x^k)\Vert \right) . \end{aligned}$$

Since $\lim _{k \rightarrow \infty }x^k = x^*$, $\lim _{k \rightarrow \infty } F(x^k) = F(x^*)$, and $\lim _{k \rightarrow \infty } \Vert y^k\Vert = +\infty$, taking the limit on the both sides of the above inequality, we have

$$\begin{aligned} \phi (x^*, y^*) = \lim _{k \rightarrow \infty } \phi (x^k, y^*) \le \lim _{k \rightarrow \infty } \left[ -\Vert x^k -y^k \Vert \left( \frac{\rho }{2} \Vert x^k - y^k\Vert - \Vert F(x^k)\Vert \right) \right] = - \infty . \end{aligned}$$

This is a contradiction. $\square$

By Lemma 3.1, we can write $\psi (x) = \max _{y \in \varOmega } \phi (x, y).$ Furthermore, thanks to Theorem 2.1 (see also Remark 2.2), it is not hard to check that the function $\psi$ is semialgebraic.

Lemma 3.2

The function $\psi$ is locally Lipschitz and satisfies

$$\begin{aligned} \partial ^\circ \psi (x)= & {} \mathrm {conv} \left\{ \nabla _x \phi (x, y) \ : \ y \in \varOmega (x) \right\} \quad \text {for all } \quad x \in {\mathbb {R}}^n, \end{aligned}$$

where $\nabla _x \phi$ is the derivative of $\phi$ with respect to x. In particular, $\partial ^\circ \psi (x)$ is a nonempty, compact, and convex set.

Proof

Let ${\bar{x}} \in {\mathbb {R}}^n$ and $\epsilon > 0.$ By Lemma 3.1, there exists $R > 0$ such that $\Vert y\Vert < R$ for all $y \in \varOmega (x)$ and all $x \in {\mathbb {B}}_\epsilon ({\bar{x}}).$ Hence, we can write

$$\begin{aligned} \psi (x) = \max _{y \in \varOmega , \Vert y\Vert \le R} \phi (x, y) \quad \text { for all } \quad x \in {\mathbb {B}}_\epsilon ({\bar{x}}). \end{aligned}$$

This implies easily that $\psi$ is locally Lipschitz. Finally, the formula for $\partial ^\circ \psi$ follows immediately from [4, Theorem 2.1]. $\square$

It is well known that (see, for example, [8]) if the constraint set $\varOmega$ is convex, then the regularized gap function $\psi$ is continuously differentiable. On the other hand, as shown in the next example, in the general case, the function $\psi$ cannot be differentiable.

Example 3.1

Let $n := 1, F(x) := x$ and $\varOmega := \{x \in {\mathbb {R}} \ : \ |x| \ge 1\}.$ Take $\rho := 2.$ Then,

$$\begin{aligned} \phi (x, y) = x(x - y) - (x - y)^2 = xy - y^2. \end{aligned}$$

Hence

$$\begin{aligned} \psi (x)= & {} \sup _{|y| \ge 1} (xy - y^2) \ = \ {\left\{ \begin{array}{ll} -x - 1 &{} \text { if } x \in [-2, 0], \\ x - 1 &{} \text { if } x \in [0, 2], \\ \frac{x^2}{4} &{} \text { if } |x| \ge 2. \end{array}\right. } \end{aligned}$$

Clearly, $\psi$ is not differentiable at $x = 0.$

We need the following qualification condition imposed on the constraint set $\varOmega .$

Definition 3.1

We say that the Mangasarian–Fromovitz constraint qualification (MFCQ) holds on $\varOmega$ if, for every $x \in \varOmega ,$ the gradient vectors $\nabla h_j(x), j = 1, \ldots , s,$ are linearly independent and there exists a vector $v \in \mathbb {R}^n$ such that $\langle \nabla g_i(x), v \rangle < 0, i \in \{i : g_i(x) = 0\}$ and $\langle \nabla h_j(x), v \rangle = 0, j = 1, \ldots , s.$

For each $x \in \varOmega ,$ we let

$$\begin{aligned}&N(\varOmega , x)\\&\quad := \left\{ \sum _{i=1}^r \mu _i \nabla g_i(x) + \sum _{j=1}^s\kappa _j\nabla h_j(x) \ : \ \mu _i, \kappa _j \in {\mathbb {R}}, \mu _i \ge 0, \ \mu _i g_i(x) = 0, \ i = 1, \ldots , r \right\} . \end{aligned}$$

One can check that the set $N(\varOmega , x)$ is a convex cone and if (MFCQ) holds, then $N(\varOmega , x)$ is a closed set.

We are ready to formulate a nonsmooth version of the Łojasiewicz gradient inequality with explicit exponent for the regularized gap function $\psi ,$ which plays a key role in establishing our error bounds (see Theorems 4.1 and 4.2).

Theorem 3.1

Assume that (MFCQ) holds on $\varOmega .$ For each ${\bar{x}} \in \varOmega ,$ there exist constants $c > 0$ and $\epsilon > 0$ such that for all $x \in \varOmega \cap {\mathbb {B}}_{\epsilon }({\bar{x}}),$

$$\begin{aligned} \inf \{\Vert w\Vert \ : \ w \in \partial ^\circ \psi (x) + N(\varOmega , x) \}\ge & {} c |\psi (x) - \psi ({\bar{x}})|^{1 - \alpha }, \end{aligned}$$

(2)

where $\alpha := \frac{1}{{\mathcal {R}}(n(n + 3) + r(n + 2) + s(n + 2), d + 2)}$ and the function ${\mathcal {R}}(\cdot , \cdot )$ is defined in (1).

The proof of Theorem 3.1 will be divided into several steps, which are summarized as follows:

• (a) Prove the set-valued map ${\mathbb {R}}^n \rightrightarrows {\mathbb {R}}^n, x \mapsto \varOmega (x),$ and certain Lagrange multipliers are upper Hölder continuous.

• (b) Estimate from above the Clarke subdifferential $\partial ^\circ \psi (x).$

• (c) Construct explicitly a polynomial function P based on this estimate and the definition of the cone $N(\varOmega , x).$

• (d) Prove the inequality (2) by applying Theorem 2.3 to P.

We first show the upper Hölder continuity of the set-valued map ${\mathbb {R}}^n \rightrightarrows {\mathbb {R}}^n, x \mapsto \varOmega (x).$

Lemma 3.3

Let ${\bar{x}} \in {\mathbb {R}}^n.$ For each $\epsilon > 0$, there exist constants $c > 0$ and $\alpha > 0$ such that

$$\begin{aligned} \varOmega (x) \subset \varOmega ({\bar{x}}) + c\Vert x - {\bar{x}}\Vert ^\alpha {\mathbb {B}} \quad \text { for all } \quad x \in {\mathbb {B}}_\epsilon ({\bar{x}}). \end{aligned}$$

Proof

Define the function $\varGamma :{\mathbb {R}}^n \times {\mathbb {R}}^n \rightarrow {\mathbb {R}}$ by

$$\begin{aligned} \varGamma (x, y) := [\psi (x) - \phi (x, y)]_+ + \sum _{i = 1}^r [g_i(y)]_+ + \sum _{j = 1}^s |h_j(y)|. \end{aligned}$$

It is easy to check that $\varGamma$ is locally Lipschitz and semialgebraic. Furthermore, we have

$$\begin{aligned} \varOmega (x)= & {} \{y \in \varOmega \ : \ \psi (x) - \phi (x, y) = 0\} \\= & {} \{y \in {\mathbb {R}}^n \ : \ \varGamma (x, y) = 0\}. \end{aligned}$$

Let $\epsilon > 0.$ By Lemma 3.1, there exists a constant $R > 0$ such that $\varOmega (x) \subset {\mathbb {B}}_R$ for all $x \in {\mathbb {B}}_\epsilon ({\bar{x}}).$ Since ${\mathbb {B}}_R$ is a compact set, it follows from the classical Łojasiewicz inequality (see Theorem 2.2) that there are constants $c > 0$ and $\alpha > 0$ such that

$$\begin{aligned} c\, \mathrm {dist}(y , \varOmega ({\bar{x}}))\le & {} |\varGamma ({\bar{x}}, y)|^{\alpha } \quad \text { for all } \quad y \in {\mathbb {B}}_R. \end{aligned}$$

On the other hand, since $\varGamma$ is locally Lipschitz, it is globally Lipschitz on the compact set ${\mathbb {B}}_\epsilon ({\bar{x}}) \times {\mathbb {B}}_R;$ in particular, there exists a constant $L > 0$ such that

$$\begin{aligned} |\varGamma (x, y) - \varGamma ({\bar{x}}, y)|\le & {} L \Vert x - {\bar{x}}\Vert \quad \text { for all } \quad (x, y) \in {\mathbb {B}}_\epsilon ({\bar{x}}) \times {\mathbb {B}}_R. \end{aligned}$$

Let $x \in {\mathbb {B}}_\epsilon ({\bar{x}}),$ and take an arbitrary $y \in \varOmega (x).$ Then, $y \in {\mathbb {B}}_R$ and $\varGamma (x, y) = 0.$ Therefore,

$$\begin{aligned} c\, \mathrm {dist}(y , \varOmega ({\bar{x}}))\le & {} |\varGamma ({\bar{x}}, y)|^{\alpha } \ = \ |\varGamma (x, y) - \varGamma ({\bar{x}}, y)|^{\alpha } \\\le & {} L^{\alpha } \Vert x - {\bar{x}}\Vert ^{\alpha }. \end{aligned}$$

This implies immediately the required statement. $\square$

The next three lemmas provide estimates for the Fréchet, limiting and Clarke subdifferentials of the function $\psi .$

Lemma 3.4

Assume that (MFCQ) holds on $\varOmega .$ Let ${x} \in {\mathbb {R}}^n.$ For each $y \in \varOmega (x),$ it holds that

$$\begin{aligned} {{\hat{\partial }}} (-\psi ) (x)\subset & {} \left\{ v \ : \ (v, 0) \in - \nabla \phi (x, y) + \{0\} \times N(\varOmega , y) \right\} . \end{aligned}$$

Proof

It suffices to consider the case where the set ${{\hat{\partial }}} (-\psi ) (x)$ is nonempty. Let $y \in \varOmega (x).$ Take arbitrary $v \in {{\hat{\partial }}} (-\psi ) (x)$ and $\epsilon >0.$ By the definition of the Fréchet subdifferential, there is a constant $\delta >0$ such that

$$\begin{aligned} -\psi (x') + \psi (x) - \langle v, x' - x\rangle\ge & {} - \epsilon \Vert x' - x\Vert \quad \text { for all } \quad x' \in {\mathbb {B}}_{\delta }(x). \end{aligned}$$

Then, for any $(x', y')\in {\mathbb {B}}_{\delta }(x)\times \varOmega$, we have

$$\begin{aligned} -\phi (x',y')-\langle v, x' - x\rangle + \epsilon \Vert x'-x\Vert\ge & {} -\psi (x')-\langle v, x'-x\rangle +\epsilon \Vert x'-x\Vert \\\ge & {} -\psi (x) \ = \ -\phi (x,y), \end{aligned}$$

which yields that (x, y) is a minimizer of the (locally Lipschitz) function

$$\begin{aligned} \varGamma :{\mathbb {B}}_{\delta }(x)\times \varOmega \rightarrow {\mathbb {R}}, \quad (x',y') \mapsto -\phi (x',y')-\langle v, x'-x\rangle +\epsilon \Vert x'-x\Vert . \end{aligned}$$

By Lagrange’s multipliers theorem, then

$$\begin{aligned} (0, 0)\in & {} \partial \varGamma (x, y) + \{0\}\times N(\varOmega ,y). \end{aligned}$$

Applying the sum rule (see, for example, [24, Theorem 3.36]), we get

$$\begin{aligned} \partial \varGamma (x, y)= & {} -\nabla \phi (x, y) - (v, 0)+\epsilon ({\mathbb {B}} \times \{0\}). \end{aligned}$$

Therefore,

$$\begin{aligned} (0, 0)\in & {} -\nabla \phi (x, y) - (v, 0)+\epsilon ({\mathbb {B}} \times \{0\}) + \{0\}\times N(\varOmega ,y). \end{aligned}$$

Letting $\epsilon \rightarrow 0$ yields

$$\begin{aligned} (v, 0)\in & {} -\nabla \phi (x, y) + \{0\}\times N(\varOmega , y), \end{aligned}$$

which completes the proof. $\square$

Lemma 3.5

Assume that (MFCQ) holds on $\varOmega .$ For all $x \in {\mathbb {R}}^n$ and all $v \in \partial (-\psi ) (x),$ there exists $y \in \varOmega (x)$ such that

$$\begin{aligned} v = - \nabla _x \phi (x, y) \quad \text { and } \quad \nabla _y \phi (x, y) \in N(\varOmega , y), \end{aligned}$$

where $\nabla _x \phi$ (resp., $\nabla _y \phi$) is the derivative of $\phi$ with respect to x (resp., y).

Proof

Observe that the function $-\psi$ is locally Lipschitz, and so the set $\partial (-\psi ) (x)$ is nonempty for all $x \in {\mathbb {R}}^n.$ Let $v \in \partial (-\psi )(x).$ The definition of the limiting subdifferential gives us the existence of sequences $\{x^k\}_{k \in {\mathbb {N}}} \subset {\mathbb {R}}^n$ and $\{v^k\}_{k \in {\mathbb {N}}} \subset {\hat{\partial }} (-\psi )(x^k)$ with

$$\begin{aligned} \lim _{k \rightarrow \infty } x^k= & {} x \quad \text { and } \quad \lim _{k \rightarrow \infty }v^k \ = \ v. \end{aligned}$$

For each integer number k,  take any $y^k \in \varOmega (x^k).$ By Lemmas 3.1 and 3.3 (and by choosing a subsequence, if necessary), we may assume, without loss of generality, that there exists $y \in \varOmega (x)$ such that $y = \lim _{k \rightarrow \infty } y^k.$ On the other hand, by Lemma 3.4, we have

$$\begin{aligned} (v^k, 0) \in -\nabla \phi (x^k, y^k) + \{0\} \times N(\varOmega , y^k). \end{aligned}$$

Letting k tend to infinity, we get

$$\begin{aligned} (v, 0) \in -\nabla \phi (x, y) + \{ 0 \} \times N(\varOmega , y), \end{aligned}$$

and so the desired conclusion follows. $\square$

Lemma 3.6

Assume that (MFCQ) holds on $\varOmega .$ For all $x \in {\mathbb {R}}^n,$ we have

$$\begin{aligned} \partial ^\circ \psi (x)\subset & {} \mathrm {conv}(\cup _{y \in \varOmega (x)} \{ v : (v, 0) \in \nabla \phi (x, y) - \{ 0 \} \times N(\varOmega , y) \} ). \end{aligned}$$

Proof

Indeed, it follows from the definitions that

$$\begin{aligned} \partial ^\circ \psi (x) \ = \ - \partial ^\circ (-\psi ) (x) \ = \ - \mathrm {conv}(\partial (-\psi ) (x)). \end{aligned}$$

This combined with Lemma 3.5 leads to the desired assertion. $\square$

Remark 3.1

It is well known that if $\varOmega$ is convex then for each x, $\varOmega (x)$ is singleton, $-\nabla _x\phi (x, y)$ ($y \in \varOmega (x)$) depends only on x and $\psi$ would be differentiable (see, for example, [8]). However, when the constraint set $\varOmega$ is not convex, $\varOmega (x)$ may not be singleton, $-\nabla _x\phi (x, y)$ may depend on the choice $y \in \varOmega (x)$, and $\psi$ may not be differentiable. For instance, let us consider the following polynomial variational inequality VI($F, \varOmega$) given by:

$F(x) = x^2$, $\varOmega = [-4, -2] \cup [0, 1] \cup [2, +\infty )$. Take $\rho = \frac{1}{2}$.

$$\begin{aligned} \begin{aligned} \phi (x,y)&= \ x^2(x-y) - \frac{1}{4}(y-x)^2\\&= -\frac{1}{4}y^2 + \left( \frac{1}{2}x-x^2\right) y +x^3 - \frac{1}{4}x^2. \end{aligned} \end{aligned}$$

It is clear that $\nabla _x\phi (x, y) = (\frac{1}{2}-2x)y + 3x^2 - \frac{1}{2}x$.

By direct computation, we have

$$\begin{aligned} \psi (x) = {\left\{ \begin{array}{ll} x^3 +\frac{15}{4}x^2 -2x - 4&{} \text { if } x \in \left( -\infty , \frac{1-\sqrt{33}}{4}\right) \cup \left( \frac{1+\sqrt{33}}{4}, +\infty \right) \\ x^4 &{} \text { if } x \in \left[ \frac{1-\sqrt{33}}{4}, \frac{1-\sqrt{17}}{4}\right] \cup \left[ 0, \frac{1}{2}\right] \cup \left[ \frac{1+\sqrt{17}}{4}, \frac{1+\sqrt{33}}{4}\right] \\ x^3+\frac{7}{4}x^2 - x - 1 &{} \text { if } x \in \left( \frac{1-\sqrt{17}}{4}, -\frac{1}{2}\right) \cup \left( 1, \frac{1+\sqrt{17}}{4}\right) \\ x^3 - \frac{1}{4}x^2 &{} \text { if } x \in \left( -\frac{1}{2}, 0\right) \cup (\frac{1}{2}, 1]. \end{array}\right. } \end{aligned}$$

For $x = 1$, we have

$$\begin{aligned} \psi (1) = \sup _{y \in \varOmega }\phi (1, y) = \sup _{y \in \varOmega }\left\{ -\frac{1}{4}y^2 - \frac{1}{2}y + \frac{3}{4}\right\} = \frac{3}{4}, \end{aligned}$$

$\varOmega (1) = \{ -2, 0\}$, and $\nabla _x\phi (1, -2) = \frac{11}{2}$, $\nabla _x\phi (1, 0) = \frac{5}{2}.$

Therefore, $\nabla _x\phi (1, -2) \ne \nabla _x\phi (1, 0)$; it means that $\nabla _x\phi (x, y)$ depend on $y \in \varOmega (x).$ It is clear that $\psi$ is not differentiable.

The following lemma is simple but useful.

Lemma 3.7

Assume that (MFCQ) holds on $\varOmega .$ Let $\{x^k\}_{k \in {\mathbb {N}}} \subset \varOmega$ and $\{v^k\}_{k \in {\mathbb {N}}} \subset N(\varOmega , x^k)$ be two bounded sequences such that

$$\begin{aligned} v^k= & {} \sum _{i=1}^r \mu _i^k \nabla g_i(x^k) + \sum _{j=1}^s \kappa _j^k \nabla h_j(x^k), \\ 0= & {} \mu _i^k g_i(x^k), \ \mu _i^k \ge 0, \ \text { for } \ i = 1, \ldots , r, \end{aligned}$$

for some $\mu ^k := (\mu _1^k, \ldots , \mu _r^k) \in {\mathbb {R}}^r$ and $\kappa ^k := (\kappa _1^k, \ldots , \kappa _s^k) \in {\mathbb {R}}^s.$ Then, the sequences $\{\mu ^k\}_{k \in {\mathbb {N}}}$ and $\{\kappa ^k\}_{k \in {\mathbb {N}}}$ are bounded.

Proof

Arguing by contradiction, assume that

$$\begin{aligned} \lim _{k \rightarrow \infty } \Vert (\mu ^k, \kappa ^k)\Vert= & {} +\infty . \end{aligned}$$

Passing to a subsequence if necessary we may assume that the following limits exist:

$$\begin{aligned} ({\bar{\mu }}, {\bar{\kappa }}):= & {} \lim _{k \rightarrow \infty } \frac{(\mu ^k, \kappa ^k)}{\Vert (\mu ^k, \kappa ^k)\Vert } \in {\mathbb {R}}^r \times {\mathbb {R}}^s,\\ {\bar{x}}:= & {} \lim _{k \rightarrow \infty } x^k \in \varOmega . \end{aligned}$$

Then, we have $({\bar{\mu }}, {\bar{\kappa }}) \ne (0, 0)$ and

$$\begin{aligned} 0= & {} \sum _{i=1}^r {\bar{\mu }}_i \nabla g_i({\bar{x}}) + \sum _{j = 1}^s {\bar{\kappa }}_j \nabla h_j({\bar{x}}), \\ 0= & {} {\bar{\mu }}_i g_i({\bar{x}}), \ {\bar{\mu }}_i \ge 0, \ \text { for } \ i = 1, \ldots , r. \end{aligned}$$

Since (MFCQ) holds at ${\bar{x}} \in \varOmega ,$ the gradient vectors $\nabla h_j({\bar{x}}), j = 1, \ldots , s,$ are linearly independent and there exists a vector $v \in \mathbb {R}^n$ such that $\langle \nabla g_i({\bar{x}}), v \rangle < 0, i \in \{i : g_i({\bar{x}}) = 0\}$ and $\langle \nabla h_j({\bar{x}}), v \rangle = 0, j = 1, \ldots , s.$ Therefore,

$$\begin{aligned} 0= & {} \sum _{i=1}^r {\bar{\mu }}_i \langle \nabla g_i({\bar{x}}), v \rangle + \sum _{j = 1}^s {\bar{\kappa }}_j \langle \nabla h_j({\bar{x}}), v \rangle \\= & {} \sum _{i=1}^r {\bar{\mu }}_i \langle \nabla g_i({\bar{x}}), v \rangle . \end{aligned}$$

Then, we deduce easily that $({\bar{\mu }}, {\bar{\kappa }}) = (0, 0),$ which is a contradiction. $\square$

Clearly, we can write

$$\begin{aligned}&N(\varOmega , x)\\&\quad = \left\{ \sum _{i=1}^r \mu _i^ 2 \nabla g_i(x) + \sum _{j=1}^s\kappa _j\nabla h_j(x) \ : \ \mu \in {\mathbb {R}}^r, \ \kappa \in {\mathbb {R}}^s, \ \mu _i g_i(x) = 0, \ i = 1, \ldots , r \right\} . \end{aligned}$$

Here, $\mu := (\mu _1, \ldots , \mu _r) \in {\mathbb {R}}^r$ and $\kappa := (\kappa _1, \ldots , \kappa _s) \in {\mathbb {R}}^s.$ For simplicity of notation, we put

$$\begin{aligned} a := (y^1, \ldots , y^{n + 1}, \mu ^1, \ldots , \mu ^{n + 1}, \kappa ^1, \ldots , \kappa ^{n + 1}, \lambda ) \in {\mathbb {R}}^{n(n + 1)} \times {\mathbb {R}}^{r(n + 1)} \times {\mathbb {R}}^{s(n + 1)} \times {\mathbb {R}}^{n}. \end{aligned}$$

For each $x \in {\mathbb {R}}^n,$ let

$$\begin{aligned} A(x):= & {} \Big \{ a : \nabla _y \phi (x, y^k) - \sum _{i = 1}^{r} [\mu ^k_i]^2 \nabla g_i(y^k) - \sum _{j = 1}^{s} \kappa ^k_j \nabla h_j(y^k) = 0, \ k = 1, \ldots , n + 1, \\&\quad \mu ^k_i g_i(y^k) = 0, \ k = 1, \ldots , n + 1, i = 1, \ldots , r, \ y^1, \ldots , y^{n + 1} \in \varOmega (x), \ \lambda \in {\mathbf {P}} \Big \}, \end{aligned}$$

where we put

$$\begin{aligned} {\mathbf {P}}:= & {} \left\{ \lambda := (\lambda _1, \ldots , \lambda _{n}) \in {\mathbb {R}}^{n} : \lambda _k \ge 0 \text { and } \sum _{k = 1}^n \lambda _k \le 1\right\} . \end{aligned}$$

The next two lemmas show the upper Hölder continuity of Lagrange multipliers.

Lemma 3.8

Let (MFCQ) hold on $\varOmega .$ The following statements hold:

• (i) For each $x \in {\mathbb {R}}^n,$ A(x) is a nonempty compact set.

• (ii) Let ${\bar{x}} \in {\mathbb {R}}^n.$ For each $\epsilon > 0$ there exist constants $c > 0$ and $\alpha > 0$ such that

  $$\begin{aligned} A(x) \subset A({\bar{x}}) + c\Vert x - {\bar{x}}\Vert ^\alpha {\mathbb {B}} \quad \text { for all } \quad x \in {\mathbb {B}}_\epsilon ({\bar{x}}). \end{aligned}$$

Proof

• (i) The set A(x) is obviously closed and it is bounded because of Lemma 3.7. Furthermore, by Lemma 3.6, it is not hard to see that A(x) is nonempty.

• (ii) Take any $\epsilon > 0.$ Since (MFCQ) holds on $\varOmega ,$ we can find a constant $R > 0$ such that $A(x) \subset {\mathbb {B}}_R$ for all $x \in {\mathbb {B}}_\epsilon ({\bar{x}}).$

On the other hand, by definition, for each $x \in {\mathbb {R}}^n$ we have $y \in \varOmega (x)$ if and only if $y \in \varOmega$ and $\psi (x) = \phi (x, y),$ or equivalently

$$\begin{aligned} g_i(y) \le 0, \ i=1, \ldots , r, \ h_j(y) = 0, \ j=1, \ldots , s, \text { and } \psi (x) = \phi (x, y). \end{aligned}$$

Therefore, we can write

$$\begin{aligned} A(x)= & {} \{a : G_i(x, a) \le 0, i = 1, \ldots , {\tilde{r}}, \ \text { and } \ H_j(x, a) = 0, j = 1, \ldots , {\tilde{s}} \} \end{aligned}$$

for some locally Lipschitz and semialgebraic functions $G_i$ and $H_j.$ Let

$$\begin{aligned} \varGamma (x, a):= & {} \sum _{i = 1}^{{\tilde{r}}} [G_i(x, a)]_+ + \sum _{j = 1}^{{\tilde{s}}} |H_j(x, a)|. \end{aligned}$$

Then, $\varGamma$ is a locally Lipschitz and semialgebraic function and $A(x) = \{a : \varGamma (x, a) = 0\}.$ Since ${\mathbb {B}}_R$ is a compact set, it follows from the classical Łojasiewicz inequality (see Theorem 2.2) that there are constants $c > 0$ and $\alpha > 0$ such that

$$\begin{aligned} c\, \mathrm {dist}(a , A({\bar{x}}))\le & {} |\varGamma ({\bar{x}}, a)|^{\alpha } \quad \text { for all } \quad a \in {\mathbb {B}}_R. \end{aligned}$$

On the other hand, since $\varGamma$ is locally Lipschitz, it is globally Lipschitz on the compact set ${\mathbb {B}}_\epsilon ({\bar{x}}) \times {\mathbb {B}}_R;$ in particular, there exists a constant $L > 0$ such that

$$\begin{aligned} |\varGamma (x, a) - \varGamma ({\bar{x}}, a)|\le & {} L \Vert x - {\bar{x}}\Vert \quad \text { for all } \quad (x, a) \in {\mathbb {B}}_\epsilon ({\bar{x}}) \times {\mathbb {B}}_R. \end{aligned}$$

Let $x \in {\mathbb {B}}_\epsilon ({\bar{x}})$ and take an arbitrary $a \in A(x).$ Then $A(x) \subset {\mathbb {B}}_R$ and $\varGamma (x, a) = 0.$ Therefore,

$$\begin{aligned} c\, \mathrm {dist}(a , A({\bar{x}}))\le & {} |\varGamma ({\bar{x}}, a)|^{\alpha } \ = \ |\varGamma (x, a) - \varGamma ({\bar{x}}, a)|^{\alpha } \\\le & {} L^{\alpha } \Vert x - {\bar{x}}\Vert ^{\alpha }. \end{aligned}$$

This implies immediately the required statement. $\square$

For simplicity of notation, we write $b := (\mu ^0_1, \ldots , \mu ^0_r, \kappa ^0_1, \ldots , \kappa ^0_s) \in {\mathbb {R}}^r \times {\mathbb {R}}^s.$ For each $x \in \varOmega$ and $R > 0,$ let

$$\begin{aligned} B_R(x):= & {} \{b : \text {there exists } v \in \partial ^\circ \psi (x) \text { such that } \\&v + \sum _{i = 1}^{r} [\mu ^0_i]^2 \nabla g_i(x) + \sum _{j = 1}^{s} \kappa ^0_j \nabla h_j(x) \in {\mathbb {B}}_R, \\&\mu ^0_i g_i(x) = 0, \ i = 1, \ldots , r\}. \end{aligned}$$

Lemma 3.9

Let (MFCQ) hold on $\varOmega$ and let ${\bar{x}} \in \varOmega .$ For each $\epsilon > 0$, there exist constants $R> 0, c > 0$ and $\alpha > 0$ such that for all $x \in \varOmega \cap {\mathbb {B}}_\epsilon ({\bar{x}}),$ the set $B_R(x)$ is nonempty compact and satisfies

$$\begin{aligned} B_R(x) \subset B_R({\bar{x}}) + c\Vert x - {\bar{x}}\Vert ^\alpha {\mathbb {B}}. \end{aligned}$$

Proof

By Lemmas 3.1 and 3.2 , there exists a constant $R > 0$ such that for all $x \in {\mathbb {B}}_{\epsilon }({\bar{x}}),$ we have $\partial ^\circ \psi (x)$ is a nonempty compact subset of ${\mathbb {B}}_R;$ in particular, $0 \in B_R(x).$ Furthermore, in light of Lemma 3.7, it is easy to see that the set $B_R(x)$ is compact.

On the other hand, it follows from Lemma 3.2 and the Carathéodory theorem that for each $x \in {\mathbb {R}}^n$ we have $v \in \partial ^\circ \psi (x)$ if and only if there are $(\lambda _1, \ldots , \lambda _n) \in {\mathbf {P}}$ and $y^1, \ldots , y^{n + 1} \in \varOmega (x),$ which depend on x,  such that

$$\begin{aligned} v= & {} \sum _{k = 1}^{n} \lambda _k \nabla _x \phi (x, y^k) + \left( 1 - \sum _{k = 1}^{n} \lambda _k\right) \nabla _x \phi (x, y^{n + 1}). \end{aligned}$$

Recall that $y \in \varOmega (x)$ if and only if $y \in \varOmega$ and $\psi (x) = \phi (x, y),$ or equivalently

$$\begin{aligned} g_i(y) \le 0, \ i=1, \ldots , r, \ h_j(y) = 0, \ j=1, \ldots , s, \text { and } \psi (x) = \phi (x, y). \end{aligned}$$

Therefore, by definition, we can write

$$\begin{aligned} B_R(x)= & {} \{b \ : \ \exists z \in {\mathbb {R}}^m, G_i(x, z, b) \le 0, i = 1, \ldots , {\tilde{r}}, \ \text { and } \ H_j(x, z, b)\\= & {} 0, j = 1, \ldots , {\tilde{s}} \} \end{aligned}$$

for some locally Lipschitz and semialgebraic functions $G_i$ and $H_j.$ In particular, $B_R(x)$ is the image of the set

$$\begin{aligned} C(x)= & {} \{(z, b) \ : \ G_i(x, z, b) \le 0, i = 1, \ldots , {\tilde{r}}, \ \text { and } \ H_j(x, z, b) = 0, j = 1, \ldots , {\tilde{s}} \} \end{aligned}$$

under the map ${\mathbb {R}}^m \times {\mathbb {R}}^{r + s} \rightarrow {\mathbb {R}}^{r + s}, (z, b) \mapsto b.$ As in the proof of Lemma 3.8(ii), we can find constants $c > 0$ and $\alpha > 0$ such that

$$\begin{aligned} C(x) \subset C({\bar{x}}) + c\Vert x - {\bar{x}}\Vert ^\alpha {\mathbb {B}} \quad \text { for all } \quad x \in {\mathbb {B}}_\epsilon ({\bar{x}}). \end{aligned}$$

Take any $b \in B_R(x).$ Then, there exists $z \in {\mathbb {R}}^m$ such that $(z, b) \in C(x).$ Therefore,

$$\begin{aligned} \mathrm {dist}(b, B_R({\bar{x}}))\le & {} \mathrm {dist}((z, b), C({\bar{x}})) \ \le \ c\Vert x - {\bar{x}}\Vert ^\alpha , \end{aligned}$$

from which the desired conclusion follows. $\square$

We can now finish the proof of Theorem 3.1.

Proof of Theorem 3.1

Let ${\bar{x}} \in \varOmega$ and fix a positive real number $\epsilon _1.$ By Lemmas 3.1, 3.2, and 3.9 , there exists a constant $R > 0$ such that for all $x \in {\mathbb {B}}_{\epsilon _1}({\bar{x}}),$ we have $\partial ^\circ \psi (x) \subset {\mathbb {B}}_R$ and $B_R(x)$ is nonempty compact. In particular, it holds that

$$\begin{aligned} \inf \{\Vert w\Vert \ : \ w \in \partial ^\circ \psi (x) + N(\varOmega , x) \}= & {} \inf \{\Vert w\Vert \ : \ w \in \left( \partial ^\circ \psi (x) + N(\varOmega , x)\right) \cap {\mathbb {B}}_R \}. \end{aligned}$$

Therefore, in order to prove the inequality (2), it suffices to consider vectors $w \in \partial ^\circ \psi (x) + N(\varOmega , x)$ with $\Vert w\Vert \le R.$

Recall that we write

$$\begin{aligned} \lambda:= & {} (\lambda _1, \ldots , \lambda _n) \in {\mathbb {R}}^n,\\ a:= & {} (y^1, \ldots , y^{n + 1}, \mu ^1, \ldots , \mu ^{n + 1}, \kappa ^1, \ldots , \kappa ^{n + 1}, \lambda ) \in {\mathbb {R}}^{n(n + 1)} \times {\mathbb {R}}^{r(n + 1)} \times {\mathbb {R}}^{s(n + 1)} \times {\mathbb {R}}^{n}, \\ b:= & {} (\mu ^0, \kappa ^0) \in {\mathbb {R}}^{r} \times {\mathbb {R}}^{s}. \end{aligned}$$

Define the function P by

$$\begin{aligned} P(x, a, b):= & {} \sum _{k = 1}^{n} \lambda _k \left[ \phi (x, y^k) - \sum _{i = 1}^{r} [\mu ^k_i]^2 g_i(y^k) - \sum _{j = 1}^{s} \kappa ^k_j h_j(y^k) \right] \\&+ \ \left( 1 - \sum _{k = 1}^{n} \lambda _k\right) \left[ \phi (x, y^{n + 1}) - \sum _{i = 1}^{r} [\mu ^{n + 1}_i]^2 g_i(y^{n + 1}) - \sum _{j = 1}^{s} \kappa ^{n + 1}_j h_j(y^{n + 1}) \right] \\&+ \ \sum _{i = 1}^{r} [\mu ^0_i]^2 g_i(x) + \sum _{j = 1}^{s} \kappa ^0_j h_j(x). \end{aligned}$$

Then P is a polynomial in $n(n + 3) + r(n + 2) + s(n + 2)$ variables of degree at most $d + 2.$ By Theorem 2.3, for each $({\bar{a}}, {\bar{b}}),$ there exist constants $c({\bar{a}}, {\bar{b}}) > 0$ and $\epsilon ({\bar{a}}, {\bar{b}}) > 0$ such that for all $\Vert (x, a, b) - ({\bar{x}}, {\bar{a}}, {\bar{b}})\Vert \le \epsilon ({\bar{a}}, {\bar{b}}),$

$$\begin{aligned} \Vert \nabla P(x, a, b) \Vert\ge & {} c({\bar{a}}, {\bar{b}}) |P(x, a, b) - P({\bar{x}}, {\bar{a}}, {\bar{b}})|^{1 - \alpha }, \end{aligned}$$

where $\alpha := \frac{1}{{\mathcal {R}}(n(n + 3) + r(n + 2) + s(n + 2), d + 2)}.$

We have

$$\begin{aligned} A({\bar{x}}) \times B_R({\bar{x}})\subset & {} \bigcup \left\{ (a, b) : \Vert (a, b) - ({\bar{a}}, {\bar{b}})\Vert < \frac{\epsilon ({\bar{a}}, {\bar{b}})}{4} \right\} , \end{aligned}$$

where the union is taken over all $({\bar{a}}, {\bar{b}})$ in $A({\bar{x}}) \times B_R({\bar{x}}).$ By Lemmas 3.8 and 3.9 , $A({\bar{x}}) \times B_R({\bar{x}})$ is nonempty compact, and so there exist $({\bar{a}}^l, {\bar{b}}^l) \in A({\bar{x}}) \times B_R({\bar{x}})$ for $l = 1, \ldots , N,$ such that

$$\begin{aligned} A({\bar{x}}) \times B_R({\bar{x}})\subset & {} \bigcup _{l = 1}^N \left\{ (a, b) : \Vert (a, b) - ({\bar{a}}^l, {\bar{b}}^l)\Vert < \frac{\epsilon ({\bar{a}}^l, {\bar{b}}^l)}{4} \right\} . \end{aligned}$$

Let $\epsilon _2 := \min _{l = 1, \ldots , N} \epsilon ({\bar{a}}^l, {\bar{b}}^l) > 0$ and $c := \min _{l = 1, \ldots , N} c({\bar{a}}^l, {\bar{b}}^l) > 0.$ By Lemmas 3.8 and 3.9 again, there exists a positive constant $\epsilon \le \min \{\epsilon _1, \frac{\epsilon _2}{2}\}$ such that for all $x \in \varOmega \cap {\mathbb {B}}_\epsilon ({\bar{x}}),$

$$\begin{aligned} \mathrm {dist}((a, b), A({\bar{x}}) \times B_R({\bar{x}}))\le & {} \frac{\epsilon _2}{4} \quad \text { for all } \quad (a, b) \in A(x) \times B_R(x). \end{aligned}$$

Take any $x \in \varOmega \cap {\mathbb {B}}_\epsilon ({\bar{x}})$ and any $w \in \partial ^\circ \psi (x) + N(\varOmega , x)$ with $\Vert w\Vert \le R.$ It follows from Lemma 3.6 and the Carathéodory theorem that there exist $v \in \partial ^\circ \psi (x)$ and $(a, b) \in A(x) \times B_R(x)$ satisfying the following conditions

$$\begin{aligned} w= & {} v + \sum _{i = 1}^{r} [\mu ^0_i]^2 \nabla g_i(x) + \sum _{j = 1}^{s} \kappa ^0_j \nabla h_j(x), \\ v= & {} \sum _{k = 1}^{n} \lambda _k \nabla _x \phi (x, y^k) + \left( 1 - \sum _{k = 1}^{n} \lambda _k\right) \nabla _x \phi (x, y^{n + 1}) \\ 0= & {} \nabla _y \phi (x, y^k) - \sum _{i = 1}^{r} [\mu ^k_i]^2 \nabla g_i(y^k) - \sum _{j = 1}^{s} \kappa ^k_j \nabla h_j(y^k), \ k = 1, \ldots , n + 1, \\ 0= & {} \mu ^0_i g_i(x), \ i = 1, \ldots , r, \\ 0= & {} \mu ^k_i g_i(y^k), \ k = 1, \ldots , n + 1, \ i = 1, \ldots , r, \\&y^1, \ldots , y^{n + 1} \in \varOmega (x), \quad \lambda \in {\mathbf {P}}. \end{aligned}$$

A direct computation shows that

$$\begin{aligned} P(x, a, b)= & {} \psi (x) \quad \text { and } \quad \nabla P(x, a, b) \ = \ (w, 0, 0). \end{aligned}$$

On the other hand, since the set $A({\bar{x}}) \times B_R({\bar{x}})$ is nonempty compact, there is $({\bar{a}}, {\bar{b}}) \in A({\bar{x}}) \times B_R({\bar{x}})$ such that

$$\begin{aligned} \Vert (a, b) - ({\bar{a}}, {\bar{b}})\Vert= & {} \mathrm {dist}((a, b), A({\bar{x}}) \times B_R({\bar{x}})). \end{aligned}$$

There exists an index $l \in \{1, \ldots , N\}$ such that

$$\begin{aligned} \Vert ({\bar{a}}, {\bar{b}}) - ({\bar{a}}^l, {\bar{b}}^l)\Vert< & {} \frac{\epsilon ({\bar{a}}^l, {\bar{b}}^l)}{4}. \end{aligned}$$

We have

$$\begin{aligned} \Vert ({a}, {b}) - ({\bar{a}}^l, {\bar{b}}^l)\Vert\le & {} \Vert ({a}, {b}) - ({\bar{a}}, {\bar{b}})\Vert + \Vert ({\bar{a}}, {\bar{b}}) - ({\bar{a}}^l, {\bar{b}}^l)\Vert \\= & {} \mathrm {dist}((a, b), A({\bar{x}}) \times B_R({\bar{x}})) + \Vert ({\bar{a}}, {\bar{b}}) - ({\bar{a}}^l, {\bar{b}}^l)\Vert \\\le & {} \frac{\epsilon _2}{4} + \frac{\epsilon ({\bar{a}}^l, {\bar{b}}^l)}{4} \ \le \ \frac{\epsilon ({\bar{a}}^l, {\bar{b}}^l)}{2}. \end{aligned}$$

This implies that

$$\begin{aligned} \Vert (x, {a}, {b}) - ({\bar{x}}, {\bar{a}}^l, {\bar{b}}^l)\Vert\le & {} \Vert x - {\bar{x}}\Vert + \Vert (a, b) - {\bar{a}}^l, {\bar{b}}^l)\Vert \\\le & {} \epsilon + \frac{\epsilon ({\bar{a}}^l, {\bar{b}}^l)}{2} \ \le \ \frac{\epsilon _2}{2} + \frac{\epsilon ({\bar{a}}^l, {\bar{b}}^l)}{2} \ \le \ \epsilon ({\bar{a}}^l, {\bar{b}}^l). \end{aligned}$$

Note that $P({\bar{x}}, {\bar{a}}^l, {\bar{b}}^l) = \psi ({\bar{x}}).$ Therefore,

$$\begin{aligned} \Vert w\Vert \ = \ \Vert \nabla P(x, a, b) \Vert\ge & {} c({\bar{a}}^l, {\bar{b}}^l) |P(x, a, b) - P({\bar{x}}, {\bar{a}}^l, {\bar{b}}^l)|^{1 - \alpha } \\= & {} c({\bar{a}}^l, {\bar{b}}^l) |\psi (x) - \psi ({\bar{x}})|^{1 - \alpha } \\\ge & {} c |\psi (x) - \psi ({\bar{x}})|^{1 - \alpha }, \end{aligned}$$

which completes the proof. $\square$

Remark 3.2

When the constraint set $\varOmega$ is convex, a close look at the proof of Theorem 3.1 reveals that the exponent $\alpha$ in (2) can sharpen to $\alpha = \frac{1}{{\mathcal {R}}(2n + 2r + 2s, d + 2)}.$ This is due to the fact that in this case $\varOmega (x)$ is a singleton for all $x \in {\mathbb {R}}^n,$ and so we can reduce variables in the set A(x) and the polynomial P. The details are left to the reader.

4 Error Bounds for the Regularized Gap Function

In this section, we establish an error bound result for the regularized gap function $\psi$ associated with the variational inequality (VI).

Note by definition that $\psi$ is nonnegative on $\varOmega .$ Assume that the set

$$\begin{aligned} \{x \in \varOmega \ : \ \psi (x) = 0\} \end{aligned}$$

is nonempty.

Theorem 4.1

Let (MFCQ) hold on $\varOmega .$ For any compact set $K \subset \mathbb {R}^n,$ there exists a constant $c > 0$ satisfying the following error bound

$$\begin{aligned} c\, \mathrm {dist}(x, [x \in \varOmega : \psi (x) = 0])\le & {} [\psi (x)]^{\alpha } \quad \text { for all } \quad x \in \varOmega \cap K, \end{aligned}$$

where $\alpha := \frac{1}{{\mathcal {R}}(n(n + 3) + r(n + 2) + s(n + 2), d + 2)}$ and the function ${\mathcal {R}}(\cdot , \cdot )$ is defined in (1).

Proof

(cf. [27, Theorem 1.1]). Define for notational convenience ${\mathcal {Z}} := \{x \in \varOmega \ : \ \psi (x) = 0\}.$ By using standard compactness arguments, it suffices to show, for each ${\bar{x}} \in \varOmega ,$ that there exist constants $c({\bar{x}}) > 0$ and $\epsilon ({\bar{x}}) > 0$ such that

$$\begin{aligned} c({\bar{x}})\, \mathrm {dist}(x, {\mathcal {Z}})\le & {} [\psi (x)]^{\alpha } \quad \text { whenever } \quad x \in \varOmega \cap {\mathbb {B}}_{\epsilon ({\bar{x}})}({{\bar{x}}}). \end{aligned}$$

Indeed, the statement is rather straightforward provided that ${\bar{x}} \not \in {\mathcal {Z}}$ (because of $\psi ({\bar{x}}) > 0$ and the function $\psi$ is continuous). Let us consider the case ${\bar{x}} \in {\mathcal {Z}},$ i.e., $\psi ({\bar{x}}) = 0.$ In view of Theorem 3.1, there are constants $c > 0$ and $\epsilon > 0$ such that

$$\begin{aligned} \inf \{\Vert w\Vert : w \in \partial ^\circ \psi (x) + N(\varOmega , x) \}\ge & {} c |\psi (x)|^{1 - \alpha } \quad \text { for } \quad x \in \varOmega \cap {\mathbb {B}}_{\epsilon }({{\bar{x}}}). \end{aligned}$$

We will show that

$$\begin{aligned} \frac{c \alpha }{4}\, \mathrm {dist}(x, {\mathcal {Z}})\le & {} [\psi (x)]^{\alpha } \quad \text { for } \quad x \in \varOmega \cap {\mathbb {B}}_{\frac{\epsilon }{2}}({{\bar{x}}}). \end{aligned}$$

Arguing by contradiction, suppose that there exists ${\bar{y}} \in \varOmega \cap {\mathbb {B}}_{\frac{\epsilon }{2}}({{\bar{x}}})$ such that

$$\begin{aligned} \frac{c \alpha }{4} \, \mathrm {dist}({\bar{y}}, {\mathcal {Z}})> & {} [\psi ({\bar{y}})]^{\alpha }. \end{aligned}$$

Then, ${\bar{y}} \not \in {\mathcal {Z}}$ and so $\psi ({\bar{y}}) > 0.$ Let us consider the continuous (semialgebraic) function

$$\begin{aligned} \theta :\varOmega \rightarrow {\mathbb {R}}, \quad x \mapsto [\psi (x)]^{\alpha }. \end{aligned}$$

Clearly, the function $\theta$ is locally Lipschitz on $\{x \in \varOmega \ : \ \psi (x) > 0\}.$ Furthermore, we have

$$\begin{aligned} \inf _{x \in \varOmega \cap {\mathbb {B}}_{{\epsilon }}({{\bar{x}}})} \theta (x)= & {} 0< \theta ({\bar{y}}) = [\psi ({\bar{y}})]^{\alpha } < \frac{c \alpha }{4} \, \mathrm {dist}({\bar{y}}, {\mathcal {Z}}). \end{aligned}$$

Thanks to the Ekeland variational principle [7], there exists a point ${\bar{z}} \in \varOmega \cap {\mathbb {B}}_{\epsilon }({{\bar{x}}})$ such that

$$\begin{aligned} \theta ({\bar{z}})\le & {} \theta ({\bar{y}}), \quad \Vert {\bar{y}} - {\bar{z}}\Vert \ < \ \frac{\mathrm {dist}({\bar{y}}, {\mathcal {Z}})}{2}, \end{aligned}$$

and ${\bar{z}}$ is a minimizer of the function

$$\begin{aligned} \varOmega \cap {\mathbb {B}}_{{\epsilon }}({{\bar{x}}}) \rightarrow {\mathbb {R}}, \quad x \mapsto \theta (x) + \frac{c \alpha }{2} \Vert x - {\bar{z}}\Vert . \end{aligned}$$

By construction, then

$$\begin{aligned} \mathrm {dist}({\bar{z}}, {\mathcal {Z}})\ge & {} \mathrm {dist}({\bar{y}}, {\mathcal {Z}}) - \Vert {\bar{y}} - {\bar{z}}\Vert \> \ \frac{\mathrm {dist}({\bar{y}}, {\mathcal {Z}})}{2} \ > \ 0, \end{aligned}$$

which implies that ${\bar{z}} \not \in {\mathcal {Z}}$ and $\psi ({\bar{z}})> 0.$ Furthermore, we have

$$\begin{aligned} \Vert {\bar{z}} - {\bar{x}}\Vert\le & {} \Vert {\bar{y}} - {\bar{z}}\Vert + \Vert {\bar{y}} - {\bar{x}}\Vert \\< & {} \frac{\mathrm {dist}({\bar{y}}, {\mathcal {Z}})}{2} + \Vert {\bar{y}} - {\bar{x}}\Vert \\\le & {} \frac{\Vert {\bar{y}} - {\bar{x}}\Vert }{2} + \Vert {\bar{y}} - {\bar{x}}\Vert \\\le & {} \frac{\epsilon }{4} + \frac{\epsilon }{2} < \epsilon , \end{aligned}$$

and so ${\bar{z}}$ is an interior point of the closed ball ${\mathbb {B}}_{\epsilon }({\bar{x}}).$

We therefore deduce from Lagrange’s multipliers theorem that

$$\begin{aligned} 0\in & {} \partial \theta ({\bar{z}}) + \frac{c \alpha }{2}{\mathbb {B}} + N(\varOmega , {\bar{z}}). \end{aligned}$$

Note that

$$\begin{aligned} \partial \theta ({\bar{z}})= & {} \alpha [\psi ({\bar{z}})]^{\alpha - 1} \partial \psi ({\bar{z}}). \end{aligned}$$

Hence,

$$\begin{aligned} 0\in & {} \partial \psi ({\bar{z}}) + \frac{c}{2} [\psi ({\bar{z}})]^{1 - \alpha } {\mathbb {B}} + N(\varOmega , {\bar{z}}) \\\subset & {} \partial ^\circ \psi ({\bar{z}}) + \frac{c}{2} [\psi ({\bar{z}})]^{1 - \alpha } {\mathbb {B}} + N(\varOmega , {\bar{z}}). \end{aligned}$$

This implies that

$$\begin{aligned} \inf \{\Vert w\Vert \ : \ w \in \partial ^\circ \psi ({\bar{z}}) + N(\varOmega , {\bar{z}}) \}\le & {} \frac{c}{2} \, [\psi ({\bar{z}})]^{1 - \alpha } \ < \ c \, [\psi ({\bar{z}})]^{1 - \alpha }, \end{aligned}$$

which is a contradiction. $\square$

The following example indicates that in general the error bound result in Theorem 4.1 cannot hold globally for all $x \in {\mathbb {R}}^n.$

Example 4.1

Consider the variational inequality (VI) with data

$$\begin{aligned} F(x_1, x_2):= & {} (x_2 - 1, x_1 x_2 - 1) \quad \text { and } \quad \varOmega \ := \ {\mathbb {R}}^2. \end{aligned}$$

Take any $\rho > 0.$ Then, it is easily seen that

$$\begin{aligned} \psi (x)= & {} \frac{1}{2\rho }\Vert F(x)\Vert ^2 \ = \ \frac{1}{2\rho }\left[ (x_2 - 1)^2 + (x_1 x_2 - 1)^2\right] , \end{aligned}$$

and so $\psi ^{-1}(0) = \{(1, 1)\}.$ Consider the sequence $x^k := (k, \frac{1}{k})$ for $k \ge 1.$ As $k \rightarrow +\infty ,$ we have

$$\begin{aligned} \psi (x^k)= & {} \frac{1}{2\rho } \left( \frac{1}{k} - 1\right) ^2 \ \rightarrow \frac{1}{2\rho }, \\ \mathrm {dist}(x^k, \psi ^{-1}(0))= & {} \sqrt{(k - 1)^2 + \left( \frac{1}{k} - 1\right) ^2} \ \rightarrow \ + \infty . \end{aligned}$$

It turns out that there cannot exist any positive scalars c and $\alpha$ such that

$$\begin{aligned} c\, \mathrm {dist}(x^k, \psi ^{-1}(0))\le & {} [\psi (x^k)]^{\alpha } \end{aligned}$$

for all k sufficiently large. Thus, a global error bound with the regularized gap function $\psi ,$ even raised to any positive power, cannot hold in this case.

We now assume that $\varOmega$ is convex and let SOL be the solution set of the variational inequality (VI). In view of [8, Theorem 10.2.3], $x \in \mathrm {SOL}$ if and only if $x \in \varOmega \cap \psi ^{-1}(0).$ Finally, recalling Remark 3.2, the argument in the proof of Theorem 4.1 actually proves the following result.

Theorem 4.2

Let (MFCQ) hold on $\varOmega .$ If the constraint set $\varOmega$ is convex, then for any compact set $K \subset \mathbb {R}^n$ there exists a constant $c > 0$ satisfying the following error bound

$$\begin{aligned} c\, \mathrm {dist}(x, \mathrm {SOL})\le & {} [\psi (x)]^{\alpha } \quad \text { for all } \quad x \in \varOmega \cap K, \end{aligned}$$

where $\alpha := \frac{1}{{\mathcal {R}}(2n + 2r + 2s, d + 2)}$ and the function ${\mathcal {R}}(\cdot , \cdot )$ is defined in (1).

Remark 4.1

As usual, the generality may exclude simple cases: the exponents in Theorems 4.1 and 4.2 are not “sharp” because in the case F is strongly monotone and $\varOmega$ is closed convex, $\alpha = \frac{1}{{\mathcal {R}}(2n + 2r + 2s, d + 2)},$ while it is well known that (see [15, 26, 30,31,32]) the exponent equals $\frac{1}{2}$ in such a case. Thus, although our exponent estimate works for the general case, it may not be tight in particular settings. This calls for further improvements in the exponents obtained in the general polynomial variational inequalities.

5 Conclusions

In this paper, we have established a nonsmooth extension of the Łojasiewicz gradient inequality to the regularized gap function associated with a polynomial variational inequality with exponent explicitly determined by the dimension of the underlying space and the number/degree of the involved polynomials. Using this result, we have obtained some error bounds for the regularized gap function with explicitly calculated exponents. It should be noted that we do not require the monotonicity of the cost map or the convexity of the constraint set.

Nevertheless, many significant issues in these directions still need further investigation. Some of them are indicated in the text; see, e.g., Remark 4.1. It would be also important to identify remarkable classes of variational inequalities for which the general local and global error bounds can be sharpened.