Properties of Generalized Polyhedral Convex Multifunctions

The concept of polyhedral convex sets or convex polyhedra can be traced back to ancient Greece, where Plato discussed the five regular polyhedra in his book “Timaeus.” However, it wasn’t until the 19th century that the study of convex polyhedra gained significant interest due to their crucial role in the theory of linear programming and their connection to convex analysis and optimization. The notion of polyhedral convex sets has since been used to define polyhedral convex functions and polyhedral convex multifunctions, which require their epigraphs and graphs, respectively, to be polyhedral convex sets. Polyhedral convex sets, functions, and multifunctions have many nice properties that can be used in convex analysis and optimization, making them valuable in many applications; see, e.g., Lee_Tam_Yen_2005 ; mordukhovich_nam_2021 ; Qui_Yen_NA_2011 ; Rockafellar_1970 ; Zheng_Yang_2008 .

The important role of polyhedral convex sets in optimization and other areas has led to the development of a more general concept called generalized polyhedral convex set in the framework of locally convex Hausdorff topological vector spaces. This concept was introduced by Bonnans and Shapiro in their book “Perturbation Analysis of Optimization Problems”, where they defined a generalized polyhedral convex set as the intersection of a polyhedral convex set and a closed affine subspace (Bonnans_Shapiro_2000, , Definition 2.195). These more general sets allow for a broader range of applications in optimization and other fields, particularly in the theories of generalized linear programming and quadratic programming (Bonnans_Shapiro_2000, , Sections 2.5.7 and 3.4.3).

It is well known that any infinite-dimensional normed space equipped with the weak topology is not metrizable, but it is a locally convex Hausdorff topological vector space. Similarly, the dual space of any infinite-dimensional normed space equipped with the weak^∗ topology is not metrizable, but it is a locally convex Hausdorff topological vector space. The just mentioned two models provide us with the most typical examples of locally convex Hausdorff topological vector spaces, whose topologies cannot be given by norms. Therefore, it is necessary to study the generalized polyhedral convex set in locally convex Hausdorff topological vector spaces.

A generalized polyhedral convex function and a generalized polyhedral convex multifunction can be defined accordingly by requiring their epigraphs and graphs, respectively, to be generalized polyhedral convex sets. So, the concept of generalized polyhedral convex set has proved to be very useful in many issues of convex analysis and applications; see Ban_Mordukhovich_Song_2011 ; Ban_Song_2016 ; Gfrerer_2013 ; Gfrerer_2014 ; Lim_Tuan_Yen_2022a ; Lim_Tuan_Yen_2022b ; Luan_Acta_2018 ; Luan_Nam_Thieu_Yen ; Luan_Yen_Optim_2020 ; Yen_Yang_2016 ; Zheng_2009 ; Zheng_Ng_2014 ; Zheng_Yang_2021 and the references therein. The paper of Luan, Yao, and Yen Luan_Yao_Yen_2018 can be seen as a comprehensive study on generalized polyhedral convex sets, generalized polyhedral convex functions on locally convex Hausdorff topological vector spaces, and the related constructions such as sum of sets, sum of functions, directional derivative, infimal convolution, normal cone, conjugate function, subdifferential, sum rule. Some results of Luan_Yao_Yen_2018 can be considered as adequate extensions of the corresponding classical results in (Rockafellar_1970, , Section 19).

The present paper explores many properties of generalized polyhedral convex multifunctions with refinements to the case of polyhedral convex ones. We first examine the generalized polyhedral convexity of the domains and ranges as well as the direct and inverse images of generalized polyhedral convex sets under these mappings. Our new results include an answer to the question of whether the domain of a generalized polyhedral convex multifunction is also a generalized polyhedral convex set in locally convex topological vector spaces. This is an important extension of a related result by Bonnans and Shapiro in the Banach space setting (see (Bonnans_Shapiro_2000, , Theorem 2.207)). Then we study the preservation of polyhedral convexity for multifunctions under various operations. We provide our answers to another question asking if the sum or composition of two generalized polyhedral convex multifunctions remains a generalized polyhedral convex multifunction. The question has not been fully answered in the literature, even in the case of polyhedral convex mappings. We also study the generalized polyhedral convexity of the optimal value function, which is important in parametric optimization. The specific features of generalized polyhedral convex sets allow us to obtain a representation for their generalized relative interiors, which we use to study the generalized relative interiors of graphs of generalized polyhedral convex multifunctions in locally convex topological vector spaces. Our developments have great potential applications to the theory of generalized differentiation involving generalized polyhedral convex sets, functions, multifunctions, and to optimization theory.

