Evenly Convex Sets: Linear Systems Containing Strict Inequalities

Abstract

This chapter deals with linear systems with an arbitrary (possibly infinite) number of weak and/or strict inequalities and their solution sets, the so-called evenly convex sets, which can be seen as the two faces of a same coin. Section 1.1 provides different characterizations of evenly convex sets and shows that this class of sets enjoys most of the well-known properties of the subclass of closed convex sets. Since the intersection of evenly convex sets belongs to the same family, any set has an evenly convex hull. Section 1.2 is focussed on the operations with evenly convex hulls and their relationships with other hulls. Section 1.3 reviews different types of separation theorems involving evenly convex sets. Section 1.4 provides existence theorems for linear systems with strict inequalities and characterizations of the linear inequalities which are consequence of consistent systems (those systems with nonempty solution set), which allows us to tackle set containment problems involving evenly convex sets. Section 1.5 is aimed to study the so-called evenly linear semi-infinite programming problems (i.e., linear semi-infinite programming problems with strict inequalities). Finally, Sect. 1.6 describes applications to polarity (treated in a detailed way as it was the problem which inspired the concept of evenly convex set), semi-infinite games, approximate reasoning, optimality conditions in mathematical programming, and strict separation of families of sets.

This chapter deals with linear systems with an arbitrary (possibly infinite) number of weak and/or strict inequalities and their solution sets, the so-called evenly convex sets, which can be seen as the two faces of a same coin. Section 1.1 provides different characterizations of evenly convex sets and shows that this class of sets enjoys most of the well-known properties of the subclass of closed convex sets. Since the intersection of evenly convex sets belongs to the same family, any set has an evenly convex hull. Section 1.2 is focussed on the operations with evenly convex hulls and their relationships with other hulls. Section 1.3 reviews different types of separation theorems involving evenly convex sets. Section 1.4 provides existence theorems for linear systems with strict inequalities and characterizations of the linear inequalities which are consequence of consistent systems (those systems with nonempty solution set), which allows us to tackle set containment problems involving evenly convex sets. Section 1.5 is aimed to study the so-called evenly linear semi-infinite programming problems (i.e., linear semi-infinite programming problems with strict inequalities). Finally, Sect. 1.6 describes applications to polarity (treated in a detailed way as it was the problem which inspired the concept of evenly convex set), semi-infinite games, approximate reasoning, optimality conditions in mathematical programming, and strict separation of families of sets.

1.1 Evenly Convex Sets

Since any equation can be replaced by two inequalities, we shall consider (linear) systems in $\mathbb {R}^{n}$ of the form

$$\displaystyle \begin{aligned} \sigma =\left\{ \left\langle a_{t},x\right\rangle \leq b_{t}, { \, }t\in W;\,\left\langle a_{t},x\right\rangle <b_{t}, t\in S\right\} , {} \end{aligned} $$

(1.1)

where $\left \langle \cdot ,\cdot \right \rangle$ denotes the standard inner product in $\mathbb {R}^{n}$, W and S are disjoint index sets, $a_{t}\in \mathbb {R}^{n}$ and $b_{t}\in \mathbb {R}$ for all t ∈ T := W ∪ S ≠ ∅ (a possibly infinite set). The solution set of σ, say

$$\displaystyle \begin{aligned} F=\left\{ x\in \mathbb{R}^{n}:\left\langle a_{t},x\right\rangle \leq b_{t}, { \, }t\in W;\,\left\langle a_{t},x\right\rangle <b_{t}, t\in S\right\} , \end{aligned}$$

is the intersection of halfspaces and, so, it is a convex set, i.e., any segment $\left [ x,y\right ]$ determined by x, y ∈ F is contained in F. Since $\left [ x,y\right ]$ is an arc joining x and y, any convex set is arc-connected and, so, it is connected, i.e., it cannot be represented as the union of two or more disjoint nonempty open subsets for the topology induced by the Euclidean norm in F.

The above system σ is said to be ordinary when S = ∅, finite when T is finite and semi-infinite otherwise. Moreover, it is said homogeneous when b _t = 0 for all t ∈ T.

The solution sets of ordinary systems are intersections of closed halfspaces and, so, they are closed and convex. The converse holds as a consequence of the basic separation theorem which asserts that, if $\emptyset \neq C\varsubsetneq \mathbb {R}^{n}$ is a closed convex set and y∉C, then, there exist a vector a ≠ 0_n and a scalar $b\in \mathbb {R}$ such that $\left \langle a,y\right \rangle >b$ and $\left \langle a,x\right \rangle \leq b$ , for all x ∈ C (see, e.g., [91, Ch. A: Th. 4.1.1]). Since we can write $\mathbb {R}^{n}=\left \{ x\in \mathbb {R}^{n}:\left \langle 0_{n},x\right \rangle \leq 0\right \}$ and $\emptyset =\left \{ x\in \mathbb {R} ^{n}:\left \langle 0_{n},x\right \rangle \leq -1\right \} ,$ any closed convex set is the solution set of some ordinary system.

The following concept is the counterpart of closed convex set for non-ordinary systems: a set $C\subset \mathbb {R}^{n}$ is evenly convex (e-convex, in brief) if it is the intersection of some family, possibly empty, of open halfspaces. Clearly, any e-convex set is convex, and the converse only holds for sets in $\mathbb {R}$. From the definition, any e-convex set is the solution set of a system as the one in (1.1). Conversely, since any weak inequality $\left \langle a,x\right \rangle \leq b,$ with a ≠ 0_n and $b\in \mathbb {R},$ has the same solutions as the system of strict inequalities $\left \{ \left \langle a,x\right \rangle <b+ \frac {1}{k},k\in \mathbb {N}\right \}$, the solution set of the linear system σ in (1.1) is an e-convex set. So, ordinary systems and closed convex sets are particular types of linear systems and e-convex sets, respectively, as Diagram 1.1 shows:

Diagram 1.1 Linear representations of convex sets

In this book we mainly use the standard notation of convex analysis and optimization. So, given a set $X\subset \mathbb {R}^{n},$ we denote by $\operatorname { int}X$, $\operatorname {rint}X,$ $\operatorname {cl}X$, $\operatorname {bd}X$, and $\operatorname {rbd}X$ the interior, the relative interior, the closure, the boundary, and the relative boundary of X, respectively. The set X is said to be relatively open if $\operatorname {rint}X=X$ (so, ∅ and $\mathbb {R}^{n}$ are relatively open). Moreover, $\operatorname {conv}X$ stands for the convex hull of X, whereas $\operatorname { cone}X:=\mathbb {R}_{+}\operatorname {conv}X$ means the convex conical hull of X ∪{0_n}, where 0_n denotes the null vector of $\mathbb {R}^{n}.$ Additionally, if X is a nonempty finite set, we say that $\operatorname {conv}X$ is a polytope and $\operatorname {cone}X$ is a finitely generated cone. When $\emptyset \neq X\subset \mathbb {R}^{n},$ we denote by $\operatorname {span}X$ and $\operatorname {aff}X$ the linear span and the affine span of X, respectively, and by

$$\displaystyle \begin{aligned} 0^{+}X:=\{d\in \mathbb{R}^{n}:x+td\in X,\forall t\geq 0,\forall x\in X\} \end{aligned}$$

the recession cone of X. The Minkowski sum of X, $Y\subset \mathbb {R}^{n}$ is the set $X+Y:=\left \{ x+y:x\in X,\,y\in Y\right \}$. Additionally, if C is a nonempty convex subset of $\mathbb {R}^{n}$, $\dim C$ denotes the dimension of C (defined as the dimension of $\operatorname {aff}C$) and, for $\overline {x}\in C$, the cone of feasible directions of C at $\overline {x}$ is

$$\displaystyle \begin{aligned} D(C,\overline{x}):=\left\{ v\in \mathbb{R}^{n}:\overline{x}+\alpha v\in C \text{ for some }\alpha >0\right\} =\mathbb{R}_{+}\left( C-\overline{x} \right) . \end{aligned}$$

