On Robust Global Error Bounds for a Class of Uncertain Piecewise Linear Inequality Systems

Abstract

This paper is concerned with the radius of robust global error bounds for an uncertain piecewise linear inequality system where the uncertain data are assumed to be in polytope uncertain sets. We first present a dual characterization for robust global error bounds of this uncertain piecewise linear inequality system. Then, we establish upper and lower bounds for the radius of robust global error bounds of the system of uncertain piecewise linear inequalities in terms of the Minkowski function generalized by the polytope uncertain sets. Moreover, we also investigate robust global error bounds for this uncertain piecewise linear inequality system when the uncertain polytope sets are symmetric sets.

1. Introduction

Let $f_j:{\mathbb{R}}^n\to \mathbb{R},$ $j\in J:=\{1,\dots ,p\}$, be convex functions. Let S be the solution set of the following convex inequality system:

$$\mathrm{Find} x\in {\mathbb{R}}^n\mathrm{such} \mathrm{that}{f}_j\left(x\right)\le 0,j\in J.$$

(1)

This modeling of systems as (1) is said to have a global error bound iff there exists a real number $\tau >0$ such that

$$d(x,S)\le \tau {\left[f\left(x\right)\right]}_{+},\mathrm{for}\mathrm{all}x\in {\mathbb{R}}^{\mathrm{n}},$$

where $f\left(x\right):=\max \{f_j\left(x\right):j\in J\}$, ${\left[f\left(x\right)\right]}_{+}:=\max \{f\left(x\right),0\}$, and $d(x,S)$ is the distance function of a point $x\in {\mathbb{R}}^n$ to the solution set S.

As we know, the investigation of error bounds for convex inequality systems is a very interesting research area in mathematical programming such as sensitivity analysis, convergence analysis, and asymptotic analysis. Global error bound for convex inequality systems was first investigated in [1]. Subsequently, many researchers have been attracted to investigate error bounds for convex inequality systems from different points of view. For example, by using a Slater condition and an asymptotic qualification condition, error bound results for a differentiable convex inequality system are obtained in [2]. An extension of Hoffman’s error bound for polynomial inequalities/equalities systems is obtained in [3]. Hoffman’s error bound for a convex inequality system in a reflexive Banach space is considered in [4] under a Slater constraint qualification. Hoffman’s error bounds for convex quadratic/affine inequality systems in Banach spaces are given in [5] in terms of an Abadie qualification condition. Various types of error bounds for unconstrained and polyhedral-constrained convex polynomials are established in [6]. Error bound moduli for a locally Lipschitz and regular function is studied in [7] by virtue of outer limiting subdifferential sets. Using the Clarke generalized Jacobian, a global error bound for nonmonotone Ky Fan inequalities is obtained in [8]. For more details on error bounds, please see the survey paper [9].

However, many inequality systems are inevitably contaminated by prediction errors or a lack of information. Due to these situations, many researchers have focused on the investigation of inequality systems under uncertain data. This system (1) with uncertain data can be captured by the following uncertain convex inequality system:

$$(\mathrm{SU})\mathrm{Find} x\in {\mathbb{R}}^n\mathrm{such} \mathrm{that}{f}_j(x,u_j)\le 0,j\in J,$$

where $U_j\subset {\mathbb{R}}^m,j\in J$, are uncertain convex compact sets, $u_j\in U_j,$ $j\in J$, are uncertain parameters, and $f_j:U_j\times {\mathbb{R}}^n\to \mathbb{R},$ $j\in J$, are convex functions.

Following robust optimization [10,11,12,13,14,15], the robust counterpart of $\left(\mathrm{SU}\right)$ is formulated as follows

$$\left(\mathrm{SR}\right)\mathrm{Find} x\in {\mathbb{R}}^n\mathrm{such} \mathrm{that}{f}_j(x,u_j)\le 0,\forall u_j\in U_j,j\in J.$$

The uncertain inequality system $\left(\mathrm{SU}\right)$ is said to admit a robust error bound iff the robust counterpart $\left(\mathrm{SR}\right)$ has an error bound, i.e., there exists a real number $\tau >0$ such that

$$d(x,S_R)\le \tau {\left[f_R\left(x\right)\right]}_{+}\mathrm{for}\mathrm{all}x\in {\mathbb{R}}^{\mathrm{n}},$$

where $S_R:=\{x\in {\mathbb{R}}^n:f_j(x,u_j)\le 0,\forall u_j\in U_j,j\in J\}$, $f_{U_j}\left(x\right):=\max \{f_j(x,u_j):u_j\in U_j\}$, $f_R\left(x\right):=\max \{f_{U_j}\left(x\right):j\in J\}$ and ${\left[f_R\left(x\right)\right]}_{+}:=\max \{f_R\left(x\right),0\}$.