The paper is structured as follows. Section 2 introduces basic notions and results related to generalized polyhedral convex sets and multifunctions. In Section 3, we discuss some properties of generalized polyhedral convex multifunctions including their domains and ranges, as well as the direct and inverse images of generalized polyhedral convex sets under such mappings. The stability of generalized polyhedral convexity under basic operations is presented in Section 4. Section 5 is devoted to the study of generalized relative interiors of generalized polyhedral convex sets. We obtain a representation for the relative interior of the graph of a generalized polyhedral convex multifunction in locally convex topological vector spaces.

In the sequel, $X$, $Y$, and $Z$ are assumed to be locally convex Hausdorff topological vector spaces. We use the notation $X^{*}$ to denote the topological dual space of $X$, and $\langle x^{*},x\rangle$ to represent the value of $x^{*}\in X^{*}$ at $x\in X$. For a subset $\Omega\subset X$, we denote its topological closure and interior by $\overline{\Omega}$ and ${\rm int}\,\Omega$, respectively. The same notation is used for subsets of $X^{*}$. The cone (resp., the linear subspace) generated by a set $\Omega\subset X$ are denoted by ${\rm cone}\,\Omega$ (resp., ${\rm span}\,\Omega$).

This section recalls the definitions of generalized polyhedral convex sets, functions, and multifunctions, as well as some basic notations and results that will be used throughout the paper. The readers are referred to Bonnans_Shapiro_2000 for more details.

Let $X_{0}\subset X$ be a closed linear subspace. Recall that the codimension of $X_{0}$ is the dimension of the quotient space $X/X_{0}$ (see (Rudin_1991, , p. 106)). In the lemma below, we present two well-known characterizations of finite-codimensional linear subspaces and provide a detailed proof for the convenience of the readers.

A subset $D\subset X$ is said to be a generalized polyhedral convex set, or a generalized convex polyhedron, if there exist $x^{*}_{i}\in X^{*}$, $\alpha_{i}\in\mathbb{R}$, $i=1,2,\ldots,m$, and a closed affine subspace $L\subset X$ such that

If $D$ can be represented in the form (2.1) with $L=X$, then we say that it is a polyhedral convex set, or a convex polyhedron.

Let $D$ be given as in (2.1). By (Bonnans_Shapiro_2000, , Remark 2.196), there exists a continuous surjective linear mapping $A$ from $X$ to a locally convex Hausdorff topological vector space $Z$ and a vector $z\in Z$ such that $L=\big{\{}x\in X\mid A(x)=z\big{\}}$. Then $D$ can be represented by

If $D$ is a polyhedral convex set in $X$, then one can choose $Z=\{0\}$, $A\equiv 0$, and $z=0$.

It follows from the definition that every generalized polyhedral convex set is a closed set. If $X$ is finite-dimensional, a subset $D\subset X$ is a generalized polyhedral convex set if and only if it is a polyhedral convex set. In that case, we can represent a given affine subspace $L\subset X$ as the solution set of a system of finitely many linear inequalities.

The following representation theorem for generalized convex polyhedral sets in the spirit of Rockafellar_1970 is crucial for our subsequent proofs.

Given a function $f\colon X\rightarrow\bar{\mathbb{R}}=[-\infty,\infty]$, recall that the epigraph of $f$ is defined by

The function $f$ is said to be a lower semicontinuous if $\mbox{\rm epi}\,f$ is a closed set in $X\times\mathbb{R}$. We also say that $f$ is a generalized polyhedral convex function (resp., a polyhedral convex function) if $\mbox{\rm epi}\,f$ is a generalized polyhedral convex set (resp., a polyhedral convex set) in $X\times\mathbb{R}$.

Let $F\colon X\rightrightarrows Y$ be a multifunction. The domain, range, and graph of $F$ are defined, respectively, by

and

It is clear that ${\rm dom}\,F=\pi_{X}({\rm gph}\,F)$, where $\pi_{X}\colon\,X\times Y\rightarrow X$ with $\pi_{X}(x,y)=x$ is the projection mapping from $X\times Y$ onto $X$. Similarly, ${\rm rge}\,F=\pi_{Y}({\rm gph}\,F)$, where $\pi_{Y}\colon\,X\times Y\rightarrow Y$ with $\pi_{Y}(x,y)=y$ is the projection mapping from $X\times Y$ onto $Y$. Observe that ${\rm rge}\,F^{-1}={\rm dom}\,F$ and ${\rm rge}\,F={\rm dom}\,F^{-1}$, where the inverse multifunction $F^{-1}\colon Y\rightrightarrows X$ of $F$ is given by $F^{-1}(y)=\{x\in X\mid y\in F(x)\}$.