If $\overline {x}\in \operatorname {cl}C$, the tangent cone to C at $\overline {x}$ is $T_{C}\left ( \overline {x}\right ) :=\operatorname {cl}D(\operatorname {cl }C,\overline {x})$. A convex subset D ⊂ C is said to be a face of C if, for all pairs v ₁ ≠ v ₂ of C such that $D\cap \left ] v_{1},v_{2}\right [ \neq \emptyset$, one has $\left [ v_{1},v_{2}\right ] \subset D$. The extreme points and edges of C are the zero- and one-dimensional faces of C, respectively. We say that a hyperplane H is a supporting hyperplane of C at $\overline {x}\in C$ if $\overline {x}\in H$ and C lies in one of the closed halfspaces determined by H. In such a case, we say that H supports C at $\overline {x}$. The supporting hyperplane theorem establishes that, if C is a nonempty convex set and $\overline {x}\in C\cap \operatorname {bd}C$, then there is a supporting hyperplane of C at $\overline {x}$. The intersections of C with its supporting hyperplanes are called exposed faces of C. Given X ⊂ C, the intersection of exposed faces of C containing X is an exposed face of C. So, there exists a minimal exposed face of C containing X.

Given a convex cone K, the lineality space of K is the greatest linear subspace contained in K. We denote it by $\operatorname {lin}K.$ Obviously, $\operatorname {lin}K=K\cap \left ( -K\right ) .$

The next result provides eleven characterizations of e-convex sets. One of them involves the following concept: the halfline $\left \{ x+\lambda y:\lambda \geq 0\right \}$ is a tangent ray for the convex set C if $x\in \operatorname {rbd}C,$ $y\in \operatorname {cl }D(\operatorname {cl}C,x)$, and $\left \{ x+\lambda y:\lambda \geq 0\right \} \cap \operatorname {rint}C=\emptyset$.

Theorem 1.1 (Characterization of e-Convex Sets)

Let $C\subset \mathbb {R}^{n}$ be such that $\emptyset \neq C\neq \mathbb {R}^{n}$ . Then, the following statements are equivalent to each other:

• (i) C is e-convex;

• (ii) C is the result of eliminating from a closed convex set (precisely, $\operatorname {cl}C$ ) the union of a certain family of its exposed faces;

• (iii) C is a convex set and for each $x\in \mathbb {R}^{n}\backslash C$ there exists a hyperplane H such that x ∈ H and H ∩ C = ∅;

• (iv) C is connected and through every point not in C there is some hyperplane H such that H ∩ C = ∅;

• (v) C is a convex set and x ∈ C for all $x\in \operatorname {rbd}C$ such that $\left \{ x-\lambda y:\lambda \geq 0\right \} \cap C\neq \emptyset$ for some tangent ray $\left \{ x+\lambda y:\lambda \geq 0\right \}$;

• (vi) C is a convex set and $\left ( x+\operatorname {lin} T_{C}\left ( x\right ) \right ) \cap C=\emptyset$, for any $x\in \left ( \operatorname {cl}C\right ) \backslash C$;

• (vii) C is the intersection of a nonempty collection of nonempty open convex sets;

• (viii) C is a convex set and is the intersection of a collection of complements of hyperplanes;

• (ix) C is a convex set and for any convex set D contained in $\left ( \operatorname {cl}C\right ) \backslash C$ , there exists a hyperplane containing D and not intersecting C;

• (x) C is a convex set and for any convex set $D\subset \left ( \operatorname {cl}C\right ) \backslash C$ , the minimal exposed face (in $\operatorname {cl}C$ ) containing D does not intersect C;

• (xi) C is a convex set and for any $x\in \left ( \operatorname {cl}C\right ) \backslash C$ , the minimal exposed face (in $\operatorname {cl }C$ ) containing x does not intersect C; and

• (xii) C is a convex set and for any $x\in \left (\operatorname {cl}C\right ) \backslash C$ , there exists a supporting hyperplane of $\operatorname {cl}C$ at x not intersecting C.

The equivalence of the statements (i)–(vi) has been established in different published works (precise references can be found in Sect. 1.7), while the possibility of enlarging this list with statements (vii)–(xii) was conjectured by J.E. Martínez-Legaz in a private communication to one of the authors. So, we limit ourselves to prove the equivalence of each of the statements from $\left (\textit {vii}\right )$ to $\left (\textit {xii}\right )$ with those from $\left ( i\right )$ to $\left (\textit {vi}\right )$ by turning to the following consequence of $\left ( i\right ) \Longleftrightarrow \left (\textit {iii}\right )$: any relatively open convex set is e-convex. In fact, according to [148, Th. 11.2], given a nonempty relatively open convex set C and an affine manifold M such that C ∩ M = ∅, there exists a hyperplane H such that M ⊂ H and C is contained in one of the two open halfspaces determined by H. Applying this result to the zero dimensional affine manifolds, i.e., the singleton sets, it is easy to see that condition (iii) holds. So, any relatively open convex set (in particular, any open convex set) is e-convex.

Partial Proof of Theorem 1.1

$\left [ \left ( i\right ) \Rightarrow \left (\textit {vii}\right ) \Rightarrow \left ( i\right ) \right ]$ By the definition, any e-convex set C such that $\emptyset \neq C\neq \mathbb {R}^{n}$ is the intersection of some nonempty family of open halfspaces, so C satisfies $\left (\textit {vii}\right )$. Conversely, it is obvious that the intersection of e-convex sets is an e-convex set and, since each nonempty open convex set is e-convex, the intersection of a collection of nonempty open convex sets is e-convex.

$\left [ \left (\textit {iii}\right ) \Rightarrow \left (\textit {viii}\right ) \Rightarrow \left ( i\right ) \right ]$ If C satisfies condition $\left (\textit {iii}\right )$, then, given $t\in T:=\mathbb {R}^{n}\backslash C$, there exists a hyperplane H _t such that t ∈ H _t and H _t ∩ C = ∅. Therefore,

$$\displaystyle \begin{aligned} C\subset \underset{t\in T}{\cap }\left( \mathbb{R}^{n}\backslash H_{t}\right) {} \end{aligned} $$

(1.2)

and

$$\displaystyle \begin{aligned} \mathbb{R}^{n}\backslash C=T\subset \underset{t\in T}{\cup }H_{t}. {} \end{aligned} $$

(1.3)

By applying De Morgan’s laws to (1.3), we obtain the equality in ( 1.2), so C satisfies $\left (\textit {viii}\right )$.

Now, suppose that C satisfies $\left (\textit {viii}\right )$ and let $C=\underset { t\in T}{\cap }\left ( \mathbb {R}^{n}\backslash H_{t}\right )$, with H _t =  $\{ x\in \mathbb {R}^{n} : \langle a_{t},x \rangle = b_{t} \}$, $a_{t}\in \mathbb {R}^{n}\backslash \left \{ 0_{n}\right \}$ and $b_{t}\in \mathbb {R}$, for all t ∈ T. Since C is a convex set and, for each t ∈ T, $C\subset \mathbb {R}^{n}\backslash H_{t}$, we have that C is contained in one of the two open halfspaces determined by H _t. Then, we can suppose, without loss of generality, that

$$\displaystyle \begin{aligned} C\subset \underset{t\in T}{\cap }\left\{ x\in \mathbb{R}^{n}: \langle a_{t},x \rangle > b_{t}\right\} \text{.} {} \end{aligned} $$

(1.4)

On the other hand, if $\overline {x}\notin C$, there exists s ∈ T such that $\overline {x}\notin \mathbb {R}^{n}\backslash H_{s}$ or, equivalently, $\langle a_{s}, \overline {x} \rangle = b_{s}$. Therefore, $\overline {x}\notin \left \{ x\in \mathbb {R}^{n}: \langle a_{s}, x \rangle >b_{s}\right \}$ and we obtain the equality in (1.4). So, C is e-convex.

Finally, we shall prove $\left (\textit {ii}\right )$ ⇒ $\left (\textit {ix}\right )$ ⇒ $\left ( x\right )$ ⇒ $\left ( xi\right )$ ⇒ $\left (\textit {xii}\right )$ ⇒ $\left (\textit {iii}\right )$ .

$\left [ \left (\textit {ii}\right ) \Rightarrow \left (\textit {ix}\right ) \right ]$ Let $\left \{ X_{t},\;t\in T\right \}$ be a family of exposed faces of $\operatorname {cl}C$ such that

$$\displaystyle \begin{aligned} C=\left( \operatorname{cl}C\right) \backslash \left[ \underset{t\in T}{\cup }X_{t} \right] . \end{aligned}$$

Let $D\subset \left ( \operatorname {cl}C\right ) \backslash C=\underset {t\in T}{ \cup }X_{t}$ be a nonempty convex set (if D = ∅, any hyperplane not intersecting C contains D) and let $\overline {x}\in \operatorname {rint}D$. Then, there exists t ∈ T such that $\overline {x}\in X_{t}$, so that X _t is a face of $\operatorname {cl}C$ intersecting $\operatorname {rint}D$ and, by [148, Th. 18.1], D ⊂ X _t. Since X _t is an exposed face of $\operatorname {cl}C$, there exists a hyperplane H such that $X_{t}=H\cap \operatorname {cl}C$ and, therefore, D ⊂ H and

$$\displaystyle \begin{aligned} H\cap C=H\cap \left[ \left( \operatorname{cl}C\right) \cap C\right] =X_{t}\cap C=\emptyset . \end{aligned}$$

$\left [ \left (\textit {ix}\right ) \Rightarrow \left ( x\right ) \right ]$ Let $D\subset \left ( \operatorname {cl}C\right ) \backslash C$ be a convex set and let X be the minimal exposed face (in $\operatorname {cl}C$) such that D ⊂ X. By $\left (\textit {ix}\right )$, there exists a hyperplane H such that D ⊂ H and H ∩ C = ∅. If we take $Y:=H\cap \operatorname {cl}C\neq \emptyset$ (since D ⊂ Y ), then Y  is an exposed face containing D such that

$$\displaystyle \begin{aligned} Y\cap C=\left( H\cap \operatorname{cl}C\right) \cap C=H\cap C=\emptyset . {} \end{aligned} $$

(1.5)

Since X is the minimal exposed face containing D, we have X ⊂ Y  and, by (1.5), X ∩ C = ∅.

$\left [ \left ( x\right ) \Rightarrow \left ( xi\right ) \right ]$ It is trivial because $\left ( xi\right )$ is a particular case of $\left ( x\right )$ .

$\left [ \left ( xi\right ) \Rightarrow \left (\textit {xii}\right ) \right ]$ Let $x\in \left ( \operatorname {cl}C\right ) \backslash C$ and let X be the minimal exposed face (in $\operatorname {cl}C$) containing x. Since X is an exposed face of $\operatorname {cl}C$, there exists a hyperplane H such that $\operatorname {cl}C$ is contained in one of the closed halfspaces determined by H and $X=H\cap \operatorname {cl}C$, so that x ∈ H and H supports $\operatorname {cl} C$ at x. Moreover, since X ∩ C = ∅, we have

$$\displaystyle \begin{aligned} H\cap C=H\cap \left[ \left( \operatorname{cl}C\right) \cap C\right] =X\cap C=\emptyset . \end{aligned}$$

$\left [ \left (\textit {xii}\right ) \Rightarrow \left (\textit {iii}\right ) \right ]$ Let $x\in \mathbb {R}^{n}\backslash C$. We obtain a hyperplane H such that x ∈ H and H ∩ C = ∅ as a consequence of $\left (\textit {xii}\right )$, if $x\in \left ( \operatorname {cl}C\right ) \backslash C$, and as a consequence of $\operatorname { cl}C$ being an e-convex set, if $x\notin \operatorname {cl}C$. □

Example 1.1

Consider the closed convex set

$$\displaystyle \begin{aligned} C=\left\{ x\in \mathbb{R}^{2}:-tx_{1}+(t-1)x_{2}\leq t^{2}-t,\;t\in \left[ 0,1\right] \right\} . {} \end{aligned} $$

(1.6)

The set $C_{1}:=C\backslash \left ( \left [ 1,+\infty \right [ \times \left \{ 0\right \} \right )$ is e-convex, whereas $C_{2}:=C\backslash \left ( \left ] 1,+\infty \right [ \times \left \{ 0\right \} \right )$ is not, even though C ₂ is convex, and so connected (see Fig. 1.1). In fact, one has:

• 1. The elimination of the unique exposed face of $C=\operatorname {cl}C_{2}$ containing $\left ( 2,0\right ) ,$ $\left [ 1,+\infty \right [ \times \left \{ 0\right \} ,$ yields C ₁ instead of C ₂ (so $\left (\textit {ii}\right )$ fails).

  Fig. 1.1

  

  (a) The e-convex set C ₁; (b) The non e-convex set C ₂

• 2. C ₂ is convex, $\left ( 2,0\right ) \notin C_{2}$, but H ∩ C ₂ ≠ ∅ for any hyperplane H such that $\left ( 2,0\right ) \in H$, so $\left (\textit {iii}\right )$, $\left (\textit {iv}\right )$ and $\left (\textit {ix}\right )$ fail (taking $D=\left \{ \left ( 2,0\right ) \right \} \subset \left ( \operatorname {cl }C_{2}\right ) \backslash C_{2}$ in the latter case).

• 3. C ₂ is convex and $\left [ 2,+\infty \right [ \times \left \{ 0\right \}$ is a tangent ray emanating from $\left ( 2,0\right ) \in \operatorname { bd}C_{2}$ such that $\left ( \left [ -\infty ,2\right [ \times \left \{ 0\right \} \right ) \cap C_{2}=\left \{ \left ( 1,0\right ) \right \} ,$ but $\left ( 2,0\right ) \notin C_{2}$ (so $\left ( v\right )$ fails).

• 4. C ₂ is convex, $\overline {x}=\left ( 2,0\right ) \in \left ( \operatorname {cl} C_{2}\right ) \backslash C_{2}$, $T_{C_{2}}\left ( \overline {x}\right ) =\mathbb { R\times }\left [ 0,+\infty \right [$, $\overline {x}+\operatorname {lin}T_{C_{2}}\left ( \overline {x}\right ) =\mathbb {R\times }\left \{ 0\right \}$ and $\left ( \overline {x}+ \operatorname {lin}T_{C_{2}}\left ( \overline {x}\right ) \right ) \cap C_{2}=\left \{ \left ( 1,0\right ) \right \}$ (so, $\left (\textit {vi}\right )$ fails).

• 5. C ₂ is convex and $\left [ 1,+\infty \right [ \times \left \{ 0\right \}$ is the minimal exposed face in $\operatorname {cl}C_{2}$ containing $\left ( 2,0\right )$, but $\left ( \left [ 1,+\infty \right [ \times \left \{ 0\right \} \right ) \cap C_{2}=\left \{ \left ( 1,0\right ) \right \}$ (so, $\left ( x\right )$ and $\left ( xi\right )$ fail).

• 6. C ₂ is convex and the unique supporting hyperplane of $\operatorname {cl} C_{2}$ at $\left ( 2,0\right )$ is $H=\left \{ x\in \mathbb {R} ^{2}:x_{2}=0\right \}$, but $H\cap C_{2}=\left \{ \left ( 1,0\right ) \right \}$ (so, $\left (\textit {xii}\right )$ fails).

From the comment prior to the proof of Theorem 1.1, since $\operatorname {rint}C$ is relatively open, any convex set C ≠ ∅ can be fitted from inside by its relative interior $\operatorname {rint}C$ and from outside by its closure $\operatorname {cl}C$, both approximating sets being e-convex. Analogously, any strictly convex set C (i.e., a convex set C such that its boundary, $\operatorname {bd}C$, does not contain segments) is e-convex since the exposed faces of $\operatorname {cl}C$ are the singleton sets determined by its boundary points. On the other hand, any convex set C ≠ ∅ in the real line $\mathbb {R}$ is an interval and, by Theorem 1.1(ii), it is always an e-convex set.

The next result allows to compare the cone of feasible directions at x, $D\left ( C,x\right ) ,$ the set $\operatorname {extr}C$ of extreme points, and the recession cone 0⁺C of an e-convex set C with those of its closure $\operatorname {cl}C$. This comparison shows that e-convex sets enjoy many known properties of closed convex sets (see, e.g., [148, Ths. 8.3, 8.4 and Cor. 8.4.1]).

Proposition 1.1 (Properties of e-Convex Sets)

If $C\subset \mathbb {R}^{n}$ is a nonempty e-convex set, then the following statements hold:

• (i) $D\left ( C,x\right ) =D\left ( \operatorname {cl}C,x\right )$ for all x ∈ C.

• (ii) $\operatorname {extr}C=C\cap \operatorname {extr}\operatorname {cl}C.$

• (iii) $\left [ x,y\right [ \subset C$ for any x ∈ C and $y\in \operatorname {cl}C.$

• (iv) $0^{+}C=0^{+}\left ( \operatorname {cl}C\right )$. Consequently, C is bounded if and only if $0^{+}C=\left \{ 0_{n}\right \}$.

• (v) If y ≠ 0_n and there exists x ∈ C such that $\left \{ x+\lambda y:\lambda \geq 0\right \} \subset C$, then y ∈ 0⁺C.

• (vi) If M is an affine manifold such that C ∩ M is a nonempty bounded set, then M ^′∩ C is also bounded for each affine manifold M ^′ which is parallel to M.

The convex sets satisfying property $\left (\textit {iii}\right )$ are said to be wholefaced in the sense of Motzkin [131]. The well-known accessibility lemma asserts that, for any convex set C, $\left [ x,y\right [ \subset \operatorname {rint}C$ for any $x\in \operatorname {rint}C$ and $y\in \operatorname {cl}C$ (see, e.g., [148, Th. 6.1]). Since $\operatorname {cl}\operatorname {rint}C=\operatorname {cl}C,$ this lemma means that the relatively open convex sets are wholefaced and $\left (\textit {iii}\right )$ is nothing but the extension of this property from relatively open convex sets to e-convex sets.

The next example shows that all statements of Proposition 1.1 may hold, and also fail, simultaneously for convex sets which are not e-convex.

Example 1.2

Let C be as in Example 1.1. Neither $C_{3}:=C\backslash \left \{ \left ( 1,0\right ) \right \}$ nor $C_{4}=C\backslash \left ( \left ] 2,+\infty \right [ \times \left \{ 0\right \} \right )$ is e-convex; however, C ₃ satisfies statements from $\left ( i\right )$ to $\left (\textit {vi}\right )$ of Proposition 1.1; in particular, C ₃ is wholefaced even though it is not e-convex. In the contrary, C ₄ violates the six statements in Proposition 1.1. In fact, taking $x=\left ( 2,0\right ) ,$ $y=\left ( 3,0\right ) ,$ $M=\mathbb {R} \times \left \{ 0\right \}$ and $M^{\prime }=\mathbb {R}\times \left \{ 1\right \}$ in Fig. 1.2b, we can see that $\left ( i\right )$, $\left (\textit {iii}\right )$ and $\left (\textit {vi}\right )$ fail. Moreover, $x=\left ( 2,0\right ) \in \left ( \operatorname {extr}C_{4}\right ) \backslash \left ( \operatorname {extr}\operatorname {cl}C_{4}\right )$ (so, $\left (\textit {ii}\right )$ fails) and $\left \{ \left ( 0,1\right ) +\lambda \left ( 1,0\right ) :\lambda \geq 0\right \} \subset C_{4}$ with $\left ( 0,1\right ) \in C_{4}$ and $\left ( 1,0\right ) \in \left ( 0^{+}\left ( \operatorname {cl}C_{4}\right ) \right ) \backslash \left ( 0^{+}C_{4}\right )$ (so $\left (\textit {iv}\right )$ and $\left ( v\right )$ fail).

Fig. 1.2

(a) C ₃ is wholefaced but not e-convex; (b) C ₄ violates all the statements in Proposition 1.1

The class of e-convex sets is closed for the same operations as the class of closed convex sets, except for the sum. Sufficient conditions for the sum of two e-convex sets to be e-convex will be given in Corollary 1.1.

Proposition 1.2 (Operations with e-Convex Sets)

The following statements hold:

• (i) If $C\subset \mathbb {R}^{n}$ is an e-convex set, then αC (resp., C + v) is e-convex for all $\alpha \in \mathbb {R}$ (resp., $v\in \mathbb {R}^{n}$).

• (ii) If $C\subset \mathbb {R}^{n}$ is an e-convex set and $A:\mathbb {R}^{m}\rightarrow \mathbb {R}^{n}$ is a linear transformation such that A ⁻¹C ≠ ∅, then A ⁻¹C is e-convex and $0^{+}(A^{-1}C) = A^{-1}\left ( 0^{+}C\right ) .$

• (iii) If $C_{1}\subset \mathbb {R}^{n}$ and $C_{2}\subset \mathbb {R}^{m}$ are nonempty sets, then C ₁ × C ₂ is e-convex if and only if C ₁ and C ₂ are e-convex.

• (iv) If $C_{1},C_{2}\subset \mathbb {R}^{n}$ are nonempty e-convex sets such that $\left ( 0^{+}C_{1}\right ) \cap \left ( -0^{+}C_{2}\right ) =\left \{ 0_{n}\right \} ,$ then

  $$\displaystyle \begin{aligned} 0^{+}\left( C_{1}+C_{2}\right) =0^{+}C_{1}+0^{+}C_{2}. {} \end{aligned} $$

  (1.7)

• (v) If $\left \{ C_{i},i\in I\right \}$ is a family of e-convex sets in $\mathbb {R}^{n}$ such that $\underset {i\in I}{\cap }C_{i}\neq \emptyset$ , then $\underset { i\in I}{\cap }C_{i}$ is e-convex and

  $$\displaystyle \begin{aligned} 0^{+}\left( \underset{i\in I}{\cap }C_{i}\right) =\underset{i\in I}{\cap } 0^{+}C_{i}. \end{aligned}$$

• (vi) Let $C\subset \mathbb {R}^{n}$ be a nonempty convex set with $\dim C=n$, $x\in \mathbb {R}^{n}$, and $k\in \mathbb {Z}$ such that 1 ≤ k ≤ n. If C ∩ M is e-convex for each k-dimensional affine manifold M containing x, with k ≥ 3, or $x\in \operatorname {int}C$ and k ≥ 2, then C is e-convex.

In statement $\left (\textit {vi}\right )$, conditions over k can be weakened when we replace “e-convex” by “open” or “closed”. So, C is open if C ∩ M is relatively open and 1 ≤ k ≤ n, and C is closed if C ∩ M is closed and k ≥ 2 or $x\in \operatorname {int}C$ [101, Prop. 2.1]. However, with even convexity, statement $\left (\textit {vi}\right )$ fails when k = 2 and $x\notin \operatorname {int}C,$ as the following example shows.

Example 1.3

Consider in the plane of $\mathbb {R}^{3}$ given by x ₃ = 1, a closed rectangle R and a closed half-disk D that is disjoint with $\operatorname {rint}R$ and whose diameter coincides with one of the sides of R, say the segment $\left [ y,z\right ]$, and let $G=\left ( R\cup D\right ) \backslash \left \{ y,z\right \}$. The set $C= \operatorname {conv}\left ( G\cup \left [ 0,y\right [ \cup \left [ 0,z\right [ \right )$ is not e-convex (see Fig. 1.3). However, for each 2-dimensional affine manifold M containing $0_{3}\notin \operatorname { int}C$, C ∩ M consists of a single point, a segment, a closed triangle, or a triangle with one or two missing vertices, and each one of these sets is e-convex.

Fig. 1.3

The non e-convex set $C = \operatorname {conv} \left ( G\cup \left [ 0,y \right [ \cup \left [ 0,z \right [ \right )$

Concerning the sum of closed convex sets, it is well-known that the condition $\left ( 0^{+}C_{1}\right ) \cap \left ( -0^{+}C_{2}\right ) =\left \{ 0_{n}\right \}$ guarantees that C ₁ + C ₂ is closed convex too (see, e.g., [148, Cor. 9.1.2]). The next example shows that this is not true for e-convex sets (even though one of the two sets is bounded).

Example 1.4

Consider the e-convex set C in (1.6). The compact convex set $C_{5}:=\left \{ x\in C:x_{1}+x_{2}\leq 1\right \}$ and the set

$$\displaystyle \begin{aligned} C_{6}:=\left\{ x\in \mathbb{R}^{2}:x_{1}\geq 0;\;x_{2}\geq 0;\;x_{1}+x_{2}>0\right\} \end{aligned}$$

(see Fig. 1.4) are obviously e-convex and satisfy (1.7 ). Nevertheless, C ₅ + C ₆ is not e-convex (see Fig. 1.5).

Fig. 1.4

(a) The compact convex set C ₅; (b) The e-convex set C ₆

Fig. 1.5

C ₅ + C ₆ is not e-convex

Observe also that $C_{5}+C_{6}=A\left ( C_{5}\times C_{6}\right )$ if we define $A:\mathbb {R}^{2n}\rightarrow \mathbb {R}^{n}$ as $A\left ( x,z\right ) =x+z$. This shows that the image of an e-convex set through a linear transformation may fail to be e-convex (as it happens with the closed convex sets). In contrast, the linear transformation of a relatively open convex set is another relatively open convex set [148, Th. 6.6].

1.2 Evenly Convex Hull

Given $X\subset \mathbb {R}^{n}$, if $\operatorname {conv}X\varsubsetneq \mathbb {R} ^{n}$, the intersection of all open halfspaces containing X is the minimal e-convex set which contains X, i.e., it is the e-convex hull of X, denoted by $\operatorname {eco}X$. Alternatively, if $\operatorname {conv}X=\mathbb {R}^{n}$ (i.e., if it does not exist a halfspace containing X), then $\operatorname {eco}X=\mathbb {R}^{n}$ . Obviously, X is e-convex if and only if $\operatorname {eco}X=X$. This happens, for instance, if X is either a closed or a relatively open convex set. Consequently, if X is a compact (open) set, then $\operatorname {conv}X$ is a compact (open) convex set and $\operatorname {eco}X=\operatorname {conv}X$. This is the case, in particular, if $\left \vert X\right \vert <\infty$, where $\left \vert X\right \vert$ denotes the cardinality of X. From the properties of e-convex sets, for each $\overline {x}\in \mathbb {R}^{n}$ one has

$$\displaystyle \begin{aligned} \overline{x}\notin \operatorname{eco}X\ \Longleftrightarrow \ \exists \,z\in \mathbb{ R}^{n}:\left\langle z,x\right\rangle <\left\langle z,\overline{x} \right\rangle ,\ \forall x\in X. {} \end{aligned} $$

(1.8)

For any $X\subset \mathbb {R}^{n}$, since $\operatorname {cl}\operatorname {conv}X$ is e-convex and $\operatorname {eco}X$ is convex, we have

$$\displaystyle \begin{aligned} \operatorname{conv}X\subset \operatorname{eco}X\subset \operatorname{cl}\operatorname{conv}X. {} \end{aligned} $$

(1.9)

For $\emptyset \neq X\subset \mathbb {R}^{n}$, since [148, Th. 6.2], we also have that $\operatorname {aff}\operatorname {eco}X=\operatorname {aff}\operatorname {conv}X$ and $\dim \operatorname { eco}X=\dim \operatorname {conv}X$.

The next result establishes the existing relation between the two latter sets in (1.9).

Proposition 1.3 (Characterization of e-Convex Hulls)

For any $X\subset \mathbb {R} ^{n}$, $\operatorname {eco}X$ is the result of eliminating from $\operatorname {cl}\operatorname {conv}X$ the union of all its exposed faces which do not intersect X.

Example 1.5

Given the set

$$\displaystyle \begin{aligned} X:=\left\{ x\in \mathbb{R}^{2}:x_{2}=\dfrac{1}{1+x_{1}^{2}}\right\} , \end{aligned}$$

we have that $\operatorname {conv}X=\left ( \mathbb {R\times }\left ] 0,1\right [ \right ) \cup \left \{ \left ( 0,1\right ) \right \}$ (see Fig. 1.6), $\operatorname {eco}X=\mathbb {R\times }\left ] 0,1\right ]$ and $\operatorname {cl}\operatorname {conv} X=\mathbb {R\times }\left [ 0,1\right ]$. Therefore, the inclusions in (1.9) are strict in this case. Observe that $\operatorname {eco}X$ is obtained by eliminating from $\operatorname {cl}\operatorname {conv}X$ its unique exposed face which does not intersect X (the line $\mathbb {R}\times \{ 0\}$).

Fig. 1.6

The convex hull of X

The next result describes how e-convex hulls behave under different operators as closures, relative interiors and convex or conical hulls.

Proposition 1.4 (Relationships Between $\operatorname {eco}$ and Other Hulls)

Let $X\subset \mathbb {R}^{n}$ . Then, the following statements hold:

• (i) $\operatorname {cl}\operatorname {eco}X=\operatorname {cl}\operatorname {conv} X$.

• (ii) $\operatorname {rint}\operatorname {eco}X=\operatorname {rint}\operatorname { conv}X$.

• (iii) $\operatorname {eco}\operatorname {conv}X=\operatorname {eco}X=\operatorname {conv} \operatorname {eco}X.$

• (iv) $\operatorname {cone}\operatorname {eco}X\subset \operatorname {eco} \operatorname {cone}X=\operatorname {cl}\operatorname {cone}X$.

• (v) If X is a nonempty bounded set , then $\operatorname {cl}\operatorname {eco}X=\operatorname {eco}\operatorname {cl}X=\operatorname {conv}\operatorname {cl}X.$

Statements $\left ( i\right )$ and $\left (\textit {ii}\right )$ are easily obtained by taking closures and relative interiors, respectively, in (1.9). An immediate consequence of the equality in statement $\left (\textit {iv}\right )$ is that a translated convex cone containing its apex is e-convex if and only if it is closed [101, Prop. 3.3].

The inclusion in statement $\left (\textit {iv}\right )$ can be strict and the boundedness assumption in statement $\left ( v\right )$ cannot be eliminated, as we can see in the next example.

Example 1.6 (Example 1.5 Revisited)

We have that

$$\displaystyle \begin{aligned} \operatorname{cone}\operatorname{eco}X=\operatorname{cone}X=\left( \mathbb{R }\times\left] 0,+\infty \right[ \right) \cup \left\{ 0_{2}\right\} , \end{aligned}$$

whereas $\operatorname {eco}\operatorname {cone}X=\operatorname {cl}\operatorname {cone}X=\mathbb { R\times }\left [ 0,+\infty \right [$, so that the inclusion in statement $\left (\textit {iv}\right )$ is strict.

On the other hand, X is an unbounded set for which $\operatorname {conv}\operatorname {cl} X=\operatorname {conv}X$ and $\operatorname {eco}\operatorname {cl}X=\operatorname {eco}X$ (since X is closed). Moreover, by statement $\left ( i\right )$, $\operatorname {cl}\operatorname {eco}X= \operatorname {cl}\operatorname {conv}X$. Therefore, as we have already seen in Example 1.5,

$$\displaystyle \begin{aligned} \operatorname{conv}\operatorname{cl}X\varsubsetneq \operatorname{eco}\operatorname{cl}X\varsubsetneq \operatorname{cl}\operatorname{eco}X \end{aligned}$$

and so, the boundedness assumption in statement $\left ( v\right )$ cannot be removed.

Proposition 1.5 (Operations with e-Convex Hulls)

The following statements hold:

• (i) If $X,Y\subset \mathbb {R}^{n}$ and X ⊂ Y , then $\operatorname {eco}X\subset \operatorname {eco}Y$.

• (ii) If $X\subset \mathbb {R}^{n}$ and $Y\subset \mathbb {R}^{m}$ , then $\operatorname {eco}\left ( X\times Y\right ) =\left ( \operatorname {eco}X\right ) \times \left ( \operatorname {eco}Y\right ) .$

• (iii) If X is a nonempty set in $\mathbb {R}^{m}$ and $A:\mathbb {R}^{m}\rightarrow \mathbb {R}^{n}$ is a linear transformation, then $A\left ( \operatorname {eco}X\right ) \subset \operatorname {eco}\left ( AX\right )$.

• (iv) If $X,Y\subset \mathbb {R}^{n}$ , then $\operatorname {eco}X+ \operatorname {eco}Y\subset \operatorname {eco}\left ( X+Y\right ) .$

• (v) If X is a nonempty set in $\mathbb {R}^{n}$ and $A:\mathbb {R}^{n}\rightarrow \mathbb {R}^{n}$ is a bijective linear transformation, then $A\left ( \operatorname {eco} X\right ) =\operatorname {eco}\left ( AX\right )$.

• (vi) If X is a nonempty set in $\mathbb {R}^{n}$ and $A:\mathbb {R}^{m}\rightarrow \mathbb {R}^{n}$ is a linear transformation such that A ⁻¹X ≠ ∅ , then $\operatorname {eco}(A^{-1}X) \subset A^{-1}\left ( \operatorname {eco}X\right )$ .

• (vii) If $\left \{ X_{i},i\in I\right \}$ is a family of nonempty sets in $\mathbb {R}^{n}$ , then

  $$\displaystyle \begin{aligned} \operatorname{eco}\left( \underset{i\in I}{\cap }X_{i}\right) \subset \underset{i\in I}{\cap }\left( \operatorname{eco}X_{i}\right) . \end{aligned}$$

As pointed out in Sect. 1.7, where the reader can find precise references, the above statements are already known with the unique exception of statement $\left ( v\right ) .$

Partial Proof of Proposition 1.5

$\left ( v\right )$ By definition of e-convex hull, if one has $\overline {y}\in \operatorname {eco}\left ( AX\right )$, then $\overline {y}$ belongs to any open halfspace containing AX. As A is bijective, we can consider $\overline {x}:=A^{-1}\overline {y}$. We shall prove that $\overline {x}\in \operatorname {eco}X$.

If $\overline {x}\notin \operatorname {eco}X$, then by (1.8), there exists $z\in \mathbb {R}^{n}\backslash \left \{ 0_{n}\right \}$ such that $\left \langle z,x-\overline {x}\right \rangle <0$ for all x ∈ X and, therefore,

$$\displaystyle \begin{aligned} 0>\left\langle z,x-\overline{x}\right\rangle =\left\langle z,A^{-1}A\left( x-\overline{x}\right) \right\rangle =\left\langle ( A^{-1}) ^{\top}z,Ax-A\overline{x}\right\rangle ,\;\forall x\in X, \end{aligned}$$

where (A ⁻¹)^⊤ represents the adjoint operator of A ⁻¹ (i.e., the unique linear transformation such that $\left \langle x,A^{-1}y\right \rangle =\left \langle ( A^{-1}) ^{\top }x,y\right \rangle$ for all $x,y\in \mathbb {R}^{n}$). Taking d := (A ⁻¹)^⊤z and y := Ax, we have that $\left \langle d,y-\overline {y} \right \rangle <0$ for all y ∈ AX and so, $\overline {y}\notin \operatorname {eco} \left ( AX\right )$. We have shown that $\operatorname {eco}\left ( AX\right ) \subset A\left ( \operatorname {eco}X\right )$ and the conclusion follows from $\left (\textit {iii}\right )$. □

Taking the e-convex sets X = C ₅ and Y = C ₆ as in Example 1.4, we have that $\operatorname {eco}X=X$ and $\operatorname {eco}Y=Y$ whereas $\operatorname {eco} \left ( X+Y\right ) \neq X+Y$ (since X + Y  is not an e-convex set; see Fig. 1.5). So, the inclusions in statements $\left (\textit {iii}\right )$ and $\left (\textit {iv}\right )$ cannot be replaced by equalities.

In the same way, the inclusions in statements $\left (\textit {vi}\right )$ and $\left (\textit {vii}\right )$ can be strict as we can see in the following examples.

Example 1.7

Let $X:=\left ( \left ] 0,+\infty \right [ \times \left ] 0,+\infty \right [ \right ) \cup \left \{ 0_{2}\right \} \subset \mathbb {R}^{2}$ and let $A:\mathbb {R}^{2}\rightarrow \mathbb {R}^{2}$ be the linear transformation defined as $A\left ( x_{1},x_{2}\right ) =\left ( x_{1},0\right )$. Then, $A^{-1}X=\left \{ 0\right \} \times \mathbb {R}$ is an e-convex set whereas $A^{-1}\left ( \operatorname {eco}X\right ) =\mathbb {R}_{+}\times \mathbb {R}$. So, $\operatorname {eco}( A^{-1}X) =A^{-1}X\varsubsetneq A^{-1}\left ( \operatorname {eco}X\right )$.

Example 1.8

Let $X_{1}:=\mathbb {R}^{2}\times \left \{ 0\right \}$ and

$$\displaystyle \begin{aligned} X_{2}:=\operatorname{conv}\left[ \left\{ \begin{pmatrix} -\cos t \\ -\sin t \\ -1 \end{pmatrix} ,\,t\in \left] 0,2\pi \right[ \right\} +\mathbb{R}_{+}\left\{ \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \right\} \right] \cup \left\{ \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \right\} , \end{aligned}$$

(represented in Fig. 1.7).

Fig. 1.7

The set X ₂, where $\overline {x}= \left ( 1,0,1 \right )$

Since $\operatorname {eco}X_{1}=X_{1}$ and $\operatorname {eco}X_{2}=\operatorname {cl}X_{2}$, we have $(\operatorname {eco}X_{1}) \cap (\operatorname {eco}X_{2}) = \{ \left ( x_{1},x_{2},0\right ) \in \mathbb {R}^{3}:\left ( x_{1}-1\right ) ^{2}+x_{2}^{2}\leq 1 \}$ whereas

$$\displaystyle \begin{aligned} \operatorname{eco}\left( X_{1}\cap X_{2}\right) =X_{1}\cap X_{2}=\left\{ \left( x_{1},x_{2},0\right) \in \mathbb{R}^{3}:\left( x_{1}-1\right) ^{2}+x_{2}^{2}\leq 1\right\} \backslash \left\{ 0_{3}\right\} . \end{aligned}$$

1.3 Separation Theorems

The standard separation theorem for convex sets asserts that any two nonempty disjoint convex sets $X,Y\subset \mathbb {R}^{n}$ are weakly separated by a hyperplane, that is, there exists a hyperplane H such that one of the closed halfspaces determined by H contains X and the other one contains Y. This type of separation is so weak that it does not require X and Y  be disjoint. Stronger types of separation are valid for pairs X, Y  of convex sets satisfying suitable topological assumptions as openness, closedness and compactness of some of the two sets. The separation theorems for pairs of closed convex sets are useful tools in the study of ordinary systems and those optimization problems whose constraint system is ordinary. Analogously, separation theorems for pairs of e-convex sets are useful in the study of non-ordinary systems and optimization problems with strict inequality constraints. This is the type of separation theorems provided by Victor Klee in 1968 in his attempt to obtain maximal separation theorems, that is, sufficient conditions for certain type of separation of X from Y  under minimal hypotheses on these sets. Following Klee [99], given two disjoint sets $X,Y\subset \mathbb {R}^{n}$, we say that a hyperplane H separates X from Y :

• Nicely provided that H is disjoint from X or from Y  (without specifying which).

• Openly provided that H is disjoint from X.

• Strictly provided that H is disjoint from both X and Y.

• Strongly provided that H is at positive distance from both X and Y.

It is easy to prove that, given a closed convex set X and $x\in \mathbb {R} ^{n}\backslash X$, the hyperplane H orthogonal to the midpoint of the segment joining x with its projection on X separates strongly X from $\left \{ x\right \}.$ So, a nonempty set X is closed and convex if and only if it is strongly separated from any singleton set contained in $\mathbb {R} ^{n}\backslash X.$ Analogously, from the equivalence $\left ( i\right ) \Longleftrightarrow \left (\textit {iii}\right )$ in Theorem 1.1, a set X is e-convex if and only if it is openly separated from any singleton set contained in $\mathbb {R}^{n}\backslash X$ (cf. (1.8)).

It is easy to separate by suitable examples the concepts involved in Diagram 1.2 for any n ≥ 2. For instance, given a hyperplane H determining two open halfspaces, H ₊ and H ₋, and two different points, x, y ∈ H, defining the disjoint convex sets $X:=H_{+}\cup \left \{ x\right \}$ and $Y:=H_{-}\cup \left \{ y\right \} ,$ H separates weakly X from Y, but not nicely. If one aggregates the condition that X and Y  should be closed, the counterexample must be built in dimension at least 3, as the following one.

Diagram 1.2 Types of separation

Example 1.9

Consider the line $X:=\left \{ \left ( 0,x_{2},1\right ) :x_{2}\in \mathbb {R}\right \}$ and the closed convex cone

$$\displaystyle \begin{aligned} Y:=\left\{ y\in \mathbb{R}_{+}^{3}:y_{3}^{2}\leq y_{1}y_{2}\right\} . \end{aligned}$$

The hyperplane $H=\left \{ x\in \mathbb {R}^{3}:x_{1}=0\right \}$ contains X, while Y  lies in the halfspace $\left \{ x\in \mathbb {R}^{3}:x_{1}\geq 0\right \}$. In fact, H is the unique hyperplane separating weakly X from Y , but the separation is not nice, as Fig. 1.8 shows.

Fig. 1.8

X is (just) weakly separated from Y 

Maximal strong and strict separation theorems involving closedness or openness (among other) assumptions can be found in [99, Ths. 2 and 3]. In particular, [99, Th. 3(d)] states that the openness of two nonempty disjoint convex sets is a minimal condition for strict separation, so that weaker conditions as even convexity cannot imply this kind of separation. Before stating Klee’s (maximal) nice and open separation theorems we must introduce some concepts.

Given a set X such that $\emptyset \neq X\varsubsetneq \mathbb {R}^{n},$ if $Y\subset \mathbb {R}^{n}\backslash X$ is a j-dimensional affine manifold such that $d\left ( X,Y\right ) :=\inf \left \{ d\left ( x,y\right ) :x\in X,y\in Y\right \} =0,$ then Y  is called a j-asymptote of X.

A convex set X is called continuous provided that X is closed and its support function $\sigma _{X}:=\sup \left \{ \left \langle \cdot ,x\right \rangle :x\in X\right \}$ is continuous; this is equivalent to say that there is no halfline contained in $\operatorname {bd}X$ and no 1-asymptote. Given a supporting hyperplane of X, we say that X is continuous relative to H if H ∩ X is closed and convex but it has neither ray contained in its relative boundary nor 1-asymptote relative to H.

A convex set $\emptyset \neq X\varsubsetneq \mathbb {R}^{n}$ is called a strip provided that it is a union of translates of a given hyperplane. Equivalently, a strip is a hyperplane, an open or closed halfspace, or a set of the form S or H ₁ ∪ S, or H ₁ ∪ S ∪ H ₂, where H ₁ and H ₂ are parallel hyperplanes and S is the set of all points of $\mathbb {R}^{n}$ lying between H ₁ and H ₂. All strips are e-convex.

A set $X\subset \mathbb {R}^{n}$ is said to be quasi-polyhedral (or boundedly polyhedral) provided that its intersection with any polytope is a polytope and to be polyhedral at x ∈ X provided that X contains a polytope which is a neighborhood of x relative to X. A set is quasi-polyhedral if and only if it is closed, convex, and polyhedral at each of its points.

The next two results collect six open and six nice separation theorems, respectively.

Theorem 1.2 (Open Separation Theorems)

For $X,Y\subset \mathbb {R} ^{n}$ disjoint nonempty convex sets, each of the following conditions implies X is openly separated from Y .

• (i) X is open; Y  is arbitrary.

• (ii) X is e-convex and its intersection with any supporting hyperplane is compact; Y  is closed.

• (iii) X admits no asymptote in any supporting hyperplane intersecting X; Y  admits no asymptote.

• (iv) X is e-convex and its intersection with any supporting hyperplane is closed; Y  is e-convex, Y  admits no hyperplane asymptote, and Y  is continuous relative to every supporting hyperplane.

• (v) X’s projections are all e-convex; Y  admits no asymptote and is quasi-polyhedral.

• (vi) X is e-convex; Y  is singleton or a closed strip.

Concerning Theorem 1.2, each statement “(i) (respectively, (ii), …, (vi)) implies X is openly separated from Y ” is an open separation theorem, and all of them are maximal in Klee’s sense [99], except that (vi) does not when n = 2.

Theorem 1.3 (Nice Separation Theorems)

For $X,Y\subset \mathbb {R} ^{n}$ disjoint nonempty convex sets, each of the following conditions implies X is nicely separated from Y .

• (I) X is open or a strip; Y  is arbitrary.

• (II) X is e-convex and is continuous relative to any supporting hyperplane; Y  is e-convex and its intersection with any supporting hyperplane is closed.

• (III) X admits no asymptote in any supporting hyperplane; Y  admits no asymptote in any supporting hyperplane.

• (IV) X’s projections are all e-convex and X is polyhedral at each of its points; Y ’s projections are all e-convex and Y  is polyhedral at each of its points.

• (V) X’s projections are all e-convex; Y  admits no asymptote in any supporting hyperplane and Y  is polyhedral at each of its points.

• (VI) X is e-convex; Y  is singleton or open or a strip.

Regarding Theorem 1.3, each statement “(I) (respectively, (II), …, (V I)) implies X is nicely separated from Y ” is a nice separation theorem, and all of them are maximal in Klee’s sense [99], except that (V I) does not when n = 2.

Since Klee’s paper was published before the standard terminology and notation of convex analysis was established by Rockafellar in his celebrated book [148], the original proofs of the two previous theorems are hardly readable for today’s readers. Because of this, we give a sketch of them, which precludes cumbersome arguments based on induction. The keys are Proposition 1.1(iii) and the following lemma.

Lemma 1.1

Let $X,Y\subset \mathbb {R}^{n}$ be disjoint nonempty convex sets. Then, X is openly separated from Y  if and only if there is no point p ∈ X which lies in every hyperplane separating X from Y . Any such point p satisfies at least one of the following conditions:

• (a) $p\in \operatorname {cl}Y$.

• (b) There is a point $w\in \operatorname {cl}Y$ such that $\left [ p,w\right ] \subset \left ( \operatorname {cl}X\right ) \cap H$ for every hyperplane H separating X from Y .

• (c) There are sequences $\left \{ p^{k}\right \} \subset \mathbb {R}^{n}$, $\left \{ x^{k}\right \} \subset X$, and $\left \{ y^{k}\right \} \subset Y$ such that $y^{k}\in \left [ p^{k},x^{k}\right ]$ for all k, $\lim p^{k}=p$, $\lim x^{k}=x,$ and $\left [ p,x\right ]$ is contained in some ray which lies in $\left ( \operatorname {cl}X\right ) \cap H$ for every hyperplane H separating X from Y .

If X and Y  are e-convex, then condition $\left ( c\right )$ is satisfied for each point p ∈ X which lies in every hyperplane separating X from Y  and each separating hyperplane H such that X ∩ H and Y ∩ H are both closed and nonempty.

Sketch of the Proofs of Theorems 1.2 and 1.3.

By the standard separation theorem, there is a hyperplane H separating X from Y .

If X is open, then X ∩ H = ∅. If X is a strip, it can happen that H supports X and, therefore, H ⊂ X and Y ∩ H = ∅, or that H ∩ X = ∅. So, statements $\left ( i\right )$ and $\left ( I\right )$ imply that X is openly and nicely separated from Y , respectively.

The proofs for statements $\left (\textit {vi}\right )$ and $\left (\textit {VI}\right )$ are trivial.

The separation theorems corresponding to statements $\left (\textit {ii}\right )$, $\left (\textit {iv}\right )$ and $\left (\textit {II}\right )$ are proved by contradiction. Supposing that X is not openly separated from Y , by Lemma 1.1, there is a point p ∈ X which lies in every hyperplane H separating X from Y . Therefore, p ∈ X ∩ H and H is a supporting hyperplane of X, which, under statements $\left (\textit {ii}\right )$, $\left (\textit {iv}\right )$ or $\left (\textit {II}\right )$, implies that X is e-convex and X ∩ H is nonempty and closed.

Regarding the set Y , if Y ∩ H ≠ ∅, any of the three conditions implies that Y  is e-convex and Y ∩ H is nonempty and closed, and then, by the last assertion in Lemma 1.1, condition $\left ( c\right )$ is satisfied for p, X, Y  and H.

If Y ∩ H = ∅, under $\left (\textit {ii}\right )$, conditions $\left ( a\right )$ and $\left ( b\right )$ in Lemma 1.1 are excluded by the fact that Y  is closed, so $\left ( c\right )$ is satisfied; under $\left (\textit {iv}\right )$, the fact that Y  admits no hyperplane asymptote yields to a contradiction; and finally, under $\left (\textit {II}\right )$, Y ∩ H = ∅ implies that X is nicely separated from Y  and there is nothing to prove.

Condition $\left ( c\right )$ in Lemma 1.1 claims the existence of a ray

$$\displaystyle \begin{aligned} r:=\left\{ p+\lambda u:\lambda \geq 0\right\} \subset \left( \operatorname{cl} X\right) \cap H \end{aligned}$$

and, since p ∈ X and X is e-convex, by Proposition 1.1(iii), r ⊂ X ∩ H, which is a contradiction under statements $\left (\textit {ii}\right )$ and $\left (\textit {II}\right )$. Finally, under $\left (\textit {iv}\right )$, [63, Lems. 1.1 and 1.2] assert the existence of a parallel ray to r which is a boundary ray or an asymptote of Y ∩ H and we obtain a contradiction again.

The remaining statements are proved by induction on n. □

Corollary 1.1 (Even Convexity of the Sum of Convex Sets)

If X and Y  are two proper convex sets in $\mathbb {R}^{n}$ , not necessarily disjoint, and they satisfy any of the conditions of Theorems 1.2 and 1.3, then the set X + Y  is e-convex.

Proof

The conditions on Y  in Theorems 1.2 and 1.3 are symmetric in the sense that they hold for Y  if and only if they hold for − Y  and they are also preserved under translations. If we take z∉X + Y , then the sets X and − Y + z are disjoint (otherwise, there exist x ∈ X and y ∈ Y  such that x = −y + z and z = x + y ∈ X + Y ). Then, since X and − Y + z are disjoint, any of the conditions of Theorems 1.2 and 1.3 implies the existence of $a\in \mathbb {R}^{n}\backslash \left \{ 0_{n}\right \}$ such that $\left \langle a,x\right \rangle <\left \langle a,-y+z\right \rangle$ for all x ∈ X and y ∈ Y , whence, $\left \langle a,x+y\right \rangle <\left \langle a,z\right \rangle$ and we have that $H=\left \{ x\in \mathbb {R}^{n}:\left \langle a,x\right \rangle =\left \langle a,z\right \rangle \right \}$ is a hyperplane which contains z and misses X + Y  and, since X + Y  is convex, by Proposition 1.1(iii), X + Y  is e-convex. □

Observe that X and Y  are simultaneously e-convex under conditions $\left (\textit {ii}\right ) ,$ $\left (\textit {iv}\right ) ,$ $\left (\textit {vi}\right ) ,$ $\left (\textit {II}\right )$ and $\left (\textit {IV}\right ) ,$ so that Corollary 1.1 can be interpreted, in those cases, as providing sufficient conditions for the sum of two e-convex sets to be e-convex.

1.4 Linear Systems Containing Strict Inequalities

This section provides characterizations of the existence of solutions of linear systems (Sect. 1.4.1), of the linear inequalities defining half-spaces which include their solution sets (Sect. 1.4.2), and of those pairs of systems such that the solution set of one of them is contained in the solution set of the other one (Sect. 1.4.3). The common feature of all these characterizations is that they are checkable in the sense that they involve different hulls of sets which are expressed in terms of the data (that is, the coefficients of the inequalities).

We associate with the linear system

$$\displaystyle \begin{aligned} \sigma =\left\{ \left\langle a_{t},x\right\rangle \leq b_{t},{ \, }t\in W;\,\left\langle a_{t},x\right\rangle <b_{t},t\in S\right\} {} \end{aligned} $$

(1.10)

its relaxed system

$$\displaystyle \begin{aligned} \overline{\sigma }=\left\{ \left\langle a_{t},x\right\rangle \leq b_{t}, { \, }t\in T\right\} , \end{aligned}$$

obtained by replacing $\left \langle a_{t},x\right \rangle <b_{t}$ with $\left \langle a_{t},x\right \rangle \leq b_{t}$ for all t ∈ S. Obviously, the consistency of $\overline {\sigma }$ does not entail the consistency of σ (consider, e.g., the system $\sigma =\left \{ 0<x<0\right \}$ in $\mathbb {R}$). The next simple result, on the relationships between the respective solution sets, F and $\overline {F},$ is fundamental along this section.

Proposition 1.6 (Relationships Between F and $\overline {F}$)

Let F and $\overline {F}$ be the solution sets of σ and $\overline {\sigma },$ respectively. Then, the following statements hold:

• (i) If F ≠ ∅, then $\overline {F}=\operatorname {cl}F.$

• (ii) If F = ∅ and σ does not contain the trivial inequality $\left \langle 0_{n},x\right \rangle \leq 0,$ then either $\overline {F}=\emptyset$ or $\dim \overline {F}<n.$

1.4.1 Existence of Solutions

We recall that σ is consistent if F ≠ ∅ and inconsistent otherwise. We next show that the consistency of a linear system σ as in (1.10), with strict inequalities (i.e., S ≠ ∅), can be characterized in terms of the membership, or not, of two particular vectors to the closed convex hull and the e-convex hull of suitable sets involving the data.

It is well known that the consistency of $\overline {\sigma }$ can be characterized by means of the cones

$$\displaystyle \begin{aligned} N(\overline{\sigma}) :=\operatorname{cone}\left\{ \dbinom{a_{t}}{ b_{t}},t\in T\right\} \text{ and }K(\overline{\sigma}) := N(\overline{\sigma}) +\mathbb{R}_{+}\dbinom{0_{n}}{1}, \end{aligned}$$

which are called, in the linear semi-infinite programming literature, second order moment cone and characteristic cone of $\overline {\sigma },$ respectively. Indeed, $\overline {\sigma }$ is consistent if and only if

$$\displaystyle \begin{aligned} \dbinom{0_{n}}{-1} \notin \operatorname{cl}N(\overline{\sigma}), {} \end{aligned} $$

(1.11)

if and only if

$$\displaystyle \begin{aligned} \dbinom{0_{n}}{-1} \notin \operatorname{cl}K(\overline{\sigma}). {} \end{aligned} $$

(1.12)

Analogously, we define the moment set of σ as

$$\displaystyle \begin{aligned} C(\sigma) :=\left\{ \dbinom{a_{t}}{b_{t}},\,t\in S\right\} +\mathbb{R}_{+}\left\{ \dbinom{a_{t}}{ b_{t}},\,t\in W\right\} , \end{aligned}$$

and the characteristic set of σ as

$$\displaystyle \begin{aligned} D(\sigma) :=C(\sigma) \cup \left\{ \dbinom{0_{n}}{1}\right\} . \end{aligned}$$

Observe that $\operatorname {cone}C(\sigma ) \subset N(\overline {\sigma }) \subset \operatorname {cl}\operatorname {cone}C(\sigma )$ and, therefore, $\operatorname {cl}\operatorname {cone}C(\sigma ) = \operatorname {cl}N(\overline {\sigma })$. Similarly, $\operatorname {cone}D(\sigma ) \subset K(\overline {\sigma }) \subset \operatorname {cl}\operatorname {cone}D(\sigma )$ and $\operatorname {cl}\operatorname {cone} D(\sigma ) = \operatorname {cl}K(\overline {\sigma })$. So, conditions (1.15) and (1.17) below express the consistency of the relaxed system $\overline {\sigma }$, which is necessary but not sufficient for the consistency of σ. We now show that, assuming the consistency of $\overline {\sigma }$, the additional conditions, (1.16) and (1.18), at statements $\left (\textit {ii}\right )$ and $\left (\textit {iii}\right ) ,$ are equivalent, that is, the non-trivial implication, $\left [ \Rightarrow \right ] ,$ in

$$\displaystyle \begin{aligned} 0_{n+1}\notin \operatorname{eco}C(\sigma) \Longleftrightarrow 0_{n+1}\notin \operatorname{eco}D(\sigma) \end{aligned}$$

holds. Since $\dbinom {0_{n}}{-1}\notin \operatorname {cl}\operatorname {cone}C(\sigma )$, the separation theorem for closed convex cones allows to assert the existence of some vector $\dbinom {u}{u_{n+1}}\in \mathbb {R}^{n+1}\backslash \left \{ 0_{n+1}\right \}$ such that

$$\displaystyle \begin{aligned} -u_{n+1} = \left\langle \dbinom{u}{u_{n+1}},\dbinom{0_{n}}{-1}\right\rangle <0 \end{aligned}$$

and

$$\displaystyle \begin{aligned} \left\langle \dbinom{u}{u_{n+1}},\dbinom{x}{x_{n+1}}\right\rangle \geq 0,\qquad \forall \dbinom{x}{x_{n+1}}\in C(\sigma) . {} \end{aligned} $$

(1.13)

Assume that $0_{n+1}\notin \operatorname {eco}C(\sigma )$. Then, by Theorem 1.1(iii), there exist $\dbinom {v}{v_{n+1}}\in \mathbb {R }^{n+1}\backslash \left \{ 0_{n+1}\right \}$ and $v_{n+2}\in \mathbb {R}$ such that

$$\displaystyle \begin{aligned} v_{n+2}=\left\langle \dbinom{v}{v_{n+1}},\dbinom{0_{n}}{0}\right\rangle =0 \end{aligned}$$

and

$$\displaystyle \begin{aligned} \left\langle \dbinom{v}{v_{n+1}},\dbinom{x}{x_{n+1}}\right\rangle >v_{n+2}=0,\qquad \forall \dbinom{x}{x_{n+1}}\in C(\sigma) . {} \end{aligned} $$

(1.14)

Since u _n+1 > 0, v _n+1 + αu _n+1 > 0 for some α > 0 sufficiently large. For such a large scalar α one has, from (1.13) and (1.14), that

$$\displaystyle \begin{aligned} \left\langle \dbinom{v+\alpha u}{v_{n+1}+\alpha u_{n+1}} , \dbinom{x}{x_{n+1} } \right\rangle >0,\qquad \forall \dbinom{x}{x_{n+1}} \in C(\sigma) \end{aligned}$$

while

$$\displaystyle \begin{aligned} \left\langle \dbinom{v+\alpha u}{v_{n+1}+\alpha u_{n+1}} ,\dbinom{0_n}{1} \right\rangle =v_{n+1}+\alpha u_{n+1}>0 \end{aligned}$$

as well. So, the hyperplane

$$\displaystyle \begin{aligned} \left\langle \dbinom{v+\alpha u}{v_{n+1}+\alpha u_{n+1}} ,\dbinom{x}{x_{n+1}} \right\rangle =0 \end{aligned}$$

contains 0_n+1 while D(σ) lies in one of the two open halfspaces it determines, proving that

$$\displaystyle \begin{aligned} 0_{n+1}\notin \operatorname{eco}D(\sigma) . \end{aligned}$$

Theorem 1.4 (Existence Theorem)

Let $\sigma =\left \{ \left \langle a_{t},x\right \rangle \leq b_{t}, \, t\in W;\,\left \langle a_{t},x\right \rangle <b_{t},\right .$ $\left .t\in S\right \}$ with S ≠ ∅. Then, the following statements are equivalent:

• (i) σ is consistent.

• (ii)
  $$\displaystyle \begin{aligned} \dbinom{0_{n}}{-1}\notin \operatorname{cl}\operatorname{cone}\left[ \left\{ \dbinom{ a_{t}}{b_{t}},\,t\in S\right\} +\mathbb{R}_{+}\left\{ \dbinom{a_{t}}{b_{t}} ,\,t\in W\right\} \right] {} \end{aligned} $$

  (1.15)

  and

  $$\displaystyle \begin{aligned} 0_{n+1}\notin \operatorname{eco}\left[ \left\{ \dbinom{a_{t}}{b_{t}},\,t\in S\right\} +\mathbb{R}_{+}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W\right\} \right] . {} \end{aligned} $$

  (1.16)
• (iii)
  $$\displaystyle \begin{aligned} \dbinom{0_{n}}{-1}\notin \operatorname{cl}\operatorname{cone}\left[ \left\{ \dbinom{ a_{t}}{b_{t}},\,t\in S\right\} +\mathbb{R}_{+}\left\{ \dbinom{a_{t}}{b_{t}} ,\,t\in W\right\} \cup \left\{ \dbinom{0_{n}}{1}\right\} \right] {} \end{aligned} $$

  (1.17)

  and

  $$\displaystyle \begin{aligned} 0_{n+1}\notin \operatorname{eco}\left[ \left\{ \dbinom{a_{t}}{b_{t}},\,t\in S\right\} +\mathbb{R}_{+}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W\right\} \cup \left\{ \dbinom{0_{n}}{1}\right\} \right] . {} \end{aligned} $$

  (1.18)

The equivalence $\left [ \left (\textit {ii}\right ) \Longleftrightarrow \left (\textit {iii}\right ) \right ]$ holds because conditions (1.15) and (1.16) are equivalent to (1.17) and (1.18), respectively. Nevertheless, it is easy to prove that condition (1.18) implies (1.17), so that we obtain the following result as a consequence of $\left [ \left ( i\right ) \Longleftrightarrow \left (\textit {iii}\right ) \right ]$ in Theorem 1.4.

Corollary 1.2

Let σ be as in Theorem 1.4. Then, σ is consistent if and only if (1.18) holds.

Proof

We only prove that (1.18) implies (1.17). Suppose that (1.18) holds, that is, $0_{n+1}\notin \operatorname {eco} D(\sigma )$. Then, by (1.8), there exists $c\in \mathbb {R }^{n+1}$ such that $\left \langle c,x\right \rangle <0$, for all x ∈ D(σ). So, $\left \langle c,\dbinom {0_{n}}{1} \right \rangle <0$ or, equivalently, $\left \langle c,\dbinom {0_{n}}{-1} \right \rangle >0$. Denoting $X:=\left \{ x\in \mathbb {R}^{n+1}:\left \langle c,x\right \rangle \leq 0\right \} ,$ we have that X is an homogeneous closed halfspace such that $D\left ( \sigma \right ) \subset X$ and $\dbinom {0_{n}}{-1 }\notin X$. Then, by [148, Cor. 11.7.2], $\dbinom {0_{n}}{-1}\notin \operatorname {cl}\operatorname {cone}D(\sigma )$. □

The next corollaries are straightforward consequences of the equivalence $\left ( i\right ) \Longleftrightarrow \left (\textit {ii}\right )$ in Theorem 1.4. Similar results could be obtained from the equivalence $\left ( i\right ) \Longleftrightarrow \left (\textit {iii}\right ) .$

Corollary 1.3

Let σ be as in Theorem 1.4 . Then:

• (i) If σ is consistent, then $\dbinom {0_n}{-1} \notin \operatorname {cl}\operatorname {cone}C(\sigma )$ and

  $$\displaystyle \begin{aligned} 0_{n+1}\notin \operatorname{conv}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in S\right\} + \operatorname{cone}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W\right\} . {} \end{aligned} $$

  (1.19)

• (ii) If $\overline {\sigma }$ is consistent, (1.19) holds and the set in (1.19) is closed, then σ is consistent.

In [78, Lem. 2.1], it is proved that $\operatorname {conv}\left ( A+\mathbb {R }_{+}B\right ) =\operatorname {conv}A+\operatorname {cone}B$ for any nonempty sets A and B in $\mathbb {R}^{n}$, so that, taking into account the definition of C(σ), we have

$$\displaystyle \begin{aligned} \operatorname{conv}C(\sigma) =\operatorname{conv}\left\{ \dbinom{a_{t}}{b_{t} },\,t\in S\right\} +\operatorname{cone}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W\right\} . {} \end{aligned} $$

(1.20)

Since $\operatorname {eco}C(\sigma ) = \operatorname {eco}\operatorname {conv} C(\sigma )$, one has

$$\displaystyle \begin{aligned} \operatorname{eco}C(\sigma) = \operatorname{eco}\left[ \operatorname{conv}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in S\right\} +\operatorname{cone}\left\{ \dbinom{a_{t}}{ b_{t}},\,t\in W\right\} \right] , {} \end{aligned} $$

(1.21)

so (1.19) is an immediate consequence of (1.16). On the other hand, if the set in (1.19) is closed, then $\operatorname {eco}C(\sigma ) = \operatorname {conv}C(\sigma )$ and conditions (1.19) and (1.16) coincide.

The following example shows that the closedness assumption in statement $\left (\textit {ii}\right )$ of Corollary 1.3 is not superfluous. It also illustrates the use of Theorem 1.4 in the dubious case that the mentioned closedness fails.

Example 1.10

Let $\sigma :=\left \{ -tx_{1}-x_{2}<t^{2},\;t\in \left [ -1,1\right ] \backslash \left \{ 0\right \} ;\;x_{2}<0\right \}$. The set in Fig. 1.9a,

$$\displaystyle \begin{aligned} \left\{ \begin{pmatrix} -t \\ -1 \\ t^{2} \end{pmatrix} ,\,t\in \left[ -1,1\right] \backslash \left\{ 0\right\} \right\} \cup \left\{ \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} , \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \right\} , \end{aligned}$$

generates the (non-closed) characteristic cone

$$\displaystyle \begin{aligned} K(\overline{\sigma}) = \left( \mathbb{R}^{2}\times \left] 0,+\infty \right[ \right) \cup \mathbb{R}_{+} \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} . \end{aligned}$$

Fig. 1.9

(a) Generators of $K(\overline {\sigma })$; (b) The set Y 

Since (1.15) holds, $\overline {\sigma }$ is consistent. The set in ( 1.19) is

which does not contain 0₃. So, σ satisfies the necessary condition $\left ( i\right )$ in Corollary 1.3 but not the sufficient one, $\left (\textit {ii}\right )$. We finally observe that $\operatorname {eco}C(\sigma )$ is the closure of the set Y  in Fig. 1.9b as all its exposed faces contain points of Y. Hence,

$$\displaystyle \begin{aligned} 0_{3}\in \operatorname{eco}C(\sigma) = \operatorname{cl}Y = \operatorname{conv} \left( \left\{ \begin{pmatrix} -t \\ -1 \\ t^{2} \end{pmatrix} ,\,t\in \left[ -1,1\right] \right\} \cup \left\{ \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \right\} \right) , \end{aligned} $$

and σ turns out to be inconsistent by Theorem 1.4.

Corollary 1.4 (Motzkin-Like Existence Theorem)

Let

$$\displaystyle \begin{aligned} \sigma =\left\{ \left\langle a_{t},x\right\rangle <0,\,t\in S;\,\left\langle a_{t},x\right\rangle \leq 0,\,t\in W;\,\left\langle a_{t},x\right\rangle =0,\,t\in E\right\} {} \end{aligned} $$

(1.22)

be an homogeneous system such that the index sets are pairwise disjoint and S ≠ ∅. Then, σ is consistent if and only if

(1.23)

In the particular case that the set

$$\displaystyle \begin{aligned} \operatorname{conv}\left\{ a_{t},\,t\in S\right\} +\operatorname{cone}\left\{ a_{t},\,t\in W\right\} +\operatorname{span}\left\{ a_{t},\,t\in E\right\} \end{aligned} $$

is closed, σ is consistent if and only if

$$\displaystyle \begin{aligned} 0_{n}\notin \operatorname{conv}\left\{ a_{t},\,t\in S\right\} +\operatorname{cone}\left\{ a_{t},\,t\in W\right\} +\operatorname{span}\left\{ a_{t},\,t\in E\right\} . \end{aligned}$$

It is customary in mathematical programming to express the existence theorems in the equivalent form of alternative theorems asserting that exactly one of two statements holds, being one of them relative to the consistency of some system, and the other relative to the membership of certain vector in a suitable set. For instance, the reformulation of Corollary 1.4 as an alternative theorem asserts that either σ in (1.22) is consistent or

$$\displaystyle \begin{aligned} 0_{n}\in \operatorname{eco}\left[ \left\{ a_{t},\,t\in S\right\} +\mathbb{R} _{+}\left\{ a_{t},\,t\in W\right\} +\mathbb{R}\left\{ a_{t},\,t\in E\right\} \right] , \end{aligned}$$

but not both.

Corollary 1.5 (Gordan-Like Existence Theorem)

An homogeneous system $\sigma =\left \{ \left \langle a_{t},x\right \rangle <0,\,t\in S\right \}$ is consistent if and only if

$$\displaystyle \begin{aligned} 0_{n}\notin \operatorname{eco}\left\{ a_{t},\,t\in S\right\} . {} \end{aligned} $$

(1.24)

In the particular case that $\operatorname {conv}\left \{ a_{t},\,t\in S\right \}$ is closed, σ is consistent if and only if $0_{n}\notin \operatorname {conv}\left \{ a_{t},\,t\in S\right \}$.

Obviously, Corollary 1.5 can be expressed as an alternative theorem by saying that either $\sigma =\left \{ \left \langle a_{t},x\right \rangle <0,\,t\in S\right \}$ is consistent or $0_{n}\in \operatorname { eco}\left \{ a_{t},\,t\in S\right \} ,$ but not both.

The next alternative theorem is another immediate consequence of Theorem 1.4. There, $\mathbb {R}^{\left ( T\right ) }$ denotes the space of generalized finite sequences, that is, the linear space of those functions $\lambda :T\rightarrow \mathbb {R}$ whose support, $\operatorname {supp}\lambda :=\left \{ t\in T:\lambda _{t}\neq 0\right \} ,$ is finite. We denote by $\mathbb {R}_{+}^{\left ( T\right ) }$ the positive cone in $\mathbb {R}^{\left ( T\right ) }$. This notation allows us to characterize the existence of solutions in terms of the inexistence of certain multipliers.

Corollary 1.6 (Rockafellar-Like Alternative Theorem)

Let σ be as in Theorem 1.4 . Assume that $\left \{ \left \langle a_{t},x\right \rangle \leq b_{t},\,t\in W\right \}$ is consistent and that

$$\displaystyle \begin{aligned} \operatorname{cone}\left\{ \binom{a_{t}}{b_{t}},\,t\in T\right\} \ \mathit{and}\ \operatorname{conv}\left\{ \binom{a_{t}}{b_{t}},\,t\in S\right\} +\operatorname{cone}\left\{ \binom{a_{t}}{b_{t}},\,t\in W\right\} \end{aligned}$$

are closed sets. Then one and only one of the following alternatives holds:

• (i) σ is consistent.

• (ii) There exists $\lambda \in \mathbb {R} _{+}^{\left ( T\right ) }$ such that at least one of the numbers λ _t , t ∈ S, is nonzero, and

  $$\displaystyle \begin{aligned} \underset{t\in T}{\sum }\lambda _{t}a_{t}=0_{n}{\ \ }{and \ } \underset{t\in T}{\sum }\lambda _{t}b_{t}\leq 0. \end{aligned}$$

If $\left \{ \dbinom {a_{t}}{b_{t}},\,t\in S\right \}$ is compact and $\operatorname { cone}\left \{ \dbinom {a_{t}}{b_{t}},\,t\in W\right \}$ is closed, the closedness assumptions in Corollary 1.6 hold. In particular, if S and W are finite, then Proposition 1.6 becomes [148, Th. 22.2] (see Corollary 2.4).

The following alternative theorem is an immediate consequence of Corollary 1.6 for systems of strict linear inequalities.

Corollary 1.7 (Carver-Like Alternative Theorem)

Let $\sigma =\left \{ \left \langle a_{t},x\right \rangle <b_{t},\,t\in S\right \}$ be such that $\operatorname {conv}\left \{ \dbinom {a_{t}}{b_{t}},\,t\in S\right \}$ is closed. Then one and only one of the following alternatives holds:

• (i) σ is consistent.

• (ii) There exists $\lambda \in \mathbb {R} _{+}^{\left ( T\right ) }$ such that at least one of the numbers λ _t,t ∈ S, is nonzero, and

  $$\displaystyle \begin{aligned} \underset{t\in S}{\sum }\lambda _{t}a_{t}=0_{n}{\ \ }and \ \underset{t\in S}{\sum }\lambda _{t}b_{t}\leq 0. \end{aligned}$$

We finish this section showing the natural way to decide whether σ is consistent or not, and to compute a solution of σ in the first case. To do this we associate with σ the ordinary linear semi-infinite programming (LSIP in short) problem

$$\displaystyle \begin{aligned} \begin{array}{lcl} \left( P_{\sigma }\right) \quad & \operatorname*{\mathrm{Min}} \limits_{(x,x_{n+1}) \in \mathbb{R}^{n+1}} & x_{n+1} \\ & \text{s.t.} & \left\langle a_{t},x\right\rangle -x_{n+1}\leq b_{t}, t\in S, \\ & & \left\langle a_{t},x\right\rangle \leq b_{t}, t\in W, \end{array} \end{aligned}$$

whose optimal value is denoted by v(P _σ).

Proposition 1.7 (Checking the Consistency of σ via LSIP)

The following statements hold:

• (i) If v(P _σ) < 0 , then σ is consistent.

• (ii) If v(P _σ) > 0 , then σ is inconsistent.

• (iii) If v(P _σ) = 0 and $\left ( P_{\sigma }\right )$ is not solvable, then σ is inconsistent.

If v(P _σ) = 0 and $\left ( P_{\sigma }\right )$ is solvable, there exists an optimal solution of $\left ( P_{\sigma }\right )$ which can be written as $\dbinom {\overline {x}}{0}$. Then $\overline {x}$ is solution of $\overline { \sigma }$. Nevertheless, σ is not necessarily consistent as the next example shows.

Example 1.11

Consider the inconsistent system in Example 1.10. We claim that v(P _σ) = 0 with $\left ( P_{\sigma }\right )$ solvable. In fact, taking limits as t → 0 in − tx ₁ − x ₂ − x ₃ ≤ t ², t ≠ 0, gives − x ₂ − x ₃ ≤ 0. The remaining constraint is x ₂ − x ₃ ≤ 0, so that x ₃ ≥ 0 for all feasible solution of $\left ( P_{\sigma }\right )$. Since 0₃ is a feasible solution, $v\left ( P_{\sigma }\right ) =0$ and 0₃ is an optimal solution of $\left ( P_{\sigma }\right )$.

Observe that, given ε < 0, if $\dbinom {\overline {x}}{\overline {x} _{n+1}}$ is a solution of

$$\displaystyle \begin{aligned} \sigma _{\varepsilon }:=\left\{ \left\langle a_{t},x\right\rangle +b_{t}x_{n+1}\leq \varepsilon ,\;t\in S;\;x_{n+1}\leq \varepsilon ;\;\left\langle a_{t},x\right\rangle +b_{t}x_{n+1}\leq 0,\;t\in W\right\} , \end{aligned}$$

then $\left ( -\overline {x}_{n+1}\right ) ^{-1}\dbinom {\overline {x}}{ \varepsilon }$ is a feasible solution of $\left ( P_{\sigma }\right )$, so that (as observed in [42]) the consistency of σ _ε entails the consistency of σ, according to Proposition 1.7 . The converse statement holds if $\left \vert S\right \vert <\infty$ (since, given $\overline {x}\in F$, then $\varepsilon \delta ^{-1}\dbinom {\overline {x} }{-1}$ is solution of σ _ε for $\delta :=\max \left \{ -1;\;\left \langle a_{t},\overline {x}\right \rangle -b_{t},\;t\in S\right \}$ ), but it may fail for infinite systems. In fact, for the system in $\mathbb { R}$ $\sigma =\left \{ -tx<t^{2},\;t\neq 0\right \}$, $F=\left \{ 0\right \}$ whereas σ _ε is inconsistent for all ε < 0.

1.4.2 Consequent Inequalities

An inequality $\left \langle a,x\right \rangle \leq b$ (respectively, $\left \langle a,x\right \rangle <b$) is consequence of

$$\displaystyle \begin{aligned} \sigma =\left\{ \left\langle a_{t},x\right\rangle <b_{t}, t\in S;\,\left\langle a_{t},x\right\rangle \leq b_{t},{ \, }t\in W\right\} \end{aligned}$$

if $\left \langle a,\overline {x}\right \rangle \leq b$ (respectively, $\left \langle a,\overline {x}\right \rangle <b$) holds for every $\overline {x} \in \mathbb {R}^{n}$ solution of σ. If σ is inconsistent, then any linear inequality is consequence of σ. So we assume throughout this section that σ is consistent.

One way of generating consequent weak inequalities of the ordinary system $\overline {\sigma }=\left \{ \left \langle a_{t},x\right \rangle \leq b_{t},t\in T\right \}$ consists in picking some $\lambda \in \mathbb {R}_{+}^{\left ( T\right ) },$ multiplying the inequality $\left \langle a_{t},x\right \rangle \leq b_{t}$ by λ _t for each $t\in \operatorname {supp}\lambda$ and summing up these inequalities. The resulting inequality,

$$\displaystyle \begin{aligned} \left\langle \underset{t\in T}{\sum }\lambda _{t}a_{t},x\right\rangle \leq \underset{t\in T}{\sum }\lambda _{t}b_{t}, {} \end{aligned} $$

(1.25)

is of course a consequence of $\overline {\sigma },$ as well as those obtained by strengthening the constant term in (1.25), i.e., the inequalities of the form

$$\displaystyle \begin{aligned} \left\langle \underset{t\in T}{\sum }\lambda _{t}a_{t},x\right\rangle \leq \underset{t\in T}{\sum }\lambda _{t}b_{t}+\mu ,\text{ with }\mu \geq 0. \end{aligned}$$

In other words, if

$$\displaystyle \begin{aligned} \dbinom{a}{b}\in \operatorname{cone}\left\{ \dbinom{a_{t}}{b_{t}} ,t\in T;\dbinom{ 0_{n}}{1} \right\} =K(\overline{\sigma }) , \end{aligned}$$

then $\left \langle a,x\right \rangle \leq b$ is a consequence of $\overline { \sigma }.$ These are all the consequences of $\overline {\sigma }$ when T is finite, by the non-homogeneous Farkas lemma proved by Minkowski in 1911, but we can use limits to get more consequences whenever T is infinite. Indeed, if $\left \{ \dbinom {a^{k}}{b^{k}}\right \}$ is a sequence in $\mathbb {R}^{n+1}$ converging to $\dbinom {a}{b}$ such that

$$\displaystyle \begin{aligned} \dbinom{a^{k}}{b^{k}}\in K(\overline{\sigma}) ,k=1,2,\ldots \end{aligned}$$

then $\left \langle a,x\right \rangle \leq b$ is consequence of $\overline { \sigma }.$ Even more, the weak inequalities which are consequence of $\overline {\sigma }$ are characterized by the generalized non-homogeneous Farkas lemma for ordinary systems [72, Th. 3.1] as follows:

$$\displaystyle \begin{aligned} \left\langle a,x\right\rangle \leq b,\forall x\in \overline{F} \Longleftrightarrow \binom{a}{b}\in \operatorname{cl}K(\overline{\sigma}) . {} \end{aligned} $$

(1.26)

Regarding σ, where we now assume that S ≠ ∅, one can obtain a strict consequent inequality $\left \langle a,x\right \rangle <b$ by picking some $\lambda \in \mathbb {R}_{+}^{\left ( T\right ) }$ such that λ _t > 0 for at least one index t ∈ S, in which case

$$\displaystyle \begin{aligned} \left\langle \underset{t\in T}{\sum }\lambda _{t}a_{t},x\right\rangle < \underset{t\in T}{\sum }\lambda _{t}b_{t} {} \end{aligned} $$

(1.27)

is a consequence of σ. A given $\lambda \in \mathbb {R}_{+}^{\left ( T\right ) }$ is said to be legal if λ _t > 0 for at least one index t ∈ S, while its corresponding strict inequality (1.27) is called a legal linear combination of σ. Obviously,

$$\displaystyle \begin{aligned} \left\langle \underset{t\in T}{\sum }\lambda _{t}a_{t},x\right\rangle < \underset{t\in T}{\sum }\lambda _{t}b_{t}+\mu , \text{ with }\mu \geq 0, \end{aligned}$$

is also consequence of σ, but the limiting process mentioned above provides consequent inequalities of the form $\left \langle a,x\right \rangle \leq b,$ with

$$\displaystyle \begin{aligned} \dbinom{a}{b}\in \operatorname{cl}K(\overline{\sigma}) = \operatorname{cl}\operatorname{cone}D(\sigma) , \end{aligned}$$

whose corresponding strict inequality $\left \langle a,x\right \rangle <b$ is not necessarily a consequence of σ. The next result replaces this limiting process by a stronger dual condition involving its characteristic and moment sets and legal linear combinations.

Theorem 1.5 (Characterization of Consequent Inequalities)

For any consistent system $\sigma =\left \{ \left \langle a_{t},x\right \rangle \leq b_{t}, \, t\in W;\,\left \langle a_{t},x\right \rangle <b_{t},\mathit{} t\in S\right \}$ the following statements hold:

• (i) $\left \langle a,x\right \rangle \leq b$ is consequence of σ if and only if

  $$\displaystyle \begin{aligned} \binom{a}{b}\in \operatorname{cl}\operatorname{cone}\left[ \left\{ \dbinom{a_{t}}{b_{t}} ,\,t\in S\right\} +\mathbb{R}_{+}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W\right\} \cup \left\{ \dbinom{0_{n}}{1} \right\} \right] . \end{aligned}$$

• (ii) $\left \langle a,x\right \rangle <b$ is consequence of σ if and only if either

  $$\displaystyle \begin{aligned} \dbinom{0_{n}}{-1}\in \operatorname{cl}\operatorname{cone}\left( \left\{ \dbinom{a_{t}}{ b_{t}},\,t\in S\right\} +\mathbb{R}_{+}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W\right\} -\mathbb{R}_{+}\dbinom{a}{b}\right) {} \end{aligned} $$

  (1.28)

  or

  $$\displaystyle \begin{aligned} 0_{n+1}\in \operatorname{eco}\left( \left\{ \dbinom{a_{t}}{b_{t}},\,t\in S\right\} + \mathbb{R}_{+}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W\right\} -\mathbb{R}_{+} \dbinom{a}{b}\right) . {} \end{aligned} $$

  (1.29)

• (iii) If $\left \langle a,x\right \rangle <b$ is a legal linear combination of the system $\left \{ \left \langle a_{t},x\right \rangle \leq b_{t}, t\in W\cup S; \left \langle 0_{n},x\right \rangle \right .$ $\left . <1\right \}$, then (1.28) holds and $\left \langle a,x\right \rangle <b$ is consequence of σ. The converse holds whenever the cone

  $$\displaystyle \begin{aligned} \operatorname{cone}\left( \left\{ \dbinom{a_{t}}{b_{t}},\,t\in S\right\} +\mathbb{ R}_{+}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W\right\} -\mathbb{R}_{+}\dbinom{a }{b}\right) \end{aligned}$$

  is closed.

• (iv) If $\left \langle a,x\right \rangle <b$ is a legal linear combination of σ, then (1.29) holds and the inequality $\left \langle a,x\right \rangle <b$ is consequence of σ. The converse holds whenever the convex set

  $$\displaystyle \begin{aligned} \operatorname{conv}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in S\right\} +\mathbb{R} _{+}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W\right\} -\mathbb{R}_{+}\dbinom{a}{ b} {} \end{aligned} $$

  (1.30)

  is e-convex.

Statement $\left ( i\right )$ above means that $\left \langle a,x\right \rangle \leq b$ is consequence of σ if and only if it is consequence of $\overline {\sigma }$. Regarding (ii) and $\left (\textit {iii}\right )$, taking into account that

$$\displaystyle \begin{aligned} \operatorname{cone}\left( C(\sigma) -\mathbb{R}_{+}\dbinom{a}{b} \right) \subset N(\overline{\sigma}) -\mathbb{R}_{+}\dbinom{a}{b} \subset \operatorname{cl}\operatorname{cone}\left( C(\sigma) -\mathbb{R}_{+}\dbinom{a}{b}\right) , \end{aligned}$$

condition (1.28) is equivalent to

$$\displaystyle \begin{aligned} \dbinom{0_{n}}{-1}\in \operatorname{cl}\left( N(\overline{\sigma}) - \mathbb{R}_{+}\dbinom{a}{b}\right) \end{aligned}$$

and, whenever $\operatorname {cone}\left ( C(\sigma ) -\mathbb {R}_{+} \dbinom {a}{b}\right )$ is closed, we have

$$\displaystyle \begin{aligned} \operatorname{cone}\left( C(\sigma) -\mathbb{R}_{+}\dbinom{a}{b} \right) = N(\overline{\sigma}) - \mathbb{R}_{+}\dbinom{a}{b}. \end{aligned}$$

In that case, condition (1.28) obviously yields $\left \langle a,x\right \rangle <b$ is a legal linear combination of $\overline {\sigma } \cup \left \{ \left \langle 0_{n},x\right \rangle <1\right \}$.

Regarding $\left (\textit {iv}\right )$, by (1.20), we have

$$\displaystyle \begin{aligned} \begin{array}{rcl} \operatorname{conv}\left( C(\sigma) -\mathbb{R}_{+}\dbinom{a}{b} \right) &\displaystyle =&\displaystyle \operatorname{conv}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in S\right\} +\operatorname{ cone}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W;-\dbinom{a}{b}\right\} \\ &\displaystyle =&\displaystyle \operatorname{conv}C(\sigma) -\mathbb{R}_{+}\dbinom{a}{b}, \end{array} \end{aligned} $$

so that

$$\displaystyle \begin{aligned} \operatorname{eco}\left( C(\sigma) -\mathbb{R}_{+}\dbinom{a}{b} \right) = \operatorname{eco}\left( \operatorname{conv}C(\sigma) -\mathbb{R} _{+}\dbinom{a}{b}\right)\end{aligned} $$

and, whenever $\operatorname {conv}C(\sigma ) -\mathbb {R}_{+}\dbinom {a }{b}$ is e-convex, we have

$$\displaystyle \begin{aligned} \operatorname{eco}\left( C(\sigma) -\mathbb{R}_{+}\dbinom{a}{b} \right) = \operatorname{conv}C(\sigma) -\mathbb{R}_{+}\dbinom{a}{b}. \end{aligned}$$

The closedness assumption at $\left (\textit {iii}\right )$ and even convexity at $\left (\textit {iv}\right )$ are not superfluous for the validity of the converse statements, as the next example shows.

Example 1.12

The inequality − x ₂ < 0, in $\mathbb {R}^{2}$, is a consequence of

$$\displaystyle \begin{aligned} \sigma :=\left\{ 2tx_{1}-x_{2}<t^{2},\,t\in U;\,x_{1}-x_{2}<0\right\} , \end{aligned}$$

where $U=\left ] -1,0\right [$, as far as the solution set F of σ is the interior of the convex hull of the graph of the function $f:\mathbb {R}\rightarrow \mathbb {R}$ defined by

$$\displaystyle \begin{aligned} f\left( x_{1}\right) =\left\{ \begin{array}{ll} -2x_{1}-1, & \text{if }x_{1}<-1, \\ x_{1}^{2}, & \text{if }-1\leq x_{1}\leq 0, \\ x_{1}, & \text{if }x_{1}>0, \end{array} \right. \end{aligned}$$

(see Fig. 1.10). Nevertheless, − x ₂ < 0 fails to be a legal linear combination of $\overline {\sigma }\cup \left \{ \left \langle 0_{n},x\right \rangle <1\right \}$ or σ, since the following two systems are inconsistent:

$$\displaystyle \begin{aligned} \left\{ \begin{array}{c} \begin{pmatrix} 0 \\ -1 \\ 0 \end{pmatrix} =\underset{t\in U}{\sum }\lambda _{t} \begin{pmatrix} 2t \\ -1 \\ t^{2} \end{pmatrix} +\gamma \begin{pmatrix} 1 \\ -1 \\ 0 \end{pmatrix} +\mu \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \\ \lambda \in \mathbb{R}_{+}^{\left( U\right) },\,\gamma \geq 0,\,\mu >0 \end{array} \right\} \end{aligned}$$

Fig. 1.10

(a) The closure of F; (b) The solution set F

and

$$\displaystyle \begin{aligned} \left\{ \begin{array}{c} \begin{pmatrix} 0 \\ -1 \\ 0 \end{pmatrix} =\underset{t\in U}{\sum }\lambda _{t} \begin{pmatrix} 2t \\ -1 \\ t^{2} \end{pmatrix} +\gamma \begin{pmatrix} 1 \\ -1 \\ 0 \end{pmatrix} \\ \underset{t\in U}{\sum }\lambda _{t}+\gamma >0 \\ \lambda \in \mathbb{R}_{+}^{\left( U\right) },\,\gamma \geq 0 \end{array} \right\} . \end{aligned}$$

Actually, (1.29) holds, but $\operatorname {conv}C(\sigma ) - \mathbb {R}_{+}\dbinom {a}{b}$ is not e-convex (see Fig. 1.11).

Fig. 1.11

The set $\operatorname {conv}C(\sigma ) - \mathbb {R}_{+}\dbinom {a}{b}$

Regarding the fulfilment of the additional assumption for the converse statement in $\left (\textit {iv}\right )$, i.e., the even convexity of $\operatorname {conv}C(\sigma ) -\mathbb {R}_{+}\dbinom {a}{b}$, this set is open whenever $\operatorname {conv}C(\sigma )$ is open, and it is closed whenever $\left \{ \dbinom {a_{t}}{b_{t}} , t\in S\right \}$ is compact and W = ∅ (and so e-convex in both cases). Moreover, according to Corollary 1.1, $\operatorname {conv}C(\sigma ) -\mathbb {R}_{+}\dbinom {a}{b }$ is e-convex if the pair of sets $X:=\operatorname {conv}C(\sigma )$ and $Y:=\mathbb {R}_{+}\dbinom {a}{b}$ satisfies any of the conditions of Theorems 1.2 and 1.3, for instance, at least one of the conditions $\left (\textit {ii}\right )$, $\left (\textit {iii}\right )$, $\left ( v\right )$, and $\left ( I\right )$, which here collapse to:

• $\operatorname {conv}C(\sigma )$ is e-convex and its intersection with any supporting hyperplane is compact.

• $\operatorname {conv}C(\sigma )$ admits no asymptote in any supporting hyperplane.

• The projections of $\operatorname {conv}C(\sigma )$ are all e-convex.

• $\operatorname {conv}C(\sigma )$ is a strip.

1.4.3 Set Containment of Evenly Convex Sets

One of the basic tools in machine learning are the so-called linear classifiers, which are affine functions allowing to incorporate prior knowledge obtained from sets (the so-called learning sets), which are usually formed by individuals which have been previously classified (e.g., as either healthy or ill in medical tests). Mangasarian considered infinite learning sets, starting with the simple ones, the polyhedral sets [117, 118]. The main question was how to model the condition that a given polyhedral knowledge set F satisfies $F\subset \left \{ x\in \mathbb {R}^{n}:\left \langle a,x\right \rangle -b\leq 0\right \} ,$ where $a\in \mathbb {R}^{n}\backslash \left \{ 0_{n}\right \}$ and $b\in \mathbb {R}$ are the decision variables determining the best linear classifier $\left \langle a,\cdot \right \rangle -b$ for certain criterion.

Since, by the separation theorem, any closed convex set F is the intersection of all closed halfspaces containing F, we associate with F the so-called weak dual cone of F,

$$\displaystyle \begin{aligned} K_{F}^{\leq }:=\left\{ \begin{pmatrix} a \\ b \end{pmatrix} \in {\mathbb{R}}^{n+1}:\left\langle a,x\right\rangle \leq b,\forall x\in F\right\} . {} \end{aligned} $$

(1.31)

Then,

$$\displaystyle \begin{aligned} F\subset \left\{ x\in \mathbb{R}^{n}:\left\langle a,x\right\rangle \leq b\right\} \Longleftrightarrow \begin{pmatrix} a \\ b \end{pmatrix} \in K_{F}^{\leq }. {} \end{aligned} $$

(1.32)

If F is expressed as the solution set of a finite system $\left \{ \left \langle a_{t},x\right \rangle \leq b_{t}, { \, }t\in W\right \} ,$ the classical non-homogeneous Farkas lemma asserts that

$$\displaystyle \begin{aligned} K_{F}^{\leq }:=\operatorname{cone}\left\{ \dbinom{a_{t}}{b_{t}},\;t\in W;\;\dbinom{ 0_{n}}{1}\right\} , \end{aligned}$$

providing the aimed characterization,

$$\displaystyle \begin{aligned} F\subset \left\{ x\in \mathbb{R}^{n}:\left\langle a,x\right\rangle \leq b\right\} \Longleftrightarrow \begin{pmatrix} a \\ b \end{pmatrix} \in \operatorname{cone}\left\{ \dbinom{a_{t}}{b_{t}},\;t\in W;\;\dbinom{0_{n}}{1} \right\} , \end{aligned}$$

for the containment of F in a halfspace in terms of the data.

More generally, the containment problem, which consists of deciding, for a given couple of subsets of $\mathbb {R}^{n},$ the inbody F and the circumbody G, whether F ⊂ G or not, was first posed in 2000 by Mangasarian [117]. The sets F and G are usually given as solution sets of inequality systems, and the aim is the characterization of the inclusion F ⊂ G in terms of the data (usually, the constraints describing these sets). Mangasarian [117] solved the containment problem for polyhedral convex sets (the situation illustrated by Fig. 1.12) via linear programming, by exploiting the following consequence of (1.32): given two polyhedra F and G,

$$\displaystyle \begin{aligned} F\subset G\Longleftrightarrow K_{G}^{\leq }\subset K_{F}^{\leq }, {} \end{aligned} $$

(1.33)

where $K_{F}^{\leq }$ and $K_{G}^{\leq }$ are the weak dual cones of F and G defined as in (1.31).

Fig. 1.12

Inclusion of a polyhedron F in another one G

Consequently,

$$\displaystyle \begin{aligned} F=G\Longleftrightarrow K_{F}^{\leq }=K_{G}^{\leq }. \end{aligned}$$

If F is the solution set of $\left \{ \left \langle a_{t},x\right \rangle \leq b_{t},t\in W\right \} ,$ from the definition of $K_{F}^{\leq }$ and the non-homogeneous Farkas lemma for linear semi-infinite systems [72, Cor. 3.1.2], one gets

$$\displaystyle \begin{aligned} K_{F}^{\leq }=\operatorname{cl}\operatorname{cone}\left\{ \dbinom{a_{t}}{b_{t}},t\in W; \dbinom{0_{n}}{1}\right\} . \end{aligned}$$

As shown in [68, Prop. 4.1], if F and G are the sets of solutions of two given systems of weak inequalities, the preservation of the inclusion F ⊂ G under sufficiently small perturbations of the respective linear representations is related with the condition that $F\subset \operatorname {int}G$. Here, both sets F and $\operatorname {int}G$ are e-convex as the inbody F is a closed convex set while the circumbody $\operatorname {int}G$ is an open convex set. In order to extend (1.33) to e-convex sets we must associate with F the cone which results of replacing “≤” with “<  ” in (1.31).

One can define the weak dual cone $K_{F}^{\leq }$ of an arbitrary set F by (1.31). Then, given a couple F and G of proper subsets of ${\mathbb {R}}^{n},$ one has $\operatorname {cl}\operatorname {conv}F\subset \operatorname {cl}\operatorname {conv}G$ if and only if $K_{G}^{\leq }\subset K_{F}^{\leq }$ and $\operatorname {cl}\operatorname {conv}F=\operatorname {cl}\operatorname {conv}G$ if and only if $K_{G}^{\leq }=K_{F}^{\leq }.$

The strict dual cone of a set F such that $\emptyset \neq F\subset \mathbb {R}^{n}$ is

$$\displaystyle \begin{aligned} K_{F}^{<}:=\left\{ \begin{pmatrix} a \\ b \end{pmatrix} \in {\mathbb{R}}^{n+1}:\left\langle a,x\right\rangle <b,\forall x\in F\right\} . \end{aligned}$$

Observe that $K_{F}^{<}$ and $K_{F}^{\leq }$ can be seen as solution sets of homogeneous linear systems of strict and weak inequalities in ${\mathbb {R}} ^{n+1}$ indexed by F, respectively. So, they are an e-convex cone not containing 0_n+1 and a closed convex cone, respectively. From their definitions, we have that $\operatorname {cl}K_{F}^{<}\subset K_{F}^{\leq }.$ Moreover, the reverse inclusion holds as any $\begin {pmatrix} a \\ b \end {pmatrix} \in K_{F}^{\leq }$ is the limit of the sequence $\left \{ \begin {pmatrix} a \\ b+\frac {1}{k} \end {pmatrix} \right \}$ contained in $K_{F}^{<}.$ So,

$$\displaystyle \begin{aligned} \dbinom{0_{n}}{1}\in \operatorname{cl}K_{F}^{<}=K_{F}^{\leq }. \end{aligned}$$

Proposition 1.8 (Characterization of the Strict Dual Cone)

Let F be the solution set of $\sigma =\left \{ \left \langle a_{t},x\right \rangle <b_{t}, \mathit{}t\in S;\,\left \langle a_{t},x\right \rangle \leq b_{t},\mathit{{ \, }}t\in W\right \} .$ Then the following statements hold:

• (i) $K_{F}^{<}$ is formed by all vectors $\dbinom {a}{b}$ such that $\left \langle a,x\right \rangle <b$ is a legal linear combination of σ provided the set

  $$\displaystyle \begin{aligned} C(\sigma) =\left\{ \dbinom{a_{t}}{b_{t}},\,t\in S\right\} + \mathbb{R}_{+}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W\right\} \end{aligned}$$

  satisfies at least one of the following conditions:

  • (a) $\operatorname {conv}C(\sigma )$ is open.

  • (b) $\left \{ \dbinom {a_{t}}{b_{t}} ,t\in S\right \}$ is compact and W = ∅.

  • (c) $\operatorname {conv}C(\sigma )$ is e-convex and its intersection with any supporting hyperplane is compact.

  • (d) $\operatorname {conv}C(\sigma )$ admits no asymptote in any supporting hyperplane.

  • (e) The projections of $\operatorname {conv}C(\sigma )$ are all e-convex.

  • (f) $\operatorname {conv}C(\sigma )$ is a strip.

• (ii) If W = ∅, then

  $$\displaystyle \begin{aligned} K_{F}^{<}=\operatorname{eco}\mathbb{R}_{++}\left\{ \dbinom{a_{t}}{b_{t}},\;t\in S;\;\dbinom{0_{n}}{1}\right\} . {} \end{aligned} $$

  (1.34)

Partial Proof

Since statement (ii) is known, we only prove here statement (i). Any of the conditions from $\left ( i.a\right )$ to $\left ( i.f\right )$ guarantees that $\operatorname {conv}C(\sigma ) -\mathbb {R}_{+}\dbinom {a}{b}$ is e-convex for all $\dbinom {a}{b}\in \mathbb {R}^{n+1}$ by Corollary 1.1. The conclusion follows from Theorem 1.5(iv). □

The strict dual cone of F, $K_{F}^{<},$ gathers useful geometric information on F; for instance, the recession cone of F is

$$\displaystyle \begin{aligned} 0^{+}F=\left\{ y\in \mathbb{R}^{n}:\left\langle a,y\right\rangle \leq 0,\ \forall \begin{pmatrix} a \\ b \end{pmatrix} \in K_{F}^{<}\right\} , \end{aligned}$$

and F is bounded if and only if $\begin {pmatrix} 0_{n} \\ 1 \end {pmatrix} \in \operatorname {int}K_{F}^{<}.$

Proposition 1.9 (Dual Characterization of the Containment of e-Convex Sets)

Given two proper subsets of $\mathbb {R}^{n},$ F and G, one has

$$\displaystyle \begin{aligned} \operatorname{eco}F\subset \operatorname{eco}G\Longleftrightarrow K_{G}^{<}\subset K_{F}^{<}. \end{aligned}$$

Moreover, if both sets are e-convex, then

$$\displaystyle \begin{aligned} F\subset G\Longleftrightarrow K_{G}^{<}\subset K_{F}^{<}. \end{aligned}$$

Consequently,

$$\displaystyle \begin{aligned} F=G\Longleftrightarrow K_{F}^{<}=K_{G}^{<}. \end{aligned}$$

Proof

The first statement comes from the definitions of strict dual cone and e-convex hull, and the second from the obvious equations $\operatorname { eco}F=F$ and $\operatorname {eco}G=G$ when these two sets are e-convex. □

The next result suggests the existence of an intriguing topological duality between e-convex sets and their strict dual cones.

Proposition 1.10 (On the Topology of e-Convex Sets and Their Dual Cones)

Let F ≠ ∅ be an e-convex set. Then the following statements hold:

• (i) F is open if and only if $K_{F}^{<}\cup \left \{ 0_{n+1}\right \}$ is closed.

• (ii) If $K_{F}^{<}$ is relatively open, then F is closed.

• (iii) If F is compact, then $K_{F}^{<}$ is open.

Example 1.13

Consider the closed convex set $F=\mathbb {R}_{+}^{2}.$ From the definition of strict dual cone one gets $K_{F}^{<}=\left ( -\mathbb {R}_{+}\right ) ^{2}\times \mathbb {R}_{++}$ (it can also be obtained from (1.34) by observing that $F=\left \{ x\in \mathbb {R}^{2}:-x_{i}<\alpha ,\alpha \in \mathbb {R}_{++},i=1,2\right \}$). Since $K_{F}^{<}$ is neither closed nor open, the converse statement of Proposition 1.10(ii) does not hold, and one cannot replace “compact” with “closed” in Proposition 1.10(iii). Finally, let us observe that $\begin {pmatrix} 0_{2} \\ 1 \end {pmatrix} \in \operatorname {bd}K_{F}^{<}$ as F is unbounded.

1.5 Evenly Linear Semi-Infinite Programming

Strict inequality constraints naturally arise in many real situations, even though they are usually replaced in optimization models by their corresponding weak inequalities. For instance, in production planning problems, where the decision variable x _j represents the production level of the j-th good (or commodity), j ∈ J, sign constraints of the type x _j > 0 are usually replaced by their relaxation x _j ≥ 0, which provides relaxed optimization problems of the accurate ones. In the same context, when the j-th good contains a percentage p _j of some obnoxious component and the percentage of this component at the whole production is required to be less or equal than some given percentage threshold P, this condition can be formulated as $\frac { \sum \nolimits _{j\in J}p_{j}x_{j}}{\sum \nolimits _{j\in J}x_{j}}\leq P$ provided that x _j > 0 for some j ∈ J, that is, the following pair of linear constraints hold:

In this section we obtain information on the accurate model from its relaxation.

To this aim, we associate with the given linear semi-infinite programming problem with strict inequalities (in short, e-LSIP problem)

$$\displaystyle \begin{aligned} \begin{array}{lcl} \left( P\right) \quad & \operatorname*{\mathrm{Min}}\limits_{x\in \mathbb{R}^{n}} & \left\langle c,x\right\rangle \\ & \text{s.t.} & \left\langle a_{t},x\right\rangle \leq b_{t}, t\in W, \\ & & \left\langle a_{t},x\right\rangle <b_{t}, t\in S\neq \emptyset , \end{array} {} \end{aligned} $$

(1.35)

where c ≠ 0_n and W and S are arbitrary disjoint index sets, its relaxed problem

$$\displaystyle \begin{aligned} \begin{array}{lcl} (\overline{P}) \quad & \operatorname*{\mathrm{Min}}\limits_{x\in \mathbb{R}^{n}} & \left\langle c,x\right\rangle \\ & \text{s.t.} & \left\langle a_{t},x\right\rangle \leq b_{t}, t\in T=W\cup S. \end{array} {} \end{aligned} $$

(1.36)

We denote by σ and $\overline {\sigma }$ the linear systems given by the constraints of $\left ( P\right )$ and $\left ( \overline {P}\right )$, respectively, and by F and $\overline {F}$ their corresponding solution sets, which are the feasible sets of $\left ( P\right )$ and $\left ( \overline {P}\right )$, respectively. Observe that, since $\overline {\sigma }$ corresponds to the relaxed system of σ, by Proposition 1.6 , we have that $\overline {F}=\operatorname {cl}F$ when $\left ( P\right )$ is consistent (that is, F ≠ ∅).

In order to obtain geometrical information on the feasible set F and to decide whether a given x ^∗∈ F is an optimal solution of $\left ( P\right )$ by means of a condition involving the data (that is, the coefficients of the constraints), we must introduce assumptions on σ which are generically called constraint qualifications.

1.5.1 Constraint Qualifications

We first introduce five global constraint qualifications. We say that σ is continuous if T is a compact topological space and the coefficient function $t\longmapsto \left ( a_{t},b_{t}\right )$ is continuous on T. In particular, σ is said to be analytical (respectively, polynomial) if T is a compact interval in $\mathbb {R}$ and the n + 1 projections of the vector-valued function $t\longmapsto \left ( a_{t},b_{t}\right )$ are analytical (respectively, polynomial). We say that σ satisfies the Slater constraint qualification (SCQ in short) if there exists some $\widehat {x}\in \mathbb {R}^{n}$ such that $\left \langle a_{t},\widehat {x} \right \rangle <b_{t}$ for all t ∈ T. Finally, we say that σ satisfies the Farkas-Minkowski constraint qualification (FMCQ in brief) if it is consistent and each weak inequality $\left \langle a,x\right \rangle \leq b$ which is consequence of σ is also consequence of a finite subsystem of σ.

Assume that FMCQ holds and $\left \langle a,x\right \rangle \leq b$ is consequence of σ. Then there exist two finite sets W ₁ ⊂ W and S ₁ ⊂ S such that $\left \langle a,x\right \rangle \leq b$ is consequence of $\sigma _{1}=\left \{ \left \langle a_{t},x\right \rangle \leq b_{t}, { \, }t\in W_{1};\,\left \langle a_{t},x\right \rangle <b_{t}, t\in S_{1}\right \}$ and, according to Theorem 1.5 ,

$$\displaystyle \begin{aligned} \dbinom{a}{b}\in \operatorname{cl}\operatorname{cone}\left( \left\{ \dbinom{a_{t}}{b_{t}} ,\,t\in S_{1}\right\} +\mathbb{R}_{+}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W_{1}\right\} \cup \dbinom{0_{n}}{1} \right) . \end{aligned}$$

Since the convex cone generated by the union of finitely many halflines together with one element of the vertical axis is not necessarily closed, we cannot assert that

$$\displaystyle \begin{aligned} \binom{a}{b}\in \operatorname{cone}\left( \left\{ \dbinom{a_{t}}{b_{t}},\,t\in S_{1}\right\} +\mathbb{R}_{+}\left\{ \dbinom{a_{t}}{b_{t}},\,t\in W_{1}\right\} \cup \dbinom{0_{n}}{1} \right) . \end{aligned}$$

Thus, the closedness of $\operatorname {cone}D(\sigma )$ is a sufficient, but not necessary, condition for the fulfillment of FMCQ. Actually, σ satisfies FMCQ if and only if the characteristic cone of the relaxed system $\overline {\sigma }$,

$$\displaystyle \begin{aligned} K(\overline{\sigma}) = \operatorname{cone}\left\{ \dbinom{a_{t}}{b_{t} } ,t\in T;\dbinom{0_{n}}{1} \right\} , \end{aligned}$$

is closed [72, Th. 5.3(i)]. The definition of the next two constraint qualifications involves $\overline {\sigma }.$

We say that σ satisfies the locally Farkas-Minkowski constraint qualification (LFMCQ in short) at $\overline {x}\in \overline {F}$ (not necessarily in F) if it is consistent and each inequality $\left \langle a,x\right \rangle \leq b$ which is consequence of $\overline {\sigma }$ and binding at $\overline {x}$ (i.e., $\left \langle a,\overline {x}\right \rangle =b)$ is also consequence of a finite subsystem of σ. Obviously, FMCQ implies LFMCQ at any $\overline {x}\in \overline {F}$, but the converse statement does not hold (see Example 1.14).

Finally, we say that σ satisfies the locally polyhedral constraint qualification (LOPCQ) at $\overline {x}\in \overline {F}$ if $A(\overline {x})^{\circ } = D(\overline {F};\overline {x})$, where

$$\displaystyle \begin{aligned} A(\overline{x}) :=\operatorname{cone}\left\{ a_{t}:\langle a_{t}, \overline{x}\rangle =b_{t},\,t\in T\right\} \end{aligned}$$

is the so-called active cone at $\overline {x}$ and $A(\overline {x})^{\circ }$ denotes its (negative) polar cone, i.e.,

$$\displaystyle \begin{aligned} A(\overline{x})^{\circ }=\{y\in \mathbb{R}^{n}:\left\langle a_{t},y\right\rangle \leq 0,\forall t\in T\text{ such that }\langle a_{t}, \overline{x}\rangle =b_{t}\} \end{aligned}$$

(see Sect. 1.6.1). A necessary condition for LOPCQ is $\overline {F}$ be quasipolyhedral and its set of extreme points be isolated [72, Th. 5.6(ii)]. Any consistent finite system satisfies LOPCQ at any point of $\overline {F}$, which in turn implies LFMCQ at any point of $\overline {F}$. Diagram 1.3, where $\overline {x}$ denotes an arbitrary element of $\overline {F},$ shows the relationships between the above constraint qualifications.

Diagram 1.3 Types of ordinary linear systems

When σ satisfies one of the above constraint qualifications, its corresponding relaxed system $\overline {\sigma }$ also satisfies the same condition (recall that, according to Theorem 1.5(i), an inequality $\left \langle a,x\right \rangle \leq b$ is consequence of σ if and only if it is consequence of $\overline { \sigma }$). This allows us to adapt the known results on ordinary semi-infinite linear systems and ordinary semi-infinite linear programming to systems and linear problems containing strict inequalities.

Example 1.14

Let . It satisfies LFMCQ at any $\overline {x}\in \operatorname {bd}F=\operatorname {bd}\overline {F}$ as each inequality of $\overline {\sigma }$ describes the halfplane determined by a different supporting hyperplane to $\overline {F}$ (the convex hull of the graph of the function $x\longmapsto \frac {1}{x}$ restricted to $\mathbb {R}_{++}$ ). However, FMCQ fails as − x ₁ ≤ 0 and − x ₂ ≤ 0 are linear consequences of $\overline {\sigma }$ which are not consequences of finite subsystems of $\overline {\sigma }$ (Fig. 1.13 shows that the halfplanes − x ₁ ≤ 0 and − x ₂ ≤ 0 do not contain the solution set of the subsystem obtained by replacing T by $\left \{ t_{1},t_{2},t_{3}\right \}$ in $\overline {\sigma }$).

Fig. 1.13

σ satisfies LFMCQ everywhere but not FMCQ

Example 1.15

The system is polynomial and satisfies SCQ as $\widehat {x}=\left ( 1,1\right )$ is a Slater point. Thus, σ ₁ satisfies FMCQ (Fig. 1.14 shows K(σ ₁)) and, so, LFMCQ everywhere. However, LFMCQ is lost by the elimination of at least one of the redundant inequalities corresponding to the indices t = 0, 1. For instance, $\sigma _{2}=\left \{ -tx_{1}+(t-1)x_{2}<t^{2}-t,\;t\in \left ] 0,1\right [ \right \}$ does not satisfy LFMCQ at $\left ( 1,0\right )$ and $\left ( 0,1\right )$ as − x ₁ ≤ 0 and − x ₂ ≤ 0 are linear consequences of $\overline {\sigma }_{2}$ defining supporting halfspace to its feasible set $\overline {F}_{2}=\overline {F}_{1},$ but they are not consequences of any finite subsystems of $\overline {\sigma }_{2}$. Figure 1.15 shows that the halfplanes − x ₁ ≤ 0 and − x ₂ ≤ 0 do not contain the solution set of the subsystem corresponding to the index set $\left \{ t_{1},t_{2},t_{3}\right \}$. Observe that $\overline {F}_{1}=\operatorname {int}\overline {F}_{2}$ is the result of eliminating from $\overline {F}_2$ its two facets.

Fig. 1.14

Characteristic cone of $\overline {\sigma }_{1}$

Fig. 1.15

σ ₂ does not satisfy LFMCQ at two points

1.5.2 Feasible Set

Since we are assuming that F ≠ ∅ and its closure is $\operatorname {cl }F=\overline {F},$ by [148, Ths. 6.2 and 6.3], F and $\overline {F}$ have the same relative interiors and, so, the same relative boundaries, affine hulls, and dimensions. Moreover, if $\operatorname {int}F\neq \emptyset ,$ the interiors and the boundaries of F and $\overline {F}$ are also the same.

The next result is an immediate consequence of [72, Th. 9.3] taking into account that

$$\displaystyle \begin{aligned} 0^{+}F=0^{+}\overline{F}=\left\{ x\in \mathbb{R}^{n}:\left\langle a_{t},x\right\rangle \leq 0,\ t\in T\right\} . \end{aligned}$$

Proposition 1.11 (Boundedness of the Solution Set)

The following statements are equivalent:

• (i) F is bounded.

• (ii) 0_n is the unique solution of $\left \{ \left \langle a_{t},x\right \rangle \leq 0,t\in T\right \} .$

• (iii) $\dbinom {0_{n}}{1} \in \operatorname {int}K\left ( \overline {\sigma }\right ) .$

• (iv) $\operatorname {cone}\left \{ a_{t},t\in T\right \} = \mathbb {R}^{n}.$

To get a formula for $\dim F$ in terms of the data we must introduce another concept. Since

$$\displaystyle \begin{aligned} \left\langle a_{t},x\right\rangle =b_{t},\forall x\in F\Longleftrightarrow \left\langle a_{t},x\right\rangle =b_{t},\forall x\in \overline{F}, \end{aligned}$$

the set of carrier indices of σ, defined as

$$\displaystyle \begin{aligned} T^{=}:=\left\{ t\in T:\left\langle a_{t},x\right\rangle =b_{t},\forall x\in F\right\} \subset W, \end{aligned}$$

coincides with the set of carrier indices of $\overline {\sigma }$ (as defined in [72, p. 101] for ordinary systems), SCQ holds if and only if T ⁼ = ∅ [72, Cor. 5.1.1] and, by [72, Th. 5.1],

$$\displaystyle \begin{aligned} \operatorname{rint}F\subset \left\{ x\in \mathbb{R}^{n}:\left\langle a_{t},x\right\rangle <b_{t},t\in T\backslash T^{=};\left\langle a_{t},x\right\rangle =b_{t},t\in T^{=}\right\} . \end{aligned}$$

The next result involves the lineality of a convex cone K (recall that $\operatorname {lin}K=K\cap \left ( -K\right )$).

Proposition 1.12 (Dimension Formulas)

The following statements hold true:

• (i) $\dim F=n-\dim \operatorname {lin}\operatorname {cl}K(\overline {\sigma }).$ Moreover, if LFMCQ holds at each $\overline {x} \in \overline {F}$ (e.g., if FMCQ holds), then

  $$\displaystyle \begin{aligned} \dim F=n-\dim \operatorname{span}\left\{ a_{t}:t\in T^{=}\right\} \end{aligned}$$

  and

  $$\displaystyle \begin{aligned} \operatorname{aff}F=\left\{ x\in \mathbb{R}^{n}:\left\langle a_{t},x\right\rangle =b_{t},\;t\in T^{=}\right\} . \end{aligned}$$
• (ii)

• (iii) $\dim \operatorname {lin}0^{+}F=n-\dim \operatorname {cone} \left \{ a_{t}:t\in T\right \} .$

Proof

$\left ( i\right )$ comes from [72, Ths. 5.8 and 5.9] , as $\dim F=\dim \overline {F},$ while $\left (\textit {ii}\right )$ and $\left (\textit {iii}\right )$ follow from [72, Remark after Th. 5.8] recalling that $0^{+}F=0^{+}\overline {F}$. □

To get information on the boundary points of F we denote by

$$\displaystyle \begin{aligned} F_{t}:=\left\{ x\in \overline{F}:\left\langle a_{t},x\right\rangle =b_{t}\right\} \end{aligned}$$

the (possibly empty) exposed face of $\overline {F}$ associated with index t ∈ T. Obviously, $F= \overline {F}\backslash \bigcup \limits _{t\in S}F_{t}.$

If σ is analytical, we associate with each $\overline {x}\in F$ a linear subspace $L( \overline {x})$ of $\mathbb {R}^{n}$ defined as the linear span of the union of the sets of successive derivatives $\left \{ a_{t},a_{t}^{\left ( 1\right ) },\ldots ,a_{t}^{\left ( d(t)\right ) }\right \}$ of the slack function at $\overline {x},$ $t\longmapsto \langle a_{t},\overline {x}\rangle - b_{t}$ at those indices t ∈ T which are roots (with order of multiplicity d(t) + 1).

Proposition 1.13 (Boundary and Extreme Points)

The following statements hold true:

• (i) If LFMCQ holds at each $\overline {x}\in \overline {F}$ (e.g., if FMCQ holds), then

  $$\displaystyle \begin{aligned} \operatorname{rint}F=\left\{ x\in \mathbb{R}^{n}:\left\langle a_{t},x\right\rangle =b_{t},\;t\in T^{=};\;\left\langle a_{t},x\right\rangle <b_{t},\;t\in T\backslash T^{=}\right\} , \end{aligned}$$
  $$\displaystyle \begin{aligned} \operatorname{rbd}F=\cup \left\{ F_{t}:t\in T\backslash T^{=}\right\} \end{aligned}$$

  and

  $$\displaystyle \begin{aligned} \operatorname{bd}F=\cup \left\{ F_{t}:a_{t}\neq 0_{n},\;t\in T\right\} . \end{aligned}$$

• (ii) Given $\overline {x}\in F,$ if $\dim A( \overline {x}) =n,$ then $\overline {x}$ is an extreme point of F. The converse statement holds under LOPCQ at $\overline {x}.$

• (iii) Let σ be an analytical system and let $\overline {x}\in F$ be such that the slack function at $\overline {x}$ is not the null function on T. Then, $\overline {x}$ is an extreme point of F if and only if $\dim L(\overline {x}) =n.$

Proof

$\left ( i\right )$ comes from [72, Th. 5.9], as $\operatorname {rint}F=\operatorname {rint}\overline {F},$ and $\left (\textit {ii}\right )$ and $\left (\textit {iii}\right )$ follow from [72, Th. 9.1], recalling that $\operatorname {extr }F=F\cap \operatorname {extr}\overline {F}$ by Proposition 1.1(ii). □

Example 1.16 (Example 1.15 Revisited)

The solution set F ₂ of the system

$$\displaystyle \begin{aligned} \sigma _{2}:=\left\{ -tx_{1}+(t-1)x_{2}<t^{2}-t,\;t\in \left] 0,1\right[ \right\} {} \end{aligned} $$

(1.37)

is the result of eliminating from the set $\overline {F}_{1}$ in Fig. 1.15 the points of the arc $\sqrt {x_{1}}+\sqrt {x_{2}}=1,$ − x ₁ < 0, − x ₂ < 0 (see [72, Ex 1.1]). Since

$$\displaystyle \begin{aligned} \operatorname{cone}\left\{ a_{t},\;t\in \left] 0,1\right[ \right\} =\operatorname{cone} \left\{ \dbinom{-t}{t-1},\;t\in \left] 0,1\right[ \right\} \neq \mathbb{R} ^{2}, \end{aligned}$$

by Proposition 1.11, F is unbounded. Moreover, $\operatorname {aff }F_{2}=\mathbb {R}^{2}$ and $\dim F_{2}=2$, as prescribed by Proposition 1.12(i) even though the additional assumption does not hold. Regarding Proposition 1.13, since T ⁼ = ∅, the three equations in (i) fail, showing the necessity of LFMCQ. Regarding statement (ii), observe that $A(x) =\left \{ 0_{2}\right \}$ for all x ∈ F ₂, even at the extreme points of F ₂, $\left ( 1,0\right )$ and $\left ( 0,1\right ) ,$ which shows that LOPCQ is not superfluous for the converse. Finally, regarding $\left (\textit {iii}\right )$, if we take the analytical system

$$\displaystyle \begin{aligned} \sigma _{3}:=\left\{ -tx_{1}+(t-1)x_{2}<t^{2}-t,\;t\in \left] 0,1\right] ;-tx_{1}+(t-1)x_{2}\leq t^{2}-t,\;t=0\right\}, \end{aligned}$$

whose solution set F ₃ is the result of eliminating from F ₂ the exposed face $\left \{ 0\right \} \times \left [ 1,+\infty \right [$, the slack function at $\overline {x}=\left ( 1,0\right ) \in F_{3}$ is t↦ − t ², whose unique zero is 0, with multiplicity $2=d\left ( 0\right ) +1,$ i.e., $d\left ( 0\right ) =1.$ Since a _t =  ( −t t − 1 ) and $a_{t}^{\left ( 1\right ) }= \begin {pmatrix} -1 \\ 1 \end {pmatrix} ,$

$$\displaystyle \begin{aligned} L(\overline{x}) =\operatorname{span}\left\{ \begin{pmatrix} 0 \\ -1 \end{pmatrix} , \begin{pmatrix} -1 \\ 1 \end{pmatrix} \right\} \end{aligned}$$

and $\dim L(\overline {x}) =2,$ as expected.

1.5.3 Optimality and Duality

Now, we consider the e-LSIP problem (P) and its relaxed problem $(\overline {P})$, defined in (1.35) and (1.36 ), respectively. We adopt the standard convention that the optimal value of a minimization problem is + ∞ (respectively, −∞) when the problem is inconsistent (respectively, unbounded). We denote by v(P), F, and F ^∗ the optimal value, the feasible set, and the optimal set of (P), and by $v(\overline {P})$, $\overline {F}$, and $\overline {F}^{\ast }$ the optimal value, the feasible set, and the optimal set of $(\overline {P})$.

Observe that F ^∗ is the intersection of the e-convex set F with the hyperplane $\left \{ x\in \mathbb {R}^{n}:\left \langle c,x\right \rangle =v\left ( P\right ) \right \} ,$ so it is an e-convex set too. Moreover, since $F\subset \overline {F},$ $v(\overline {P}) \leq v(P)$ (even in the case that F = ∅ due to the above convention). Observe also that, for the e-LSIP problem given by

$$\displaystyle \begin{aligned} \begin{array}{lcl} \left( P\right) \quad & \operatorname*{\mathrm{Min}}\limits_{x\in \mathbb{R}} & x \\ & \text{s.t.} & zx<0, z\in \mathbb{Z}\backslash \left\{ 0\right\} , \end{array} \end{aligned}$$

one has F = F ^∗ = ∅ and v(P) = +∞ while $\overline {F} = \overline {F}^{\ast } = \left \{ 0\right \}$ and $v(\overline {P}) = 0$. So, if F = ∅, we may have $v(\overline {P}) <v( P) =+\infty$ and $F\cap \overline {F}^{\ast }\subsetneq F^{\ast }$.

Proposition 1.14 (Optimal Value and Optimal Set in e-LSIP)

If the e-LSIP problem (P) is consistent, then $v(P) =v(\overline {P})$ and $F^{\ast }=F\cap \overline {F}^{\ast }.$

Proof

On the one hand, since $\emptyset \neq F\subset \overline {F} ,$ there exists a sequence $\left \{ x^{k}\right \}$ contained in $\overline { F}$ such that

$$\displaystyle \begin{aligned} \lim_{k\rightarrow\infty}\langle c,x^{k}\rangle =v(\overline{P}). {} \end{aligned} $$

(1.38)

On the other hand, since $\overline {F}=\operatorname {cl}F,$ for each $k\in \mathbb {N}$ there exists z ^k ∈ F such that

$$\displaystyle \begin{aligned} \left\Vert z^{k}-x^{k}\right\Vert <\frac{1}{k},\forall k\in \mathbb{N}. {} \end{aligned} $$

(1.39)

From (1.38) and (1.39) one gets

$$\displaystyle \begin{aligned} v( P) \leq \lim_{k\rightarrow\infty}\langle c,z^{k}\rangle =\lim_{k\rightarrow\infty}\langle c,x^{k}\rangle = v(\overline{P}), \end{aligned}$$

which combined with $v(\overline {P}) \leq v( P)$ yields $v(\overline {P}) = v(P)$.

It remains to prove the non-trivial inclusion $F^{\ast }\subset F\cap \overline {F}^{\ast }.$ Take an arbitrary x ^∗∈ F ^∗⊂ F. Then $\left \langle c,x^{\ast }\right \rangle \leq \left \langle c,x\right \rangle$ for all x ∈ F. Given $\overline {x}\in \overline {F}$ there exists a sequence $\left \{ x^{k}\right \}$ contained in F such that $\lim _{k}x^{k}=\overline {x}.$ Then,

$$\displaystyle \begin{aligned} \left\langle c,\overline{x}\right\rangle =\lim_{k\rightarrow\infty}\langle c,x^{k}\rangle \geq \left\langle c,x^{\ast }\right\rangle , \end{aligned}$$

showing that $x^{\ast }\in F\cap \overline {F}^{\ast }$. □

From Proposition 1.14, any outer approximation method for $(\overline {P})$, as grid and cutting plane discretization methods, is also an outer approximation method for $\left ( P\right )$. Similarly, any inner approximation method for $( \overline {P})$, like, for instance, feasible directions methods (in particular, simplex-like methods) and interior-point methods, provides a sequence of feasible solutions for $\left ( P\right )$ approaching v(P) even though $\left ( P\right )$ is usually unsolvable.

We now discuss how to associate a suitable dual problem for $\left ( P\right )$ when F ≠ ∅. To this aim we must construct lower bounds for $\left \{ \left \langle c,x\right \rangle :x\in F\right \} .$ Since we are assuming F ≠ ∅, by Proposition 1.14,

$$\displaystyle \begin{aligned} v( P) = \inf \left\{ \left\langle c,x\right\rangle :x\in F\right\} = \inf \left\{ \left\langle c,\overline{x}\right\rangle : \overline{x}\in \overline{F}\right\} = v(\overline{P}) , \end{aligned}$$

which means that we can replace the strict inequalities with weak ones in order to get lower bounds. If $-c\in \operatorname {cone}\left \{ a_{t}:t\in T\right \}$ there exists $\lambda \in \mathbb {R}_{+}^{(T)}$ such that $\sum \nolimits _{t\in T}\lambda _{t}a_{t}=-c.$ Then, for any x ∈ F, one has

$$\displaystyle \begin{aligned} \left\langle c,x\right\rangle =-\sum\nolimits_{t\in T}\lambda _{t}\left\langle a_{t},x\right\rangle \geq -\sum\nolimits_{t\in T}\lambda _{t}b_{t}. {} \end{aligned} $$

(1.40)

Observe that, if λ is a legal element of $\mathbb {R}_{+}^{\left ( T\right ) },$ there exists a t ∈ T such that $\lambda _{t}\left ( \left \langle a_{t},x\right \rangle -b_{t}\right ) <0$ and the inequality in ( 1.40) is strict, but this is not an advantage when one looks for conditions guaranteeing a zero duality gap. So, we associate with $\left ( P\right )$ the Haar dual problem of $(\overline {P})$, which consists in maximizing the lower bound for $\left \langle c,x\right \rangle$ provided by (1.40), that is

$$\displaystyle \begin{aligned} \begin{array}{lcl} \left( D\right) \quad & \operatorname*{\mathrm{Max}}\limits_{\lambda \in \mathbb{R}_{+}^{(T)}} & -\sum_{t\in T}\lambda _{t}b_{t} \\ & \text{s.t.} & -\sum_{t\in T}\lambda _{t}a_{t}=c.\; \end{array} \end{aligned}$$

Defining the Lagrange function of $(\overline {P})$ as

$$\displaystyle \begin{aligned} L\left( x,\lambda \right) :=\left\langle c,x\right\rangle +\sum_{t\in T}\lambda _{t}(\left\langle a_{t},x\right\rangle -b_{t}), {} \end{aligned} $$

(1.41)

one has

$$\displaystyle \begin{aligned} \begin{array}{ll} \inf_{x\in \mathbb{R}^{n}}L\left( x,\lambda \right) & =\inf_{x\in \mathbb{R} ^{n}}\left( -\sum_{t\in T}\lambda _{t}b_{t}+\left\langle c+\sum_{t\in T}\lambda _{t}a_{t},x\right\rangle \right) \\ & =\left\{ \begin{array}{ll} -\sum_{t\in T}\lambda _{t}b_{t}, & \text{if }\lambda \in \mathbb{R}_{+}^{(T)} \text{ and }\sum\nolimits_{t\in T}\lambda _{t}a_{t}=-c, \\ -\infty , & \text{otherwise,} \end{array} \right. \end{array} \end{aligned}$$

so that $\left ( D\right )$ can be reformulated as the classical Lagrangian dual problem of $(\overline {P})$:

$$\displaystyle \begin{aligned} \operatorname*{\mathrm{Max}}\limits_{\lambda \in \mathbb{R}_{+}^{(T)}} \ \inf_{x\in \mathbb{R} ^{n}}L\left( x,\lambda \right) . \end{aligned}$$

Theorem 1.6 (Duality in e-LSIP)

Let $\left ( P\right )$ and $\left ( D\right )$ be consistent. If either FMCQ holds or $-c\in \operatorname {rint}\operatorname {cone} \left \{ a_{t}:t\in T\right \} ,$ then $v(P) = v(D) \in \mathbb {R}$ . In the first case, $\left ( D\right )$ is solvable.

Proof

From the LSIP duality theorems in [72, Th. 8.4] and [155] (see also [72, Ths. 8.1 and 8.2]) one gets that $v(\overline {P}) = v(D) \in \mathbb {R}$, with $\left ( D\right )$ being solvable under FMCQ, and that $v(\overline {P}) = v(D) \in \mathbb {R}$ with $\overline {F}^{\ast }$ being the sum of a nonempty compact convex set with a linear subspace (see [75, Remark 4.16] for this last statement), respectively. We get the conclusion observing that $v(\overline {P})$ coincides with v(P). □

The assumptions of Theorem 1.6 do not guarantee, however, the solvability of (P). Proposition 1.14 also allows us to obtain optimality conditions in e-LSIP.

Theorem 1.7 (Optimality and Strong Uniqueness in e-LSIP)

Each one of the following statements is sufficient for the optimality of x ^∗∈ F regarding $\left ( P\right ) ,$ and they are also necessary when LFMCQ holds at x ^∗:

• (i) $-c\in \operatorname {cl}A(x^{\ast })$.

• (ii) − c ∈ A(x ^∗) (KKT condition) .

• (iii) There exists a feasible solution $\overline {\lambda }$ of $\left ( D\right )$ such that $\overline {\lambda }_{t}\left ( b_{t}-\left \langle a_{t},x^{\ast }\right \rangle \right ) =0$ for all t ∈ T (complementarity condition) .

• (iv) There exists $\overline {\lambda }\in \mathbb {R}_{+}^{(T)}$ such that $L( x^{\ast },\lambda ) \leq L( x^{\ast }, \overline {\lambda }) \leq L( x,\overline {\lambda })$ for all x ∈ $\mathbb {R}^{n},$ with L(⋅, ⋅) defined as in (1.41), and for all $\lambda \in \mathbb {R}_{+}^{(T)}$ (Lagrange saddle point condition).

If, additionally, $-c\in \operatorname {int}A( x^{\ast }) ,$ then x ^∗ is a strongly unique optimal solution of (P), i.e., there exists κ > 0 such that

$$\displaystyle \begin{aligned} \left\langle c,x\right\rangle \geq \left\langle c,x^{\ast }\right\rangle +\kappa \left\Vert x-x^{\ast }\right\Vert \mathit{\text{ for all }}x\in F. {} \end{aligned} $$

(1.42)

The converse also holds under LFMCQ at x ^∗.

Proof

According to [72, Th. 7.1], any of the conditions from $\left ( i\right )$ to $\left (\textit {iv}\right )$ implies that $x^{\ast }\in \overline {F}^{\ast }.$ So, $x^{\ast }\in F\cap \overline {F}^{\ast }=F^{\ast },$ by Proposition 1.14. Under the LFMCQ at x ^∗ these conditions are also sufficient, again by [72, Th. 7.1].

Regarding the strong uniqueness, $-c\in \operatorname {int}A( x^{\ast })$ guarantees [72, Th. 10.6] the existence of κ > 0 such that

$$\displaystyle \begin{aligned} \left\langle c,x\right\rangle \geq \left\langle c,x^{\ast }\right\rangle +\kappa \left\Vert x-x^{\ast }\right\Vert \text{ for all }x\in \overline{F}, {} \end{aligned} $$

(1.43)

which obviously entails (1.42). Since $\overline {F}=\operatorname {cl}F,$ ( 1.42) is actually equivalent to (1.43) and one can apply the converse statement in [72, Th. 10.6] thanks to the LFMCQ assumption. □

Example 1.17 (Example 1.16 Revisited)

Consider the e-LSIP problem

$$\displaystyle \begin{aligned} \begin{array}{lcl} \left( P_{1}\right) \quad & \operatorname*{\mathrm{Min}}\limits_{x\in \mathbb{R}^{2}} & \langle c^{1},x\rangle :=x_{1} \\ & \text{s.t.} & -tx_{1}+(t-1)x_{2}<t^{2}-t,\;t\in \left] 0,1\right[ . \end{array} \end{aligned}$$

We have

$$\displaystyle \begin{aligned} A_{1}(x) =\left\{ 0_{2}\right\} ,\forall x\in F_{1}^{\ast }= \overline{F}_{1}^{\ast }=\left\{ \begin{pmatrix} 0 \\ x_{2} \end{pmatrix} :x_{2}\geq 1\right\} , \end{aligned}$$

which shows the necessity of LFMCQ at Theorem 1.7 (see Fig. 1.16). Moreover, since

$$\displaystyle \begin{aligned} -c^{1}= \begin{pmatrix} -1 \\ 0 \end{pmatrix} \notin \operatorname{cone}\left\{ a_{t},\;t\in \left] 0,1\right[ \right\} =\operatorname{cone }\left\{ \dbinom{-t}{t-1},\;t\in \left] 0,1\right[ \right\} , \end{aligned}$$

its dual problem (D ₁) is inconsistent and v(D ₁) = −∞ < v(P ₁) = 0, abnormality due to the violation of three conditions of Theorem 1.6, namely, the consistency of (D), FMCQ, and $-c\in \operatorname {rint}\operatorname { cone}\left \{ a_{t}:t\in T\right \} .$

Fig. 1.16

The sets F ₁ and $F_{1}^{\ast }$

In contrast with this abnormality, for the problem

$$\displaystyle \begin{aligned} \begin{array}{lcl} \left( P_{2}\right)\quad & \operatorname*{\mathrm{Min}}\limits_{x\in \mathbb{R}^{2}} & \langle c^{2},x\rangle :=x_{1}+x_{2} \\ & \text{s.t.} & -tx_{1}+(t-1)x_{2}<t^{2}-t,\;t\in \left] 0,1\right[ , \end{array} \end{aligned}$$

we have $F_{2}^{\ast }=\emptyset$ while $\overline {F}_{2}^{\ast }=\left \{ \left ( \frac {1}{4},\frac {1}{4}\right ) \right \} ,$ $v(P_{2}) = v( \overline {P}_{2}) = \frac {1}{2},$ and $-c^{2}\in \operatorname {rint}\operatorname { cone}\left \{ a_{t}:t\in T\right \} ,$ so that we must have $v( P_{2}) =v( D_{2}) \in \mathbb {R}$ by Theorem 1.6. In fact, for $\lambda ^{\ast }\in \mathbb {R}_{+}^{(\left ] 0,1 \right [ )}$ such that

$$\displaystyle \begin{aligned} \lambda _{t}^{\ast }=\left\{ \begin{array}{ll} 2, & t=\frac{1}{2}, \\ 0, & \text{otherwise,} \end{array} \right. \end{aligned}$$

one has $-\sum \nolimits _{t\in \left ] 0,1\right [ }\lambda _{t}^{\ast }b_{t}= \frac {1}{2}=v( P_{2}) ,$ so λ ^∗ is an optimal solution of $\left ( D_{2}\right )$ and $v( D_{2}) =\frac {1}{2}$ too.

1.6 Selected Applications

Semi-infinite systems containing strict inequalities (i.e., with S ≠ ∅) naturally arise in polarity, strict separation of sets, stability analysis, linear optimization, and other fields.

1.6.1 Polarity

H. Minkowski [128] defined in 1911 the (negative) polar of a closed convex set X such that 0_n ∈ X as

$$\displaystyle \begin{aligned} X^{\circ }:=\{y\in \mathbb{R}^{n}:\left\langle y,x\right\rangle \leq 1,\ \forall x\in X\}. \end{aligned}$$

Of course, X ^∘ enjoys the same properties as X.

This definition was later extended by H. Rådström [13] to any set X (not necessarily closed and convex), with X ^∘ being still closed and convex with 0_n ∈ X ^∘ and

$$\displaystyle \begin{aligned} \left( \operatorname{cl}X\right) ^{\circ }=X^{\circ }. {} \end{aligned} $$

(1.44)

Moreover, X ⊂ X ^∘∘ holds as any y ∈ X ^∘ satisfies $\left \langle y,x\right \rangle \leq 1,$ for all x ∈ X, so $\operatorname {cl}\operatorname {conv}X\subset X^{\circ \circ }.$ To prove the reverse inclusion, take $y\notin \operatorname {cl}\operatorname {conv}X.$ By the strict separation theorem, there exist $a\in \mathbb {R}^{n},$ a ≠ 0_n, and $b\in \mathbb {R}$ such that $\left \langle a,x\right \rangle <b$ for all x ∈ X and $\left \langle a,y\right \rangle >b.$ Since 0_n ∈ X, b > 0. Then, $\frac {a}{b}\in X^{\circ }$ with $\left \langle \frac {a}{b} ,y\right \rangle >1,$ showing that y∉X ^∘∘. Hence, $X^{\circ \circ }=\operatorname {cl}\operatorname {conv}X$ and the unique sets X containing 0_n and satisfying X ^∘∘ = X are the closed convex ones.

A straightforward consequence of the last statement is the extended Farkas lemma for cones asserting that the involution formula X ^∘∘ = X holds true for closed convex cones, for which, as observed by E. Steinitz [168],

$$\displaystyle \begin{aligned} X^{\circ }=\{y\in \mathbb{R}^{n}:\left\langle y,x\right\rangle \leq 0,\forall x\in X\}. {} \end{aligned} $$

(1.45)

In fact, if X is a cone, given y ∈ X ^∘, one has $\left \langle \lambda y,x\right \rangle =\left \langle y,\lambda x\right \rangle \leq 1,$ for all x ∈ X and λ > 0. Since $\left \langle y,x\right \rangle \leq \frac {1}{\lambda }$ for all x ∈ X, taking limits when λ → +∞ one gets $\left \langle y,x\right \rangle \leq 0,$ so that $X^{\circ }\subset \{y\in \mathbb {R}^{n}:\left \langle y,x\right \rangle \leq 0,\forall x\in X\}$, while the reverse inclusion holds trivially by observing that $\left \langle y,x\right \rangle \leq 0$ entails $\left \langle y,x\right \rangle \leq 1.$

W. Fenchel wondered in 1952 whether it was possible to define a wider class of convex sets than that of closed cones which is reproduced by a suitably defined polarity. Actually, he showed [55] that the answer is affirmative if one considers e-convex sets (concept introduced in that seminal paper) and defined the e-polar of a set X as

$$\displaystyle \begin{aligned} X^{e}:=\{y\in \mathbb{R}^{n}:\left\langle y,x\right\rangle <1,\forall x\in X\}, \end{aligned}$$

which is, obviously, an e-convex set which contains 0_n. Since X ^e ⊂ X ^∘ and X ^∘ is closed, $\operatorname {cl}X^{e}\subset X^{\circ }.$ Conversely, given y ∈ X ^∘, by the definitions of X ^∘ and X ^e, $\left ( 1-\frac {1}{k}\right ) y\in X^{e}$ for all $k\in \mathbb {N},$ so that $y=\lim \nolimits _{k \rightarrow \infty }\left ( 1-\frac {1}{k}\right ) y\in \operatorname {cl}X^{e}.$ Thus, one has

$$\displaystyle \begin{aligned} \operatorname{cl}X^{e}=X^{\circ }. {} \end{aligned} $$

(1.46)

We now prove that X ^ee = X characterizes the e-convex sets which contain 0_n from the characterization of the evenly convex hull in Sect. 1.2. It is obvious that if X ^ee = X, then X is an e-convex set containing 0_n. Assume now that X is an e-convex set containing 0_n . The inclusion $\operatorname {eco}X = X\subset X^{ee}$ holds as any y ∈ X ^e satisfies $\left \langle y,x\right \rangle <1$ for all x ∈ X. To prove the reverse inclusion, let $\overline {x}\notin \operatorname {eco}X$. According to (1.8), there exists $z\in \mathbb {R}^{n}$ such that $\left \langle z,x\right \rangle < \left \langle z,\overline {x}\right \rangle$ for all x ∈ X. Since 0_n ∈ X, then z ≠ 0_n and $b:=\left \langle z,\overline {x} \right \rangle >0$. Letting $\widetilde {z}:=\frac {z}{b}$ one has $\langle \widetilde {z},x \rangle < 1 = \langle \widetilde {z},\overline {x} \rangle$ for all x ∈ X. Thus, $\widetilde {z}\in X^e$ and $\langle \widetilde {z}, \overline {x} \rangle = 1$, which shows that $\overline {x} \notin X^{ee}$.

This involutory formula for the e-polars of e-convex sets implies Minkowski’s one, X ^∘∘ = X, for the polars of closed convex sets. In fact, given an arbitrary closed convex set X containing 0_n, since X is e-convex, we get the nontrivial inclusion X ^∘∘⊂ X from (1.44) and from the fact that X ^e ⊂ X ^∘ implies X ^∘e ⊂ X ^ee as follows:

$$\displaystyle \begin{aligned} X^{\circ \circ }=\operatorname{cl}X^{\circ e}\subset \operatorname{cl}X^{ee}=\operatorname{ cl}X=X. \end{aligned}$$

The term e-polar was first used to refer to X ^e in [101]. In this paper, Klee and his coauthors consider the following binary operations for $X,Y\subset \mathbb {R}^{n}$:

$$\displaystyle \begin{aligned} \begin{array}{l} X\wedge _{1}Y=\left( \operatorname{int}X\right) \cap \left( \operatorname{int}Y\right) \\ X\wedge _{2}Y=X\cap Y \\ X\wedge _{3}Y=\left( \operatorname{cl}X\right) \cap \left( \operatorname{cl}Y\right) \\ X\wedge _{4}Y=\left( X\cap \operatorname{cl}Y\right) \cup \left( Y\cap \operatorname{cl }X\right) \\ X\vee _{1}Y=\operatorname{cl}\operatorname{conv}\left( X\cup Y\right) \\ X\vee _{2}Y=\operatorname{eco}\left( X\cup Y\right) \\ X\vee _{3}Y=\operatorname{conv}\left( \left( \operatorname{int}X\right) \cup \left( \operatorname{int}Y\right) \right) \\ X\vee _{4}Y=\operatorname{eco}\left( X\cup \operatorname{int}Y\right) \cap \operatorname{eco }\left( Y\cup \operatorname{int}X\right) . \end{array} \end{aligned}$$

It is obvious that, if X and Y  are e-convex sets, X ∧_iY  and X ∨_iY  are also e-convex for 1 ≤ i ≤ 3. The even convexity of X ∧₄Y  and X ∨₄Y  is proved in [101, Prop. 4.1]. Moreover, in [101, Prop. 4.3], it is showed that, for 1 ≤ i ≤ 4 , the operations ∧_i and ∨_i are dual in the sense that $\left ( X\wedge _{i}Y\right ) ^{e}=X^{e}\vee _{i}Y^{e}$ and $\left ( X\vee _{i}Y\right ) ^{e}=X^{e}\wedge _{i}Y^{e}$, whenever X and Y  are e-convex sets with 0_n ∈ X ∩ Y .

1.6.2 Semi-Infinite Zero-Sum Two Person Games

A semi-infinite game is a two-person zero-sum game determined by a real matrix with finitely many columns and infinitely many rows. The first papers on semi-infinite games [74, 167, 180] considered countable many rows. They assumed that the only admissible strategies of player I are those which have a finite support so that the reward can be expressed as a finite sum. If the mentioned matrix is $\left \{ a_{t},t\in T\right \}$, with T countable, the mixed strategies of players I and II are

$$\displaystyle \begin{aligned} \varLambda :=\left\{ \lambda \in \mathbb{R}_{+}^{\left( T\right) }:\sum_{t\in T}\lambda _{t}=1\right\} \text{ and }Y:=\left\{ y\in \mathbb{R}_{+}^{n}:\sum_{i=1}^{n}y_{i}=1\right\} , \end{aligned}$$

respectively, whose elements are discrete probability distributions over the corresponding sets of pure strategies. The payoff function is $P\left ( \lambda ,y\right ) =\sum \nolimits _{t\in T}\lambda _{t}\left \langle a_{t},y\right \rangle ,$ which represents the expected outcome of player II when players I and II choose the mixed strategies λ and y, respectively. The maximin and minimax values are

$$\displaystyle \begin{aligned} v_{I}:=\sup_{\lambda \in \varLambda }\min_{j=1,\ldots ,n}P\left( \lambda ,e^{j}\right) \text{ and }v_{II}:=\inf\limits_{y\in Y}\sup_{t\in T}\left\langle a_{t},y\right\rangle , \end{aligned}$$

respectively. Obviously, −∞ < v _I ≤ v _II. The duality gap is v _II − v _I ≥ 0. Denote by $\widetilde {\varLambda }$ and $\widetilde {Y}$ the sets of optimal strategies of players I and II, respectively.

A.L. Soyster proved [167] that, if either player’s problem is consistent and bounded, so is that of his adversary, and the minimax theorem (v _II = v _I) holds. Moreover, $\widetilde {\varLambda }\neq \emptyset$ while player II needs not have an optimal strategy. S.H. Tijs [180], in turn, provided sufficient conditions guaranteeing that v _II = v _I and gave also a new proof that $\widetilde {\varLambda }\neq \emptyset$. Few years later, in [74], falling back on alternative theorems for ordinary semi-infinite systems, it was shown that v _II = v _I and $\widetilde {Y}\neq \emptyset$; the main novelty in this paper was the consideration of semi-infinite games with an arbitrary set T (not necessarily countable) and the analysis of an important type of strategies. A pure strategy t of player I is called essential if, assuming $\widetilde {\varLambda }\neq \emptyset ,$ there exists some $\widetilde {\lambda } \in \widetilde {\varLambda }$ such that $\widetilde {\lambda }_{t}>0.$ Similarly, a pure strategy e ^j of player II is called essential if, assuming $\widetilde {Y}\neq \emptyset ,$ there exists some $\widetilde {y}\in \widetilde {Y}$ such that $\widetilde {y}_{j}>0.$ Theorems 2.4 and 2.6 in [74] provide sufficient conditions for the existence of essential strategies of player II and I, respectively, whose proofs are based on Corollary 1.4. A similar methodology was used in [111] to study more general semi-infinite games, where either the pure strategies for player I are picked, instead of homogeneous linear functions, from an infinite family of convex functions, or the set of mixed strategies available to player II, instead of being the unit simplex is a given closed convex set.

The above results were used in [110, 157, 158] to analyze the so-called semi-infinite transportation and assignment games. In transportation games, an economic agent aims at maximizing her/his profit from transporting an infinitely divisible good from a finite number of suppliers to an infinite number of demanders. The assignment games arise when a finite set of agents of one type is assigned to a countably infinite set of agents of another type; this has to be done in such a way that the total profit arising from these assignments is as large as possible. Finally, it is worth mentioning that nonzero-sum semi-infinite games with arbitrary sets of pure strategies and bounded payoffs have been studied in [143].

1.6.3 Approximate Reasoning

Approximate reasoning is a subdiscipline of artificial intelligence which is focused on the treatment of imprecision and uncertainty. It covers both the foundations of uncertainty theories and the design of intelligent systems for scientific and engineering applications. The generic term imprecise probabilities encompasses several mathematical models to deal with ignorance and uncertainty such as upper and lower probabilities, upper and lower previsions, classes of additive probability measures and partial preference orderings, among other qualitative models (see [187]). Methods of approximate reasoning and statistical inference using imprecise probabilities are based on a behavioral interpretation of probability and principles of coherence. We now introduce some basic notions in approximate reasoning theory.

Assume that the set of outcomes of an experiment is finite, say $\varOmega =\left \{ \omega _{1},\ldots ,\omega _{n}\right \}$. A gamble is a function $x:\varOmega \rightarrow \mathbb {R}$ that can be viewed as a vector in $\mathbb {R}^{n}$. A preference ordering ≻ is a strict partial order over pairs of gambles (i.e., a binary relation on $\mathbb {R}^{n}$ that is irreflexive and transitive). A gamble $x\in \mathbb {R}^{n}$ is called desirable if x ≻ 0. The preference ordering ≻ is monotone whenever, for all $x,y\in \mathbb {R}^{n}$,

$$\displaystyle \begin{aligned} \left[ x_{i}>y_{i},\,\forall i=1,\ldots ,n\right] \Longrightarrow x\succ y, \end{aligned}$$

and it satisfies the cancellation rule whenever, for any $x,y,z\in \mathbb {R}^{n}$, $\alpha \in \left ] 0,1\right ]$, one has

$$\displaystyle \begin{aligned} x\succ y\Longleftrightarrow \alpha x+\left( 1-\alpha \right) z\succ \alpha y+\left( 1-\alpha \right) z. \end{aligned}$$

The literature on sets of desirable gambles employs cones of gambles to model preferences. More precisely, a preference ordering can be captured by focusing on preferences with respect to the zero gamble, or, equivalently, by focusing on a convex cone of gambles. In this sense, the representation in [33, Prop. 2] establishes that, if a preference ordering ≻ satisfies monotonicity and cancellation, then there exists a convex cone D of gambles, not containing the origin but containing the interior of the positive orthant, such that, for every $x,y\in \mathbb {R}^{n}$,

$$\displaystyle \begin{aligned} x\succ y\Longleftrightarrow x-y\in D. {} \end{aligned} $$

(1.47)

In spite of its simplicity, the theory of desirable gambles encompasses not only the Bayesian theory of probability, but also other important mathematical models like credal sets of probabilities. Credal sets is the term used in Bayesian approximate reasoning for the probability distributions which allow to express uncertainty or doubt about the probability model that should be used, or to convey the beliefs of a Bayesian agent about the possible states of the world. They are usually assumed to be compact and convex in order to express them as the closure of the convex hull of their extreme points by the Krein–Milman theorem. More precisely, a credal set is any closed convex subset of the unit simplex

$$\displaystyle \begin{aligned} \mathbb{P}_n :=\left\{p\in\mathbb{R}^n : \sum_{i=1}^{n}{p_i} = 1, 0\leq p_i \leq 1,\,\forall i=1,\ldots,n\right\}, \end{aligned}$$

the set of all probability measures over Ω, where p _i stands for the probability of ω _i for each i = 1, …, n. The duality between credal sets and (coherent) sets of almost desirable gambles (sets of gambles satisfying specific properties and representing rational choices) is well-known in the literature. Given a vector $p\in \mathbb {P}_n$ inducing a probability measure, and a gamble $x\in \mathbb {R}^n$, the expected value of x, denoted by $\mathbb {E_P}[x]$, is simply the inner product 〈p, x〉.

Similarly to (1.47), F. Cozman [33] considered recently preference orderings that can be represented by evenly convex sets of desirable gambles, which indeed can also be represented by evenly convex credal sets. An evenly convex credal set can for instance encode preference judgements through strict and weak inequalities. By introducing the property of even continuity of a preference ordering ≻ whenever, for any $y\in \mathbb {R}^{n}$, sequence of gambles {x ^k}, and sequence of positive scalars {λ _k} such that {λ _ky − x ^k} is convergent, one has

$$\displaystyle \begin{aligned} x^{k}\succ 0\ \forall k\in \mathbb{N},\text{ and }y\succeq 0\text{ is false} \Longrightarrow \lim_{k\rightarrow \infty }\left( \lambda _{k}y-x^{k}\right) \succ 0\text{ is false,} \end{aligned}$$

and calling ≻ coherent if it is monotone, satisfies the cancellation rule, and it is even continuous, the representation in [33, Prop. 7] establishes that, if a preference ordering ≻ is coherent, then there exists an evenly convex cone D of gambles, not containing the origin but containing the interior of the positive orthant, such that, for every $x,y\in \mathbb {R}^{n}$, (1.47) holds.

In addition to that, evenly convex sets of desirable gambles can be represented by evenly convex sets of probability measures. This is shown in the representation theorem [33, Th. 9] which asserts that, if ≻ is a coherent preference ordering, then there exists a unique maximal evenly convex credal set C such that

$$\displaystyle \begin{aligned} x\succ y\Longleftrightarrow \mathbb{E_{P}}[x]>\mathbb{E_{P}}[y] \end{aligned}$$

for all probability measure p ∈ C. Moreover, according to [33, Th. 10], if ≻ is a coherent preference ordering and C is the set built in the proof of the above representation theorem, then a subset C ^′ of the unit simplex of $\mathbb {R}^{n}$ represents ≻ if and only if $C=\operatorname {eco}C^{\prime }$. Thus, different evenly convex sets represent different preference orderings. Finally, the rest of the paper [33] analyzes the duality between preference orderings and credal sets and discusses regular conditioning, a concept which is also closely related to evenly convex sets.

1.6.4 Slater Condition in Mathematical Programming

In almost any branch of optimization there exists a so-called Slater condition allowing to get necessary optimality conditions, duality theorems, and stability results guaranteeing the continuity, in some sense, of the feasible set, the optimal set, and the optimal value under perturbations of the data. These Slater-type conditions can frequently be formulated in terms of the existence of solutions, called Slater points, for suitable non-ordinary systems. We just mention three cases.

• 1. Consider a continuous linear semi-infinite programming problem of the form

  $$\displaystyle \begin{aligned} \begin{array}{lcl} \left( P_{LSIP}\right) \quad & \operatorname*{\mathrm{Min}}\limits_{x\in \mathbb{R}^{n}} & \left\langle c,x\right\rangle \\ & \text{s.t.} & \left\langle a_{t},x\right\rangle \leq b_{t},{ \, }t\in W, \end{array} {} \end{aligned} $$

  (1.48)

  where W is a compact topological space and the functions t↦a _t and t↦b _t are continuous on W. The Slater elements of $\left ( P_{LSIP}\right )$ are the solutions of the non-ordinary continuous semi-infinite system $\left \{ \left \langle a_{t},x\right \rangle <b_{t},{ \, }t\in W\right \} ,$ so the set of Slater elements is e-convex. The Haar dual problem of $\left ( P_{LSIP}\right )$ is

  $$\displaystyle \begin{aligned} \begin{array}{lcl} ( D_{LSIP}^{1}) \quad & \operatorname*{\mathrm{Max}}\limits_{\lambda \in \mathbb{R}_{+}^{(W)}} & -\sum_{t\in W}\lambda _{t}b_{t} \\ & \text{s.t.} & -\sum_{t\in W}\lambda _{t}a_{t}=c, \end{array} \end{aligned}$$

  which is equivalent to the Lagrangian dual problem of $\left ( P_{LSIP}\right ) ,$ that is, the unconstrained optimization problem

  $$\displaystyle \begin{aligned} \begin{array}{ccc} ( D_{LSIP}^{2}) \quad & \operatorname*{\mathrm{Max}}\limits_{\lambda \in \mathbb{R}_{+}^{(W)}} & \inf\limits_{x\in \mathbb{R} ^{n}}L\left( x,\lambda \right) . \end{array} \end{aligned}$$

  A third dual problem for $\left ( P_{LSIP}\right )$ is the so-called continuous dual problem

  $$\displaystyle \begin{aligned} \begin{array}{lcl} ( D_{LSIP}^{3}) \quad & \operatorname*{\mathrm{Max}}\limits_{\mu \in \mathscr{C}_{+}^{\prime }\left( W\right) } & -\int_{W}b_{t}\,d\mu(t) \\ & \text{s.t.} & -\int_{W}a_{t}d\mu(t) =c, \end{array} \end{aligned}$$

  where $\mathscr {C}_{+}^{\prime }\left ( W\right )$ represents the cone of non-negative regular Borel measures on W. The optimal value $v( D_{LSIP}^{j})$ of $( D_{LSIP}^{j}) ,$ j = 1, 2, 3, is not greater than the one of $\left ( P_{LSIP}\right ) ,$ say $v\left ( P_{LSIP}\right ) ,$ i.e., weak duality always holds. Characterizations of optimality, strong duality theorems guaranteeing zero duality gap with dual solvability for the three dual pairs $\left (P_{LSIP}\right )-(D_{LSIP}^{j}), j=1,2,3$, and stability theorems, all of them under the Slater condition can be found in [73, Ths. 1 and 3] and [72, Ths. 6.9 and 10.4], respectively (recall that SCQ implies, for continuous problems, the FMCQ and, so, the weaker LFMCQ at any point).

• 2. We now consider a linear conic optimization problem of the form

  $$\displaystyle \begin{aligned} \begin{array}{lcl} \left( P_{K}\right)\quad & \operatorname*{\mathrm{Min}}\limits_{x\in \mathbb{R}^{n}} & \left\langle c,x\right\rangle \\ & \text{s.t.} & Ax+b\in K, \end{array} \end{aligned}$$

  where $c\in \mathbb {R}^{n},$ A is an m × n matrix, $b\in \mathbb {R} ^{m},$ and K is a pointed closed convex cone in $\mathbb {R}^{m}$ such that $\operatorname {int}K\neq \emptyset .$ The assumptions on K guarantee that K ^∘ satisfies the same properties and the existence of a compact base of K ^∘, that is, a compact convex set W such that 0_m∉W and $K= \operatorname {cone}W$ [65, p. 447]. For instance, a compact base of $\left ( \mathbb {R}_{+}^{m}\right ) ^{\circ }=-\mathbb {R}_{+}^{m}$ is $W=- \operatorname {conv}\left \{ e_{1},\ldots ,e_{m}\right \} ,$ where $\left \{ e_{1},\ldots ,e_{m}\right \}$ is the canonical basis of $\mathbb {R}^{m}.$ Since $K^{\circ }= \operatorname {cone}W,$

  $$\displaystyle \begin{aligned} Ax+b\in K\Longleftrightarrow \left\langle t,\left( Ax+b\right) \right\rangle \leq 0,\forall t\in W. {} \end{aligned} $$

  (1.49)

  Thus, $\left ( P_{K}\right )$ is equivalent to the continuous linear semi-infinite problem $\left ( P_{LSIP}\right )$ in (1.48) just taking a _t = A ^⊤t and $b_{t}=-\left \langle t,b\right \rangle$ for all t ∈ W. As shown in [40, Rem. 2], the dual problem for $\left ( P_{K}\right )$ in the sense of conic optimization is equivalent to the Haar dual problem $( D_{LSIP}^{1})$. Hence, the strong duality holds, for the corresponding versions of the dual problems $(D_{LSIP}^{j})$, j = 1, 2, 3, under the Slater condition that the non-ordinary system $\left \{ \left \langle A^{\top }t,x\right \rangle <-\left \langle t,b\right \rangle ,t\in W\right \}$ is consistent.

• 3. We finally consider a convex (possibly semi-infinite) problem

  $$\displaystyle \begin{aligned} \begin{array}{lcl} \left( P_{CSIP}\right) \quad & \operatorname*{\mathrm{Min}}\limits_{x\in \mathbb{R}^{n}} & f\left( x\right) \\ & \text{s.t.} & f_{t}(x)\leq 0,{ \, }t\in W, \end{array} \end{aligned}$$

  where $f,f_{t}:\mathbb {R}^{n}\rightarrow \mathbb {R}$ are continuous for all t ∈ W. The problem $\left ( P_{CSIP}\right )$ satisfies the Slater condition when the non-ordinary convex system $\left \{ f_{t}(x)<0,t\in W\right \}$ is consistent (this condition implies strong duality and allows to obtain optimality conditions). For any t ∈ W, as f _t is a convex real-valued function, it is subdifferentiable on $\mathbb {R}^{n}$. Thus, the set of Slater points of $\left \{ f_{t}(x)\leq 0,t\in W\right \}$ is the solution set of the non-ordinary semi-infinite system

  $$\displaystyle \begin{aligned} \left\{ f_{t}(y)+\left\langle u,(x-y)\right\rangle <0,\left( y,u\right) \in \operatorname{gph}\partial f_{t},t\in W\right\} , {} \end{aligned} $$

  (1.50)

  where

  $$\displaystyle \begin{aligned} \operatorname{gph}\partial f_{t}:=\left\{ \left( u,y\right) \in \mathbb{R}^{2n}:u\in \partial f_{t}(y)\right\} \end{aligned}$$

  is the graph of the subdifferential mapping $\partial f_{t}:\mathbb {R}^{n}\rightrightarrows \mathbb {R}^{n}$ defined by

  $$\displaystyle \begin{aligned} \partial f_{t}(y)=\left\{ u\in \mathbb{R}^{n}:f_{t}(x)\geq f_{t}(y)+\left\langle u,(x-y)\right\rangle ,x\in \mathbb{R}^{n}\right\} . \end{aligned}$$

  In the particular case of convex quadratic systems, we can write $f_{t}(x)= \frac {1}{2}\left \langle x,Q_{t}x\right \rangle +\left \langle c_{t},x\right \rangle +d_{t},$ where Q _t is a symmetric n × n positive semidefinite matrix, $c_{t}\in \mathbb {R}^{n}$ and $d_{t}\in \mathbb {R},$ for all t ∈ W. Then, (1.50) becomes

  $$\displaystyle \begin{aligned} \left\{ \left\langle \left( Q_{t}y+c_{t}\right) ,x\right\rangle <\frac{1}{2} \left\langle y,Q_{t}y\right\rangle -d_{t},\left( y,t\right) \in \mathbb{R} ^{n}\times W\right\} . \end{aligned}$$

1.6.5 Strict Separation of Finite Families of Sets

The search of a hyperplane separating strictly a pair of disjoint sets in $\mathbb {R}^{n}$, say Y  and Z, can be formulated as the feasibility problem for the non-ordinary system of strict inequalities (with W = ∅)

$$\displaystyle \begin{aligned} \left\{ \left\langle y,x\right\rangle <x_{n+1},\;y\in Y;\;-\left\langle z,x\right\rangle <-x_{n+1},\;z\in Z\right\} , {} \end{aligned} $$

(1.51)

where the unknown $\dbinom {x}{x_{n+1}}\in \mathbb {R}^{n+1}$ determines the vector of coefficients of the separating hyperplane. Observe that x ≠ 0_n for any solution $\dbinom {x}{x_{n+1}}$ of the system in (1.51).

The concept of strict separation of sets was extended in [12] to families of more than two sets as follows. A family of m ≥ 2 nonempty sets in $\mathbb {R}^{n}$, A ₁, …, A _m is said to be strictly separable if there exist m closed halfspaces S ₁, …, S _m such that $A_{j}\subset \operatorname {int}S_{j}$, j = 1, …, m, and $\overset {m}{\underset {j=1}{\cap }} \operatorname {int}S_{j}=\emptyset$, i.e., if, for each j = 1, …, m, there exists a solution $\dbinom {c_{j}}{d_{j}}\in \mathbb {R}^{n+1}$ of $\sigma _{j}:=\left \{ \left \langle a,x\right \rangle -x_{n+1}<0,\;a\in A_{j}\right \}$ , with c _j ≠ 0_n, such that the system $\sigma _{0}:=\left \{ \left \langle c_{j},x\right \rangle <d_{j},\;j=1,\ldots ,m\right \}$ is inconsistent.

According to [12, Th. 2], if $\underset {k\neq j}{\overset {m}{\underset { k=1}{\cap }}}A_{k}\neq \emptyset$, j = 1, …, m, then the inconsistency of σ ₀ can be replaced by the simple condition that $\sum \limits ^{m}_{j=1}{\dbinom {c_{j}}{d_{j}}} = 0_{n+1}$.

1.7 Bibliographic Notes

Many mathematicians have contributed to the convexity theory in finite dimensional spaces, but the most influential of them, thanks to the popularity attained by their respective books on the subject, have been, in chronological order:

• Hermann Minkowski: His celebrated book [128], published in 1911 (even though the first 240 pages were a reprint of his 1896 monograph [127]), introduced the concepts of extreme point, convex hull, convex body (i.e., fully dimensional compact convex set), supporting hyperplane, support function, sum of two sets, etc. Minkowski provided a conjoint theory of ordinary linear inequality systems and polyhedra, including the proof of the finiteness of the set of extreme points of the latter sets and the characterization of the linear inequalities which are the consequence of a given consistent linear inequality system (i.e., the so-called non-homogeneous Farkas lemma).

• Werner Fenchel: His book [54], where he collected his lectures at Princeton University during his sabbatical academic year 1950/51, introduced the key concept of conjugate function, the notion of strict polar of a closed convex set, etc. A year later, in 1952, he introduced the evenly convex sets in order to extend the polarity theory to nonclosed convex sets [55].

• Ralph Tyrrell Rockafellar: The preface of his classical book [148], published in 1970, where he virtually fixed the present notation and basic results of modern convex analysis, recognizes the influence of Fenchel’s view of convexity (not by chance, [148] was dedicated to Fenchel “as honorary coauthor”), in particular the crucial role played by the notion of conjugate function. Before that, Rockafellar introduced in 1963, together with Jean-Jacques Moreau, the concepts of subgradient and subdifferential and provided results involving linear systems containing strict inequalities. Victor Klee recognized that his work [99] on maximal separation theorems for e-convex sets was inspired by the mentioned paper by Fenchel on polarity together with an unpublished separation theorem, proved by Rockafellar [146], for the so-called partially polyhedral sets (a particular class of e-convex sets defined in [150, p. 510]).

After the above mentioned seminal contributions to the theory of evenly convex sets, this type of convex sets appeared sporadically in the literature for almost 30 years. Thus, in 1970 and 1972, Schröder used evenly convex sets to obtain his linear range-domain implications [161, 162]. In the eighties and early nineties, the evenly convex sets were applied in quasiconvex programming [120, 121, 138,139,140] and mathematical economy [122]. Linear systems containing strict inequalities, in turn, naturally arose in convex optimization [150, 190], separation problems [12, 99, 100], and stability analysis [72, Th. 6.9], among other fields of mathematics and computer sciences.

The resurgence of the even convexity theory in the 2000s is also motivated by the mentioned stream of new applications of linear strict inequality systems and the potential applications of evenly convex and quasiconvex functions in economy. New characterizations of e-convex sets have been obtained by Daniilidis and Martínez-Legaz [37] and by Goberna, Jornet and Rodríguez [71] (in infinite and finite dimensions, respectively), showing that the class of e-convex sets enjoys most of the well-known properties of the subclasses of open and closed convex sets. Even convexity has been used to characterize the consistency of linear semi-infinite systems containing strict inequalities in [78], whose results remain valid in Banach spaces [133], and to obtain dual characterizations of set containments with strict convex inequalities [68] (results which have been extended to systems of strict cone-convex inequalities [39] and to systems of quasiconvex inequalities, see [171, 174]). Furthermore, Klee, Maluta and Zanco have studied the behavior of e-convex sets under sections and projections [101], which unfortunately became the last publication in the fruitful research career of the first author. A suitable extension of the concept of e-convex set is used in [60] to study quasi-convex dynamic risk measures.

This chapter is mostly based on [37, 55, 68, 71, 78, 99]. More precisely, concerning Sect. 1.1, recently reviewed in [79], the proof of the equivalence between the first six conditions in Theorem 1.1 can be found in [71, Prop. 3.1], for (i)⇔(ii)⇔(iii), [55, Items 3.2 and 3.4], for (i)⇔(iv)⇔(v), and [37, Th. 5], for $\left ( i\right ) \Longleftrightarrow \left (\textit {vi}\right )$. The properties of e-convex sets gathered in Proposition 1.1 come from [55, Item 3.5], for $\left (\textit {iii}\right )$, [71, Cor. 3.2], for $\left (\textit {vi}\right )$, and [71, Prop. 3.2-3.4], for the remaining properties. The statements on operations with e-convex sets in Proposition 1.2 have been proved in [71, Prop. 3.5], for $\left (\textit {ii}\right )$, [71, Prop. 3.6], for the “if” part of $\left (\textit {iii}\right )$, [151, Prop. 1.2], for the “only if” part of $\left (\textit {iii}\right )$, [71, Prop. 3.7], for $\left (\textit {iv}\right )$, [71, Prop. 3.8], for $\left ( v\right )$ and [101, Cor. 2.3], for $\left (\textit {vi}\right )$. Example 1.3 appeared in [101, Ex. 2.5].

Section 1.2, also reviewed in [79], provides the notion of evenly convex hull that was introduced by W. Fenchel in [55, Items 4.1 and 4.2]. Its characterization in Proposition 1.3 is proved in [78, Prop. 2.1]. The relationships between $\operatorname {eco}$ and other hulls in Proposition 1.4 are [78, $\left ( 2.2\right )$ and $\left ( 2.4\right )$], for $\left (\textit {iii}\right )$ and $\left (\textit {iv}\right )$, respectively, and [78, Prop. 2.7], for $\left ( v\right )$. The results involving operations with e-convex hulls in Proposition 1.5 are proved in [78, Props. 2.3-2.6], for $\left (\textit {ii}\right )$, $\left (\textit {iii}\right )$, $\left (\textit {vi}\right )$, and $\left (\textit {vii}\right )$, respectively, and [78, Cor. 2.1], for $\left (\textit {iv}\right )$.

Section 1.3 presents a selection of the separation theorems for convex sets collected in Klee’s paper [99], which was published only 2 years before the coining of the basic concepts and notations of convex analysis in the celebrated Rockafellar’s book [148]. So, we have adapted here most Klee’s separation theorems involving e-convex sets to the modern convex analysis language, the main difficulty being the intuitive style of some arguments and the misleading use of different concepts of supporting hyperplane in [99]. Example 1.9 is attributed to T.A. Botts by the same Klee [99, p. 134], Theorems 1.2 and 1.3 are based on [99, Th. 4] and [99, Th. 5], respectively, Lemma 1.1 is [99, Lemma 1] and Corollary 1.1 is [99, Cor. p. 138].

The e-convex sets are the solution sets of the linear inequality systems possibly containing strict inequalities whose study is the objective of Sect. 1.4. The relationships between the solution sets of a system σ containing strict inequalities and its relaxed system $\overline { \sigma }$ (Proposition 1.6) appeared in [71, Prop. 1.1]. The rest of this section is devoted, firstly, to existence theorems, secondly, to Farkas-type lemmas, and, thirdly, to the containment problem for e-convex sets.

Section 1.4.1 starts recalling the known characterizations of the consistent relaxed system. We summarize in Table 1.1 the relevant information on the most outstanding existence theorems, most of them expressed as alternative theorems, i.e., theorems which have the following form: exactly one of the two formulated propositions holds true. The 11 sources in Column 1 appear chronologically ordered, as Column 2 shows. The Columns 3, 4 and 5, in turn, inform on the cardinality of the index sets, which can be empty, finite or arbitrary (abbreviated as “∅”, “fin.” and “arb.”, respectively). Column 6 informs about the kind of right-hand side scalars b _t the theorems deal with (0, in the case of homogeneous systems, and arbitrary, otherwise). Finally, Column 7 informs about the full generality or not of the corresponding existence theorem, i.e., whether the result always holds or it does just under certain assumptions.

Table 1.1 Existence theorems

Observe that all the known existence theorems for systems containing an arbitrary number of strict inequalities are only valid provided that a suitable closedness assumption holds. Cor. 3.1.1 and Th. 3.1 in [72] provide simple proofs of the characterization of the consistency of $\overline {\sigma }$ by means of conditions (1.11) and (1.12), results which also follow from existence theorems due to K. Fan [50, Th. 1] and Y. J. Zhu [193, Th. 1], respectively. These authors considered linear systems of weak inequalities of the form $\overline {\sigma }=\left \{ \left \langle a_{t}^{\ast },x\right \rangle \leq b_{t},{ \, }t\in T\right \} ,$ where x lives in a given locally convex separated (i.e., Hausdorff) topological vector space X with topological dual X ^∗, $a_{t}^{\ast }\in X^{\ast }$ and $b_{t}\in \mathbb {R}$ for all t ∈ T. The mentioned characterizations of the consistency of $\overline {\sigma },$ (1.11) and (1.12), are still valid in the infinite-dimensional setting by replacing 0_n with the null linear functional of $0_{X^{\ast }}$. In this infinite-dimensional setting, $N(\overline {\sigma })$, $K(\overline {\sigma }) \subset X^{\ast }\times \mathbb {R}$, so that conditions (1.11) and ( 1.12) can be seen as dual characterizations of the consistency of $\overline {\sigma }.$ Consequently, the same adjective, dual, applies to any condition involving subsets of either X ^∗ or $X^{\ast }\times \mathbb {R}$, which have the advantage of being expressed in terms of the data (the coefficients of $\overline {\sigma }$). The existence Theorem 1.4 for linear systems involving strict inequalities was proved in [78, Th. 3.1], Corollary 1.3 in [71, Prop. 2.1], and Corollary 1.6 in [78, Cor. 3.2], while Corollaries 1.4 (proved in [78, Cor. 3.3]) and 1.5 are improved versions of the Generalized Gordan’s alternative theorem [72, Th. 3.2] and the Extended Motzkin’s alternative theorem [72, Th. 3.5], respectively. The “like” in the names given to these results means that they extend to semi-infinite systems the corresponding results for finite systems. Proposition 1.7 is [71, Prop. 2.2].

Section 1.4.2 deals with the extension to systems of an arbitrary number of constraints possibly containing strict inequalities of the generalized non-homogeneous Farkas lemma (1.26) characterizing the weak linear inequalities which are consequence of a finite consistent system of inequalities of the same type [72, Th. 3.1], which remains valid in locally convex spaces [193, Th. 2]. The concept of legal linear combination was introduced by H.V. Kuhn [108] and by J. Stoer and C. Witzgall [170] for ordinary finite linear systems. The term legal for the non-null elements of $\mathbb {R}_{+}^{\left ( T\right ) }$ and for the corresponding linear combinations of σ were introduced by the same Kuhn [108]. The main result of this subsection, Theorem 1.5, subsumes [78, Props. 4.1 and 4.2].

Regarding Sect. 1.4.3, Proposition 1.10 comes from [68, Props. 5.1-5.3] and Proposition 1.8 from [68, Prop. 5.4]. The containment problem has been solved for different pairs of sets usually represented by inequality systems. The simplest and most studied version is the polytope containment problem, as it has important applications such as computational geometry [64], machine learning [61], and control theory [87]. Computational issues on this problem are discussed in [156]. The polyhedral containment problem was posed by Mangasarian [117], who also introduced non-polyhedral extensions. In fact, he characterized in [118], via nonlinear programing, the containment of a polyhedral convex set F in a reverse convex set (i.e., the complement of a finite union of convex sets) described by convex quadratic functions, as

$$\displaystyle \begin{aligned} G=\left\{ x\in \mathbb{R}^{n}: \frac{1}{2}\left\langle x,Q_{i}x\right\rangle +\left\langle a_{i},x\right\rangle \geq b_{i},i=1,\ldots ,m\right\} , \end{aligned}$$

with Q _i symmetric and positive semi-definite, $a_{i}\in \mathbb {R}^{n},$ and $b_{i}\in \mathbb {R}$ for i = 1, …, m, that is, the situation illustrated in Fig. 1.17. The same Mangasarian [118] characterized the containment of a convex set in a reverse convex set (the situation shown in Fig. 1.18), both represented by differentiable functions, while Jeyakumar [93] proposed a non-smooth counterpart for this containment via epigraphs of conjugate functions.

Fig. 1.17

Inclusion of a polyhedron F in a quadratic reverse set G

Fig. 1.18

Inclusion of a convex set F in a quadratic reverse convex set G

The containment problem has also been solved for pairs of sets represented by systems of cone-convex inequalities [39], by quasiconvex systems [173, 174], by quasiconvex systems containing strict inequalities [171], by sum-of-squares convex polynomial systems [96], etc.

Section 1.5 is basically the transcription of known results on ordinary linear semi-infinite systems and linear semi-infinite programming to systems and problems containing strict inequalities where the concept of carrier index plays a crucial role. As pointed out in [104], the term carrier index was used for the first time in [72] (in the context of linear SIP), but it has received different names in the literature: always binding constraint in [1], implicit equality constraint in [83], and immobile index in [102, 103], as well as in different papers of Kostyukova and Tchemisova (e.g., [105, 106]). The set of carrier indices was called equality set of constraints in [189]. The existence of carrier indexes is incompatible with the SCQ, which was introduced by M. Slater in the framework of convex programming [164], the FMCQ by Charnes, Cooper and Kortanek in [31] to guarantee zero-duality gap in LSIP, and the LFMCQ by Puente and Vera de Serio in [144] as the weakest constraint qualification allowing to characterize optimality in LSIP. The term “continuous linear system” was first used in the framework of stability while analytical systems and polynomial systems appeared in [3] (in order to give a simplex-like method for LSIP problems) and [70] (in a geometric setting), respectively. The LSIP problems satisfying the LOPCQ may also be treated by means of some simplex-like method [2].

The natural extension to the infinite-dimensional setting of LSIP problems are the linear infinite programming (LIP) problems of the form

$$\displaystyle \begin{aligned} \begin{array}{lcl} \left( P\right) \quad & \operatorname*{\mathrm{Min}}\limits_{x\in X} & \left\langle c,x\right\rangle \\ & \text{s.t.} & \left\langle a_{t},x\right\rangle \leq b_{t}, t\in T, \end{array} \end{aligned}$$

where the decision space X is locally convex and c, a _t ∈ X ^∗ for all t ∈ T. Duality theorems for different types of dual problems for $\left ( P\right )$, among them the LIP Haar dual defined in the same way as in LSIP, can be found in [75, Rem. 3.10, 4.16 and 5.6, and Cor. 4.15] and [76, Section 6]. From these results it is possible to obtain e-LIP versions of Theorem 1.7.