Recently, following robust optimization methodology, some characterizations of robust error bounds have been presented for uncertain inequality system $\left(\mathrm{SU}\right)$ and its generalizations. In [16], necessary and sufficient dual conditions for the existence of robust global error bounds are first given for an uncertain linear inequality system with interval uncertain sets. Then, by using project operators and dual conditions, an exact formula for computing the radius of robust global error bounds for this uncertain linear inequality system is also obtained. In [17], some complete characterizations of the existence of robust local error bounds are given for an uncertain linear inequality system. Robust Farkas-Minkowski constraint qualification conditions for an uncertain inequality system is considered in [18] based on the existence of robust global error bounds. By employing Minkowski functions, an exact formula for computing the radius of robust global error bound is obtained in [19] for a piecewise linear inequality system with polytope uncertain sets. By using right derivatives and projection operators, some sufficient and necessary conditions for the existence of robust global error bounds of an uncertain convex inequality system are obtained in [20]. In [21], by using the Ekeland variational principle, a robust error bound for an uncertain convex inequality system with compact uncertain sets is presented. As an application, the authors also obtained robust error bounds for an uncertain polynomial inequality system.

We observe that there exist only two papers devoted to the study of the radius of robust error bounds for uncertain linear inequality systems; see [16,19]. One of the most important reasons is that the necessary dual condition for the existence of robust error bounds for uncertain linear inequality systems in [16,19] is not available for the case of nonlinear inequality systems. It is worth noting that such dual conditions play an important role in the study of the radius of robust error bounds of an uncertain inequality system. Therefore, in this paper, we consider an uncertain piecewise linear inequality system with general polytope uncertain sets. In this case, we can show that necessary and sufficient dual conditions for the existence of robust global error bounds are satisfied. More precisely, we first give necessary and sufficient dual conditions of the existence of robust global error bounds for this uncertain piecewise linear inequality system. Then, we introduce the concept of the radius of robust global error bounds. By virtue of the dual conditions and the so-called hypographical set of the nominal system, we give an upper bound and a lower bound for radius of the robust global error bound of this uncertain piecewise linear inequality system. Moreover, we give a numerical example to illustrate the obtained results. As a special case, we also given some results on robust global error bounds for this uncertain piecewise linear inequality system with uncertain symmetric polytope sets.

This paper is organized as follows. Section 2 describes some basic notions and preliminary results for uncertain piecewise linear inequality systems. Section 3 presents upper and lower bounds for radius of robust global error bound of an uncertain piecewise linear inequality system with general polytope uncertain sets. Section 4 provides the conclusions.

2. Preliminaries

In this section, we give some basic notations and preliminary results that will be used in the sequel. Unless otherwise specified, let ${\mathbb{R}}^n$ be the n-dimensional Euclidean space equipped with the usual Euclidean norm $\parallel ·\parallel$. The origin of ${\mathbb{R}}^n$ is denoted by $0_n$. The inner product in ${\mathbb{R}}^n$ is denoted by $\langle x,y\rangle :=x^{\top }y$ for any $x,y\in {\mathbb{R}}^n$. The so-called simplex in ${\mathbb{R}}^n$ is denoted by

$${\Delta }_n:=\left\{\lambda :=\left({\lambda }_1,\dots ,{\lambda }_n\right)\in {\mathbb{R}}^n:{\lambda }_j\ge 0,\sum _{j=1}^n{\lambda }_j=1\right\}.$$

For a set $\mathsf{\Theta }\subseteq {\mathbb{R}}^n$, the interior, the closure, the convex hull and the conical hull of $\mathsf{\Theta }$ are denoted by $\mathrm{int}\mathsf{\Theta }$, $\mathrm{cl}\mathsf{\Theta }$, $\mathrm{conv}\mathsf{\Theta }$ and $\mathrm{cone}\mathsf{\Theta }$, respectively. The distance function $d(·,\mathsf{\Theta })$ of $\mathsf{\Theta }\subseteq {\mathbb{R}}^n$ is defined by

$$d(x,\mathsf{\Theta }):=\inf \{\parallel x-y\parallel :y\in \mathsf{\Theta }\},\forall x\in {\mathbb{R}}^n.$$

We shall adopt the convention that $d(x,\mathsf{\Theta }):=+\infty$ when $\mathsf{\Theta }=\varnothing$.

Let $\mathsf{\Lambda }$ be a nonempty and convex subset of ${\mathbb{R}}^n$ with $0_n\in \mathrm{int}\mathsf{\Lambda }$. The function

$${\varphi }_{\mathsf{\Lambda }}\left(x\right):=\inf \{t>0:x\in t\mathsf{\Lambda }\},x\in {\mathbb{R}}^n,$$

(2)

is called Minkowski function of $\mathsf{\Lambda }$.

The following properties of the Minkowski function ${\varphi }_{\mathsf{\Lambda }}$ are obtained in [22].

Lemma 1.

Let $\mathsf{\Lambda }$ be a convex subset of ${\mathbb{R}}^n$ with $0_n\in \mathrm{int}\mathsf{\Lambda }$. Then, the following properties hold:

(i)

${\varphi }_{\mathsf{\Lambda }}$ is sublinear and continuous;

(ii)

$\left\{x\in {\mathbb{R}}^n:{\varphi }_{\mathsf{\Lambda }}\left(x\right)\le 1\right\}=\mathrm{cl}\mathsf{\Lambda }$;

(iii)

