Quasiconvexity of set-valued maps assures well-posedness of robust vector optimization

Abstract

Robust optimization is a fast growing methodology to study optimization problems with uncertain data. An uncertain vector optimization problem can be studied through its robust or optimistic counterpart, as in Ben-Tal and Nemirovski (Math Oper Res 23:769–805, 1998) and Beck and Ben-Tal (Oper Res Lett 37: 1–6, 2009). In this paper we formulate the counterparts as set optimization problems. This setting appears to be more natural, especially when the uncertain problem is a non-linear vector optimization problem. Under this setting we study the well-posedness of both the robust and the optimistic counterparts, using the embedding technique for set optimization developed in Kuroiwa and Nuriya (Proceedings of the fourth international conference on nonlinear and convex analysis, pp 297–304, 2006). To prove our main results we also need to study the notion of quasiconvexity for set-valued maps, that is the property of convexity of level set. We provide a general scheme to define the notion of level set and we study the relations among different subsequent definitions of quasi-convexity. We prove some existing notions arise as a special case in the proposed scheme.

Appendix: Proof of main theorems

Throughout this section, $Y$, $K$, and ${\mathcal {Y}}$ are as defined in Sect. 2. At first we introduce a normed vector space in which ${\mathcal {Y}}$ is embedded. The approach can be found in Rådström (1952) and Kuroiwa and Nuriya (2006).

1.1 The embedding space and parametrized embedding functions

Any two couples $(A,B);(C,D)\in {\mathcal {Y}}^2$ are equivalent if $A+D+K=B+C+K$. When this occurs we write $(A,B)\equiv (C,D)$. The equivalence family of the couple $(A,B)$ is defined by the set

$$\begin{aligned} \left[ A,B\right] :=\left\{ \left( C,D\right) \in {\mathcal {Y}}^2\,|\,\left( A,B\right) \equiv \left( C,D\right) \right\} , \end{aligned}$$

and the quotient space ${\mathcal {Y}}^2\!/\!\equiv$ is given by

$$\begin{aligned} {\mathcal {Y}}^2\!/\!\equiv := \left\{ \left[ A,B\right] \mid \left( A,B\right) \in {\mathcal {Y}}^2\right\} . \end{aligned}$$

In Kuroiwa and Nuriya (2006) it has been introduced the vector space $\left( {\mathcal {Y}}^2\!/\!\equiv , +, \cdot \right)$, where

• $\left[ A,B\right] +\left[ C,D\right] =\left[ A+C,B+D\right]$;