A multifunction $F\colon X\rightrightarrows Y$ is said to be generalized polyhedral (resp., polyhedral) if ${\rm gph}\,F$ is a union of finitely many generalized polyhedral convex sets (resp., polyhedral convex sets) in $X\times Y$. If ${\rm gph}\,F$ is generalized polyhedral convex (resp., polyhedral convex), then we say that $F$ is generalized polyhedral convex (resp., polyhedral convex).

Clearly, if $F\colon X\rightrightarrows Y$ is generalized polyhedral convex (resp., polyhedral convex), then $F^{-1}$ is also generalized polyhedral convex (resp., polyhedral convex).

Let $F\colon X\rightrightarrows Y$ be a generalized polyhedral convex multifunction. If $A\colon X\times Y\rightarrow Z$ is a continuous linear mapping, then the formula $A_{1}(x)=A(x,0)$ for $x\in X$ (resp., the formula $A_{2}(y)=A(0,y)$ for $y\in Y$) defines a continuous linear mapping from $X$ to $Z$ (resp., a continuous linear mapping from $Y$ to $Z$), and one has

Note also that $(X\times Y)^{*}=X^{*}\times Y^{*}$. Therefore, the graph of $F$ can be given by the formula

where $A_{1}$ (resp., $A_{2}$) is a continuous linear mapping from $X$ (resp., from $Y$) to $Z$, $z\in Z$, $x^{*}_{i}\in X^{*}$, $y^{*}_{i}\in Y^{*}$, $\beta_{i}\in\mathbb{R}$, for $i=1,\ldots,m$. Conversely, if the graph of a multifunction $F\colon X\rightrightarrows Y$ can be represented by (2.5), then $F$ is a generalized polyhedral convex multifunction. Note that if $\mbox{\rm gph}\,F$ is the emptyset, then by definition $F$ is a generalized polyhedral convex multifunction. Clearly, if $F$ is a polyhedral convex multifunction, then one can choose $Z=\{0\}$, $A_{1}\equiv 0$, $A_{2}\equiv 0$ and $z=0$. If the graph of a multifunction $F\colon X\rightrightarrows Y$ can be represented by (2.5), where $Z=\{0\}$, $A_{1}\equiv 0$, $A_{2}\equiv 0$ and $z=0$, then $F$ is a polyhedral convex multifunction.

We say that a continuous linear mapping $A\colon Y\rightarrow Z$ is closed under finite-codimensional subspaces if $A(Y_{0})$ is closed for every finite-codimensional closed linear subspace $Y_{0}\subset Y$. Clearly, if $A$ is closed under finite-codimensional subspaces, then $A(Y)$ is closed. The converse is true if both $Y$ and $Z$ are Fréchet spaces (see Theorem 3.11 below). In particular, any continuous linear mapping between Banach spaces with a closed range is closed under finite-codimensional subspaces. This fact has been established by one of the two referees with direct proof.

In this section, we study the domains and ranges of generalized polyhedral convex multifunctions, as well as the direct and inverse images of generalized polyhedral convex sets under such mappings. We will also discuss refinements of the obtained results in the case of polyhedral convex sets and multifunctions.

First, we will extend a part of Theorem 2.207 in the book by Bonnans and Shapiro Bonnans_Shapiro_2000 , which was given in a Banach space setting, to the case of generalized polyhedral convex multifunctions in locally convex Hausdorff topological vector spaces.

Combining the result in the claim above with the continuity of the linear mapping $\widetilde{A}_{1}$, we can assert that $\widetilde{A}_{1}^{-1}(\widetilde{A}_{2}(Y))$ is closed. Therefore, the subspace $\pi_{X}(W_{0})$ is closed by formula (3.10). From (3.6), we conclude that ${\rm dom}\,F$ is a generalized polyhedral convex set by Theorem 2.2. $\hfill\Box$

To derive the following result, we use a similar argument as in the proof of Theorem 3.1.

We can explore an interesting question related to Theorem 3.1: Can the assumption that the mapping $A_{2}$ is closed under finite-codimensional subspaces be removed from this theorem? To answer this question, let us provide an example.

The following theorem addresses a special case of Theorem 3.1 in which $F$ is a polyhedral convex multifunction.