If $\mathsf{\Lambda }$ is bounded and symmetric (i.e., $x\in \mathsf{\Lambda }\Rightarrow -x\in \mathsf{\Lambda }$), then ${\varphi }_{\mathsf{\Lambda }}:={\parallel ·\parallel }_{\mathsf{\Lambda }}$ is a norm on ${\mathbb{R}}^n$ generated by $\mathsf{\Lambda }$.

In what follows, let $Z_j\subset {\mathbb{R}}^{n+1}$, $j\in J$, be polytope uncertain sets with $0_{n+1}\in \mathrm{int}{Z}_j$. Let $({\overline{a}}_j,{\overline{b}}_j)\in {\mathbb{R}}^n\times \mathbb{R}$ and ${\tilde{\alpha }}_j\in {\mathbb{R}}_{+}$. For any ${\alpha }_j\in {\mathbb{R}}_{+}$, $j\in J$, the uncertain sets $U_j^{{\tilde{\alpha }}_j,{\alpha }_j}$, $j\in J$, are defined as follows:

$$U_j^{{\tilde{\alpha }}_j,{\alpha }_j}:=({\overline{a}}_j,{\overline{b}}_j)+({\alpha }_j+{\tilde{\alpha }}_j)Z_j,j\in J.$$

(3)

Motivated by [16,19], in this paper, we consider the following piecewise linear inequality system under polytope uncertain sets

$$({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})\mathrm{Find} x\in {\mathbb{R}}^n\mathrm{such} \mathrm{that}{g}_j\left(x\right)+a_j^{\top }x-b_j\le 0,j\in J,$$

where $g_j:{\mathbb{R}}^n\to \mathbb{R}$, $j\in J$, are given functions and $(a_j,b_j)\in U_j^{{\tilde{\alpha }}_j,{\alpha }_j}$ are uncertain parameters. In what follows, unless otherwise specified, we assume that $g_j$, $j\in J$, are piecewise linear functions defined by

$$g_j\left(x\right):=\underset{x\in {\mathbb{R}}^n}{\max }\left\{c_j^{k\top }x-d_j^k:k\in I\right\},$$

(4)

where $\left(c_j^k,d_j^k\right)\in {\mathbb{R}}^n\times \mathbb{R}$, $k\in I:=\{1,\dots ,l\}$, $j\in J$.

To deal with $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$, it is usually associated with the so-called robust counterpart

$$({\mathrm{SR}}_{{\tilde{\alpha }}_j,{\alpha }_j})\mathrm{Find} x\in {\mathbb{R}}^n\mathrm{such} \mathrm{that}{g}_j\left(x\right)+a_j^{\top }x-b_j\le 0,\forall (a_j,b_j)\in U_j^{{\tilde{\alpha }}_j,{\alpha }_j},j\in J.$$

In what follows, we always assume that the system $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ admits a robust global error bound at ${\tilde{\alpha }}_j=0$, that is the nominal system

$$({\mathrm{SR}}_{0,{\alpha }_j})\mathrm{Find} x\in {\mathbb{R}}^n\mathrm{such} \mathrm{that}{g}_j\left(x\right)+a_j^{\top }x-b_j\le 0,\forall (a_j,b_j)\in U_j^{0,{\alpha }_j},j\in J,$$

admits a global error bound. Here, $U_j^{0,{\alpha }_j}=({\overline{a}}_j,{\overline{b}}_j)+{\alpha }_j{Z}_j$, for all $j\in J$.

Now, we give the following result, which can be regarded as a dual characterization of the existence of the robust global error bound of $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$.

Proposition 1.

The system $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ has a robust global error bound if and only if

$$(0_n,-1)\notin \mathrm{cone}\left\{\bigcup _{k\in I,i\in M,j\in J}\left(c_j^k+a_j^{i,{\tilde{\alpha }}_j,{\alpha }_j},d_j^k+b_j^{i,{\tilde{\alpha }}_j,{\alpha }_j}\right)\right\}.$$

(5)

Here, $M:=\{1,\dots ,m\}$, $\left(a_j^{i,{\tilde{\alpha }}_j,{\alpha }_j},b_j^{i,{\tilde{\alpha }}_j,{\alpha }_j}\right)\in {\mathbb{R}}^n\times \mathbb{R}$, $i\in M$, $j\in J$, are the extreme points of the polytope uncertain set $U_j^{{\tilde{\alpha }}_j,{\alpha }_j}$, i.e.,

$$U_j^{{\tilde{\alpha }}_j,{\alpha }_j}=\mathrm{conv}\left\{\left(a_j^{1,{\tilde{\alpha }}_j,{\alpha }_j},b_j^{1,{\tilde{\alpha }}_j,{\alpha }_j}\right),\dots ,\left(a_j^{m,{\tilde{\alpha }}_j,{\alpha }_j},b_j^{m,{\tilde{\alpha }}_j,{\alpha }_j}\right)\right\},j\in J.$$

Proof. 

The proof is similar to the one given in Theorem 3.7 of [17], and so, it is omitted. □

Following [16], we introduce the following concept of radius of robust global error bound for the system $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$. It is worth noting that this concept is motivated by the concepts of radius of robust feasibility for uncertain optimization problems; see [23,24,25,26,27,28] for more details.

