A study of interval optimization problems

Abstract

We study optimization problems with interval objective functions. We focus on set-type solution notions defined using the Kulisch–Miranker order between intervals. We obtain bounds for the asymptotic cones of level, colevel and solution sets that allow us to deduce coercivity properties and coercive existence results. Finally, we obtain various noncoercive existence results. Our results are easy to check since they are given in terms of the asymptotic cone of the constraint set and the asymptotic functions of the end point functions. This work extends, unifies and sheds new light on the theory of these problems.

1 Introduction

Optimization problems are significant since they are applied to many research fields. As pointed out in [23], depending on the choice of the coefficients of the objective function, we have different types of problems: when they are numbers, we have deterministic problems; when they are random variables with known distributions, we have stochastic problems; and when they are closed intervals, we have interval problems. The last type of problems is important since it allows us to deal with nonstatistical and nonprobabilistic uncertain optimization problems. The aim of this paper is to develop a general theory for studying these problems.

There exist two types of solution notions for an interval optimization problem: vector- and set-type solutions. In this paper, we focus on the latter, where the images of the objective function are compared using the Kulisch–Miranker order. An interval optimization problem, by considering this order, can be cast as a bi-objective optimization problem and it is a particular case of a set optimization problem. Consequently, some of our results are consequences of well-known results for such problems. However, we study the interval optimization problem from scratch and obtain our main results by exploiting the structure of interval functions. An advantage of our results lies in the fact that they are easy to check since they are given in terms of the asymptotic cone of the constraint set and the asymptotic functions of the end point functions.

The paper is organized as follows. In Sect. 2, we formulate the problem, introduce the notation, recall notions of interval arithmetic, asymptotic cones, asymptotic functions, scalar minimization problems, convergence of intervals and orders between them. We define vector- and set-type solution notions of an interval optimization problem. We cast this problem as a bi-objective optimization problem. In Sect. 3, we study properties of level, colevel, and set-type solutions, prove an existence result when the constraint set is bounded and provide a formula for the solution set by using linear scalarizations. In Sect. 4, we recall some classes of interval functions and study their properties. In Sect. 5, we deal with problems with unbounded data. We use asymptotic cones and asymptotic functions to obtain bounds for the asymptotic cones of level, colevel and solution sets. By using this information, we obtain coercivity properties and coercive existence results. We also obtain various noncoercive existence results. Finally, in Sect. 6, we provide a summary of conclusions.

2 Formulation of the problem, notation and preliminaries

In the last years, several problems in science and technology have been formulated as an interval optimization problem. We illustrate this with an example.

Example 1

[19] The portfolio selection problem of n investment types can be formulated as the following scalar optimization problem:

$$\begin{aligned} {\mathrm {Minimize}}&\varphi (x):=\frac{1}{2}\sum \limits _{i,j=1}^n\sigma _{ij}x_ix_j \\ {\mathrm {subject}}\; {\mathrm {to}}&\sum \limits _{i=1}^nx_i=1,\; x_i\ge 0,\; i\in \{1,\ldots ,n\}, \end{aligned}$$

where $(\sigma _{ij})$ is a symmetric matrix with $\sigma _{ij}$ being the covariance between $R_i$ and $R_j$ where $R_i$ is the return and $x_i$ is the investment fund devoted to the investment type $i\in \{1,\ldots ,n\}$, and $\varphi (x)$ is the risk of investment of $x=(x_1,\ldots ,x_n)^\top$. Regrettably, due to various kinds of uncertainties, it is difficult to determine the coefficients $\sigma _{ij}$, but we can determine intervals $[a_{ij}^L,a_{ij}^U]$ that contain them. So, we can reformulate this problem as follows:

$$\begin{aligned} {\mathrm {Minimize}}&f(x):=\frac{1}{2}\sum \limits _{i,j=1}^n[a_{ij}^L,a_{ij}^U]x_ix_j \\ {\mathrm {subject}}\; {\mathrm {to}}&\sum \limits _{i=1}^nx_i=1,\; x_i\ge 0,\; i\in \{1,\ldots ,n\}. \end{aligned}$$

By using operations with intervals, we can write the objective function as $f(x)=[f^L(x),f^U(x)]$, that is an interval function.

In this paper, we study the interval optimization problem (for short, IOP) formulated as follows:

$$\begin{aligned} ({{\mathcal {P}}})\;\; \; \begin{array}{l} {\mathrm { Minimize }}\;\, f(x):=[f^L(x),f^U(x)] \\ {\mathrm { subject\; to }} \;\; x\in C, \end{array} \end{aligned}$$

where $C\subset {\mathbb {R}}^n$ is a nonempty set and $f^L,f^U:{\mathbb {R}}^n\rightarrow \overline{{\mathbb {R}}}$ are proper scalar functions with domain C and $f^L(x)\le f^U(x)$ for all $x\in C$. Clearly, $f^L(x)=f^U(x)=+\infty$ for all $x\notin C$, so we set $f(x)=\emptyset$ for such x. We denote the interval function by (C, f) and its end point functions by $(C,f^L)$ and $(C,f^U)$.

We list some interval functions that have been studied in the literature.

Example 2

Consider $(C_i,f_i)$ for $i\in \{1,\ldots ,4\}:$

• (i) [21] $C_1=\{x:Ax=b,x\ge 0\}$ and $f_1(x)=\sum \nolimits _{i=1}^nx_i[a^L_i,a^U_i]$;

• (ii) [19] $C_2=\{x:\sum _{i=1}^nx_i=1,x\ge 0\}$ and $f_2(x)=\frac{1}{2}\sum \nolimits _{i,j=1}^nx_ix_j[a^L_{ij},a^U_{ij}]$;

• (iii) [17] $C_3=\{x:Ax= b,x\ge 0\}$ and $f_3(x)=\dfrac{\sum \nolimits _{i=1}^nx_i[a^L_i,a^U_i]+[c^L,c^U]}{\sum \nolimits _{i=1}^nx_i[b^L_i,b^U_i]+[d^L,d^U]}$;

• (iv) [3] $C_4=\{x:\sum _{j=1}^nx_{ij}=a_i,\sum \nolimits _{i=1}^m x_{ij}=b_j,\sum _{i=1}^m a_i=\sum \nolimits _{j=1}^nb_j, x\ge 0\}$       and $f_4(x)=\dfrac{\sum \nolimits _{i=1}^m\sum \nolimits _{j=1}^nx_{ij}[a^L_{ij},a^U_{ij}]}{\sum \nolimits _{i=1}^m\sum \nolimits _{j=1}^nx_{ij}[b^L_{ij},b^U_{ij}]}$.

There exist various solution notions for problem $({\mathcal {P}})$. For instance, we have vector-type solutions that have been defined in [18] as follows.

Definition 1

A vector $\bar{x}$ is said to be a vector-type solution of problem $({\mathcal {P}})$, denoted by ${\bar{x}}\in {\mathrm {Eff}}(C,f)$, if ${\bar{x}}\in C$ and $f^L({\bar{x}})=\inf f(C)$; i.e., ${\bar{x}}\in \arg \min _{C} f^L$.

This type of solution is not suitable since other elements of $f({\bar{x}})$ that could be ‘bad elements’ are ignored. This occurs since when finding them we do not compare the images of the objective function. To compare them, we require some orders between intervals. In this work, we consider the Kulisch–Miranker order introduced in [16].

Let ${\mathcal {K}}_c:=\{A=[a^L,a^U]:a^L,a^U\in {\mathbb {R}}, a^L\le a^U\}$ be the family of nonempty bounded closed intervals. For A and B being from this family, the Kulisch–Miranker order between them is defined by:

$$\begin{aligned} A\le ^{s}B\Longleftrightarrow a^L\le b^L, a^U\le b^U\quad \text{ and }\quad A<^{s}B\Longleftrightarrow a^L< b^L,\, a^U< b^U. \end{aligned}$$

This order has been employed to define a standard for interval arithmetic in [15].

We recall some operations with intervals $A,B\in {\mathcal {K}}_c$ and $\lambda \in {\mathbb {R}}$:

$$\begin{aligned} A+B:= & {} [a^L+b^L,a^U+b^U], \\ \lambda A:= & {} \left\{ \begin{array}{ll}\, [\lambda a^L ,\lambda a^U], &{} \hbox {if }\lambda \ge 0; \\ \, [\lambda a^U ,\lambda a^L], &{} \hbox {if }\lambda <0, \end{array} \right. \\ A/B:= & {} [\min \, T,\max \, T], \end{aligned}$$

where $T:=\{\frac{a^L}{b^L},\frac{a^L}{b^U},\frac{a^U}{b^L},\frac{a^U}{b^U}\}$ with $b^L,b^U\ne 0$ (see [19, 22, 23]).

Remark 1

(i) Let K be a pointed convex cone of a real linear space Y. The following orders between nonempty sets U and V from Y have been used in set optimization (see [9, 12, 14]): $U\preccurlyeq ^l V$ if $V\subset U+K$; $U\preccurlyeq ^u V$ if $U\subset V-K$; and $U\preccurlyeq ^s V$ if $U\preccurlyeq ^l V$ and $U\preccurlyeq ^u V$. If in addition K is solid, then $U\prec ^{l}V$ if $V\subset U+{\text {int}}K$; $U\prec ^{u}V$ if $U\subset V-{\text {int}}K$; and $U\prec ^{s}V$ if $U\prec ^{l}V$ and $U\prec ^{u}V$. Clearly, if $Y={\mathbb {R}}$, $K={\mathbb {R}}_+$ and the sets are from ${\mathcal {K}}_c$, then $\preccurlyeq ^s$ and $\prec ^{s}$ coincide with $\le ^s$ and $<^s$, respectively.

(ii) The order $\le ^s$ is compatible with the addition and multiplication with nonnegative numbers; i.e., for all $A,B,C,D\in {\mathcal {K}}_c$ it holds that $A\le ^s B$ and $C\le ^s D$ imply $A+C\le ^s B+D$, $A\le ^s B$ and $\lambda \ge 0$ imply $\lambda A\le ^s \lambda B$. The order $<^s$ is compatible with the addition and multiplication with positive numbers.

(iii) [10] The order $A\le ^{cw}B$ is defined by $a^C\le b^C$ and $a^W\le b^W$, where $a^C:=\frac{1}{2}(a^L+a^U)$ is the center and $a^W:=\frac{1}{2}(a^U-a^L)$ is the half-width of the interval A. The orders $\le ^s$ and $\le ^{cw}$ are not comparable. Indeed, $[5,7]\le ^s[10,11]$ but $[5,7]\not \le ^{cw}[10,11]$ and $[5,7]\not \le ^s[4,9]$ but $[5,7]\le ^{cw}[4,9]$.

(iv) [4] The order $A\le ^{ls}B$ is defined by $a^L\le b^L$ and $a^S\le b^S$, where $a^S:=a^U-a^L$ is the width of the interval A; $A<^{ls}B$ by $A\le ^{ls}B$ and $A\ne B$; and $A<^{lu}B$ by $A\le ^{s}B$ and $A\ne B$. Clearly, $A<^{ls}B$ implies $A<^sB$ which in turn implies $A<^{lu}B$. The reverse implication does not hold. Indeed, $[1,2]\le ^{lu}[1,3]$ but $[1,2]\nless ^s[1,3]$. For a comparative study of orders between intervals see [13].

(v) [8] The generalized Hukuhara difference between intervals always exists and is defined by $A\ominus _{gH}B:=[\min \{a^L-b^L,a^U-b^U\},\max \{a^L-b^L,a^U-b^U\}]$. It is easy to check that $A\le ^s B$ iff $(A\ominus _{gH}B)^U\le 0$. Moreover, if $A\le ^{cw}B$ then $(A\ominus _{gH}B)^L\le 0$ and $(A\ominus _{gH}B)^C\le 0$. This difference has been used in [8] to define a comparison index for interval orders.

Set-type solution notions for problem $({\mathcal {P}})$ have been defined in [18] via comparisons of the images by using the Kulisch–Miranker order as follows.

Definition 2

A vector ${\bar{x}}\in C$ is said to be:

• an s-efficient solution of problem $({\mathcal {P}})$, denoted by ${\bar{x}}\in {\text {Eff}}_s(C,f)$, if $x\in C$ and $f(x)\le ^s f({\bar{x}})$ imply $f({\bar{x}})= f(x)$.

• a weakly s-efficient solution of problem $({\mathcal {P}})$, denoted by ${\bar{x}}\in {\text {WEff}}_s (C,f)$, if there is no $x\in C$ such that $f(x)<^s f({\bar{x}})$.

We will study only weakly s-efficient solutions.

Remark 2

• (i) ${\text {Eff}}_s(C,f)\subset {\text {WEff}}_s(C,f)$.

• (ii) If $f^L= f^U=\varphi$, with $\varphi$ being a scalar function, then ${\text {Eff}}_s(C,f)= {\text {WEff}}_s(C,f)=\arg \min _C\varphi$.

• (iii) Problem $({\mathcal {P}})$ can be cast as the bi-objective optimization problem:

  $$\begin{aligned} \begin{array}{l} {\mathrm { Minimize }} \;\;{\tilde{f}}(x):= \left( f^L(x),f^U(x)\right) ^\top \\ {\mathrm { subject \; to }}\;\; x\in C, \end{array} \end{aligned}$$

  where ${\tilde{f}}$ is the associated vector function and ${\mathbb {R}}^2$ is ordered by: $x\le _{{\mathbb {R}}^2_+} y$ if $y-x\in {\mathbb {R}}^2_+$, i.e., $x_1\le y_1$ and $x_2\le y_2$ and $x<_{{\mathbb {R}}^2_+}y$ if $y-x\in {\mathrm {int}}\,{\mathbb {R}}^2_+$, i.e., $x_1< y_1$ and $x_2< y_2$. A vector ${\bar{x}}\in C$ is said to be a weakly efficient solution of this problem, denoted by ${\bar{x}}\in {\text {WEff}}(C,{\tilde{f}})$, if there is no $x\in C$ such that ${\tilde{f}}(x)<_{{\mathbb {R}}^2_+} {\tilde{f}}({\bar{x}})$. As $[a^L,a^U] <^s [b^L,b^U]$ iff $\left( a^L, a^U\right) ^\top <_{{\mathbb {R}}^2_+}\left( b^L,b^U\right) ^\top$, we have

  $$\begin{aligned} {\text {WEff}}_s(C,f)={\text {WEff}}(C,{\tilde{f}}). \end{aligned}$$

  (1)

  Clearly, ${\tilde{f}}({\text {WEff}}_s(C,f))={\mathrm {WMin}}{\tilde{f}}(C):=\{y\in {\tilde{f}}(C):(y-{\mathrm {int}}\,{\mathbb {R}}^2_+)\cap {\tilde{f}}(C)=\emptyset \}$.

• (iv) Let $\le ^a$, $<^a$ and $\le ^b$, $<^b$ be orders in ${\mathcal {K}}_c$. We can define set-type solutions of problem $({\mathcal {P}})$ by using them; i.e., we have ${\text {Eff}}_t (C,f)$ and ${\text {WEff}}_t (C,f)$ with $t\in \{a,b\}$. Clearly, if $A\le ^a B$ implies $A\le ^bB$ (resp. $A<^a B$ implies $A<^b B)$ for all $A,B\in {\mathcal {K}}_c$, then ${\text {Eff}}_b (C,f)\subset {\text {Eff}}_a (C,f)$ (resp. ${\text {WEff}}_b (C,f)\subset {\text {WEff}}_a (C,f))$. For the orders in Remark 1, we have ${\text {WEff}}_{lu} (C,f)\subset {\text {WEff}}_s(C,f)\subset {\text {WEff}}_{ls}(C,f)$.

For an interval function (C, f), we denote by ${\mathrm {Gph}}(C,f):=\{(x,y)\in C\times {\mathbb {R}}:y\in f(x)\}$ its graph, by ${\mathrm {Epi}}_s(C,f):=\{(x,Y)\in C\times {\mathcal {K}}_c:f(x)\le ^s Y\}$ its epigraph, by ${\mathrm {Coepi}}_s(C,f):=\{(x,Y)\in C\times {\mathcal {K}}_c:Y\not <^sf(x)\}$ its coepigraph, by ${\mathrm {Lev}}_s(C,f,Y):=\{x\in C:f(x)\le ^s Y\}$ its level set at height $Y\in {\mathcal {K}}_c$ and by ${\mathrm {Colev}}_s(C,f,Y):=\{x\in C:Y\not <^sf(x)\}$ its colevel set at height $Y\in {\mathcal {K}}_c$, by $f(A):=\cup _{x\in A}f(x)$ the image of $A\subset {\mathbb {R}}^n$, and by $(C,{\tilde{f}})$ the associated vector function ${\tilde{f}}:=(f^L,f^U)^\top$. Clearly, ${\mathrm {Epi}}_s(C,f)\subset {\mathrm {Coepi}}_s(C,f)$, ${\mathrm {Gph}}(C,f)\subset {\mathrm {Coepi}}_s(C,f)$ and ${\mathrm {Lev}}_s(C,f,Y)\subset {\mathrm {Colev}}_s(C,f,Y)$.

We recall some notions that allow us to establish coercivity properties and existence results for the scalar minimization problem:

$$\begin{aligned} ({\mathcal {P}}') \quad \begin{array}{l} \text{ Minimize } \varphi (x) \\ \text{ subject } \text{ to } x\in C, \end{array} \end{aligned}$$

where $\varphi :{\mathbb {R}}^n\rightarrow {\overline{{\mathbb {R}}}}$ is a proper function with ${\mathrm {dom}}\,\varphi =C$, i.e., $\varphi (x)=+\infty$ for all $x\not \in C$. We denote the function by $(C,\varphi )$, by $\arg \min \nolimits _{C} \varphi$ its solution set, by ${\mathrm {lev}}(C,\varphi ,\lambda ):=\{x\in C:\varphi (x)\le \lambda \}$ its level set at height $\lambda \in {\mathbb {R}}$ and by ${\mathrm {epi}}(C,\varphi ):=\{(x,y)\in C\times {\mathbb {R}}:\varphi (x)\le y\}$ its epigraph.

When the constraint set is bounded, we have the following existence result: if $(C,\varphi )$ is lsc with C compact, then $\arg \min \nolimits _{C} \varphi$ is nonempty and compact. To obtain an existence result when the constraint is unbounded, we use the notions of asymptotic cone and asymptotic function (see [1, 2, 20]).

The asymptotic cone of a set $C\subset {\mathbb {R}}^{n}$ is defined by

$$\begin{aligned} C^{\infty }:=\left\{ u\in {\mathbb {R}}^{n}:\exists t_{k}\rightarrow +\infty ,\exists x^{k} \in C \text{ s.t. } \frac{x^{k}}{t_{k}}\rightarrow u\right\} \, \text{ and } \,\emptyset ^\infty =\{0\}. \end{aligned}$$

(2)

This notion characterizes the boundedness of a set as follows:

$$\begin{aligned} C\, \text{ is } \text{ bounded }\,\;\Longleftrightarrow \,\; C^\infty =\{0\}. \end{aligned}$$

(3)

If C is closed and convex, then for all $x\in C$

$$\begin{aligned} C^{\infty }=\Big \{u\in {\mathbb {R}}^{n}:~x+\lambda u\in C,~\forall \lambda \ge 0 \Big \}. \end{aligned}$$

(4)

The asymptotic function of $(C,\varphi )$ is the function $\varphi ^{\infty }:{\mathbb {R}}^{n}\rightarrow \overline{{\mathbb {R}}}$ with domain D, denoted by $(D,\varphi ^\infty )$, such that ${\mathrm {epi}}(D,\varphi ^{\infty })=[{\mathrm {epi}}(C,\varphi )]^{\infty }$. Clearly, $D\subset C^\infty$ and

$$\begin{aligned} \varphi ^{\infty } (u) =\inf \left\{ \liminf _{k \rightarrow + \infty } \frac{\varphi (t_k u^k)}{t_k} : t_k \rightarrow +\infty , u^k \rightarrow u \right\} . \end{aligned}$$

(5)

If $(C,\varphi )$ is lsc and convex with C closed and convex, then for all $x\in C$

$$\begin{aligned} \varphi ^{\infty }(u)=\lim _{t\rightarrow +\infty }\frac{\varphi (x+tu)-\varphi (x)}{t}= \sup _{t > 0}\frac{\varphi (x+tu)-\varphi (x)}{t}. \end{aligned}$$

(6)

For any $\lambda \in {\mathbb {R}}$, we have

$$\begin{aligned} {\mathrm {lev}}(C,\varphi ,\lambda )^\infty \subset \{v\in C^\infty :\varphi ^\infty (v)\le 0\}, \end{aligned}$$

(7)

where the equality holds, if $(C,\varphi )$ is lsc and convex with C is closed and convex, and the level set is nonempty. The right-hand set in (7), that is a closed cone, plays an important role in our approach. We denote it by

$$\begin{aligned} R(C,\varphi ):=\{v\in C^\infty :\varphi ^\infty (v)\le 0\}. \end{aligned}$$

We say that $(C,\varphi )$ is coercive if $\varphi ^{\infty }> 0$ on $C^\infty \backslash \{0\}$, and that it is level-bounded if all its level sets are bounded. It is easy to check that $(C,\varphi )$ is level-bounded iff $\lim _{||x ||\rightarrow + \infty }\varphi (x)=+ \infty$, and that $(C,\varphi )$ is coercive iff $R(C,\varphi )=\{0\}$. From (3) and (7), we have that if $(C,\varphi )$ is coercive, then it is level-bounded.

We recall a necessary condition from [1].

Theorem 1

If $\arg \min \nolimits _{C} \varphi$ is nonempty, then $\varphi ^\infty \ge 0$ on $C^\infty$.

We recall a coercive existence result (see [1, Corollary 3.2.4] or [2, Proposition 3.1.3]).

Theorem 2

• (a) If $(C,\varphi )$ is lsc with C closed and has one bounded level set, then $\arg \min \nolimits _{C} \varphi$ is nonempty and compact.

• (b) If $(C,\varphi )$ is lsc and convex with C closed and convex, then the following statements are equivalent:

  • (i) $R(C,\varphi )=\{0\}$ (or equivalently $(C,\varphi )$ is coercive); 

  • (ii) $(C,\varphi )$ is level-bounded (or equivalently $\lim _{||x ||\rightarrow + \infty }\varphi (x)=+ \infty );$

  • (iii) $\arg \min \nolimits _{C} \varphi$ is nonempty and compact.

We recall a noncoercive existence result from [1, Theorem 15.1.1]. To do this, we recall the set:

$$\begin{aligned} K(C,\varphi ):=\{v\in C^\infty :\varphi ^\infty (v)=0\}. \end{aligned}$$

If $(C,\varphi )$ is convex with C convex and $\varphi ^\infty \ge 0$ on $C^\infty$, then $K(C,\varphi )$ is a closed convex cone. Moreover, $K(C,\varphi )=-K(C,\varphi )$ iff $K(C,\varphi )$ is a linear subspace.

Theorem 3

If $(C,\varphi )$ is lsc and convex with C closed and convex, $\varphi ^\infty \ge 0$ on $C^\infty$, and $K(C,\varphi )=-K(C,\varphi )$, then $\arg \min \nolimits _{C} \varphi$ is nonempty and closed (possibly unbounded).

A function $(C,\varphi )$ is said to be asymptotically directionally constant (adc), if $v\in K(C,\varphi )$ implies $\varphi (x+\rho v)=\varphi (x)$ for all $x\in C$ and $\rho \in {\mathbb {R}}$. Under the hypothesis of Theorem 3, we have $K(C,\varphi )=-K(C,\varphi )$ iff $(C,\varphi )$ is adc (see [2], for more details).

We recall another noncoercive existence result from [11] that holds without convexity assumptions. To this end, we approximate problem $(\mathcal {P'})$ by the family of problems with $\varepsilon _k\searrow 0$:

$$\begin{aligned} ({\mathcal {P}}'_{k}) \; \begin{array}{l} \text{ Minimize } \quad \varphi ^k(x):=\varphi (x)+\frac{\varepsilon _k}{2}||x||^2 \\ \text{ subject } \text{ to } \;\, x\in C. \end{array} \end{aligned}$$

Theorem 4

If $(C,\varphi )$ is lsc with C closed, $\lim _{||x||\rightarrow +\infty }\varphi ^k(x)=+\infty$ for each k, and the following condition holds: for any sequence $\{x^k\}$ in C with $||x^k||\rightarrow +\infty$, $\frac{x^k}{||x^k||}\rightarrow u$ and $\{\varphi (x^k)\}$ bounded from above, there exist scalars $\rho _k\in (0,||x^k||)$ and $k_0=k_0(\{\rho _k\},\{x^k\})$ such that $x^k-\rho _ku\in C$ and $\varphi (x^k-\rho _ku)\le \varphi (x^k)$ for all $k\ge k_0$, then $\arg \min \nolimits _{C} \varphi$ is nonempty and closed (possibly unbounded).

Finally, to perturb intervals, we recall the Pompeiu-Hausdorff distance between intervals A and B from ${\mathcal {K}}_c$ defined in [19] by

By using it, we define a metric on ${\mathbb {R}}^n\times {\mathcal {K}}_c$ by

Clearly, for $\{(x^k,A^k)\}$ and (x, A) from ${\mathbb {R}}^n\times {\mathcal {K}}_c$, we have

3 Properties of level, colevel and solution sets

We obtain various properties and formulas for level, colevel and solution sets.

Proposition 1

If ${\bar{x}}\in {\text {WEff}}_s(C,f)$ and $f({\hat{x}})\le ^s f({\bar{x}})$ for some ${\hat{x}}\in C$, then ${\hat{x}}\in {\text {WEff}}_s(C,f)$; i.e., ${\mathrm {Lev}}_s(C,f,f({\bar{x}}))\subset {\text {WEff}}_s(C,f)$.

Proof

On the contrary, if there exists ${\hat{x}}\in C$ such that $f({\hat{x}})\le ^s f({\bar{x}})$ but that ${\hat{x}}\notin {\text {WEff}}_s(C,f)$, then there exists $x^0\in C$ such that $f(x^0)<^s f({\hat{x}})$. Hence, $f(x^0)<^s f({\bar{x}})$, which is a contradiction. $\square$

We obtain formulas for level, colevel and solution sets.

Lemma 1

For $Y=[\alpha ,\beta ]\in {\mathcal {K}}_c$, we have

$$\begin{aligned} {\mathrm {Lev}}_s(C,f,Y)= & {} {\mathrm {lev}}(C,f^L,\alpha )\cap {\mathrm {lev}}(C,f^U,\beta ), \end{aligned}$$

(8)

$$\begin{aligned} {\mathrm {Colev}}_s(C,f,Y)= & {} {\mathrm {lev}}(C,f^L,\alpha )\cup {\mathrm {lev}}(C,f^U,\beta ), \end{aligned}$$

(9)

$$\begin{aligned} {\text {WEff}}_s(C,f)= & {} \bigcap \nolimits _{{\bar{x}}\in C}{\mathrm {Colev}}_s(C,f,f({\bar{x}})). \end{aligned}$$

(10)

In addition, if $(C,f^L)$ and $(C,f^U)$ are lsc with C closed, then level, colevel and solution sets are closed.

Proof

Formulas (8)–(9) are easy to check. Formula (10) follows from definition and (9). The closedness of the sets follows from these formulas. $\square$

We relate the minimizers of the end point functions with the solution set.

Lemma 2

$$\begin{aligned} (\arg \min \nolimits _{C}f^L\cup \arg \min \nolimits _{C}f^U)\subset {\text {WEff}}_s(C,f). \end{aligned}$$

(11)

Proof

On the contrary, if there exists ${\bar{x}}$ in the left-side such that $f(x^0)<^s f({\bar{x}})$ for some $x^0\in C$, then $f^L(x^0)<f^L({\bar{x}})$ and $f^U(x^0)<f^U({\bar{x}})$, a contradiction. $\square$

Remark 3

(i) If $\arg \min _{C}f^L$ or $\arg \min _{C}f^U$ is nonempty, then ${\text {WEff}}_s(C,f)$ is nonempty. However, the solution set may be nonempty even though $\arg \min _{C}f^L$ and $\arg \min _{C}f^U$ are empty. Indeed, for the function (C, f) with $C={\mathbb {R}}$ and $f(x)=[\min \{e^{-x}-1,0\},\min \{e^x,1\}]$, the sets $\arg \min _{C}f^L$ and $\arg \min _{C}f^U$ are empty but ${\text {WEff}}_s(C,f)={\mathbb {R}}$.

(ii) The inclusion in (11) may be strict even if $(C,f^L)$ and $(C,f^U)$ are continuous and convex with C closed and convex. Indeed, for (C, f) with

$$\begin{aligned} C=[0,4],\; f^L(x)=\left\{ \begin{array}{ll} -\frac{x}{2}+1, &{} \hbox {if } 0\le x<2; \\ 0, &{} \hbox {if }2\le x\le 4, \end{array} \right. \, f^U(x)=\left\{ \begin{array}{ll} 2, &{} \hbox {if }0\le x<1; \\ \frac{2x}{3}+\frac{4}{3}, &{} \hbox {if }1\le x\le 4, \end{array} \right. \end{aligned}$$

we have $\arg \min _{C}f^L=[2,4]$, $\arg \min _{C}f^U=[0,1]$ and ${\text {WEff}}_s(C,f)=[0,4]$.

We obtain a formula for the solution set that is related to inclusion (11). It is well-known in multiobjective optimization (see [5, Propositions 3.9–3.10]). So, it can be transferred to problem $({\mathcal {P}})$ via (1) but we prove it for completeness. To do this, for $\xi =(\xi _1,\xi _2)^\top \in {\mathbb {R}}^2_+\backslash \{0\}$, we define the linear scalarization function:  $\varphi _{\xi ,f}(\cdot ):=\xi _1f^L(\cdot )+\xi _2f^U(\cdot )$.

Lemma 3

$$\begin{aligned} \bigcup _{\xi \in {\mathbb {R}}^2_+\backslash \{0\}}\arg \min \nolimits _{C}\varphi _{\xi ,f}\subset {\text {WEff}}_s(C,f), \end{aligned}$$

(12)

where the equality holds, if ${\text {WEff}}_s(C,f)$ is nonempty and ${\tilde{f}}(C)+{\mathbb {R}}^2_+$ is convex.

Proof

The proof of (12) runs similarly as for (11). So, it remains to prove the reverse inclusion. If ${\bar{x}}$ is in the right-hand set, then by Remark 2 (iii), we obtain that ${\tilde{f}}(C)\cap ({\tilde{f}}({\bar{x}})-{\mathrm {int}}\,{\mathbb {R}}^2_+)=\emptyset$; thus, $({\tilde{f}}(C)+{\mathbb {R}}^2_+)\cap ({\tilde{f}}({\bar{x}})-{\mathrm {int}}\,{\mathbb {R}}^2_+)=\emptyset$. As ${\tilde{f}}(C)+{\mathbb {R}}^2_+$ is convex, by a separation theorem there exists $\xi \in {\mathbb {R}}^2\backslash \{0\}$ such that $\langle \xi ,{\tilde{f}}(x)+p\rangle \ge \langle \xi ,{\tilde{f}}({\bar{x}})-q\rangle$ for all $x\in C$, $p\in {\mathbb {R}}^2_+$ and $q\in {\mathrm {int}}\,{\mathbb {R}}^2_+$. From this, we conclude that $\xi \in {\mathbb {R}}^2_+\backslash \{0\}$ and ${\bar{x}}\in \arg \min _{C}\varphi _{\xi ,f}$. $\square$

Remark 4

(i) For $C={\mathbb {R}}$ and $f(x)=[-e^x,e^x]$, we have $\arg \min _{C}f^L=\arg \min _{C}f^U=\emptyset$ but ${\text {WEff}}_s(C,f)=\arg \min _{C}\varphi _{\xi ,f}={\mathbb {R}}$ for all $\xi =(\gamma ,\gamma )^\top$ with $\gamma >0$. Note that ${\tilde{f}}(C)+{\mathbb {R}}^2_+$ is convex although $(C,f^L)$ is non-convex.

(ii) [24] A vector function $(C,{\tilde{f}})$ is said to be ${\mathbb {R}}^2_+$-convexlike, if for every $x,y\in C$ and $t\in [0,1]$ there exists $z\in C$ such that $t{\tilde{f}}(x)+(1-t){\tilde{f}}(y)\subset {\tilde{f}}(z)+{\mathbb {R}}^2_+$. It is known that $(C,{\tilde{f}})$ is ${\mathbb {R}}^2_+$-convexlike iff ${\tilde{f}}(C)+{\mathbb {R}}^2_+$ is convex.

(iii) [7] If C is convex, then ${\bar{x}}\in \cup _{\xi \in {\mathbb {R}}^2_+\backslash \{0\}}\arg \min \nolimits _{C}\varphi _{\xi ,f}$ iff ${\bar{x}}\in {\text {WEff}}_s(C,f)$ and ${\mathrm {cone}}({\tilde{f}}(C)-{\tilde{f}}({\bar{x}})+{\mathrm {int}}\,{\mathbb {R}}^2_+)$ is convex.

We obtain an existence result when the constraint set is bounded.

Theorem 5

If $(C,f^L)$ or $(C,f^U)$ is lsc with C compact, then ${\text {WEff}}_s(C,f)$ is nonempty and bounded. If both end point functions are lsc, it is closed as well.

Proof

If $(C,f^L)$ (resp. $(C,f^U)$) is lsc with C compact, then $\arg \min _Cf^L$ (resp. $\arg \min _Cf^U$) is nonempty. Hence ${\text {WEff}}_s(C,f)$ is nonempty by Lemma 2. Clearly, it is bounded. If both end point functions are lsc, then it is closed by Lemma 1. $\square$

Remark 5

(i) This result with lsc end point functions follows from (1) and an existence result for multicriteria optimization problems with compact constraint sets and lsc components (see [5, Theorem 2.19]).

(ii) If C is compact and only one of the end point functions is lsc, then the solution set is nonempty but may not be closed. Indeed, for (C, f) with

$$\begin{aligned} C=[0,1],\,\;f^L(x)=x,\,\;\text{ and }\;\, f^U(x)=\left\{ \begin{array}{ll} 3, &{} \hbox {if }x=1; \\ 2, &{} \hbox {if }0\le x<1, \end{array} \right. \end{aligned}$$

only $(C,f^L)$ is lsc and ${\text {WEff}}_s(C,f)=[0,1)$.

4 Classes of interval functions

We recall some classes of interval functions and study their properties.

Definition 3

An interval function (C, f) with C closed is said to be

• s-upper semicontinuous $(s\hbox {-usc})$ at $\bar{x}\in C$, if for any interval $A\in {\mathcal {K}}_c$ such that $A<^sf(\bar{x})$, there exists an open set $U\subset {\mathbb {R}}^n$ containing $\bar{x}$ such that $A<^s f(x)$ for every $x\in C\cap U$.

• s-lower semicontinuous $(s\hbox {-lsc})$ at $\bar{x}\in C$, if $(C,f^L)$ and $(C,f^U)$ are lsc at ${\bar{x}}$.

• s-usc (resp. s-lsc), if it is s-usc (resp. s-lsc) at every $x\in C$.

Remark 6

[4, 22] An interval function (C, f) with C closed is said to be continuous at ${\bar{x}}\in C$, if . Clearly, (C, f) is continuous at ${\bar{x}}$ iff $(C,f^L)$ and $(C,f^U)$ are continuous at ${\bar{x}}$.

Example 3

The functions in Example 2 are continuous on their domains. We will only prove that $({\mathbb {R}}^n,f_1)$ is continuous. To do this, we first show that function $({\mathbb {R}},g)$ with $g(t):=t[a,b]$ $(a<b)$ is continuous. Clearly, $g(t)=[g^L(t),g^U(t)]$, where

$$\begin{aligned} g^L(t)=\left\{ \begin{array}{ll} at, &{} \hbox {if }t\ge 0; \\ bt, &{} \hbox {if } t<0, \end{array} \right. \;\, \text{ and } \;\, g^U(t)=\left\{ \begin{array}{ll} bt, &{} \hbox {if } t\ge 0; \\ at, &{} \hbox {if }t<0. \end{array} \right. \end{aligned}$$

As these functions are continuous on ${\mathbb {R}}$, function $({\mathbb {R}},g)$ is continuous. Setting $g_i(x_i):=x_i[a^L_i,a^U_i]=[g_i^L(x_i),g_i^U(x_i)]$ as above for $i\in \{1,\ldots ,n\}$, we have $f_1(x)=[f_1^L(x),f_1^U(x)]$ where $f_1^L(x)=\sum _{i=1}^ng_i^L(x_i)$ and $f_1^U(x)=\sum _{i=1}^ng_i^U(x_i)$. As these functions are continuous on ${\mathbb {R}}$, function $({\mathbb {R}}^n,f_1)$ is continuous.

We list some properties of these notions. To do this, in ${\mathbb {R}}^n\times {\mathcal {K}}_c$, we use the topology induced by metric .

Proposition 2

Consider (C, f) with C closed.

• (a) The following statements are equivalent:

  • (i) ${\mathrm {Coepi}}_s(C,f)$ is closed; 

  • (ii) (C, f) has closed colevel sets; 

  • (iii) (C, f) is s-usc; 

  • (iv) (C, f) is s-lsc.

• (b) If (C, f) is s-lsc, then ${\text {Epi}}_s(C,f)$ is closed.

• (c) ${\text {Epi}}_s(C,f)$ is closed iff (C, f) has closed level sets.

Proof

(a): $(i)\Rightarrow (ii)$ Let $Y\in {\mathcal {K}}_c$ and $\{x^k\}\subset {\mathrm {Colev}}_s(C,f,Y)$ be such that $x^k\rightarrow x$. We have $\{(x^k,Y)\}\subset {\mathrm {Coepi}}_s(C,f)$. By hypothesis, we obtain $(x,Y)\in {\mathrm {Coepi}}_s(C,f)$; thus, $x\in {\mathrm {Colev}}_s(C,f,Y)$.

$(ii)\Rightarrow (iii)$ Suppose the implication were false. Then there exist $x^0\in C$ and $Y^0\in {\mathcal {K}}_c$, with $f(x^0)>^s Y^0$ such that for every k there exists a vector $x^k\in C\cap {\mathbb {B}}(x^0,\frac{1}{k})$ satisfying $f(x^k)\not >^sY^0$. Thus, $\{x^k\}\subset {\mathrm {Colev}}_s(C,f,Y^0)$, $x^k\rightarrow x^0$ but $x^0\notin {\mathrm {Colev}}(C,f,Y^0)$, a contradiction.

$(iii)\Leftrightarrow (iv)$ It is trivial.

$(iv)\Rightarrow (i)$ It follows from Lemma 1.

(b): Let $\{(x^k,A^k)\}\subset {\text {Epi}}_s (C,f)$ be such that . We have $x^k\in C$, $f^L(x^k)\le a^L_k$ and $f^U(x^k)\le a^U_k$ for all k, $x^k\rightarrow x$, $a^L_k\rightarrow a^L$ and $a^U_k\rightarrow a^U$. After taking the lower limit and since C is closed, we obtain $x\in C$, $f^L(x)\le a^L$ and $f^U(x)\le a^U$; thus, $(x,A)\in {\text {Epi}}_s (C,f)$.

(c): $(\Rightarrow )$ Let $Y\in {\mathcal {K}}_c$ and $\{x^k\}\subset {\mathrm {Lev}}_s(C,f,Y)$ be such that $x^k\rightarrow x$. As $\{(x^k,Y)\}\subset {\text {Epi}}_s (C,f)$, by hypothesis, we obtain $(x,Y)\in {\text {Epi}}_s (C,f)$; thus, $x\in {\mathrm {Lev}}_s(C,f,Y)$.

$(\Leftarrow )$ Let $\{(x^k,A^k)\}\subset {\text {Epi}}_s (C,f)$ be such that . As $a_k^L\rightarrow a^L$ and $a^U_k\rightarrow a^U$, for an arbitrary $\varepsilon >0$ there exists $N_\varepsilon \in {\mathbb {N}}$ such that $a^L_k<a^L+\varepsilon$ and $a^U_k<a^U+\varepsilon$ for all $k\ge N_\varepsilon$. Clearly, $f(x^k)<^s[a^L+\varepsilon ,a^U+\varepsilon ]$; i.e., $x^k\in {\mathrm {Lev}}_s(C,f,[a^L+\varepsilon ,a^U+\varepsilon ])$ for such k. As $x^k\rightarrow x$, by hypothesis, we obtain $x\in {\mathrm {Lev}}_s(C,f,[a^L+\varepsilon ,a^U+\varepsilon ])$; thus, $x\in C$, $f^L(x)<a^L+\varepsilon$ and $f^U(x)<a^U+\varepsilon$. After taking the limit $\varepsilon \rightarrow 0^+$, we get $f^L(x)\le a^L$ and $f^U(x)\le a^U$, thus, $(x,A)\in {\text {Epi}}_s (C,f)$. $\square$

Remark 7

Parts (b)–(c) can be derived from properties of the associated vector function $(C,{\tilde{f}})$ (see Remark 2 (iii) and [6, Proposition 2.5]).

Definition 4

An interval function (C, f) with C convex is said to be

• s-convex, if $f(tx+(1-t)y)\le ^s tf(x)+(1-t)f(y)$ for all $x,y\in C$ and $t\in (0,1)$.

• strictly s-convex, if $f(tx+(1-t)y)<^s tf(x)+(1-t)f(y)$ for all $x,y\in C$, with $x\ne y$ and $t\in (0,1)$.

Clearly, strictly s-convex functions are s-convex.

Example 4

An interval function (C, f) with C convex is said to be convex, if $tf(x)+(1-t)f(y)\subset f(tx+(1-t)y)$ for all $x,y\in C$ and $t\in (0,1)$. Clearly, a convex function is s-convex.

We list some properties of these notions.

Proposition 3

Consider (C, f) with C convex.

• (a) (C, f) is s-convex iff $(C,f^L)$ and $(C,f^U)$ are convex iff ${\mathrm {Epi}}_s(C,f)$ is convex.

• (b) If (C, f) is s-convex, then its level sets, ${\tilde{f}}(C)+{\mathbb {R}}^2_+$ and ${\mathrm {Colev}}_s(C,f,[\alpha ,\alpha ])$ are convex.

• (c) (C, f) is strictly s-convex iff $(C,f^L)$ and $(C,f^U)$ are strictly convex. Under this property, we have ${\text {WEff}}_s(C,f)={\text {Eff}}_s (C,f)$.

• (d) If (C, f) is strictly s-convex and the point ${\bar{x}}$ is from ${\text {WEff}}_s(C,f)$, then the set $\{x\in C:f(x)=f({\bar{x}})\}$ is a singleton.

• (e) If $n=1$ and (C, f) is s-convex, then ${\text {WEff}}_s(C,f)$ is convex.

Proof

Parts (a)–(b) are easy to check.

(c): The equivalence is trivial. To prove the equality, it is sufficient to prove that ${\text {WEff}}_s(C,f)\subset {\text {Eff}}_s(C,f)$. On the contrary, if there exists $\bar{x}\in {\text {WEff}}_s(C,f)$ such that $\bar{x}\not \in {\text {Eff}}_s (C,f)$, then there exists $x\in C$ such that $f(x)\le ^s f(\bar{x})$ and $f(x)\ne f({\bar{x}})$. Defining $z:=tx+(1-t){\bar{x}}$ for $t\in (0,1)$ and since $x\ne {\bar{x}}$, by hypothesis, we have $z\in C$ and $f(z)<^s t f(x)+(1-t)f({\bar{x}})\le ^s f({\bar{x}})$, which is a contradiction.

(d): On the contrary, if for some ${\bar{x}}\in {\text {WEff}}_s(C,f)$ there exists $x\in C$ such that $x\ne {\bar{x}}$ and $f(x)=f({\bar{x}})$, then for $t\in (0,1)$ and ${\tilde{z}}:=t{\bar{x}}+(1-t)x$, we have ${\tilde{z}}\in C$ and $f({\tilde{z}})<^s tf({\bar{x}})+(1-t)f(x)=f({\bar{x}})$, which is a contradiction.

(e): Let $x^1,x^2\in {\text {WEff}}_s(C,f)$, with $x^1<x^2$ and $x\in (x^1,x^2)$. If $y\in C$ with $y>x$, then $x=\alpha x^1+(1-\alpha )y$ for some $\alpha \in (0,1)$. If we suppose that $f(y)<^sf(x)$, then by s-convexity we obtain $f(y)<^sf(x^1)$, a contradiction. Hence $f(y)\not <^sf(x)$. Similarly, we prove that if $y\in C$ with $y<x$, then $f(y)\not <^sf(x)$. Therefore, $x\in {\text {WEff}}_s(C,f)$ and the solution set is convex. $\square$

Remark 8

(i) The uniqueness of solutions is an unusual property for IOPs. Part (d) is a kind of ‘uniqueness property’ for these problems since under this condition the function $x\mapsto {\tilde{f}}(x)$ restricted to the solution set is bijective.

(ii) Part (e) appears in [6, Theorem 3.9] for vector optimization problems. For $n\ge 2$, the solution set may not be convex even if (C, f) is s-convex. Indeed, for (C, f) with $C=[-1,1]^2$ and $f(x,y)=[\min \{y^2,x^2+1\},\max \{y^2,x^2+1\}]$, we have ${\text {WEff}}_s(C,f)=(\{0\}\times [-1,1])\cup ([-1,1]\times \{0\})$.

It is important to point out that s-convexity is a restrictive property for interval functions. Indeed, the ‘simple’ interval functions $g(t)=t[a,b]$ (see Example 3) and $g(t)=t^2[a,b]$ $(a<0<b)$ are not s-convex since $({\mathbb {R}},g^L)$ is non-convex in both cases. For this reason, in what follows, we do not assume this property.

5 Main results

We first study the boundedness of level and colevel sets. To this end, we observe that as $f^L\le f^U$, for all $\lambda \in {\mathbb {R}}$ and $\xi =(\xi _1,\xi _2)^\top \in {\mathbb {R}}^2_+\backslash \{0\}$ it holds that

$$\begin{aligned}&f^L\le \frac{\phi _{\xi ,f}}{\xi _1+\xi _2}\le f^U\;\, \text{ and } \,\; (f^L)^\infty \le \frac{\phi _{\xi ,f}^\infty }{\xi _1+\xi _2} \le (f^U)^\infty , \end{aligned}$$

(13)

$$\begin{aligned}&{\mathrm {lev}}(C,f^U,\lambda )\subset {\mathrm {lev}}(C,\varphi _{\xi ,f},(\xi _1+\xi _2)\lambda )\subset {\mathrm {lev}}(C,f^L,\lambda ), \end{aligned}$$

(14)

$$\begin{aligned}&R(C,f^U)\subset R(C,\varphi _{\xi ,f}) \subset R(C,f^L). \end{aligned}$$

(15)

From (13)–(15), we see that, if $(C,f^L)$ is level-bounded (resp. coercive), then $(C,\varphi _{\xi ,f})$ is level-bounded (resp. coercive) which in turn implies that $(C,f^U)$ is level-bounded (resp. coercive). From ${\mathrm {Lev}}_s(C,f,Y)\subset {\mathrm {Colev}}_s(C,f,Y)$ for $Y=[\alpha ,\beta ]$, we conclude that, if (C, f) has bounded colevel sets, then it has bounded level sets. Moreover, by Lemma 1 and (13), we have

$$\begin{aligned}&{\mathrm {lev}}(C,f^U,\alpha )\subset {\mathrm {Lev}}_s(C,f,Y)\subset {\mathrm {lev}}(C,f^U,\beta ), \end{aligned}$$

(16)

$$\begin{aligned}&{\mathrm {lev}}(C,f^L,\alpha )\subset {\mathrm {Colev}}_s(C,f,Y)\subset {\mathrm {lev}}(C,f^L,\beta ). \end{aligned}$$

(17)

From (16)–(17), we deduce the next result.

Lemma 4

• (a) (C, f) has bounded level sets iff $(C,f^U)$ is level-bounded.

• (b) (C, f) has bounded colevel sets iff $(C,f^L)$ is level-bounded.

We obtain bounds for the asymptotic cones of level and colevel sets.

Proposition 4

For $Y\in {\mathcal {K}}_c$, we have

• (a) ${\mathrm {Lev}}_s(C,f,Y)^\infty \subset R(C,f^U)$, where the equality holds, if $(C,f^U)$ is lsc and convex with C closed and convex, and the level set is nonempty.

• (b) ${\mathrm {Colev}}_s(C,f,Y)^\infty \subset R(C,f^L)$, where the equality holds, if $(C,f^L)$ is lsc and convex with C closed and convex, and the colevel set is nonempty.

Proof

Parts (a) and (b) follow after taking the asymptotic cones to (16) and (17) and applying (7), respectively. $\square$

Remark 9

From Proposition 4 and (3), we conclude that: If $R(C,f^U)=\{0\}$ (resp. $R(C,f^L)=\{0\})$, then (C, f) has bounded level (resp. colevel) sets. In addition, if $(C,f^U)$ (resp. $(C,f^L))$ is lsc and convex with C closed and convex, then for every nonempty level (resp. colevel) sets at heights Y and Z in ${\mathcal {K}}_c$, we have ${\mathrm {Lev}}_s(C,f,Y)^\infty ={\mathrm {Lev}}_s(C,f,Z)^\infty$ (resp. ${\mathrm {Colev}}_s(C,f,Y)^\infty ={\mathrm {Colev}}_s(C,f,Z)^\infty )$.

We study the boundedness of level sets.

Proposition 5

Consider the statements:

• (a) $R(C,f^U)=\{0\}$;

• (b) (C, f) has bounded level sets;

• (c) $\lim _{||x||\rightarrow +\infty }f^U(x)=+\infty$;

• (d) $\arg \min _Cf^U$ is nonempty and compact.

The following implications hold: $(a)\Longrightarrow (b)\Longleftrightarrow (c)$. If $(C,f^U)$ is lsc with C closed, then $(c)\Longrightarrow (d)$. In addition, if $(C,f^U)$ is convex with C convex, then all the assumptions are equivalent.

Proof

For implication $(a)\Rightarrow (b)$ see Remark 9 and for equivalence $(b)\Leftrightarrow (c)$ see Lemma 4(a). For the remaining implications see Sect. 2. $\square$

Remark 10

Implication $(b)\Rightarrow (a)$ does not hold without the convexity assumption. Indeed, (C, f) with $C={\mathbb {R}}$ and $f(x)=[0,\sqrt{|x|}\,]$ has bounded level sets but $R(C,f^U)={\mathbb {R}}$.

We study the boundedness of colevel sets.

Proposition 6

Consider the statements:

• (a) $R(C,f^L)=\{0\}$;

• (b) (C, f) has bounded colevel sets;

• (c) $\lim _{||x||\rightarrow +\infty }f^L(x)=+\infty$;

• (d) $\arg \min _{C}f^L$ is nonempty and compact.

The following implications hold: $(a)\Longrightarrow (b)\Longleftrightarrow (c)$. If $(C,f^L)$ is lsc with C closed, then $(c)\Longrightarrow (d)$. In addition, if $(C,f^L)$ is convex with C convex, then all the assumptions are equivalent.

Proof

The proof runs as in Proposition 5. $\square$

We obtain bounds for the asymptotic cone of the solution set.

Proposition 7

• (a) ${\text {WEff}}_s(C,f)^\infty \subset R(C,f^L)$, where the equality holds, if $(C,f^L)$ is lsc and convex with C closed and convex, and $\arg \min _{C}f^L$ is nonempty.

• (b) If $(C,f^U)$ is lsc and convex with C closed and convex, and ${\text {WEff}}_s(C,f)$ is nonempty, then $R(C,f^U)\subset {\text {WEff}}_s(C,f)^\infty$.

Proof

(a): By (10), properties of asymptotic cones [2, Proposition 2.1.9] and Proposition 4(b), we have ${\text {WEff}}_s(C,f)^\infty \subset \bigcap \nolimits _{x\in C}{\mathrm {Colev}}_s(C,f,f(x))^\infty \subset R(C,f^L)$. We prove the reverse inclusion. After taking the asymptotic cones to both sides of $\arg \min \nolimits _{C}f^L\subset {\text {WEff}}_s(C,f)$ and since $\arg \min \nolimits _{C}f^L={\mathrm {lev}}(C,f^L,\min _Cf^L)$, by the equality in (7), we obtain $R(C,f^L)\subset {\text {WEff}}_s(C,f)^\infty$.

(b): If ${\bar{x}}\in {\text {WEff}}_s(C,f)$, then by Propositions 1 and 4 (a), we obtain that $R(C,f^U)={\mathrm {Lev}}_s(C,f,f({\bar{x}}))^\infty \subset {\text {WEff}}_s(C,f)^\infty$. $\square$

Remark 11

From part (a) and (3), we conclude that, if $R(C,f^L)=\{0\}$ then ${\text {WEff}}_s(C,f)$ is bounded.

We obtain a necessary condition that extends Theorem 1.

Proposition 8

If ${\text {WEff}}_s(C,f)$ is nonempty, then $(f^U)^\infty \ge 0$ on $C^\infty$.

Proof

If ${\bar{x}}\in {\text {WEff}}_s(C,f)$, then $f(x)\not <^s f({\bar{x}})$; thus, $f^U(x)\ge f^L({\bar{x}})$ for all $x\in C$. Let $u\in C^\infty$ be fixed and $\{u^k\}$ and $\{t_k\}$ be such that $\{t_ku^k\}\subset C$, $u^k\rightarrow u$ and $t_k\rightarrow +\infty$. As $\frac{1}{t_k}f^U(t_ku^k)\ge \frac{1}{t_k}f^L({\bar{x}})$ for all k, after taking the lower limit, we obtain $\liminf _k\frac{1}{t_k}f^U(t_ku^k)\ge 0$. From this and (5), we have $(f^U)^\infty (u)\ge 0$. $\square$

Remark 12

(i) If $(f^U)^\infty (0)=0$ (e.g. when $(C,f^U)$ is lsc and convex with C closed and convex, see [20, Corollary 3.27]), then $(f^U)^\infty$ is proper (see [2, Proposition 2.5.1]) and thus $(f^U)^\infty (u)=+\infty$ for all $u\notin C^\infty$. In this case, the necessary condition reads as follows: $(f^U)^\infty \ge 0$ on ${\mathbb {R}}^n$.

(ii) The necessary condition is not sufficient. Indeed, (C, f) with $C={\mathbb {R}}$ and $f(x)=[\frac{1}{2}e^{-x},e^{-x}]$ satisfies the necessary condition since $(f^U)^\infty =\delta _{{\mathbb {R}}_+}$ but ${\text {WEff}}_s(C,f)=\emptyset$.

(iii) Condition: $(f^L)^\infty \ge 0$ on $C^\infty$, is not a necessary condition. Indeed, for (C, f) with $C={\mathbb {R}}$ and $f(x)=[\min \{0,-x\},\max \{0,x\}]$, we have ${\text {WEff}}_s(C,f)={\mathbb {R}}$ but $(f^L)^\infty (v)<0$ for $v>0$.

We now obtain various existence results when the constraint set is unbounded. It is important to point out that the solution set may be empty even if the function is continuous, as shown by (C, f) with $C={\mathbb {R}}$ and $f(x)=[x,x+1]$.

First, we obtain a coercive existence result that extends Theorem 2(a).

Theorem 6

If (C, f) is s-lsc with C closed and ${\mathrm {Colev}}_s(C,f,f(x^0))$ is bounded for some $x^0\in C$, then ${\text {WEff}}_s(C,f)$ is nonempty and compact.

Proof

The set $A:={\mathrm {Colev}}_s(C,f,f(x^0))$ is compact by Lemma 1. This and Theorem 5 imply that there exists ${\bar{x}}$ in ${\text {WEff}}_s (A,f)$. We assert that ${\bar{x}}\in {\text {WEff}}_s(C,f)$. On the contrary, there exists $x\in C\backslash A$ such that $f(x)<^s f({\bar{x}})$. From this and since $f(x^0)<^s f(x)$, we obtain $f(x^0)<^sf({\bar{x}})$, which is a contradiction. Hence ${\text {WEff}}_s(C,f)$ is nonempty. This set is bounded since for $x\in C\backslash A$ we have that $f(x^0)<^sf(x)$, so x cannot be a solution. This set is closed by Lemma 1. $\square$

Second, we obtain a noncoercive existence result without convexity assumptions that is related to Theorem 2(b).

Theorem 7

If (C, f) is given with C closed, there exists $\xi \in {\mathbb {R}}^2_+\backslash \{0\}$ such that $(C,\varphi _{\xi ,f})$ is lsc and $R(C,\varphi _{\xi ,f})=\{0\}$, then ${\text {WEff}}_s(C,f)$ is nonempty (possibly unbounded).

Proof

As $(C,\varphi _{\xi ,f})$ is coercive, by Theorem 2 we conclude that $\arg \min _{C}\varphi _{\xi ,f}$ is nonempty. This and Lemma 3 imply that ${\text {WEff}}_s(C,f)$ is nonempty. $\square$

Remark 13

(i) Taking $\xi$ equal to $(1,0)^\top$ and then equal to $(0,1)^\top$, and using Remark 11, we obtain:

− If $(C,f^L)$ is lsc with C closed and $R(C,f^L)=\{0\}$, then ${\text {WEff}}_s(C,f)$ is nonempty and bounded.

− If $(C,f^U)$ is lsc with C closed and $R(C,f^U)=\{0\}$, then ${\text {WEff}}_s(C,f)$ is nonempty.

The solution set may be unbounded in the second item. Indeed, for (C, f) with $C={\mathbb {R}}$ and $f(x)=[0,x^2]$, we have $R(C,f^U)=\{0\}$ since $(f^U)^\infty =\delta _{\{0\}}$ and ${\text {WEff}}_s(C,f)={\mathbb {R}}$.

(ii) By (15), we see that $R(C,f^L)=\{0\}$ implies $R(C,\varphi _{\xi ,f})=\{0\}$ that implies $R(C,f^U)=\{0\}$ that in turn implies the necessary condition.

(iii) By rewriting [6, Theorems 3.1 and 3.11], devoted to vector optimization problems (cf. Remark 2 (iii)), we supplement the existence results above as follows:

− If (C, f) is s-lsc with C closed and for all $x\in C\backslash C_r$, where $C_r:=r{\mathbb {B}}\cap C$ for some $r>0$, there exists $y\in C_r$ such that $f(y)<^s f(x)$, then ${\text {WEff}}_s(C,f)$ is nonempty and compact.

− If $n=1$, $C\subset {\mathbb {R}}$ is a closed ray or the entire ${\mathbb {R}}$ and (C, f) is s-lsc and s-convex, then statements (a)–(d) of Proposition 6 are equivalent to each of the following:

• (e) $\exists r>0$, $\forall x\in C\backslash C_r$, $\exists y\in C_r$: $f(y)<^s f(x)$;

• (f) ${\text {WEff}}_s(C,f)$ is nonempty and compact (it is already convex).

Example 5

Let (C, g) be from Example 3. For $\xi =(\xi _1,\xi _2)^\top \in {\mathbb {R}}^2_+\backslash \{0\}$, we have

$$\begin{aligned} \varphi _{\xi ,g}(x)= \left\{ \begin{array}{ll} (\xi _1a+\xi _2b)x, &{} \hbox {if }x\ge 0; \\ (\xi _1b+\xi _2a)x, &{} \hbox {if }x<0. \end{array} \right. \end{aligned}$$

As $\varphi _{\xi ,g}^\infty =\varphi _{\xi ,g}$, we have $R(C,\varphi _{\xi ,g})=\{0\}$ iff $\varphi _{\xi ,g}(v)>0$ for all $v\ne 0$ iff

$$\begin{aligned} \left\{ \begin{array}{rcl} A\xi &{}>&{}0 \\ \xi &{}\ge &{} 0 \end{array}\right. \text{ where } A=\left( \begin{array}{rr} a &{} b\\ -b &{} -a \\ \end{array} \right) . \end{aligned}$$

This and Theorem 7 imply that, if $a<0<b$ then ${\text {WEff}}_s(C,f)$ is nonempty.

Third, we obtain a noncoercive existence result that extends Theorem 3.

Theorem 8

If (C, f) is given with C closed convex, there exists $\xi \in {\mathbb {R}}^2_+\backslash \{0\}$ such that $(C,\varphi _{\xi ,f})$ is lsc and convex, $\varphi _{\xi ,f}^\infty \ge 0$ on $C^\infty$, and $K(C,\varphi _{\xi ,f})=-K(C,\varphi _{\xi ,f})$, then ${\text {WEff}}_s(C,f)$ is nonempty (possibly unbounded).

Proof

This result follows straightforwardly from Theorem 3 and Lemma 3. $\square$

Remark 14

(i) By (13), condition $\varphi _{\xi ,f}^\infty \ge 0$ on $C^\infty$ implies the necessary condition.

(ii) There are problems which existence of solutions can be ensured by Theorem 8 but not by Theorem 7. Indeed, for (C, f) with $C={\mathbb {R}}$ and $f(x)=[0,\max \{0,x\}]$ the hypothesis of Theorem 8 holds for $\xi =(1,0)^\top$; thus, ${\text {WEff}}_s(C,f)$ is nonempty and equal to ${\mathbb {R}}$. We cannot apply Theorem 7 since $R(C,\varphi _{\xi ,f})={\mathbb {R}}$ if $\xi _2=0$ whereas $R(C,\varphi _{\xi ,f})={\mathbb {R}}_-$ if $\xi _2>0$ for $\xi \in {\mathbb {R}}^2_+\backslash \{0\}$.

(iii) Without the convexity assumption, the solution set may be empty. Indeed, (C, f) with $C={\mathbb {R}}$ and $f(x)=[\frac{1}{2}e^{-|x|},e^{-|x|}]$ has continuous non-convex end point functions, $\varphi _{\xi ,f}^\infty =0$ and $K(C,\varphi _{\xi ,f})={\mathbb {R}}$ for all $\xi \in {\mathbb {R}}^2_+\backslash \{0\}$ but ${\text {WEff}}_s(C,f)=\emptyset$.

Finally, we obtain a noncoercive existence result without convexity assumptions that extends Theorem 4. To this end, we approximate problem $({\mathcal {P}})$ by the family of problems where $\varepsilon _k\searrow 0$:

$$\begin{aligned} ({\mathcal {P}}_{k}) \;\; \begin{array}{l} \text{ Minimize } \; f^k(x):=f(x)+\frac{\varepsilon _k}{2}||x||^2[1,1] \\ \text{ subject } \text{ to } \; x\in C. \end{array} \end{aligned}$$

We first study the behavior of sequences $\{x^k\}$ with $x^k\in {\text {WEff}}_s(C,f^{k})$ for all k.

Lemma 5

• (a) If $||x^k||\rightarrow +\infty$ and $\frac{x^k}{||x^k||}\rightarrow u$, then $u\in R(C,f^L)$.

• (b) If (C, f) is s-lsc with C closed and $x^k\rightarrow {\bar{x}}$, then ${\bar{x}}\in {\text {WEff}}_s(C,f)$.

Proof

(a): Clearly, $u\in C^{\infty }$. For $z\in C$ being fixed, we have $f^{k}(z)\not <^s f^{k}(x^{k})$; thus, $(f^{k})^U(z)\ge (f^{k})^L(x^{k})$ for all k. From this, multiplying by $\frac{1}{||x^k||}$ and setting $u^{k}:=\frac{x^{k}}{||x^k||}$ for all k, we have

$$\begin{aligned} \frac{1}{||x^k||}f^L(||x^k||u^{k})\le \frac{1}{||x^k||}f^L(||x^k||u^{k})+\frac{\varepsilon _{k}}{2}||x^{k}||\le \frac{1}{||x^k||}f^U(z)+\frac{\varepsilon _{k}}{2||x^k||}||z||^2. \end{aligned}$$

After taking the lower limit, by (5) we obtain $(f^L)^\infty (u)\le 0$; thus, $u\in R(C,f^L)$.

(b): As C is closed, we have ${\bar{x}}\in C$. For a fixed $z\in C$, we have $f^{k}(z)\not <^s f^{k}(x^{k})$; thus, $(f^{k})^L(z)\ge (f^{k})^L(x^{k})$ or $(f^{k})^U(z)\ge (f^{k})^U(x^{k})$ for all k. If $(f^{k})^L(x^{k})\le (f^{k})^L(z)$; i.e., $f^L(x^{k})\le f^L(z)+\frac{\varepsilon _{k}}{2}||z||^2$ for infinitely many k, then after taking the lower limit and as $(C,f^L)$ is lsc, we obtain $f^L({\bar{x}})\le f^L(z)$. On the other hand, if $(f^{k})^U(x^{k})\le (f^{k})^U(z)$ for infinitely many k, then, similarly, we obtain $f^U({\bar{x}})\le f^U(z)$. From both cases, we conclude that $f(z)\not <^s f({\bar{x}})$ and since $z\in C$ was arbitrary, we have ${\bar{x}}\in {\text {WEff}}_s(C,f)$. $\square$

Theorem 9

If (C, f) is s-lsc with C closed, $\lim _{||x||\rightarrow +\infty }(f^k)^U(x)=+\infty$ for all k and the following condition holds: for any sequence $\{x^k\}$ in C with $||x^k||\rightarrow +\infty$, $\frac{x^k}{||x^k||}\rightarrow u$ such that $u\in R(C,f^L)$ and $\{f^U(x^k)\}$ is bounded from above, there exist scalars $\rho _k\in (0,||x^k||)$ and $k_0=k_0(\{\rho _k\},\{x^k\})$ such that $x^k-\rho _ku\in C$ and $f(x^k-\rho _ku)\le ^sf(x^k)$ for all $k\ge k_0$, then ${\text {WEff}}_s(C,f)$ is nonempty and closed (possibly unbounded).

Proof

By Theorem 2(a) and hypothesis, there exists $x^k\in \arg \min _C(f^k)^U$ for all k. From this and Lemma 2, we have $x^k\in {\text {WEff}}_s(C,f^k)$ for such k. We assert that $\{x^k\}$ is bounded. On the contrary, we have $||x^k||\rightarrow +\infty$ and $\frac{x^k}{||x^k||}\rightarrow u$, up to subsequences, for some u. By Lemma 5(a), we have $u\in R(C,f^L)$. Let $\{\rho _k\}$ and $k_0$ be those from the hypothesis. Clearly, $f^k(x^k-\rho _ku)\not <^s f^k(x^k)$ for all $k\ge k_0$; i.e.,

$$\begin{aligned} f^L(x^k)+\frac{\varepsilon _k}{2}||x^k||^2\le f^L(x^k-\rho _ku)+\frac{\varepsilon _k}{2}||x^k-\rho _ku||^2 \end{aligned}$$

(18)

or

$$\begin{aligned} f^U(x^k)+\frac{\varepsilon _k}{2}||x^k||^2\le f^U(x^k-\rho _ku)+\frac{\varepsilon _k}{2}||x^k-\rho _ku||^2. \end{aligned}$$

(19)

If (18) holds for infinitely many $k\ge k_0$, then by hypothesis, we have

$$\begin{aligned} f^L(x^k)+\frac{\varepsilon _k}{2}||x^k||^2\le f^L(x^k)+ \frac{\varepsilon _k}{2}||x^k-\rho _ku||^2, \end{aligned}$$

i.e., $||x^k||\le ||x^k-\rho _ku||$ for such k. From this and

$$\begin{aligned} ||x^k{-}\rho _ku||{=}\Big \Vert x^k{-}\frac{\rho _k x^k}{||x^k||}{+}\rho _k(\frac{x^k}{||x^k||}{-}u)\Big \Vert {\le } ||x^k||(1{-}\frac{\rho _k}{||x^k||})+\rho _k\Big \Vert \frac{x^k}{||x^k||}-u\Big \Vert , \end{aligned}$$

we obtain $1\le ||\frac{x^k}{||x^k||}-u||$ for such k, which is a contradiction.

If (19) holds for infinitely many $k\ge k_0$, then similarly, we obtain a contradiction. Therefore, $\{x^k\}$ is bounded. Hence $x^k\rightarrow {\bar{x}}$, up to subsequences, for some ${\bar{x}}$. From this and Lemma 5(b), we have ${\bar{x}}\in {\text {WEff}}_s(C,f)$ and the solution set is nonempty. It is also closed by Lemma 1. $\square$

Remark 15

• (i) By (13), we see that the weakest coercivity condition to impose is $\lim _{||x||\rightarrow +\infty }(f^k)^U(x)=+\infty$.

• (ii) The conclusion of Theorem 9 remains correct, if the limits are replaced by $(f^U)^\infty (u)>-\infty$ for all u (see [11, Corollary 2.1]).

• (iii)The condition in Theorem 9 holds vacuously, if $R(C,f^L)=\{0\}$.

• (iv) Theorems 8 and 9 are not comparable. On the one hand, (C, f) with $C={\mathbb {R}}$ and $f(x)=[\min \{0,x^3\},e^{-x}]$ satisfies the hypothesis of Theorem 9; thus, ${\text {WEff}}_s(C,f)$ is nonempty and equal to ${\mathbb {R}}_+$ but it does not satisfy the hypothesis of Theorem 8 since $\varphi _{\xi ,f}$ is non-convex when $\xi _1>0$ and $K(C,\varphi _{\xi ,f})={\mathbb {R}}_+$ when $\xi _1=0$ for $\xi \in {\mathbb {R}}^2_+\backslash \{0\}$. On the other hand, (C, f) from Remark 4(i) satisfies the hypothesis of Theorem 8 for $\xi =(\gamma ,\gamma )^\top$ with $\gamma >0$; thus, ${\text {WEff}}_s(C,f)$ is nonempty and equal to ${\mathbb {R}}$ but it does not satisfy the hypothesis of Theorem 9.

6 Conclusions

We have studied set-type solutions of IOPs that are defined using the Kulisch–Miranker order. To deal with such problems with unbounded data, we have used tools from asymptotic analysis. We have obtained bounds for the asymptotic cones of level, colevel, and solution sets that have allowed us to deduce coercivity properties and coercive existence results. We have employed scalarizations and regularizations of the objective function to obtain two noncoercive existence results.

The results are easy to check for concrete problems, since they only require to calculate the asymptotic cone of constraint sets and the asymptotic functions of end point functions. To this end, there are plenty of formulas and calculus rules.

Some asymptotic tools have been developed in [9] to study set-type solutions of set optimization problems considering the order $\preccurlyeq ^l$, $\prec ^l$. This work is a first step in the study of such problems but considering the order $\preccurlyeq ^{s}$, $\prec ^{s}$.