On the existence of Pareto solutions for polynomial vector optimization problems

Abstract

We are interested in the existence of Pareto solutions to the vector optimization problem

$$\begin{aligned} \mathrm{Min}_{\,{\mathbb {R}}^m_+} \{f(x) \,|\, x\in {\mathbb {R}}^n\}, \end{aligned}$$

where $f:{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ is a polynomial map. By using the tangency variety of f we first construct a semi-algebraic set of dimension at most $m - 1$ containing the set of Pareto values of the problem. Then we establish connections between the Palais–Smale conditions, M-tameness, and properness for the map f. Based on these results, we provide some sufficient conditions for the existence of Pareto solutions of the problem. We also introduce a generic class of polynomial vector optimization problems having at least one Pareto solution.

1 Introduction

Existence of solutions and unboundedness are important issues in (vector) optimization theory; we refer the readers to the book [22] and to the papers [2, 3, 5, 15, 16] with the references therein. In this paper, we are interested in the question about the existence of Pareto solutions to the unconstrained vector optimization problem

$$\begin{aligned} \mathrm{Min}_{\,{\mathbb {R}}^m_+} \{f(x) \,|\, x\in {\mathbb {R}}^n\}, \end{aligned}$$

(VP)

where $f:{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ is a polynomial map.

We first consider the case $m = 1.$ It is well known that (VP) has a solution if the objective function f is coercive on ${\mathbb {R}}^n,$ i.e., $f(x)\rightarrow +\infty$ when $\Vert x\Vert \rightarrow \infty .$ This condition is equivalent to the fact that f is bounded from below and satisfies the so-called Palais–Smale condition; see the survey [32] for more details. Regarding to the coercivity property of polynomials, see the recent papers [1, 25].

We next assume that $m > 1$. By introducing some variants of the Ekeland variational principle for set-valued maps, it was proved in [2, 3, 16] that the set of weak Pareto solutions of (VP) is nonempty, provided that the following two conditions hold true:

• f is bounded from below, i.e., there exists an element $a \in {\mathbb {R}}^m$ such that

  $$\begin{aligned} f({\mathbb {R}}^n)\subset a+{\mathbb {R}}^m_+. \end{aligned}$$

• f satisfies a Palais–Smale type condition.

Note that both of these assumptions seem to be rather restrictive (see examples in Sects. 3 and 4 below). So we would like to find better sufficient conditions for the existence of Pareto solutions of (VP) in the case where f is a polynomial map.

Contribution We study the existence of Pareto solutions in polynomial vector optimization problems. To do this, we will use the so-called tangency varieties and tangency values at infinity. It is worth noting that these concepts play important roles in the study of polynomial optimization problems; see [19]. Namely, assume that the map f is polynomial, then our contribution is as follows:

• (a) We will construct a semi-algebraic subset of ${\mathbb {R}}^m$ of dimension at most $m - 1$ containing the set of Pareto values of (VP). This subset can be estimated effectively as shown very recently in [8].

• (b) Under the assumption that the image $f({\mathbb {R}}^n)$ has a bounded section at some $\bar{t} \in {\mathbb {R}}^m,$ which is indeed necessary for the existence of Pareto solutions of (VP), we show that the following statements are equivalent:

  • f is proper at the sublevel $\bar{t}$.

  • f satisfies the Palais–Smale condition at the sublevel $\bar{t}.$

  • f satisfies the weak Palais–Smale condition at the sublevel $\bar{t}.$

  • f is M-tame at the sublevel $\bar{t}.$

• (c) Based on these results, we provide some sufficient conditions under which the set of Pareto solutions of (VP) is nonempty. Finally, we show a generic class of vector optimization problems having at least one Pareto solution.

We hope that the results in this paper will be useful in finding Pareto solutions/values of polynomial vector optimization problems.

To be concrete, we state the results for polynomial maps. Analogous results, with essentially identical proofs, hold for maps definable in an “o-minimal structure” (such as semi-algebraic maps) or, even more generally, for “tame” maps. See [37] for more on the subject.

The rest of the paper is organized as follows. In Sect. 2 we recall some preliminary results from semi-algebraic geometry. Section 3 is devoted to Pareto values and tangencies. Some relationships between Palais–Smale conditions, M-tameness, and properness for polynomial maps are also established in this section. Several sufficient conditions for the existence of Pareto solutions of (VP) are given in Sect. 4. Section 5 draws some conclusions.

2 Preliminaries

We use the following notation and terminology. Fix a number $n \in {\mathbb {N}}$, $n \ge 1$, and abbreviate $(x_1, x_2, \ldots , x_n)$ by x. The space ${\mathbb {R}}^n$ is equipped with the usual scalar product $\langle \cdot , \cdot \rangle$ and the corresponding Euclidean norm $\Vert \cdot \Vert .$ The interior (resp., the closure) of a set S is denoted by $\mathrm {int}\, S$ (resp., $\mathrm {cl}\,{S}$). The closed unit ball in ${\mathbb {R}}^n$ is denoted by $\mathbb {B}^n.$ Let ${\mathbb {R}}^m_+ := \{t := (t_1, \ldots , t_m)\,|\, \, t_i\ge 0,\,\, i=1,\ldots , m\}$ be the nonnegative orthant in ${\mathbb {R}}^m$. The cone ${\mathbb {R}}^m_+$ induces the following partial order in ${\mathbb {R}}^m$: $x, y\in {\mathbb {R}}^m$, $x\le y$ if and only if $y - x\in {\mathbb {R}}^m_+.$

Now, we recall some notions and results of semi-algebraic geometry, which can be found in [4, 19].

Definition 2.1

• (i) A subset of ${\mathbb {R}}^n$ is called semi-algebraic 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}^m$ be semi-algebraic sets. A map $F :A \rightarrow B$ is said to be semi-algebraic if its graph

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

  is a semi-algebraic subset in $\mathbb {R}^n\times \mathbb {R}^m.$

By definition, it is easy to see that the class of semi-algebraic sets is closed under taking finite intersections, finite unions and complements; a Cartesian product of semi-algebraic sets is a semi-algebraic set. Furthermore, we have the following result (see [4, Proposition 2.2.7] or [19, Sect. 6]).

Theorem 2.1

(Tarski–Seidenberg Theorem) The image and inverse image of a semi-algebraic set under a semi-algebraic map are semi-algebraic sets.

Remark 2.1

As an immediate consequence of the 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 semi-algebraic sets in the corresponding spaces. It also follows that $\{ x \in A \ | \ \forall y \in B, (x, y) \in C \}$ is a semi-algebraic 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 semi-algebraic sets, then any set obtained from them with the help of a finite chain of quantifiers is also semi-algebraic. In particular, it is not hard to see that the closure and the interior of a semi-algebraic set are semi-algebraic sets.

By the Cell Decomposition Theorem (see [4, Theorem 2.3.6]), for any $p \in \mathbb {N}$ and any nonempty semi-algebraic subset $A \subset {\mathbb {R}}^n,$ we can write A as a disjoint union of finitely many semi-algebraic $C^p$-manifolds of different dimensions. The dimension$\dim A$ of a nonempty semi-algebraic set A can thus be defined as the dimension of the manifold of highest dimension of its decomposition. This dimension is well defined and independent of the decomposition of A. By convention, the dimension of the empty set is taken to be negative infinity. We will need the following result (see [4, 19]).

Proposition 2.1

(i):

Let $A \subset {\mathbb {R}}^n$ be a semi-algebraic set and $f :A \rightarrow {\mathbb {R}}^m$ a semi-algebraic map. Then $\dim f(A)\le \dim A.$

(ii):

Let $A \subset {\mathbb {R}}^n$ be a nonempty semi-algebraic set. Then

$$\begin{aligned} \dim (\mathrm {cl}\,{A}{\setminus } A) < \dim A. \end{aligned}$$

In particular, $\dim \mathrm {cl}\,{A}=\dim A.$

(iii):

Let $A, B \subset {\mathbb {R}}^n$ be semi-algebraic sets. Then

$$\begin{aligned} \dim (A \cup B) = \max \{ \dim A, \dim B\}. \end{aligned}$$

In the sequel, we will need the following useful results (see, for example, [19]).

Lemma 2.1

(Curve Selection Lemma at infinity) Let $A\subset {\mathbb {R}}^n$ be a semi-algebraic set, and let $f := (f_1, \ldots ,f_m) :{\mathbb {R}}^n \rightarrow {\mathbb {R}}^m$ be a semi-algebraic map. Assume that there exists a sequence $\{x^\ell \}$ such that $x^\ell \in A$, $\lim \nolimits _{\ell \rightarrow \infty } \Vert x^\ell \Vert = \infty$ and $\lim \nolimits _{\ell \rightarrow \infty } f(x^\ell ) = y \in (\overline{{\mathbb {R}}})^m,$ where $\overline{{\mathbb {R}}} := {\mathbb {R}} \cup \{\pm \infty \}.$ Then there exists a smooth semi-algebraic curve $\varphi :(0, \epsilon )\rightarrow {\mathbb {R}}^n$ such that $\varphi (t) \in A$ for all $t \in (0, \epsilon ), \lim \nolimits _{t \rightarrow 0} \Vert \varphi (t)\Vert = \infty ,$ and $\lim \nolimits _{t \rightarrow 0} f(\varphi (t)) = y.$

Lemma 2.2

(Growth Dichotomy Lemma) Let $f :(0, \epsilon ) \rightarrow {\mathbb {R}}$ be a semi-algebraic function with $f(t) \ne 0$ for all $t \in (0, \epsilon ).$ Then there exist constants $c \ne 0$ and $q \in {\mathbb {Q}}$ such that $f(t) = ct^q + o(t^q)$ as $t \rightarrow 0^+.$

Lemma 2.3

(Monotonicity Lemma) Let $a < b$ in ${\mathbb {R}}.$ If $f :[a, b] \rightarrow {\mathbb {R}}$ is a semi-algebraic function, then there is a partition $a =: t_1< \cdots < t_{N} := b$ of [a, b] such that $f|_{(t_l, t_{l + 1})}$ is $C^1,$ and either constant or strictly monotone, for $l \in \{1, \ldots , N - 1\}.$

3 Pareto values and tangencies

3.1 Pareto values

Let $f := (f_1,\ldots , f_m):{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ be a map and consider the vector optimization problem (VP) formulated in Sect. 1.

Definition 3.1

Let $t\in \,\mathrm {cl} f({\mathbb {R}}^n)$. We say that:

(i):

t is a Pareto (optimal) value of  (VP) if

$$\begin{aligned} f(x)\notin t - ({\mathbb {R}}^m_+{\setminus }\{0\}) \quad \text { for all } \quad x \in {\mathbb {R}}^n. \end{aligned}$$

The set of all Pareto values of (VP) is denoted by $\mathrm {val}\,$(VP).

(ii):

t is a weak Pareto (optimal) value of (VP) if

$$\begin{aligned} f(x)\notin t -\mathrm{int}\,{\mathbb {R}}^m_+\quad \text { for all } \quad x\in {\mathbb {R}}^n. \end{aligned}$$

The set of all weak Pareto values of (VP) is denoted by $\mathrm {val}^w\,$(VP).

(iii):

A point $x^*$ is said to be a Pareto (optimal) solution (resp., weak Pareto (optimal) solution) if $f(x^*)$ is a Pareto value (resp., weak Pareto value) of (VP). The set of all Pareto solutions (resp., weak Pareto solutions) is denoted by $\mathrm {sol}\,$(VP) (resp., $\mathrm {sol}^w\,$(VP)).

Remark 3.1

(i):

By definition, it is clear that $\mathrm {val}\,$(VP)$\subset \mathrm {val}^w\,$(VP). Note that the inclusion may be strict.

(ii):

In the case of $m = 1$ and f is bounded from below on ${\mathbb {R}}^n$,

$$\begin{aligned} \mathrm {val}\,(\text {VP})=\mathrm {val}^w\,(\text {VP})=\{\inf _{x\in {\mathbb {R}}^n} f(x)\}. \end{aligned}$$

(iii):

A (weak) Pareto value of the problem (VP) does not necessarily belong to $f({\mathbb {R}}^n)$ as shown in the example below.

Example 3.1

(i):

Let $f:{\mathbb {R}}^3\rightarrow {\mathbb {R}}^2$ be the polynomial map defined by

$$\begin{aligned} f(x_1, x_2, x_3):=(x_3, x_1^2+(x_1x_2-1)^2+x_3^2). \end{aligned}$$

We have that

$$\begin{aligned} f({\mathbb {R}}^3)=\{t=(t_1, t_2)\in {\mathbb {R}}^2\,|\, t_2>t_1^2\} \end{aligned}$$

is an open set in ${\mathbb {R}}^2$. Furthermore, it is easy to see that

$$\begin{aligned} \mathrm {val}\,(\text {VP})=\mathrm {val}^w\,(\text {VP})=\{t=(t_1, t_2)\in {\mathbb {R}}^2\,|\, t_2=t_1^2, t_1\le 0\} \ne \emptyset . \end{aligned}$$

Hence $\mathrm {val}\,(\text {VP})\cap f({\mathbb {R}}^3) = \mathrm {val}^w\,(\text {VP})\cap f({\mathbb {R}}^3) = \emptyset ,$ and so $\mathrm {sol}\,(\text {VP})=\mathrm {sol}^w\,(\text {VP})=\emptyset .$

(ii):

In the recent paper [13] (see also [12, 14]) it was proved that the open quadrant

$$\begin{aligned} \{(t_1, t_2) \in {\mathbb {R}}^2 \, | \, t_1> 0, t_2 > 0\} \end{aligned}$$

is the image of the polynomial map $f :{\mathbb {R}}^2 \rightarrow {\mathbb {R}}^2, \ (x_1,x_2) \mapsto ((x_1^2x_2^4 + x_1^4x_2^2 - x_2^2 -1)^2 + x_1^6x_2^4, (x_1^6x_2^2 + x_1^2x_2^2 - x_1^2 - 1)^2 + x_1^6x_2^4).$ For this f,  we have

$$\begin{aligned} \mathrm {val}\,(\text {VP})=\mathrm {val}^w\,(\text {VP}) = \{(t_1, t_2) \in {\mathbb {R}}^2 \, | \, t_1 t_2 = 0, t_1 \ge 0, t_2 \ge 0 \} \ne \emptyset . \end{aligned}$$

Therefore, $\mathrm {val}\,(\text {VP})\cap f({\mathbb {R}}^2) = \mathrm {val}^w\,(\text {VP})\cap f({\mathbb {R}}^2) = \emptyset ,$ and so $\mathrm {sol}\,(\text {VP})=\mathrm {sol}^w\,(\text {VP})=\emptyset .$

Remark 3.2

It was proved very recently in [20] that both the proper Pareto solution set and the weak Pareto solution set of a vector variational inequality, where the convex constraint set is given by polynomial functions and all the components of the basic operators are polynomial functions, have finitely many connected components, provided that the Mangasarian–Fromovitz constraint qualification is satisfied at every point of the constraint set. In addition, if the proper Pareto solution set is dense in the Pareto solution set, then the latter also has finitely many connected components. Applying the above result to vector optimization problems under polynomial constraints, where all the components of the basic operators are polynomial functions, the authors obtained some topological properties of the stationary point set, as well as the weak Pareto solution set, of the problem in question.

We would like to remark that all the results in the cited paper can be concluded immediately from Theorem 2.1 without any convexity assumption or constraint qualification conditions. Indeed it suffices to assume that maps and constraint sets are semi-algebraic. As an illustrative example, we prove here that the sets $\mathrm {val}\,(\text {VP})$ and $\mathrm {sol}\,(\text {VP})$ are semi-algebraic provided that f is a (not necessarily continuous) semi-algebraic map and so, thanks to Bochnak et al. [4, Theorem 2.4.4], they have a finite number of (path) connected components.

Let $f :=(f_1,\ldots , f_m):{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ be a semi-algebraic map. By Theorem 2.1, the set $f({\mathbb {R}}^n)$ is semi-algebraic and so is $\mathrm {cl}\,f({\mathbb {R}}^n).$ Let $\phi$ and $\psi$ be two functions defined by

$$\begin{aligned} \phi&:{\mathbb {R}}^n\times {\mathbb {R}}^m\rightarrow {\mathbb {R}}, \quad (x, t)\mapsto \max _{i}\{f_i(x)-t_i\},\\ \psi&:{\mathbb {R}}^n\times {\mathbb {R}}^m\rightarrow {\mathbb {R}}, \quad (x, t)\mapsto \sum _{i=1}^m [f_i(x)-t_i]^2. \end{aligned}$$

In view of Theorem 2.1, it is easy to see that $\phi$ and $\psi$ are semi-algebraic functions. Furthermore, by definition we have

$$\begin{aligned} \mathrm {val}\,(\text {VP})&=\{t\in \mathrm {cl}\, f({\mathbb {R}}^n)\,\,|\,\, \forall x\in {\mathbb {R}}^n, f(x) \notin t - ({\mathbb {R}}^m_+{\setminus }\{0\})\} \\&=\{t\in \mathrm {cl}\, f({\mathbb {R}}^n)\,\,|\,\,\forall x\in {\mathbb {R}}^n, \phi (x, t)>0 \,\,\text{ or }\,\, \psi (x, t)=0\}. \end{aligned}$$

Note that $\psi (x, t)\ge 0$ on ${\mathbb {R}}^n\times {\mathbb {R}}^m$. Hence

$$\begin{aligned} \mathrm {cl}\,f({\mathbb {R}}^n){\setminus }\mathrm {val}\,(\text {VP})= \{t\in \mathrm {cl}\, f({\mathbb {R}}^n)\,\,|\,\, \exists x\in {\mathbb {R}}^n, \phi (x, t)\le 0 \,\,\text{ and }\,\, \psi (x, t)>0\}. \end{aligned}$$

Thanks to Theorem 2.1, this set is semi-algebraic because it is the projection onto the last m coordinates of the following semi-algebraic set

$$\begin{aligned} \{(x, t)\in {\mathbb {R}}^n \times \mathrm {cl}\, f({\mathbb {R}}^n) \,\,|\,\, \phi (x, t)\le 0 \,\,\text{ and }\,\, \psi (x, t)>0\}. \end{aligned}$$

Therefore, $\mathrm {val}(\text {VP})$ is a semi-algebraic set.

Finally, the set $\mathrm {sol}\,(\text {VP}) = f^{-1}(\mathrm {val}\,(\text {VP}))$ is semi-algebraic because of Theorem 2.1 again.

Similarly, it is easy to check that the sets $\mathrm {val}^w\,(\text {VP})$ and $\mathrm {sol}^w\,(\text {VP})$ are semi-algebraic and so, by Bochnak et al. [4, Theorem 2.4.4], they have a finite number of connected components, which are semi-algebraic.

3.2 Tangencies

Let $f:=(f_1,\ldots , f_m):{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ be a polynomial map. A point $t\in {\mathbb {R}}^m$ is called a regular value for f if either $f^{-1}(t)=\emptyset$ or the derivative map $D f(x):{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ is surjective at every point $x\in f^{-1}(t)$. A point $t\in {\mathbb {R}}^m$ that is not a regular value of f is called a critical value. We will denote by $K_0(f)$ the set of critical values of f.

Definition 3.2

(see [19])

• (i) By the tangency variety of f we mean the set

  $$\begin{aligned} \varGamma (f):=\{x\in {\mathbb {R}}^n\,|\, \exists \lambda _i, \mu \in {\mathbb {R}}, \,\,\text{ not } \text{ all } \text{ zero, } \text{ such } \text{ that } \,\, \sum _{i=1}^m \lambda _i\nabla f_i(x)+ \mu x=0\}, \end{aligned}$$

  here and in the following $\nabla f_i(x)$ stands for the gradient of $f_i$ at x.

• (ii) The set of tangency values (at infinity) of f is defined by

  $$\begin{aligned} T_{\infty }(f):=\{t\in {\mathbb {R}}^m\,\,|\,\, \exists \{x^k\}\subset \varGamma (f), \Vert x^k\Vert \rightarrow +\infty \,\,\text{ and }\,\, f(x^k)\rightarrow t \,\,\text{ as }\,\, k\rightarrow \infty \}. \end{aligned}$$

Remark 3.3

Very recently, relying on results from semi-algebraic geometry, it was proved in [8] (see also [7, 24]) that the set of tangency values at infinity of polynomial maps can be estimated effectively.

Lemma 3.1

$\varGamma (f)$ is an unbounded nonempty semi-algebraic set.

Proof

By Theorem 2.1, it is easy to check that the set $\varGamma (f)$ is semi-algebraic.

We next show that $\varGamma (f) \ne \emptyset .$ To this end, take any $R > 0.$ Then the sphere $S_R := \{x \in {\mathbb {R}}^n \ | \ \Vert x\Vert ^2 = R^2 \}$ is nonempty compact. Hence, the optimization problem $\mathrm{Min}_{\,{\mathbb {R}}^m_+} \{f(x) \,|\, x\in S_R\}$ has a Pareto solution, say $x(R) \in S_R.$ The Fritz-John optimality conditions [22, Theorem 7.4] imply that $x(R) \in \varGamma (f),$ and so $\varGamma (f) \ne \emptyset .$ Finally, it is clear that if $R \rightarrow \infty$ then $\Vert x(R)\Vert = R \rightarrow \infty ,$ which proves the lemma. $\square$

We now give a simple and constructive proof of the following known result [7, Theorem 2.5], [6, Theorem 5.7], [19, Theorem 1.1] and [29, Theorem 1.5].

Proposition 3.1

$T_{\infty }(f)$ is a closed semi-algebraic set of dimension at most $m - 1$.

Proof

By definition and Theorem 2.1, it is not hard to check that $T_{\infty } (f)$ is a closed semi-algebraic set.

Consider the semi-algebraic map

$$\begin{aligned} \varPhi :{\mathbb {R}}^n \rightarrow {\mathbb {R}}^{m + 1}, \quad x \mapsto (f(x), \Vert x\Vert ^2) . \end{aligned}$$

In view of Lemma 3.1 and Theorem 2.1, the image $\varPhi (\varGamma (f))$ is semi-algebraic. By definition, $\varGamma (f)$ is the set of critical points of $\varPhi .$ Thanks to Sard’s theorem (see, for example, [19, Theorem 1.9]), the set $\varPhi (\varGamma (f))$ is of dimension at most m,  and so it cannot contain a nonempty open subset of ${\mathbb {R}}^{m + 1}.$

On the other hand, since $\varPhi (\varGamma (f))$ is semi-algebraic, we can write

$$\begin{aligned} \varPhi (\varGamma (f)) = \bigcup _{i = 1}^s \{(t, R) \in {\mathbb {R}}^m \times {\mathbb {R}} \, | \, g_i(t, R) = 0,\ h_{i_j}(t, R) > 0, \ j = 1, \ldots , k_i\} \end{aligned}$$

for some polynomials $g_i$ and $h_{i_j}.$ Then we must have $g_i \not \equiv 0$ for all $i = 1, \ldots , s,$ because otherwise $\varPhi (\varGamma (f))$ would contain a nonempty open subset of ${\mathbb {R}}^{m + 1}$, a contradiction. Let $P :{\mathbb {R}}^{m + 1} \rightarrow {\mathbb {R}}$ be the product of all the polynomials $g_i, i = 1, \ldots , s.$ Clearly, $P \not \equiv 0$ and

$$\begin{aligned} \varPhi (\varGamma (f)) \subset \{(t, R) \in {\mathbb {R}}^m \times {\mathbb {R}} \ | \ P(t, R) = 0 \}. \end{aligned}$$

Write

$$\begin{aligned} P(t, R) = a_0(t) R^d + \cdots + a_d(t) \end{aligned}$$

for some polynomials $a_i(t)$ with $a_0(t) \not \equiv 0.$ By definition, then

$$\begin{aligned} T_{\infty }(f)= & {} \{t\in {\mathbb {R}}^m \ | \ \exists (t^k, R^k) \in \varPhi (\varGamma (f)), R^k \rightarrow +\infty \,\,\text{ and }\,\, t^k \rightarrow t \,\,\text{ as }\,\, k\rightarrow \infty \} \\\subset & {} \{t\in {\mathbb {R}}^m \ | \ \exists (t^k, R^k) \in P^{-1}(0), R^k \rightarrow +\infty \,\,\text{ and }\,\, t^k \rightarrow t \,\,\text{ as }\,\, k\rightarrow \infty \} \\\subset & {} \{t \in {\mathbb {R}}^m \ | \ a_0(t) = 0 \}. \end{aligned}$$

Therefore, $\dim T_\infty (f) \le m - 1,$ which completes the proof. $\square$

Remark 3.4

In [30, 31], by using semidefinite programming relaxations, the authors provided several methods to approximate as closely as desired the image of semi-algebraic sets under polynomial maps with super-level sets of single polynomials of fixed degrees. This fact, together with the proof of Proposition 3.1, gives us a hope that the set $\varPhi (\varGamma (f))$ and so $T_\infty (f)$ can be approximated effectively.

The next statement describes a relation between Pareto values and tangency values.

Theorem 3.1

The following inclusions hold true

$$\begin{aligned} \mathrm {val}\,(\text {VP}) \subset \mathrm {val}^w\,(\text {VP})\subset K_0(f)\cup T_{\infty }(f). \end{aligned}$$

In particular, the semi-algebraic sets $\mathrm {val}\,(\text {VP})$ and $\mathrm {val}^w\,(\text {VP})$ are of dimension at most $m - 1.$

Proof

The first inclusion is obvious. Let us prove the second one. Fix $t\in \mathrm {val}^w\, (\text {VP})$.

If $t\in f({\mathbb {R}}^n)$, then $t\in K_0(f)$ due to the Karush–Kuhn–Tucker necessary conditions [22, Theorem 7.4]. So assume that $t \in \,\mathrm {cl} f({\mathbb {R}}^n){\setminus } f({\mathbb {R}}^n)$. Then there is a sequence $\{x^k\}$ such that $\displaystyle \lim \nolimits _{k\rightarrow \infty } f(x^k)=t$. We claim that $\displaystyle \lim \nolimits _{k\rightarrow \infty }\Vert x^k\Vert =+\infty$. Indeed, if it is not the case, then the sequence $\{x^k\}$ has an accumulation point, say $x^* \in {\mathbb {R}}^n.$ By the continuity of f, we have $t = f(x^*) \in f({\mathbb {R}}^n),$ which is a contradiction.

For each $k\in \mathbb {N}$, we consider the scalar optimization problem

$$\begin{aligned}&\min \Vert f(x)-t\Vert ^2 \\&\text {s.t.} \quad x \in {\mathbb {R}}^n, \ \Vert x\Vert ^2=\Vert x^k\Vert ^2. \end{aligned}$$

Since $\{x\in {\mathbb {R}}^n\,\,|\,\, \Vert x\Vert ^2=\Vert x^k\Vert ^2\}$ is a nonempty compact set in ${\mathbb {R}}^n$, this problem admits an optimal solution, say $y^k$. It is easy to check that the sequence $\{y^k\}$ has the following properties:

• (a) $\displaystyle \lim \nolimits _{k\rightarrow \infty } \Vert y^k\Vert = \lim \nolimits _{k\rightarrow \infty } \Vert x^k\Vert =+\infty$,

• (b) $0\le \Vert f(y^k)-t\Vert ^2\le \Vert f(x^k)-t\Vert ^2$, and

• (c) there exists $\mu ^k\in {\mathbb {R}}$ such that

  $$\begin{aligned} \sum _{i=1}^m (f_i(y^k)-t_i)\nabla f_i(y^k) +\mu ^k y^k=0. \end{aligned}$$

  (This follows from the Karush–Kuhn–Tucker necessary conditions.)

Since $t\notin f({\mathbb {R}}^n)$, one has $f(y^k)\ne t$ for all $k\in \mathbb {N}$. Therefore $\{y^k\}\subset \varGamma (f)$. Moreover, we have

$$\begin{aligned} 0\le \lim _{k\rightarrow \infty }\Vert f(y^k)-t\Vert ^2\le \lim _{k\rightarrow \infty }\Vert f(x^k)-t\Vert ^2=0, \end{aligned}$$

and so $\displaystyle \lim \nolimits _{k\rightarrow \infty }f(y^k) = t.$ Thus $t\in T_{\infty } (f).$

Finally, due to the Sard theorem (see, for example, [19, Theorem 1.9]), $K_0(f)$ is a semi-algebraic set of dimension at most $m - 1.$ This, together with Propositions 2.1 and 3.1, implies the last statement. $\square$

3.3 Palais–Smale conditions, M-tameness and properness

Given a differentiable map $f := (f_1,\ldots , f_m):{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ and a value $\bar{t} \in ({\mathbb {R}} \cup \{+ \infty \})^m,$ we let

$$\begin{aligned} \widetilde{K}_{\infty , \le \bar{t}}(f):= & {} \{t\in {\mathbb {R}}^m\,|\, \exists \{x^k\}\subset {\mathbb {R}}^n, f(x^k) \le \bar{t}, \Vert x^k\Vert \rightarrow +\infty , f(x^k)\rightarrow t, \text{ and } \\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ \ \nu _f(x^k)\rightarrow 0 \, \text{ as } \, k\rightarrow \infty \},\\ K_{\infty , \le {\bar{t}}}(f):= & {} \{t\in {\mathbb {R}}^m\,|\, \exists \{x^k\}\subset {\mathbb {R}}^n, f(x^k) \le {\bar{t}}, \Vert x^k\Vert \rightarrow +\infty , f(x^k)\rightarrow t, \text{ and } \\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \, \ \Vert x^k\Vert \nu _f(x^k)\rightarrow 0 \, \text{ as } \, k\rightarrow \infty \}, \\ T_{\infty , \le {\bar{t}}}(f):= & {} \{t\in {\mathbb {R}}^m\,\,|\,\, \exists \{x^k\}\subset \varGamma (f), f(x^k) \le {\bar{t}}, \Vert x^k\Vert \rightarrow +\infty , \,\text{ and } \\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ \ \ \ f(x^k)\rightarrow t \,\,\text{ as }\,\, k\rightarrow \infty \}, \end{aligned}$$

where $\nu _f:{\mathbb {R}}^n\rightarrow {\mathbb {R}}$ is the Rabier function (see [28, 36]) defined by

$$\begin{aligned} \nu _f(x):=\min _{\sum _{i=1}^m|\lambda _i|=1}\left\| \sum _{i=1}^m \lambda _i\nabla f_i(x)\right\| . \end{aligned}$$

Note that if $m = 1$ then $\nu _f(x) = \Vert \nabla f(x)\Vert .$

For simplicity of notation, when $\bar{t} = (+\infty , \ldots , +\infty ),$ we write $\widetilde{K}_{\infty }(f),$${K}_{\infty }(f),$ and $T_\infty (f)$ instead of $\widetilde{K}_{\infty , \le \bar{t}}(f),$$K_{\infty , \le \bar{t}}(f),$ and $T_{\infty , \le \bar{t}}(f),$ respectively.

The following result is a generalization of [7, Theorem 2.8], [18, Theorem 1.1], and [28, Proposition 3.1].

Proposition 3.2

Let $f:{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ be a polynomial map and $\bar{t} \in ({\mathbb {R}} \cup \{+ \infty \})^m.$ The following inclusions hold:

$$\begin{aligned} T_{\infty , \le {\bar{t}}}(f)\subset K_{\infty , \le {\bar{t}}}(f)\subset \widetilde{K}_{\infty , \le \bar{t}}(f). \end{aligned}$$

Furthermore, if $n \le m,$ then these inclusions are equalities.

Proof

The second inclusion is immediate from the definitions.

To prove the first inclusion, take any $t \in T_{\infty , \le \bar{t}} (f).$ By definition, there exist sequences $\{x^k\} \subset {\mathbb {R}}^n$ and $\{(\lambda ^k, \mu ^k)\} \subset \left( {\mathbb {R}}^m \times {\mathbb {R}}\right) {\setminus } \{0\}$ such that

$$\begin{aligned}&\lim _{k \rightarrow \infty } \Vert x^k\Vert = +\infty , \quad \lim _{k \rightarrow \infty } f(x^k) = t, \quad f(x^k) \le \bar{t}, \quad \sum _{i = 1}^m \lambda ^k_i \nabla f_i(x^k) + \mu ^k x^k = 0 \end{aligned}$$

We can assume, after a scaling if necessary, that $\Vert (\lambda ^k, \mu ^k)\Vert = 1$ for all $k\in \mathbb {N}$.

Let

$$\begin{aligned} \mathscr {A}:=\big \{ (x, \lambda , \mu ) \in {\mathbb {R}}^n \times {\mathbb {R}}^{m} \times {\mathbb {R}} | f(x) \le \bar{t}, \sum _{i = 1}^m \lambda _i \nabla f_i(x) + \mu x = 0, \Vert (\lambda , \mu )\Vert = 1 \big \}. \end{aligned}$$

Then $\mathscr {A}$ is a semi-algebraic set and the sequence $(x^k, \lambda ^k, \mu ^k) \in \mathscr {A}$ tends to infinity as $k \rightarrow \infty .$ By applying Lemma 2.1 for the semi-algebraic map $\mathscr {A} \rightarrow {\mathbb {R}}^m, (x, \lambda , \mu ) \mapsto f(x),$ we get a smooth semi-algebraic curve

$$\begin{aligned} (\varphi , \lambda , \mu ) :(0, \epsilon ) \rightarrow {\mathbb {R}}^n \times {\mathbb {R}}^{m} \times {\mathbb {R}}, \quad \tau \mapsto (\varphi (\tau ), \lambda (\tau ), \mu (\tau )), \end{aligned}$$

satisfying the following conditions

• (a) $\lim \nolimits _{\tau \rightarrow 0^+} \Vert \varphi (\tau )\Vert = +\infty ;$

• (b) $\lim \nolimits _{\tau \rightarrow 0^+} f(\varphi (\tau )) = t;$

• (c) $f(\varphi (\tau )) \le \bar{t};$

• (d) $\sum _{i = 1}^m \lambda _i(\tau ) \nabla f_i(\varphi (\tau )) + \mu (\tau ) \varphi (\tau ) \equiv 0;$

• (e) $\Vert (\lambda (\tau ), \mu (\tau ))\Vert \equiv 1.$

Since the (smooth) functions $\lambda _i, \mu ,$ and $f_i \circ \varphi$ are semi-algebraic, we can assume, by shrinking $\epsilon$ if necessary, that these functions are either constant or strictly monotone (see Lemma 2.3).

It follows from (d) that

$$\begin{aligned} \frac{\mu (\tau )}{2} \frac{d \Vert \varphi (\tau )\Vert ^2}{d\tau }= & {} \mu (\tau ) \left\langle \varphi (\tau ), \frac{d \varphi (\tau )}{d\tau } \right\rangle \\= & {} - \sum _{i = 1}^m \lambda _i(\tau ) \left\langle \nabla f_i(\varphi (\tau )), \frac{d \varphi (\tau )}{d\tau } \right\rangle \\= & {} - \sum _{i = 1}^m \lambda _i(\tau ) \frac{d}{d\tau }(f_i \circ \varphi )(\tau ). \end{aligned}$$

Let $I := \{i \in \{1, \ldots , m\} \ | \ \lambda _i (\tau ) \frac{d}{d \tau } (f_i \circ \varphi )(\tau ) \not \equiv 0\}.$ Then

$$\begin{aligned} \frac{\mu (\tau )}{2} \frac{d \Vert \varphi (\tau )\Vert ^2}{d\tau }= & {} - \sum _{i \in I} \lambda _i(\tau ) \frac{d}{d\tau }(f_i \circ \varphi )(\tau ). \end{aligned}$$

(1)

Assume that $I = \emptyset .$ From (a) and (1) we have $\mu (\tau ) \equiv 0.$ By (d), hence $\nu _f(\varphi (\tau )) \equiv 0,$ which together with (a)–(c), yields $t \in K_{\infty , \le \bar{t}}(f).$

We now assume that $I \ne \emptyset .$ For each $i \in I,$ we have $\lambda _i(\tau ) \not \equiv 0$ and $f_i \circ \varphi (\tau ) \not \equiv t_i.$ By Lemma 2.2, we may write

$$\begin{aligned} \lambda _i(\tau )= & {} a_i \tau ^{\alpha _i} + \text {higher order terms in } \tau ,\\ f_i \circ \varphi (\tau )= & {} t_i + b_i \tau ^{\beta _i} + \text {higher order terms in } \tau , \end{aligned}$$

where $a_i \ne 0, b_i \ne 0$ and $\alpha _i, \beta _i \in \mathbb {Q}.$ By Conditions (e) and (b) respectively, we have $\alpha _i \ge 0$ and $\beta _i > 0.$ In particular, $\theta := \min _{i \in I} (\alpha _i + \beta _i) > 0.$

On the other hand, from (d) and (1), we have

$$\begin{aligned} \frac{\left\| \displaystyle \sum \nolimits _{i = 1}^m \lambda _i(\tau ) \nabla f_i(\varphi (\tau )) \right\| }{2\Vert \varphi (\tau )\Vert } \left| \frac{d \Vert \varphi (\tau )\Vert ^2}{d \tau } \right|= & {} \left| \sum _{i \in I} \lambda _i(\tau ) \frac{d}{d\tau }(f_i \circ \varphi )(\tau ) \right| . \end{aligned}$$

Note that asymptotically as $\tau \rightarrow 0^+,$

$$\begin{aligned} \Vert \varphi (\tau )\Vert ^2\simeq & {} \tau \frac{d \Vert \varphi (\tau )\Vert ^2}{d\tau } . \end{aligned}$$

Therefore,

$$\begin{aligned} \Vert \varphi (\tau )\Vert \left\| \sum _{i = 1}^m \lambda _i(\tau ) \nabla f_i(\varphi (\tau )) \right\|\simeq & {} \frac{\left\| \displaystyle \sum \nolimits _{i = 1}^m \lambda _i(\tau ) \nabla f_i(\varphi (\tau )) \right\| }{2\Vert \varphi (\tau )\Vert } \left| \tau \frac{d \Vert \varphi (\tau )\Vert ^2}{d \tau } \right| \\= & {} \left| \sum _{i \in I} \lambda _i(\tau ) \tau \frac{d}{d\tau }(f_i \circ \varphi )(\tau ) \right| \\= & {} c \tau ^{\theta } + \text {higher order terms in } \tau , \end{aligned}$$

for some constant $c \ge 0.$ Since $\theta > 0,$ we have

$$\begin{aligned} \lim _{t \rightarrow 0^+} \Vert \varphi (\tau )\Vert \left\| \sum _{i = 1}^m \lambda _i(\tau ) \nabla f_i(\varphi (\tau )) \right\|= & {} 0. \end{aligned}$$

Combining this with (a)–(c) one gets $t \in K_{\infty , \le \bar{t}}(f),$ thus ending the proof of the first part of our statement.

We now assume that $n \le m.$ By definition, $\varGamma (f) = {\mathbb {R}}^n,$ and so

$$\begin{aligned} T_{\infty , \le {\bar{t}}}(f) \supset \widetilde{K}_{\infty , \le \bar{t}}(f). \end{aligned}$$

This, together with proven inclusions, gives the following equalities:

$$\begin{aligned} T_{\infty , \le {\bar{t}}}(f) = K_{\infty , \le {\bar{t}}}(f) = \widetilde{K}_{\infty , \le \bar{t}}(f). \end{aligned}$$

$\square$

Remark 3.5

• (i) The first inclusion in Proposition 3.2 may be strict. For example, consider a class of polynomial functions defined by

  $$\begin{aligned} f_{nq}:{\mathbb {R}}^3\rightarrow {\mathbb {R}}, \quad (x_1, x_2, x_3)\mapsto x_1-3x_1^{2n+1}x_2^{2q}+2x_1^{3n+1}x_2^{3q}+x_2x_3, \end{aligned}$$

  where $n, q\in \mathbb {N}{\setminus }\{0\}$. By a similar argument as in [35], we can show that $T_{\infty }(f_{nq}) = \emptyset$ and that $K_{\infty }(f_{nq}) = \emptyset$ if, and only if, $n \le q$. For $n>q$ we therefore get $T_{\infty }(f_{nq}) \varsubsetneq K_{\infty }(f_{nq}) \ne \emptyset .$

• (ii) According to [28, Lemma 3.5] (see also [21, Theorem 2] and [23, Theorem 6.4]), we have

  $$\begin{aligned} \dim K_{\infty , \le {\bar{t}}}(f) \le \dim K_{\infty }(f) < m. \end{aligned}$$

On the other hand, without some extra hypothesis the set $\widetilde{K}_{\infty , \le \bar{t}}(f)$ may be quite large in the sense that $\dim \widetilde{K}_{\infty , \le \bar{t}}(f) = m.$ For example, let $f:{\mathbb {R}}^3\rightarrow {\mathbb {R}}$ be the polynomial defined by $f(x_1, x_2, x_3):= x_1+x_1^2x_2+x_1^4x_2x_3.$ Then it is not hard to check that $\widetilde{K}_{\infty }(f)={\mathbb {R}}$ (see [28, Example 2.1]), and hence

$$\begin{aligned} \dim {T}_{\infty }(f)=0<1=\dim \widetilde{K}_{\infty }(f). \end{aligned}$$

Definition 3.3

Let A be a subset in ${\mathbb {R}}^m$ and ${\bar{t}} \in {\mathbb {R}}^m$. The set $A \cap ({\bar{t}} - {\mathbb {R}}^m_+)$ is called a section of A at ${\bar{t}}$ and denoted by $[A]_{\bar{t}}.$ The section $[A]_{\bar{t}}$ is said to be bounded if, and only if, there is $a\in {\mathbb {R}}^m$ such that

$$\begin{aligned}{}[A]_{\bar{t}} \subset a + {\mathbb {R}}^m_+. \end{aligned}$$

Remark 3.6

• (i) Let $f:{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ be a map. Clearly, if the problem (VP) admits a Pareto solution, say $\bar{x}$, then the section $[f({\mathbb {R}}^n)]_{f(\bar{x})}=\{f(\bar{x})\}$ is bounded. Thus the condition that $f({\mathbb {R}}^n)$ has at least one bounded section is a necessary one for the existence of Pareto solutions of (VP).

• (ii) By definition, the section $[f({\mathbb {R}}^n)]_{\bar{t}}$ is bounded if, and only if, for each sequence $\{x^k\}\subset {\mathbb {R}}^n$ with $f(x^k)\le {\bar{t}}$, we have $\{f(x^k)\}$ possesses a convergent subsequence.

• (iii) By definition, we have for all $\bar{t} \in ({\mathbb {R}} \cup \{+ \infty \})^m,$

  $$\begin{aligned} \widetilde{K}_{\infty , \le {\bar{t}}}(f) \subset [\widetilde{K}_{\infty }(f)]_{\bar{t}}, \quad {K}_{\infty , \le {\bar{t}}}(f) \subset [{K}_{\infty }(f) ]_{\bar{t}}, \quad T_{\infty , \le {\bar{t}}}(f) \subset [T_{\infty }(f)]_{\bar{t}}. \end{aligned}$$

  These inclusions may be strict as shown in the following example.

Example 3.2

Let $f(x_1, x_2) := (x_1x_2 - 1)^2 + x_1^2$ be a polynomial function in two variables $x_1, x_2.$ We have f is strictly positive on ${\mathbb {R}}^2$ and so

$$\begin{aligned} \widetilde{K}_{\infty , \le 0}(f) = {K}_{\infty , \le 0}(f) = T_{\infty , \le 0}(f) = \emptyset . \end{aligned}$$

On the other hand, it is not hard to check that

$$\begin{aligned} \widetilde{K}_{\infty }(f) = {K}_{\infty }(f) = T_\infty (f) = \{0\}. \end{aligned}$$

Consequently,

$$\begin{aligned}{}[\widetilde{K}_{\infty }(f)]_0 = [{K}_{\infty }(f) ]_0 = [T_\infty (f)]_0 = \{0\}. \end{aligned}$$

Definition 3.4

Let $f:{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ be a map. We say that:

(i):

f is proper at a sublevel${\bar{t}} \in {\mathbb {R}}^m$ if for each compact subset $A\subset [{\mathbb {R}}^m]_{\bar{t}}$, the inverse image $f^{-1}(A)$ is also compact;

(ii):

f is proper if it is proper at every sublevel ${\bar{t}} \in {\mathbb {R}}^m.$

Remark 3.7

By definition, f is proper if, and only if, for each compact subset $A\subset {\mathbb {R}}^m$, the inverse image $f^{-1}(A)$ is also compact.

By definition, it is clear that if f is proper at the sublevel ${\bar{t}},$ then

$$\begin{aligned} \widetilde{K}_{\infty , \le {\bar{t}}}(f)={K}_{\infty , \le {\bar{t}}}(f)= T_{\infty , \le {\bar{t}}}(f) = \emptyset . \end{aligned}$$

The converse does not hold. For example, let $f:{\mathbb {R}}^2\rightarrow {\mathbb {R}}$ be the function defined by $f(x_1, x_2) := x_1 + x_2.$ We see that

$$\begin{aligned} \widetilde{K}_{\infty , \le {\bar{t}}}(f)={K}_{\infty , \le {\bar{t}}}(f)= T_{\infty , \le {\bar{t}}}(f)=\emptyset \end{aligned}$$

for all ${\bar{t}} \in {\mathbb {R}}$ but f is not proper at every sublevel. However, we have the following result.

Theorem 3.2

Let $f:{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ be a polynomial map. Assume that there exists $\bar{t}\in f({\mathbb {R}}^n)$ such that the section $[f({\mathbb {R}}^n)]_{\bar{t}}$ is bounded. Then the following statements are equivalent:

(i):

f is proper at the sublevel $\bar{t}$.

(ii):

f satisfies the Palais–Smale condition at the sublevel $\bar{t}$: $\widetilde{K}_{\infty , \le \bar{t}}(f)=\emptyset .$

(iii):

f satisfies the weak Palais–Smale condition at the sublevel $\bar{t}$: ${K}_{\infty , \le \bar{t}}(f)=\emptyset$.

(iv):

f is M-tame¹ at the sublevel $\bar{t}$: $T_{\infty , \le \bar{t}}(f)=\emptyset$.

Furthermore, the set $[f({\mathbb {R}}^n)]_{\bar{t}}$ is closed provided that one of the above equivalent conditions is satisfied.

Proof

The implications (i)$\Rightarrow$(ii)$\Rightarrow$(iii) are immediate from the definitions.

(iii)$\Rightarrow$(iv): This follows from Proposition 3.2.

(iv)$\Rightarrow$(i): Arguing by contradiction, assume that f is not proper at the sublevel $\bar{t}$. Then there exists a compact set $A\subset [{\mathbb {R}}^m]_{\bar{t}}$ such that $f^{-1}(A)$ is a non-compact subset in ${\mathbb {R}}^n$. By the continuity of f, the set $f^{-1}(A)$ is unbounded. Thus there exists a sequence $\{x^k\}\subset f^{-1}(A)$ satisfying $\displaystyle \lim \nolimits _{k\rightarrow \infty }\Vert x^k\Vert =+\infty$. Since $\{f(x^k)\}\subset A$, we have

$$\begin{aligned} f(x^k)\le \bar{t}\,\,\,\text{ for } \text{ all } \,\, k\in \mathbb {N}. \end{aligned}$$

For each $k\in \mathbb {N}$, we consider the problem

$$\begin{aligned} \mathrm{Min}_{\,{\mathbb {R}}^m_+} \{f(x) \,|\, x\in {\mathbb {R}}^n, f(x)\le \bar{t}\, \, \mathrm{and } \,\, \Vert x\Vert ^2=\Vert x^k\Vert ^2\, \}. \end{aligned}$$

Since $\{x\in {\mathbb {R}}^n \, | \, f(x)\le \bar{t}\, \, \mathrm{and } \,\, \Vert x\Vert ^2=\Vert x^k\Vert ^2\,\}$ is a nonempty compact subset of ${\mathbb {R}}^n$ and the objective function f is continuous, the problem admits a Pareto solution, say $y^k$. By the Fritz-John optimality conditions [22, Theorem 7.4], there are $(\alpha , \beta , \gamma )\in \left( {\mathbb {R}}^m_+\times {\mathbb {R}}^m_+\times {\mathbb {R}}\right) {\setminus } \{0\}$ such that

$$\begin{aligned} \sum _{i=1}^m\alpha _i\nabla f_i(y^k)+\sum _{i=1}^m \beta _i\nabla (f_i(\cdot )-\bar{t}_i)(y^k)+2\gamma y^k=0 \end{aligned}$$

or, equivalently,

$$\begin{aligned} \sum _{i=1}^m(\alpha _i+\beta _i)\nabla f_i(y^k)+2\gamma y^k=0. \end{aligned}$$

Put $\lambda _i := \alpha _i + \beta _i$ for $i := 1, \ldots , m$, and $\mu =2\gamma .$ We have

$$\begin{aligned} \sum _{i=1}^m\lambda _i\nabla f_i(y^k)+\mu y^k=0. \end{aligned}$$

Since $(\alpha , \beta , \gamma )\in \left( {\mathbb {R}}^m_+\times {\mathbb {R}}^m_+\times {\mathbb {R}}\right) {\setminus } \{0\}$, it holds that $(\lambda _1, \ldots , \lambda _m, \mu )\ne 0,$ and so $y^k\in \varGamma (f)$.

We therefore see that the sequence $\{y^k\}$ has the following properties:

• (a) $\{y^k\}\subset \varGamma (f)$,

• (b) $\Vert y^k\Vert =\Vert x^k\Vert \rightarrow +\infty$ as $k\rightarrow \infty$, and

• (c) $f(y^k)\le \bar{t}$ for all $k\in \mathbb {N}$.

Now the assumption that $[f({\mathbb {R}}^n)]_{\bar{t}}$ is bounded implies that the sequence $\{f(y^k)\}$ has an accumulation point, say $t\in {\mathbb {R}}^m$. Clearly, $t\le \bar{t}$. Thus $t\in T_{\infty , \le \bar{t}}(f)$, a contradiction.

We now assume that the condition (i) holds. To prove the set $[f({\mathbb {R}}^n)]_{\bar{t}}$ is closed, we need to show that it contains all its limit points. Indeed, let $\{t^k\}\subset [f({\mathbb {R}}^n)]_{\bar{t}}$ be an arbitrary sequence which converges to $t\in {\mathbb {R}}^m$. Then there exists a sequence $\{x^k\}\subset {\mathbb {R}}^n$ such that $f(x^k) = t^k \le \bar{t}$ for all $k\in \mathbb {N}$. Since $\displaystyle \lim \nolimits _{k\rightarrow \infty }f(x^k)=t$, there exists a compact set $A\subset {\mathbb {R}}^m$ such that $\{f(x^k)\}\subset A$. Clearly, the set $A\cap [{\mathbb {R}}^m]_{\bar{t}}$ is compact, and so is $f^{-1}\left( A\cap [{\mathbb {R}}^m]_{\bar{t}}\right)$ because f is proper at the sublevel $\bar{t}.$ It follows that the sequence $\{x^k\} \subset f^{-1}\left( A\cap [{\mathbb {R}}^m]_{\bar{t}}\right)$ has an accumulation point, say $\bar{x}\in {\mathbb {R}}^n$. By the continuity of f and the fact that $\displaystyle \lim \nolimits _{k\rightarrow \infty }f(x^k)=t$, one has $f(\bar{x})=t$. Consequently, $t\in f({\mathbb {R}}^n)$. Note that $t \le {\bar{t}}$. Therefore $t\in [f({\mathbb {R}}^n)]_{\bar{t}}$, as required. $\square$

4 Existence of Pareto solutions

The following result concerns the existence of Pareto solutions for polynomial vector optimization problems. To the best of our knowledge, the result is new even in the case $m = 1.$

Theorem 4.1

Let $f:{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ be a polynomial map. Assume that there exists $\bar{t}\in f({\mathbb {R}}^n)$ such that the section $[f({\mathbb {R}}^n)]_{\bar{t}}$ is bounded. Then the problem (VP) admits a Pareto solution, if one of the following equivalent conditions holds:

(i):

f is proper at the sublevel $\bar{t}$.

(ii):

f satisfies the Palais–Smale condition at the sublevel $\bar{t}$: $\widetilde{K}_{\infty , \le \bar{t}}(f)=\emptyset .$

(iii):

f satisfies the weak Palais–Smale condition at the sublevel $\bar{t}$: ${K}_{\infty , \le \bar{t}}(f)=\emptyset$.

(iv):

f is M-tame at the sublevel $\bar{t}$: $T_{\infty , \le \bar{t}}(f)=\emptyset$.

Proof

By Theorem 3.2, it suffices to assume that f is proper at the sublevel $\bar{t}$. We claim that $[f({\mathbb {R}}^n)]_{\bar{t}}$ is a nonempty compact subset of ${\mathbb {R}}^m$. Indeed, let $\{y^k\}$ be an arbitrary sequence in $[f({\mathbb {R}}^n)]_{\bar{t}}$. Then there exists a sequence $\{x^k\}\subset {\mathbb {R}}^n$ such that $f(x^k) = y^k \le \bar{t}$ for all $k\in \mathbb {N}.$ Since the section $[f({\mathbb {R}}^n)]_{\bar{t}}$ is bounded, $\{f(x^k)\}$ has a convergent subsequence. On the other hand, $[f({\mathbb {R}}^n)]_{\bar{t}}$ is a closed set in ${\mathbb {R}}^n$ due to Theorem 3.2. Thus $[f({\mathbb {R}}^n)]_{\bar{t}}$ is a nonempty compact set in ${\mathbb {R}}^n.$ Thanks to [5, Theorem 1], the set $f({\mathbb {R}}^n)$ has at least one Pareto efficient point, i.e., there exists $t^* \in f({\mathbb {R}}^n)$ such that $f(x) \notin t^* - ({\mathbb {R}}^m_+{\setminus }\{0\})$ for all $x\in {\mathbb {R}}^n$. This means that the problem (VP) admits a Pareto solution. The proof is complete. $\square$

As a consequence of Theorem 4.1, we obtain the following.

Corollary 4.1

Let $f:{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ be a polynomial map such that the section $[f({\mathbb {R}}^n)]_t$ is bounded for all $t\in {\mathbb {R}}^m.$ Then the problem (VP) admits a Pareto solution, provided that one of the following equivalent conditions holds:

(i):

f is proper.

(ii):

f satisfies the Palais–Smale condition: $\widetilde{K}_{\infty }(f)=\emptyset .$

(iii):

f satisfies the weak Palais–Smale condition: ${K}_{\infty }(f)=\emptyset .$

(iv):

f is M-tame: $T_{\infty }(f)=\emptyset .$

Remark 4.1

Hà [16] obtained some results on the existence of weak Pareto solutions for multiobjective optimization problems, where the objective function is bounded from below and satisfies the so-called $(\mathrm {PS})_1$condition. More recently, using the so-called quasiboundedness from below and refined subdifferential Palais–Smale condition (RSPS for short), Bao and Mordukhovich [2, 3] studied the existence of relative Pareto solutions for multiobjective optimization problems. Note that the existence theorems established in the papers mentioned do not ensure the existence of Pareto solutions, but only of weak and relative ones.

Regarding to Corollary 4.1 on the existence of Pareto solutions of the problem (VP), let us mention the following three remarks in comparison with previous results:

• Since the interior of the cone ${\mathbb {R}}^m_+$ is not empty, all the three relative Pareto solutions introduced in [3] agree and in fact they all are weak Pareto solutions. Hence, the results established in [2, 3, 16] only ensure the existence of weak Pareto solutions.

• Recall that a map $f:{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ is said to be bounded from below if there exists an element $a\in {\mathbb {R}}^m$ such that

  $$\begin{aligned} f({\mathbb {R}}^n)\subset a+{\mathbb {R}}^m_+. \end{aligned}$$

  Clearly, the map f is bounded from below if, and only if, it is quasibounded from below (see [2, 3]) in the sense that there exists a bounded set $A\subset {\mathbb {R}}^m$ such that

  $$\begin{aligned} f({\mathbb {R}}^n)\subset A+{\mathbb {R}}^m_+. \end{aligned}$$

  Furthermore, it follows from definitions that if f is bounded from below, then the section $[f({\mathbb {R}}^n)]_t$ is bounded for all $t\in {\mathbb {R}}^m$. The converse is true in the case $m = 1$ but fails to hold in the general case.

• Let $f :{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ a differentiable map. By definition, we can check that the (PS)$_1$ condition² (considered in [16]) holds for f is equivalent to the fact that $\widetilde{K}_{\infty }(f) = \emptyset ,$ which means that f satisfies the Palais–Smale condition. On the other hand, the (RSPS) condition introduced in [3] is stronger than the Palais–Smale condition. To see this, recall that the map f satisfies the (RSPS) condition if every sequence $\{x^k\} \subset {\mathbb {R}}^n$ such that $\nu _f(x^k) \rightarrow 0$ as $k \rightarrow \infty$ contains a convergent subsequence, provided that $\{f(x^k)\}$ is quasibounded from below, i.e.

  $$\begin{aligned} \{f(x^k)\} \subset A + {\mathbb {R}}^m_+ \end{aligned}$$

  for some bounded set $A\subset {\mathbb {R}}^m.$ By definition, if f satisfies the (RSPS) condition, then it also satisfies the Palais–Smale condition, but the converse fails to hold as can be checked directly for the polynomial

  $$\begin{aligned} f:{\mathbb {R}}^2 \rightarrow {\mathbb {R}}^2, \quad (x_1, x_2) \mapsto f(x_1, x_2) := (x_1^2 + x_2^2, x_1^2 - x_2^2). \end{aligned}$$

  (This polynomial f is proper, and so it satisfies the Palais–Smale condition; furthermore, we have

  $$\begin{aligned} \nu _f(k, 0) = 0 \quad \text { and } \quad f(k, 0) \in \{(0, 0)\} + {\mathbb {R}}^2_+ \quad \text { for all } k \in \mathbb {N}, \end{aligned}$$

  which implies that f does not satisfy the (RSPS) condition.)

According to the above discussions, it turns out that our results, in the polynomial setting, improve and extend [16, Theorem 4.1], [2, Theorem 4] and [3, Theorem 4.4].

Let us illustrate Theorem 4.1 and Corollary 4.1 with some examples.

Example 4.1

Let us consider the Motzkin polynomial (see [19, 33])

$$\begin{aligned} M(x_1, x_2) := x_1^2x_2^4 + x_1^4 x_2^2 - 3 x_1^2x_2^2 + 1. \end{aligned}$$

It is not difficult to see that $M(x_1, x_2) \ge 0$ for all $x := (x_1, x_2) \in {\mathbb {R}}^2.$ Moreover, we have

• If $0< t < 1,$ then $M^{-1}(t)$ is the union of 4 ovals.

• If $1 < t,$ then $M^{-1}(t)$ is the union of 4 non-compact components.

• The set $M^{-1}(1)$ is non-compact:

  $$\begin{aligned}M^{-1}(1) = \{x_1 = 0 \} \cup \{x_2 = 0 \} \cup \{x_1^2 + x_2^2 = 3 \}.\end{aligned}$$

Consequently, the polynomial M is proper at the sublevel $\bar{t}$ if, and only if, $\bar{t} < 1.$ Thanks to Theorem 4.1, M attains its infimum on ${\mathbb {R}}^2.$ In fact, we can see that the set of optimal solutions of the problem $\inf _{x \in {\mathbb {R}}^2} M(x)$ is $M^{-1}(0) = \{(1, 1), (1, -\,1), (-\,1, 1), (-\,1, 1)\}.$ Note that $1 \in T_\infty (M)$ and hence, by Proposition 3.2, M does not satisfy the Palais–Smale and weak Palais–Smale conditions. Therefore, [16, Theorem 4.1], [2, Theorem 4], [3, Theorem 4.4], and [32, Theorem 2] cannot be applied for this example.

Example 4.2

Let $f:{\mathbb {R}}^3\rightarrow {\mathbb {R}}^2$ be the polynomial map defined by

$$\begin{aligned} f(x_1, x_2, x_3)=(x_1^2+x_2^2+x_3^2, x_3^3). \end{aligned}$$

It is not hard to see that f is proper and $[f({\mathbb {R}}^3)]_t$ is bounded for each $t\in {\mathbb {R}}^2.$ By Corollary 4.1, the problem (VP) has at least one Pareto solution. On the other hand, f is not bounded from below, and so, [16, Theorem 4.1], [2, Theorem 4], and [3, Theorem 4.4] cannot be applied for this example.

The next example shows that if the objective function satisfies one of the equivalent conditions in Theorem 4.1 and $f({\mathbb {R}}^n)$ has at least a bounded section, then the set of Pareto solutions of (VP) is nonempty.

Example 4.3

Consider the polynomial map

$$\begin{aligned} f :{\mathbb {R}}^3 \rightarrow {\mathbb {R}}^3, \quad (x_1, x_2, x_3) \mapsto (x_1, x_2, M(x_1, x_2) + x_3^2), \end{aligned}$$

where M is the Motzkin polynomial defined in Example 4.1. We have

$$\begin{aligned} f({\mathbb {R}}^3) = \left\{ t =(t_1, t_2, t_3) \in {\mathbb {R}}^3 \, | \, t_3 \ge M(t_1, t_2) \right\} \end{aligned}$$

and the section $[f({\mathbb {R}}^3)]_t$ is unbounded for every $t = (t_1, t_2, t_3) \in {\mathbb {R}}^3$ with $t_3 \ge 1.$ On the other hand, if we take $\bar{t} := (1, 1, 0) \in {\mathbb {R}}^3$ then the section $[f({\mathbb {R}}^3)]_{\bar{t}}$ is bounded and f is proper at the sublevel $\bar{t}.$ Thus, by Theorem 4.1, the problem (VP) has at least one Pareto solution. However, f is not bounded from below, and so [16, Theorem 4.1], [2, Theorem 4], and [3, Theorem 4.4] cannot be applied for this example.

In the rest of the paper we shall give some classes of vector optimization problems, which satisfy the conditions in Theorem 4.1. We start with the class of linear vector optimization problems.

Corollary 4.2

(compare [11, Theorem 6.5]) Let $f_i(x) := \langle a_i, x\rangle +b_i$, where $a_i\in {\mathbb {R}}^n$ and $b_i \in {\mathbb {R}}$ for all $i = 1, \ldots , m.$ Assume that the set of vectors $\{a_1, \ldots , a_m\}$ is linearly independent. If $f({\mathbb {R}}^n)$ has a bounded section, then (VP) admits a Pareto solution.

Proof

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

$$\begin{aligned} \nu _f(x)=\min _{\sum _{i=1}^m|\lambda _i|=1}\left\| \sum _{i=1}^m \lambda _i\nabla f_i(x)\right\| =\min _{\sum _{i=1}^m|\lambda _i|=1}\left\| \sum _{i=1}^m \lambda _i a_i\right\| . \end{aligned}$$

By the compactness of the set $\{\lambda =(\lambda _1, \ldots , \lambda _m)\in {\mathbb {R}}^m\,\,|\,\, \sum _{i=1}^m|\lambda _i|=1\}$, there exists $\bar{\lambda }=(\bar{\lambda }_1, \ldots , \bar{\lambda }_m)\in {\mathbb {R}}^m$ with $\sum _{i=1}^m|\bar{\lambda }_i|=1$ such that

$$\begin{aligned} \nu _f(x)=\left\| \sum _{i=1}^m \bar{\lambda }_i a_i\right\| =:\delta . \end{aligned}$$

Since the set of vectors $\{a_1, \ldots , a_m\}$ is linearly independent and $\sum _{i=1}^m|\bar{\lambda }_i|=1$, we have $\nu _f(x)=\delta >0$ for all $x\in {\mathbb {R}}^n$. Consequently,

$$\begin{aligned} \widetilde{K}_{\infty }(f)={K}_{\infty }(f)={T}_{\infty }(f)=\emptyset . \end{aligned}$$

Thanks to Theorem 4.1, (VP) admits a Pareto solution. $\square$

We finish this section with a generic class of polynomial vector optimization problems having at least one Pareto solution. To do this, we begin with some definitions. If $\kappa = (\kappa _1, \ldots , \kappa _n) \in \mathbb {N}^n,$ we denote by $x^\kappa$ the monomial $x_1^{\kappa _1} \ldots x_n^{\kappa _n}$ and by $| \kappa |$ the sum $\kappa _1 + \cdots + \kappa _n.$ Note that when $\kappa = (0, \ldots , 0),$$x^\kappa = 1.$

Let $f :{\mathbb {R}}^n \rightarrow {\mathbb {R}}$ be a polynomial function. Suppose that f is written as $f = \sum _{\kappa } a_\kappa x^\kappa .$ By the Newton polyhedron at infinity of f,  denoted by $\mathcal {N}(f),$ we mean the convex hull in ${\mathbb {R}}^n$ of the set $\{\kappa \ | \ a_\kappa \ne 0\} \cup \{0\}.$ The polynomial f is said to be convenient if $\mathcal {N}(f)$ intersects each coordinate axis in a point different from the origin. The Newton boundary at infinity of f, denoted by $\mathcal {N}_{\infty }(f),$ is defined as the set of the faces of $\mathcal {N}(f)$ which do not contain the origin 0 in ${\mathbb {R}}^n.$ For each face $\varDelta$ of $\mathcal {N}_\infty (f),$ we define the principal part of fat infinity with respect to $\varDelta ,$ denoted by $f_\varDelta ,$ as the sum of the terms $a_\kappa x^\kappa$ such that $\kappa \in \varDelta .$

Let $f := (f_1, \ldots , f_m) :{\mathbb {R}}^n \rightarrow {\mathbb {R}}^m$ be a polynomial map. We say that f is convenient if all its components $f_i$ are convenient. Let $\mathcal {N}(f)$ denote the Minkowski sum $\mathcal {N}(f_1) + \cdots + \mathcal {N}(f_m),$ i.e.,

$$\begin{aligned} \mathcal {N}(f) := \{\kappa ^1 + \cdots + \kappa ^m \ | \ \kappa ^i \in \mathcal {N}(f_i) \ \text { for all } \ i = 1, \ldots , m\}. \end{aligned}$$

We denote by $\mathcal {N}_\infty (f)$ the set of faces of $\mathcal {N}(f)$ which do not contain the origin 0 in ${\mathbb {R}}^n.$ Let $\varDelta$ be a face of the $\mathcal {N}(f).$ According to Đinh et al. [9, Lemma 2.1], we have a unique decomposition $\varDelta = \varDelta _1 + \cdots + \varDelta _m,$ where $\varDelta _i$ is a face of $\mathcal {N}(f_{i})$ for $i = 1, \ldots , m.$ We denote by $f_\varDelta$ the map $(f_{1, \varDelta _1}, \ldots , f_{m, \varDelta _m}) :{\mathbb {R}}^n \rightarrow {\mathbb {R}}^m$, where $f_{i, \varDelta _i}$ is the principal part of $f_i$ at infinity with respect to $\varDelta _i.$

Definition 4.1

(see [26, 27]) We say that $f = (f_1, \ldots , f_m)$ is Khovanskii non-degenerate at infinity if, and only if, for any face $\varDelta$ of $\mathcal {N}_\infty (f)$ and for all $x \in ({\mathbb {R}} {\setminus } \{0\})^n \cap f_\varDelta ^{-1}(0),$ we have

$$\begin{aligned} \text {rank} \begin{pmatrix} x_1\frac{\partial f_{1, \varDelta _1}}{\partial x_1}(x) &{} \cdots &{} x_n \frac{\partial f_{1, \varDelta _1}}{\partial x_n}(x) \\ \vdots &{} \cdots &{} \vdots \\ x_1\frac{\partial f_{m, \varDelta _m}}{\partial x_1}(x) &{} \cdots &{} x_n \frac{\partial f_{m, \varDelta _m}}{\partial x_n}(x) \end{pmatrix} = m. \end{aligned}$$

Remark 4.2

We should emphasize that the class of polynomial maps (with fixed Newton polyhedra), which are non-degenerate at infinity, is an open and dense semi-algebraic set in the corresponding Euclidean space of data. For more details, see [9] and [19, Theorem 5.2].

We now present an efficient consequence of Theorem 4.1 ensuring the existence of Pareto solutions for the class of polynomials which are convenient and Khovanskii non-degenerate at infinity.

Corollary 4.3

(Frank–Wolfe type theorem) Let $f :{\mathbb {R}}^n\rightarrow {\mathbb {R}}^m$ be a polynomial map. Suppose that f is convenient and Khovanskii non-degenerate at infinity. If $f({\mathbb {R}}^n)$ has a bounded section, then (VP) admits a Pareto solution.

Proof

Thanks to [10, Theorem 3.2], $\widetilde{K}_{\infty }(f)=\emptyset$. Then the assertion follows immediately from Theorem 4.1. $\square$

5 Conclusions

In this paper, we obtained some results on the existence of Pareto solutions of polynomial vector optimization problems. Some relationships between Palais–Smale conditions, M-tameness, and properness are also examined. Further research for optimization problems with constraints will be studied in future work.