Definition 1.

The radius of robust global error bound for $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ is defined as

$$\rho :=\sup \underset{j\in J}{\inf }\left\{{\alpha }_j:({\mathrm{SR}}_{{\tilde{\alpha }}_j,{\alpha }_j})\mathrm{admits}\mathrm{a}\mathrm{global}\mathrm{error}\mathrm{bound}\right\}.$$

(6)

Remark 1.

Obviously, if ${\tilde{\alpha }}_j=0$, $j\in J$, the radius of robust global error bound ρ of $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ gives a numerical value for the largest polytope uncertain set $U_j^{{\tilde{\alpha }}_j,{\alpha }_j}$ under which $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ has a robust global error bound.

3. Characterizations of Radius of Robust Global Error Bound

This section is devoted to the investigation of radius of robust global error bound for $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ based on the Minkowski functions. Note that we need the so-called hypographical set [29,30] of the nominal system $({\mathrm{SR}}_{0,{\alpha }_j})$, which is define by

$$H\left(S\right):=\mathrm{conv}\left\{\bigcup _{k\in I,j\in J}(-c_j^k-{\overline{a}}_j,-d_j^k-{\overline{b}}_j)\right\}+{\mathbb{R}}_{+}(0_n,-1).$$

(7)

Theorem 1.

The radius ρ of robust global error bound of $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ satisfies

$$\underset{(u,v)\in H\left(S\right)}{\inf }\underset{j\in J}{\inf }{\varphi }_{Z_j}(u,v)-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\}\le \rho \le \underset{(u,v)\in H\left(S\right)}{\inf }\underset{j\in J}{\sup }{\varphi }_{Z_j}(u,v)-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\}.$$

Proof. 

We first show that

$$\rho \le \underset{(u,v)\in H\left(S\right)}{\inf }\underset{j\in J}{\sup }{\varphi }_{Z_j}(u,v)-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\}.$$

(8)

Suppose that there exist ${\alpha }_j\ge 0$, $j\in J$, such that $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ admits a robust global error bound. By Proposition 1, it follows that

$$(0_n,-1)\notin \mathrm{cone}\left\{\bigcup _{k\in I,i\in M,j\in J}\left(c_j^k+a_j^{i,{\tilde{\alpha }}_j,{\alpha }_j},d_j^k+b_j^{i,{\tilde{\alpha }}_j,{\alpha }_j}\right)\right\},$$

(9)

where $\left(a_j^{i,{\tilde{\alpha }}_j,{\alpha }_j},b_j^{i,{\tilde{\alpha }}_j,{\alpha }_j}\right)\in {\mathbb{R}}^n\times \mathbb{R}$, $i\in M$, $j\in J$, are the extreme points of $U_j^{{\tilde{\alpha }}_j,{\alpha }_j}$. Obviously, (9) is equivalent to

$$(0_n,-1)\notin \mathrm{cone}\left\{\bigcup _{(a_j,b_j)\in U_j^{{\tilde{\alpha }}_j,{\alpha }_j},k\in I,j\in J}\left(c_j^k+a_j,d_j^k+b_j\right)\right\}.$$

Then, it follows from $U_j^{{\tilde{\alpha }}_j,{\alpha }_j}=({\overline{a}}_j,{\overline{b}}_j)+({\alpha }_j+{\tilde{\alpha }}_j)Z_j$ that

$$(0_n,-1)\notin \mathrm{cone}\left\{\bigcup _{k\in I,j\in J}\left(c_j^k+{\overline{a}}_j,d_j^k+{\overline{b}}_j\right)+({\alpha }_j+{\tilde{\alpha }}_j)Z_j\right\}.$$

(10)

Now, take any $(u,v)\in H\left(S\right)$. By (7), there exist ${\lambda }_j^k\ge 0$, $k\in I$, $j\in J$, with ${\displaystyle \sum _{k\in I}}{\displaystyle \sum _{j\in J}}{\lambda }_j^k=1$, and $\mu \ge 0$, such that

$$(u,v)=\sum _{k\in I}\sum _{j\in J}{\lambda }_j^k\left(-c_j^k-{\overline{a}}_j,-d_j^k-{\overline{b}}_j\right)+\mu (0_n,-1).$$

(11)

Let $ϵ>0$. It is clear from (11) that

$$(0_n,1)=\sum _{k\in I}\sum _{j\in J}\frac{{\lambda }_j^k}{\mu +ϵ}\left(\left(-c_j^k-{\overline{a}}_j,-d_j^k-{\overline{b}}_j\right)-(u,v-ϵ)\right).$$

(12)

By the definition of ${\varphi }_{Z_j}$, we have

$$(u,v-ϵ)\in {\varphi }_{Z_j}(u,v-ϵ)Z_j.$$

Thus, we deduce from (12) that

$$(0_n,-1)\in \mathrm{cone}\left\{\bigcup _{k\in I,j\in J}\left(c_j^k+{\overline{a}}_j,d_j^k+{\overline{b}}_j\right)+{\varphi }_{Z_j}(u,v-ϵ)Z_j\right\}.$$