• $\lambda \cdot \left[ A,B\right] =\left\{ \begin{array}{ll} \left[ \lambda A,\lambda B\right] , &{}\quad \lambda \ge 0\\ \left[ -\lambda B,-\lambda A\right] , &{}\quad \lambda <0. \end{array} \right.$

Fix $k\in \mathrm{int\,}{K}$. The set $W=\{\xi \in K^+\mid \langle \xi , k\rangle =1\}$ is a weak-$*$ compact base for $K^+$ (Jameson 1970; Luc 1989). The embedding space $\left( {\mathcal {Y}}^2\!/\!\equiv ,+,\cdot \right)$ is normed (Kuroiwa and Nuriya 2006; Kuroiwa 2009), introducing

$$\begin{aligned} \Vert \left[ A,B\right] \Vert := \sup _{w\in W}\left| \inf \langle w,A\rangle -\inf \langle w,B\rangle \right| . \end{aligned}$$

(10)

A partial order in ${\mathcal {Y}}^2\!/\!\equiv$ can be introduced through the pointed, closed and convex cone

$$\begin{aligned} {\mathcal {K}}:=\left\{ \left[ A,B\right] \in {\mathcal {Y}}^2\!/\!\equiv \,|\,B\le ^l_KA\right\} \end{aligned}$$

depending on the ordering cone $K$ on $Y$. The interior of ${\mathcal {K}}$ is given by

$$\begin{aligned} \mathrm{int\,}{{\mathcal {K}}}=\left\{ \left[ A,B\right] \in {\mathcal {Y}}^2\!/\!\equiv \,|\,B<^l_KA\right\} . \end{aligned}$$

The proof of the previous equality indeed follows taking into account that it holds $B<^l_KA$ if and only if there exists a positive number $r$ such that

$$\begin{aligned} A-rk \subseteq B+K, \end{aligned}$$

(11)

and (11) in turn is equivalent to

$$\begin{aligned}{}[A,B]+r\mathcal{B}_{{\mathcal {Y}}^2\!/\!\equiv }\subseteq {\mathcal {K}}, \end{aligned}$$

where $\mathcal{B}_{{\mathcal {Y}}^2\!/\!\equiv }$ is the unit ball in ${\mathcal {Y}}^2\!/\!\equiv$.

Therefore we can define order relations in the vector space ${\mathcal {Y}}^2\!/\!\equiv$ by

$$\begin{aligned}&\left[ A,B\right] \le _{{\mathcal {K}}}\left[ C,D\right] \quad \text{ if } \left[ C,D\right] -\left[ A,B\right] \in {\mathcal {K}},\\&\text{ and }\\&\left[ A,B\right] <_{{\mathcal {K}}}\left[ C,D\right] \quad \text{ if } \left[ C,D\right] -\left[ A,B\right] \in \mathrm{int\,}{{\mathcal {K}}}. \end{aligned}$$

Next we introduce parametrized embedding functions: for each $t\in [0,1]$, a real-valued function $\psi _t$ on ${\mathcal {Y}}$ is defined by, for each $A\in {\mathcal {Y}}$,

$$\begin{aligned} \psi _t(A)=[(1-t)A,-tA], \end{aligned}$$

(12)

By using the parametrized functions, family ${\mathcal {Y}}$ is embedded to normed ordered vector space ${\mathcal {Y}}^2\!/\!\equiv$.

1.2 Properties of the embedding

At first we consider a general set-valued optimization problem and observe some properties continuously hold after embedding the problem to a vector optimization problem. For a given set-valued map $F:X\subseteq {\mathbb {R}}^n\rightarrow {\mathcal {Y}}$,

$$\begin{aligned} \min _{x\in X} F(x). \qquad (\hbox {SP}\left( F,K\right) ) \end{aligned}$$

As we already know, according to the order given by $K$, different solution concepts are given as follows: a vector ${\bar{x}}\in X$ is said to be an $l$-type solution (resp. $l$-type weak solution) of $\hbox {SP}\left( F,K\right)$ if

$$\begin{aligned}&x\in X, F(x)\le _K^l F\left( {\bar{x}}\right) \Rightarrow F\left( {\bar{x}}\right) \le _K^l F(x)\\&\quad (\text{ resp. }\ x\in X, F(x)<_K^l F\left( {\bar{x}}\right) \Rightarrow F\left( {\bar{x}}\right) <_K^l F(x)), \end{aligned}$$

and let $l$-Eff($\hbox {SP}\left( F,K\right)$) (resp. $l$-WEff($\hbox {SP}\left( F,K\right)$)) be the set of all $l$-type solutions (resp. $l$-type weak solutions) of $\hbox {SP}\left( F,K\right)$; a vector ${\bar{x}}\in X$ is said to be a $u$-type solution (resp. $u$-type weak solution) of $\hbox {SP}\left( F,K\right)$ if

$$\begin{aligned}&x\in X, F(x)\le _K^u F\left( {\bar{x}}\right) \Rightarrow F\left( {\bar{x}}\right) \le _K^u F(x)\\&\quad (\text{ resp. }\ x\in X, F(x)<_K^u F\left( {\bar{x}}\right) \Rightarrow F\left( {\bar{x}}\right) <_K^u F(x)), \end{aligned}$$

and let $u$-Eff($\hbox {SP}\left( F,K\right)$) (resp. $u$-WEff($\hbox {SP}\left( F,K\right)$)) be the set of all $u$-type solutions (resp. $u$-type weak solutions) of $\hbox {SP}\left( F,K\right)$.

By using the parametrized embedding function $\psi _t$, problem $\hbox {SP}\left( F,K\right)$ can be embedded into a vector optimization problem on $\left( {\mathcal {Y}}^2\!/\!\equiv , +, \cdot \right)$ as follows:

$$\begin{aligned} \min _{x\in X} f_t(x), \qquad (\hbox {VP}(f_t,{\mathcal {K}})) \end{aligned}$$

where $f_t=\psi _t\circ F:X\rightarrow {\mathcal {Y}}^2\!/\!\equiv$. In Kuroiwa D., Set optimization–a unified embedding approach (submitted), we find the following result.

Proposition 6

• (i) $l$-Eff($\hbox {SP}\left( F,K\right)$)= Eff(VP$(f_0,{\mathcal {K}})$), that is, ${\bar{x}}\in X$ is an $l$-type solution of $\hbox {SP}\left( F,K\right)$ if and only if it is a solution of VP$(f_0,{\mathcal {K}})$;

• (ii) $l$-WEff($\hbox {SP}\left( F,K\right)$)= WEff(VP$(f_0,{\mathcal {K}})$), that is, ${\bar{x}}\in X$ is a weak $l$-type minimizer of $\hbox {SP}\left( F,K\right)$ if and only if it is a weak solution of VP$(f_0,{\mathcal {K}})$;

• (iii) $u$-Eff($\hbox {SP}\left( F,K\right)$)= Eff(VP$(f_1,{\mathcal {K}})$), that is, ${\bar{x}}\in X$ is an $u$-type solution of $\hbox {SP}\left( F,K\right)$ if and only if it is a solution of VP$(f_1,{\mathcal {K}})$;

• (iv) $u$-WEff($\hbox {SP}\left( F,K\right)$)= WEff(VP$(f_1,{\mathcal {K}})$), that is, ${\bar{x}}\in X$ is a weak $u$-type minimizer of $\hbox {SP}\left( F,K\right)$ if and only if it is a weak solution of VP$(f_1,{\mathcal {K}})$.

Next we observe $l$ and $u$-type continuity of $F$ is Hausdorff continuity of $F+K$ and $F-K$.

Proposition 7

For a given set-valued map $F:X\subseteq {\mathbb {R}}^n\rightarrow {\mathcal {Y}}$, $F$ is $l$-type (resp. $u$-type) continuous if and only if vector-valued function $f_0$ (resp. $f_1$) is continuous, where $f_t={\psi _t\circ F}: X\rightarrow {\mathcal {Y}}^2\!/\!\equiv$.

Proof

Fix $p\in \mathrm{int\,}{K}$ and consider the $w^*$-compact base $W=\{\xi \in K^+\mid \langle \xi , p\rangle =1\}$ of $K^+$. Continuity of $f_0$ at ${\bar{x}}$ means that for each $\varepsilon >0$, there exists $\delta >0$ such that, for all $x\in {\bar{x}}+\delta \mathcal{B}_n$,

$$\begin{aligned} \left\| \left[ \left( F\left( x\right) ,F\left( {\bar{x}}\right) \right) \right] \right\| \le \varepsilon . \end{aligned}$$

(13)

(13) is equivalent to

$$\begin{aligned} -\varepsilon \le \inf \langle w,F(x)\rangle -\inf \langle w,F\left( {\bar{x}}\right) \rangle \le \varepsilon , \quad \forall w\in W, \end{aligned}$$

that is

$$\begin{aligned} \inf \langle w,F\left( {\bar{x}}\right) -\varepsilon p\rangle \le \inf \langle w,F(x)\rangle \le \inf \langle w,F\left( {\bar{x}}\right) +\varepsilon p\rangle , \quad \forall w\in W. \end{aligned}$$

(14)

Since $\inf \langle w,A\rangle \le \inf \langle w,B\rangle$ for all $w\in W$ if and only if $A\le ^l_K B$ for every $A,B\in {\mathcal {Y}}$ (Kuroiwa and Nuriya 2006), then we have (14) is equivalent to

$$\begin{aligned} F\left( {\bar{x}}\right) -\varepsilon p\le ^l_K F(x)\le ^l_K F\left( {\bar{x}}\right) +\varepsilon p. \end{aligned}$$

(15)

The equivalence of (13) and (15) shows $f_0$ is continuous if and only if $F$ is $l$-type continuous.

We can show the rest of the proof by a similar argument. $\square$

Proposition 8

A set-valued map $F:X\subseteq {\mathbb {R}}^n\rightarrow {\mathcal {Y}}$ is $l$-type (resp. $u$-type) $*$-quasiconvex if and only if vector-valued function $f_0$ (resp. $f_1$) is ${\mathcal {K}}$-quasiconvex, where $f_t=\psi _t\circ F:X\rightarrow {\mathcal {Y}}^2\!/\!\equiv$.

Proof

At first, we have the following observation:

$$\begin{aligned}&F(x)+B\le ^l_KA \ \quad \text{ if } \text{ and } \text{ only } \text{ if } \ \psi _0(F(x))\le _{\mathcal {K}}[A,B],\ \quad \text{ and }\\&F(x)+B\le ^u_KA \ \quad \text{ if } \text{ and } \text{ only } \text{ if } \ \psi _1(F(x))\le _{\mathcal {K}}[-B,-A]. \end{aligned}$$

From this observation, we have $F$ is $l$-type (resp. $u$-type) $*$-quasiconvex if and only if $\psi _0\circ F$ (resp. $\psi _1\circ F$) is ${\mathcal {K}}$-quasiconvex.$\square$

A similar result holds with respect to $K$-convexity for set-valued maps. The proof is easy and omitted.

Proposition 9

For a given $F:X\subseteq {\mathbb {R}}^n\rightarrow {\mathcal {Y}}$, $F$ is $l$-type (resp. $u$-type) convex if and only if $f_0$ (resp. $f_1$) is ${\mathcal {K}}$-convex, where $f_t=\psi _t\circ F:X\rightarrow {\mathcal {Y}}^2\!/\!\equiv$.

For general set optimization $\hbox {SP}\left( F,K\right)$, the notions of $l$ and $u$-type minimizing sequence and globally well-posedness are introduced by the same way in Sect. 4. $\hbox {SP}\left( F,K\right)$ is $u$-type globally well-posed if every $u$-type minimizing sequence $\left\{ x^n\right\}$ of $\hbox {SP}\left( F,K\right)$ admits a subsequence $\left\{ x^{n_k}\right\}$ such that $\mathrm{dist\,} {\left( x^{n_k},u-\hbox {WEff}(\hbox {P}(F,K))\right) }\rightarrow 0$; Also $\hbox {SP}\left( F,K\right)$ is $l$-type globally well-posed if every $l$-type minimizing sequence $\left\{ x^n\right\}$ of $\hbox {SP}\left( F,K\right)$ admits a subsequence $\left\{ x^{n_k}\right\}$ such that $\mathrm{dist\,} {\left( x^{n_k},l-\hbox {WEff}(\hbox {P}(F,K))\right) }\rightarrow 0$.

In Zhang et al. (2009) a first approach to extend global well-posedness to set optimization has been proposed. Definition 9 is slightly more general since it does not require that minimizing sequences converge to some specific weak efficient solution but just that the distance between the minimizing sequence and the set $\mathrm{WEff\,} {\left( F,K\right) }$ converges to $0$.

Proposition 10

Problem $\hbox {SP}\left( F,K\right)$ is $l$-type (resp. $u$-type) globally well-posed if and only if problem VP($f_0,{\mathcal {K}}$) (resp. VP($f_1,{\mathcal {K}}$)) is globally well-posed according to Definition 7, where $f_t=\psi _t\circ F:X\rightarrow {\mathcal {Y}}^2\!/\!\equiv$.

Proof

In view of Proposition 6, it is enough to prove that $\left\{ x^n\right\}$ is an $l$-type minimizing sequence for $\hbox {SP}\left( F,K\right)$ if and only if it is a minimizing sequence for VP($f_0,{\mathcal {K}}$) (resp. VP($f_1,{\mathcal {K}}$)). Indeed, if $\left\{ x^n\right\}$ is an $l$-type (resp. $u$-type) minimizing sequence for $\hbox {SP}\left( F,K\right)$, then there exists $\varepsilon _n\downarrow 0$ such that

$$\begin{aligned} F\left( x^n\right) -\varepsilon _n\,p \not \subseteq F(x)+\mathrm{int\,}{K}, \quad \forall x\in X. \end{aligned}$$

Hence

$$\begin{aligned} \left[ F(x),\left\{ 0\right\} \right] \not <_{{\mathcal {K}}}\left[ F\left( x^n\right) -\varepsilon _n\,p,\left\{ 0\right\} \right] , \quad \forall x\in X \end{aligned}$$

or, equivalently,    $\forall x\in X$

$$\begin{aligned}&\left[ F(x),\left\{ 0\right\} \right] \not <_{{\mathcal {K}}} \left[ F\left( x^n\right) ,\left\{ 0\right\} \right] +\left[ \left\{ -\varepsilon _n\,p\right\} ,\left\{ 0\right\} \right] ,\; i.e. \\&\left[ F(x),\left\{ 0\right\} \right] \not \in \left[ F\left( x^n\right) ,\left\{ 0\right\} \right] -\mathrm{int\,}{{\mathcal {K}}}-\varepsilon _n\left[ \left\{ p\right\} ,\left\{ 0\right\} \right] . \end{aligned}$$

The proof is complete, observing that $\left[ \left\{ p\right\} ,\left\{ 0\right\} \right] \in \mathrm{int\,}{{\mathcal {K}}}$, (Kuroiwa 2009).

Conversely, assume that $\left\{ x^n\right\}$ is a minimizing sequence for VP($f_0,{\mathcal {K}}$). Then, for some $\left[ P,Q\right] \in \mathrm{int\,}{{\mathcal {K}}}$ and some $\varepsilon _n\downarrow 0$, we have

$$\begin{aligned} \left( \psi _0\circ F\right) \left( x\right) \not <_{{\mathcal {K}}}\left( \psi _0\circ F\right) \left( x^n\right) -\varepsilon _n\, \left[ P,Q\right] , \quad \forall x\in X. \end{aligned}$$

By Lemma 2, we can choose $\left[ P,Q\right] =\left[ {\left\{ p\right\} ,\left\{ 0\right\} }\right] \in \mathrm{int\,}{{\mathcal {K}}}$, with $p\in \mathrm{int\,}{K}$. Hence, for all $x\in X$ we have

$$\begin{aligned} \left[ F(x),\left\{ 0\right\} \right] \not \in \left[ F\left( x^n\right) ,\left\{ 0\right\} \right] -\mathrm{int\,}{{\mathcal {K}}}-\varepsilon _n\left[ \left\{ p\right\} ,\left\{ 0\right\} \right] \end{aligned}$$

from which the conclusion easily follows.

The other equivalence is similar and we leave the proof to the reader.$\square$

Proposition 11

For a given set-valued map $F:X\subseteq {\mathbb {R}}^n\rightarrow {\mathcal {Y}}$, $F$ is $l$-type (resp. $u$-type) lower bounded if and only if $f_0$ (resp. $f_1$) is lower bounded, where $f_t=\psi _t\circ F:X\rightarrow {\mathcal {Y}}^2\!/\!\equiv$.

Proof

We observe

$$\begin{aligned}&\mathrm{Lev}(F+B,\le _K^l,A)=\mathrm{Lev}(f_0,\le _{\mathcal {K}},\left[ A,B\right] ) \quad \text{ and }\\&\mathrm{Lev}(F+B,\le _K^u,A)=\mathrm{Lev}(f_1,\le _{\mathcal {K}},[-B,-A]) \end{aligned}$$

for all $\left[ A,B\right] \in {\mathcal {Y}}$. The proof is follows from Proposition 5.$\square$

1.3 Proof of Theorem 2

Proof

In the uncertain vector optimization problem (UP), let $F=f(\cdot ,{\mathcal {U}})$ and $f_t=\psi _t\circ F:X\rightarrow {\mathcal {Y}}^2\!/\!\equiv$. If $F$ is $u$-type continuous, $u$-type lower bounded, $u$-type $*$-quasiconvex, and $\mathrm{WSol}\mathrm{(RP)}=u$-WEff($\hbox {SP}\left( F,K\right)$) is nonempty and bounded, then $f_1$ is continuous, $f_1$ is lower bounded, $f_1$ is ${\mathcal {K}}$-quasiconvex, and WEff(VP$(f_1,{\mathcal {K}})$) is nonempty and bounded, according to Propositions 7, 8, 11, and 6. Then we have VP($f_1,{\mathcal {K}}$) is globally well-posed from Theorem 1. From Proposition 10, problem $\hbox {SP}\left( F,K\right)$ is $u$-type well-posed, that is the robust counterpart of (UP) is $u$-type well-posed.

The rest of the proof is analogous.$\square$

1.4 Proof of Theorem 4

Proof

In the uncertain vector optimization problem (UP), let $F=f(\cdot ,{\mathcal {U}})$ and $f_t=\psi _t\circ F:X\rightarrow {\mathcal {Y}}^2\!/\!\equiv$. If $F$ is $u$-type convex, and $\mathrm{WSol}\mathrm{(RP)}=u$-WEff($\hbox {SP}\left( F,K\right)$) is nonempty and bounded, then $f_1$ is ${\mathcal {K}}$-convex, and WEff(VP$(f_1,{\mathcal {K}})$) is nonempty and bounded. according to Propositions 9 and 6. Then we have VP($f_1,{\mathcal {K}}$) is globally well-posed from Theorem 3. The proof now is similar to that of Theorem 2.$\square$