Proof. We can assume that ${\rm gph}\,F$ is given by (2.5) with $Z=\{0\}$, $A_{1}\equiv 0$, $A_{2}\equiv 0$ and $z=0$. Arguing similarly as in the proof of Theorem 3.1, to prove that ${\rm dom}\,F$ is a polyhedral convex set in $X$, we need only to show that $\pi_{X}(W_{0})$ is a closed linear subspace of finite codimension of $X$. In the notation of the proof of Theorem 3.1, observe that $\widetilde{A}_{2}(Y)$ is a linear subspace of the finite dimensional space $\{0\}\times\mathbb{R}^{m}$. Therefore, $\widetilde{A}_{1}^{-1}(\widetilde{A}_{2}(Y))$ is a closed linear subspace of finite codimension in $X$. Thus, from (3.10) it follows that $\pi_{X}(W_{0})$ is a closed linear subspace of finite codimension in $X$.

The fact that ${\rm rge}\,F$ a polyhedral convex set in $Y$ is obtained from the above result by considering the multifunction $F^{-1}$, which is polyhedral convex by the assumption of the theorem, and applying the formula ${\rm rge}\,F={\rm dom}\,F^{-1}$. $\hfill\Box$

As a direct consequence of Theorem 3.4, we now present a property of the projection of a polyhedral convex set in a product space onto each component of the latter.

Proof. Suppose that $P\subset X\times Y$ is a polyhedral convex set. Let $G\colon X\rightrightarrows Y$ be the multifunction defined by

Since ${\rm gph}\,G=P$, we see that $G$ is a polyhedral convex multifunction. As $\pi_{X}(P)={\rm dom}\,G$ and $\pi_{Y}(P)={\rm rge}\,G$, the desired properties follow from Theorem 3.4. $\hfill\Box$

The proposition below gives us a useful result concerning the generalized polyhedral convexity of the function values of a generalized polyhedral convex multifunction.

Proof. We can assume that the graph of $F$ can be given by (2.5). Taking any element $\bar{x}\in X$, we have

This clearly implies that $F(\bar{x})$ is a generalized polyhedral convex set in $Y$. $\hfill\Box$

We now show that the image of a generalized polyhedral convex set under a polyhedral convex multifunction is a polyhedral convex set.

Proof. Without loss of generality, suppose that both sets ${\rm gph}\,F$ and $C$ are nonempty. By the assumptions, we can assume that

and $C=\big{\{}x\in X\;\big{|}\;A(x)=z,\ \langle u^{*}_{j},x\rangle\leq\beta_{j},\ j=1,\ldots,q\big{\}},$ where $x^{*}_{i}\in X^{*},y^{*}_{i}\in Y^{*},\alpha_{i}\in\mathbb{R}$ for $i=1,\ldots,p$, $A\colon X\to Z$ is a continuous linear mapping, $z\in Z$, $u^{*}_{j}\in X^{*},\beta_{j}\in\mathbb{R}$ for $j=1,\ldots,q$. Set $X_{0}={\rm ker}\,A$, $\Omega={\rm gph}\,F\cap(C\times Y)$, and select a point $\bar{x}\in C$. Let

where $x^{*}_{0,i}$ denotes the restriction of $x^{*}_{i}$ to $X_{0}$, $\alpha_{0,i}=\alpha_{i}-\langle x^{*}_{i},\bar{x}\rangle$ for $i=1,\ldots,p$, $u^{*}_{0,j}$ denotes the restriction of $u^{*}_{j}$ to $X_{0}$, and $\beta_{0,j}=\beta_{j}-\langle u^{*}_{j},\bar{x}\rangle$ for $j=1,\ldots,q$. It is easily verified that $\Omega=(\bar{x},0)+\Omega_{0}.$ Since $F(C)=\pi_{Y}(\Omega)$, this implies that

By (3.16), the set $\Omega_{0}$ is polyhedral convex in $X_{0}\times Y$. According to Corollary 3.5, $\pi_{Y}(\Omega_{0})$ is a polyhedral convex set in $Y$. Hence, from (3.17) it follows that $F(C)$ is a polyhedral convex set in $Y$. $\hfill\Box$

The next example shows that both assertions of Proposition 3.7 are false if $F$ is merely a generalized polyhedral convex multifunction.

As a direct consequence of Proposition 3.7, the corollary below addresses the inverse image of a generalized polyhedral convex set under a polyhedral convex multifunction.

Proof. By the assumptions made, $F^{-1}\colon Y\rightrightarrows X$ is a polyhedral convex multifunction and $D$ is a generalized polyhedral convex set in $Y$. Then, by Proposition 3.7 we can assert that $F^{-1}(D)$ is a polyhedral convex set in $X$. $\hfill\Box$