This, together with (10), gives

$$\underset{j\in J}{\inf }\left\{{\alpha }_j+{\tilde{\alpha }}_j\right\}\le \underset{j\in J}{\sup }{\varphi }_{Z_j}(u,v-ϵ).$$

(13)

Note that

$$\underset{j\in J}{\inf }\left\{{\alpha }_j\right\}+\underset{j\in J}{\inf }\left\{{\tilde{\alpha }}_j\right\}\le \underset{j\in J}{\inf }\{{\alpha }_j+{\tilde{\alpha }}_j\}.$$

Then, it follows from (13) that

$$\underset{j\in J}{\inf }\left\{{\alpha }_j\right\}\le \underset{j\in J}{\sup }{\varphi }_{Z_j}(u,v-ϵ)-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\}.$$

Taking infimum over all $(u,v)\in H\left(S\right)$, we obtain

$$\sup \underset{j\in J}{\inf }\left\{{\alpha }_j\right\}\le \underset{(u,v)\in H\left(S\right)}{\inf }\underset{j\in J}{\sup }{\varphi }_{Z_j}(u,v-ϵ)-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\}.$$

(14)

Now, by the definition of the radius $\rho$, Lemma 1(i) and letting $ϵ\to 0$ in (14), it follows that

$$\sup \underset{j\in J}{\inf }\left\{{\alpha }_j\right\}\le \underset{(u,v)\in H\left(S\right)}{\inf }\underset{j\in J}{\sup }{\varphi }_{Z_j}(u,v)-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\}.$$

This means that (8) holds.

Now, we claim that

$$\rho \ge \underset{(u,v)\in H\left(S\right)}{\inf }\underset{j\in J}{\inf }{\varphi }_{Z_j}(u,v)-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\}.$$

(15)

Let $ϵ>0$ and ${\overline{\alpha }}_j:=\rho +ϵ$. By using the similar method of the inequality (19) of Theorem 3.1 in [19], we have

$$\underset{(u,v)\in H\left(S\right)}{\inf }\underset{j\in J}{\inf }{\varphi }_{Z_j}(u,v)\le {\overline{\alpha }}_j+{\tilde{\alpha }}_j=\rho +ϵ+{\tilde{\alpha }}_j.$$

(16)

Taking $ϵ\to 0$ in (16), we have

$$\underset{(u,v)\in H\left(S\right)}{\inf }\underset{j\in J}{\inf }{\varphi }_{Z_j}(u,v)-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\}\le \rho .$$

Thus, (15) holds and the proof is complete. □

Now, we give a numerical example that illustrates how we employ Theorem 1 to calculate upper and lower bounds of the radius of robust global error bound for $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ under $Z_j$, $j\in J$, are simple non-symmetric polytopic uncertain sets.

Example 1.

For $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$. Let $n:=1$ and $p=l:=2$. Let $({\overline{a}}_1,{\overline{b}}_1):=(1,0)$, $({\overline{a}}_2,{\overline{b}}_2)=:(0,1)\in {\mathbb{R}}^2$, and ${\tilde{\alpha }}_1={\tilde{\alpha }}_2:=0\in \mathbb{R}$. Let the polytope uncertain sets $Z_1\subseteq {\mathbb{R}}^2$ and $Z_2\subseteq {\mathbb{R}}^2$ be defined, respectively, by

$$Z_1=\left\{(z^1,z^2)\in {\mathbb{R}}^2:\mid z^1+1\mid \le 2,z^1+z^2\le 3,z^2\ge -1,z^1+z^2\ge -2\right\}$$

and

$$Z_2=\left\{(z^1,z^2)\in {\mathbb{R}}^2:\mid z^1\mid \le 8,\mid z^2+2\mid \le 5,\mid z^1+z^2\mid \le 6\right\}.$$

Clearly, for any ${\alpha }_1={\alpha }_2:=\alpha \in {\mathbb{R}}_{+}$,

$$U_1^{{\tilde{\alpha }}_1,{\alpha }_1}=(1,0)+\alpha Z_1,and{U}_2^{{\tilde{\alpha }}_2,{\alpha }_2}=(0,1)+\alpha Z_2.$$

Moreover, let $(c_1^1,d_1^1)=(c_2^1,d_2^1):=(1,0)$ and $(c_1^2,d_1^2)=(c_2^2,d_2^2):=(0,2)$. Clearly, $g_1\left(x\right)=g_2\left(x\right)=\max \{x,-2\}$. Then, $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ becomes

$$Findx\in {\mathbb{R}}^{n}such that\max \{x,-2\}+a_j^{\top }x-b_j\le 0,j=1,2,$$

where $(a_j,b_j)\in U_j^{{\tilde{\alpha }}_j,{\alpha }_j}$, $j=1,2$. Moreover, we have

$$\begin{array}{ccc}\hfill H\left(S\right)& =& \mathrm{conv}\left\{\left(-c_j^k-{\overline{a}}_j,-d_j^k-{\overline{b}}_j\right):k=1,2,j=1,2\right\}+{\mathbb{R}}_{+}(0,-1)\hfill \\ & =& \mathrm{conv}\{(-2,0),(-1,-2),(-1,-1),(0,-3)\}+{\mathbb{R}}_{+}(0,-1).\hfill \end{array}$$

On the other hand, for any $(u,v)\in {\mathbb{R}}^2$, it is easy to show that

$$(u,v)\in t{Z}_1\iff \left\{\begin{array}{cc}\hfill t& \ge -\frac{1}{3}u,t\ge u,\hfill \\ \hfill t& \ge -v,\hfill \\ \hfill t& \ge -\frac{1}{2}u-\frac{1}{2}v,t\ge \frac{1}{3}u+\frac{1}{3}v.\hfill \end{array}\right.$$

Then, for each $(u,v)\in {\mathbb{R}}^2$,

$$\begin{array}{cc}\hfill {\varphi }_{Z_1}(u,v)& =\inf \left\{t>0:(u,v)\in t{Z}_1\right\}\hfill \\ \hfill & =\inf \left\{t>0:t\ge \max \left\{-\frac{1}{3}u,u,-v,-\frac{1}{2}u-\frac{1}{2}v,\frac{1}{3}u+\frac{1}{3}v\right\}\right\}\hfill \\ \hfill & =\max \left\{-\frac{1}{3}u,u,-v,-\frac{1}{2}u-\frac{1}{2}v,\frac{1}{3}u+\frac{1}{3}v\right\}.\hfill \end{array}$$

Thus, for any $(u,v)\in H\left(S\right)$,

$${\varphi }_{Z_1}(u,v)=\left\{\begin{array}{cc}\hfill -\frac{1}{2}u-\frac{1}{2}v,& \mathrm{if}u+v\le -2,-2\le u\le v,u,v\le 0,\hfill \\ \hfill -v,& \mathrm{if}2u+v\le -3,u\ge v,u\ge -2,u,v\le 0.\hfill \end{array}\right.$$

Similarly, for any $(u,v)\in {\mathbb{R}}^2$, it is easy to show that

$$(u,v)\in t{Z}_2\iff \left\{\begin{array}{cc}\hfill t& \ge -\frac{1}{8}u,t\ge \frac{1}{8}u,\hfill \\ \hfill t& \ge -\frac{1}{3}v,t\ge \frac{1}{7}v,\hfill \\ \hfill t& \ge -\frac{1}{6}u-\frac{1}{6}v,t\ge \frac{1}{6}u+\frac{1}{6}v.\hfill \end{array}\right.$$

Therefore, for each $(u,v)\in {\mathbb{R}}^2$,

$$\begin{array}{cc}\hfill {\varphi }_{Z_2}(u,v)& =\inf \left\{t>0:(u,v)\in t{Z}_2\right\}\hfill \\ \hfill & =\inf \left\{t>0:t\ge \max \left\{-\frac{1}{8}u,\frac{1}{8}u,-\frac{1}{3}v,\frac{1}{7}v,-\frac{1}{6}u-\frac{1}{6}v,\frac{1}{6}u+\frac{1}{6}v\right\}\right\}\hfill \\ \hfill & =\max \left\{-\frac{1}{8}u,\frac{1}{8}u,-\frac{1}{3}v,\frac{1}{7}v,-\frac{1}{6}u-\frac{1}{6}v,\frac{1}{6}u+\frac{1}{6}v\right\}.\hfill \end{array}$$

Thus, for any $(u,v)\in H\left(S\right)$,

$${\varphi }_{Z_2}(u,v)=\left\{\begin{array}{cc}\hfill -\frac{1}{6}u-\frac{1}{6}v,& \mathrm{if}u+v\le -2,-2\le u\le v,u,v\le 0,\hfill \\ \hfill -\frac{1}{3}v,& \mathrm{if}2u+v\le -3,u\ge v,u\ge -2,u,v\le 0.\hfill \end{array}\right.$$

Obviously,

$$\begin{array}{cc}\hfill \underset{(u,v)\in H\left(S\right)}{\inf }\underset{j\in J}{\sup }{\varphi }_{Z_j}(u,v)& =\underset{(u,v)\in H\left(S\right)}{\inf }\sup \left\{{\varphi }_{Z_1}(u,v),{\varphi }_{Z_2}(u,v)\right\}\hfill \\ \hfill & =\underset{(u,v)\in H\left(S\right)}{\inf }{\varphi }_{Z_1}(u,v)=1,\hfill \end{array}$$

and

$$\begin{array}{cc}\hfill \underset{(u,v)\in H\left(S\right)}{\inf }\underset{j\in J}{\inf }{\varphi }_{Z_j}(u,v)& =\underset{(u,v)\in H\left(S\right)}{\inf }\inf \left\{{\varphi }_{Z_1}(u,v),{\varphi }_{Z_2}(u,v)\right\}\hfill \\ \hfill & =\underset{(u,v)\in H\left(S\right)}{\inf }{\varphi }_{Z_2}(u,v)=\frac{1}{3}.\hfill \end{array}$$

Consequently, we have

$$\frac{1}{3}\le \rho \le 1.$$

Thus, Theorem 1 is applicable.

In the special case when the functions $g_1=···=g_p:=0$, we can easily obtain the following result, which is a new result on robust error bound not yet being considered in the recent literature.

Corollary 1.

For the system $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$, assume that the functions $g_1=···=g_p:=0$. Then, the radius ρ of robust global error bound of $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ satisfies

$$\underset{(u,v)\in \widehat{H}\left(S\right)}{\inf }\underset{j\in J}{\inf }{\varphi }_{Z_j}(u,v)-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\}\le \rho \le \underset{(u,v)\in \widehat{H}\left(S\right)}{\inf }\underset{j\in J}{\sup }{\varphi }_{Z_j}(u,v)-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\},$$

where

$$\widehat{H}\left(S\right):=\mathrm{conv}\left\{\bigcup _{j\in J}(-{\overline{a}}_j,-{\overline{b}}_j)\right\}+{\mathbb{R}}_{+}(0_n,-1).$$

Remark 2.

Corollary 1 encompasses Theorem 4.2 of [16], where the uncertain sets are interval uncertain sets.

In the special case when $Z_1=···=Z_p:=Z$ is a convex and compact subset of ${\mathbb{R}}^{n+1}$ with $0_{n+1}\in \mathrm{int}Z$, and ${\tilde{\alpha }}_1=···={\tilde{\alpha }}_p:=0\in \mathbb{R}$. Then, for any ${\alpha }_1=···={\alpha }_p:=\alpha \in {\mathbb{R}}_{+}$, the uncertain set $U_j^{{\tilde{\alpha }}_j,{\alpha }_j}$ reduces to

$$U_j^{\alpha }:=({\overline{a}}_j,{\overline{b}}_j)+\alpha Z,j\in J.$$

(17)

Thus, $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ becomes

$$\mathrm{Find}x\in {\mathbb{R}}^n\mathrm{such} \mathrm{that}{g}_j\left(x\right)+a_j^{\top }x-b_j\le 0,j\in J,({\mathrm{SU}}_{\alpha })$$

where $g_j:{\mathbb{R}}^n\to \mathbb{R}$, $j\in J$, are defined as (4) and $(a_j,b_j)\in U_j^{\alpha }$ are uncertain parameters.

Theorem 2.

Theorem 3.1 of [19]. Assume that $({\mathrm{SU}}_{\alpha })$ has a robust global error bound at $\alpha =0$. Then, the radius $\widehat{\rho }$ of robust global error bound of $({\mathrm{SU}}_{\alpha })$ is given by

$$\widehat{\rho }=\underset{(u,v)\in H\left(S\right)}{\inf }{\varphi }_Z(u,v).$$

Remark 3.

Note that Example 1 can also used to illustrate how we employ Theorem 2 to calculate the radius $\widehat{\rho }$ of robust global error bound for $({\mathrm{SU}}_{\alpha })$. For example, let

$$Z=\left\{(z^1,z^2)\in {\mathbb{R}}^2:\mid z^1+1\mid \le 2,z^1+z^2\le 3,z^2\ge -1,z^1+z^2\ge -2\right\}.$$

By Example 1, we have $\widehat{\rho }=1$. Similarly, if

$$Z=\left\{(z^1,z^2)\in {\mathbb{R}}^2:\mid z^1\mid \le 8,\mid z^2+2\mid \le 5,\mid z^1+z^2\mid \le 6\right\},$$

then, from Example 1, we have $\widehat{\rho }=\frac{1}{3}$.

At the end of this section, we consider the system $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ when the polytope $Z_j$ is symmetric. In this case, the bounds for the radius of robust global error bound of $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ can be checked by solving a specified norm of a convex optimization problem. Here, the so-called simplex in ${\mathbb{R}}^{pl}$ is denoted by

$${\Delta }_p^l:=\left\{\lambda :=\left({\lambda }_1^1,\dots ,{\lambda }_1^l,\dots ,{\lambda }_p^1,\dots ,{\lambda }_p^l\right)\in {\mathbb{R}}^{pl}:{\lambda }_j^k\ge 0,\sum _{k\in I}\sum _{j\in J}{\lambda }_j^k=1\right\}.$$

Using a similar argument as that given for the proof of Corollary 3.1 of [19], we can deduce the following result.

Theorem 3.

Suppose that the polytope $Z_j$ are convex, compact and symmetric subsets with $0_{n+1}\in \mathrm{int}{Z}_j$, $j\in J$. Then, the radius ρ of robust global error bound of $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ satisfies

$$\begin{array}{cc}\hfill & \underset{(\lambda ,\mu )\in {\Delta }_p^l\times {\mathbb{R}}_{+}}{\inf }\underset{j\in J}{\inf }{∥\left(\sum _{k\in I}\sum _{j\in J}{\lambda }_j^k(c_j^k+{\overline{a}}_j),\mu +\sum _{k\in I}\sum _{j\in J}{\lambda }_j^k(d_j^k+{\overline{b}}_j)\right)∥}_{Z_j}-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\}\le \rho \le \hfill \\ \hfill & \underset{(\lambda ,\mu )\in {\Delta }_p^l\times {\mathbb{R}}_{+}}{\inf }\underset{j\in J}{\sup }{∥\left(\sum _{k\in I}\sum _{j\in J}{\lambda }_j^k(c_j^k+{\overline{a}}_j),\mu +\sum _{k\in I}\sum _{j\in J}{\lambda }_j^k(d_j^k+{\overline{b}}_j)\right)∥}_{Z_j}-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\},\hfill \end{array}$$