Example 3.8 has demonstrated that the conclusions of Proposition 3.7 do not hold if $F$ is just assumed to be a generalized polyhedral convex multifunction. Nevertheless, when $F$ is a surjective continuous linear mapping between Fréchet spaces (a specific type of generalized polyhedral convex multifunction), we have the following intriguing result. Recall (Rudin_1991, , p. 9) that a locally convex Hausdorff topological vector space is said to be a Fréchet space if its topology $\tau$ is induced by a complete invariant metric $d$.

Proof. We can assume that the polyhedral convex set $D$ is nonempty. Then, according to Theorem 2.2, there exist $u_{1},\ldots,u_{k}\in X$, $v_{1},\ldots,v_{\ell}\in X$, and a closed linear subspace of finite codimension $X_{0}$ in $X$ such that

Thus, by the linearity of $T$ one has

Consider the quotient space $X/{\rm ker}\,T$ and the quotient mapping $\pi\colon X\to X/{\rm ker}\,T$ (see, e.g., (Rudin_1991, , pp. 30-31)) given by

According to (Rudin_1991, , Theorem 1.41(a)), $\pi$ is linear, continuous, and open.

Let the linear mapping $\widetilde{T}\colon X/{\rm ker}\,T\to Y$ be defined by $\widetilde{T}([x])=T(x)$ for $x\in X$. Since $T$ is a surjective continuous linear mapping, $\widetilde{T}$ is a bijective continuous linear mapping. As $X$ is a Fréchet space, by (Rudin_1991, , Theorem 1.41(d)) we know that $X/{\rm ker}\,T$ is also a Fréchet space. So, thanks to Corollary 2.12(b) in Rudin_1991 , ${\widetilde{T}}^{-1}\colon Y\to X/{\rm ker}\,T$ is a continuous linear mapping. Since ${\rm ker}\,T\subset X$ is a closed linear subspace and $X_{0}\subset X$ is a closed linear subspace of finite codimension, by (Luan_Yao_Yen_2018, , Lemma 2.15) we can infer that $X_{0}+{\rm ker}\,T$ is a closed linear subspace of $X$. Then, by the openness of $\pi$, the set $\pi\Big{(}X\setminus\big{(}X_{0}+{\rm ker}\,T\big{)}\Big{)}$ is open in $X/{\rm ker}\,T$. Consequently, the obvious equality

shows that $\pi\big{(}X_{0}+{\rm ker}\,T\big{)}$ is a closed linear subspace of the quotient space. Since

the latter fact implies that $T(X_{0})$ is a closed linear subspace of $Y$. As $\mbox{\rm codim}\,X_{0}<\infty$ and $T$ is a surjective mapping, ${\rm codim}(T(X_{0}))<\infty$. Hence $T(X_{0})\subset Y$ is a closed linear subspace of finite codimension. Therefore, by the representation (3.21) and Theorem 2.2 we can assert that $T(D)$ is a polyhedral convex set in $Y$. $\hfill\Box$

The last theorem of this section establishes the relationship between the closedness under finite-codimensional subspaces and the closed range property of a continuous linear mapping between Fréchet spaces.

Proof. It suffices to prove that if $T(X)$ is closed then $T$ is closed under finite-codimensional subspaces because the converse implication is obvious. Suppose that $X_{0}$ is a finite-codimensional closed linear subspace of $X$. Using Lemma 2.1, we have the representation $X=X_{0}+X_{1}$, where $X_{0}\cap X_{1}=\{0\}$ and $X_{1}$ is a finite-dimensional subspace of $X$. By Theorem 2.2, the linear subspace $X_{0}$ is a polyhedral convex set in $X$. Since $T(X)$ is closed, the continuous linear mapping $T\colon X\rightarrow T(X)$ is surjective between two Fréchet spaces. Thus, it follows from Theorem 3.10 that $T(X_{0})$ is a polyhedral convex set in $T(X)$, so $T(X_{0})$ is closed in $T(X)$. Since $T(X)$ is closed in $Y$, we see that $T(X_{0})$ is closed in $Y$. Therefore, $T$ is closed under finite-codimensional subspaces. $\hfill\Box$

Combining Theorem 3.11 with Theorem 3.1, we get the following result.

In this section, we will examine the generalized polyhedral convex property in relation to basic operations on multifunctions. Our goal is to study the preservation of the generalized polyhedral convexity under sums and compositions of multifunctions. We will also study an important class of extended-real-valued functions known as the optimal value function defined by a polyhedral convex objective function and a polyhedral convex constrained multifunctions.

The theorem below establishes a framework in which the composition of two generalized polyhedral convex multifunctions yields another generalized polyhedral convex multifunction.