where ${\parallel ·\parallel }_{Z_j}$ is a norm on ${\mathbb{R}}^{n+1}$ generated by $Z_j$, i.e., for any $(u_j,v_j):=(u_j^1,\dots ,u_j^n,v_j)\in {\mathbb{R}}^{n+1}$,

$$\parallel (u_j,v_j){\parallel }_{Z_j}=\inf \{t_j>0:(u_j,v_j)\in t_j{Z}_j\}.$$

In the special case when $Z_j$ are convex, compact and symmetric subsets with $0_{n+1}\in \mathrm{int}{Z}_j$, $j\in J$, we can easily obtain the following result for $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ with $g_1=\cdots =g_p:=0$.

Corollary 2.

Suppose that the polytope $Z_j$ are convex, compact, and symmetric subsets with $0_{n+1}\in \mathrm{int}{Z}_j$, $j\in J$. For the system $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$, assume that the functions $g_1=\cdots =g_p:=0$. Then, the radius ρ of robust global error bound of $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ satisfies

$$\begin{array}{cc}\hfill & \underset{(\lambda ,\mu )\in {\Delta }_p\times {\mathbb{R}}_{+}}{\inf }\underset{j\in J}{\inf }{∥\left(\sum _{j\in J}{\lambda }_j{\overline{a}}_j,\mu +\sum _{j\in J}{\lambda }_j{\overline{b}}_j\right)∥}_{Z_j}-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\}\le \rho \hfill \\ \hfill & \le \underset{(\lambda ,\mu )\in {\Delta }_p\times {\mathbb{R}}_{+}}{\inf }\underset{j\in J}{\sup }{∥\left(\sum _{j\in J}{\lambda }_j{\overline{a}}_j,\mu +\sum _{j\in J}{\lambda }_j{\overline{b}}_j\right)∥}_{Z_j}-\underset{j\in J}{\min }\left\{{\tilde{\alpha }}_j\right\},\hfill \end{array}$$

where ${\parallel ·\parallel }_{Z_j}$ is a norm on ${\mathbb{R}}^{n+1}$ generated by $Z_j$, i.e., for any $(u_j,v_j):=(u_j^1,\dots ,u_j^n,v_j)\in {\mathbb{R}}^{n+1}$,

$$\parallel (u_j,v_j){\parallel }_{Z_j}=\inf \{t_j>0:(u_j,v_j)\in t_j{Z}_j\}.$$

Similarly, it is easy to show that the following result for $({\mathrm{SU}}_{\alpha })$ holds.

Corollary 3.

Corollary 3.1 of [19]. Let $\alpha \in \mathbb{R}$ and let polytope Z be a convex, compact, and symmetric subset of ${\mathbb{R}}^{n+1}$ with $0_{n+1}\in \mathrm{int}Z$. Assume that $({\mathrm{SU}}_{\alpha })$ has a robust global error bound at $\alpha =0$. Then, the radius $\widehat{\rho }$ of robust global error bound of $({\mathrm{SU}}_{\alpha })$ is given by

$$\widehat{\rho }=\underset{(\lambda ,\mu )\in {\Delta }_p^l\times {\mathbb{R}}_{+}}{\min }{∥\left(\sum _{k\in I}\sum _{j\in J}{\lambda }_j^k(c_j^k+{\overline{a}}_j),\mu +\sum _{k\in I}\sum _{j\in J}{\lambda }_j^k(d_j^k+{\overline{b}}_j)\right)∥}_Z,$$

where ${\parallel ·\parallel }_Z$ is a norm on ${\mathbb{R}}^{n+1}$ generated by Z, i.e., for any $(u,v):=(u^1,\dots ,u^n,v)\in {\mathbb{R}}^{n+1}$,

$${\parallel (u,v)\parallel }_Z=\inf \{t>0:(u,v)\in tZ\}.$$

4. Conclusions

In this paper, following the framework of robust optimization, we consider the radius of robust global error bound of a class of uncertain piecewise linear systems with general polytope uncertain sets. By using the Minkowski function, an upper bound and a lower bound for radius of the robust global error bound of $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ are established. We also give upper and lower bounds of radius of the robust global error bound for $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$ when the uncertain polytope sets are symmetric sets. The results obtained in this paper improve and extend the corresponding results obtained in [16,19].

Although some interesting results of the robust global error bounds have been given for $({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j})$, in this paper, there are also some questions to be considered in the future, for example, using similar methods to [16,17,20,21], whether we can present some results of robust global error bounds for $\left({\mathrm{SU}}_{{\tilde{\alpha }}_j,{\alpha }_j}\right)$ when the uncertain sets are general convex and compact sets. On the other hand, it is of great interest to extend our approach to investigate two-stage adjustable optimization problems [31], such as inventory-production management problems with demand uncertainty and lot-sizing problems with demand uncertainty.