Do upper-semicontinuous polyhedral multifunctions have Lipschitz continuous selections?

2010-04-22T21:48:09Z

We are interested in the following question (definitions and references are given below):

Main Question: Given an upper-semicontinuous polyhedral multifunction $F:R^n \rightarrow R^m$, is there always a Lipschitz continuous function $g:R^n \rightarrow R^m$ such that $g(x) \in F(x)$ for all $x \in R^n$ ?

In general, upper semicontinuity is probably not the right property to guarantee continuous selections (see [HP-1], page 89). On the other hand, polyhedrality of the multifunction may help.

Related Question: Under what mild conditions is a positive answer to the above question guaranteed?

Motivation: Solutions of finite-dimensional variational inequalities (VI) or complementarity problems (CP) (see [FP-1]) typically have upper semicontinuous solution maps. Furthermore, if the functions and sets defining the VI or CP have affine or linear (or polyhedral) structure, their solution maps are polyhedral multifunctions. The main question posed above is then a natural question to ask in the study of differential inclusions $\dot{x} \in G(x)$ that have these solution maps appearing in the definition of $G(x)$.

Definitions:

A multifunction is simply a set-valued map.
A multifunction $F:R^n \rightarrow R^m$ is said to be upper semicontinuous at a point $\bar{x}$ if for every open set $\mathcal{V}$ containing $F(\bar{x})$, there exists an open neighbourhood $\mathcal{U}$ of $\bar{x}$ such that, for each $x \in \mathcal{U}$, $\mathcal{V}$ contains $F(x)$.
A multifunction is said to be polyhedral if its graph is a polyhedral subset of $R^{n + m}$.

Referenecs:

[FP-1] F. Facchinei and J-S Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems (vol. 1), pp. 138-139.
[HP-1] S. Hu and N.S. Papageorgiou, Handbook of Multivalued Analysis (vol. 1), p. 36 and p. 89.
[M-1] Ernest Michael, Continuous Selections I, The Annals of Mathematics, Vol. 63, (1956), pp. 361-382.
[M-2] Ernest Michael, Continuous Selections II, The Annals of Mathematics, Vol. 64, (1956), pp. 562-580.
[M-2] Ernest Michael, Continuous Selections III, The Annals of Mathematics, Vol. 65, (1957), pp. 375-390.

Answer by CH Jeffrey Pang for Do upper-semicontinuous polyhedral multifunctions have Lipschitz continuous selections?

2010-06-15T14:47:59Z

Hi,

I happen to be working on semi-algebraic set-valued maps, and I might have a partial answer in [1]. I guess when you say polyhedral, you mean that the graph of the set-valued map is a union of finitely many polyhedrons. If that is the case, polyhedral set-valued maps are semi-algebraic. Semi-algebraic set-valued maps are strictly continuous (A generalization of Lipschitz continuity for set-valued maps: See [1]) except on a set of smaller dimension. I hope this means that there is a selection that is Lipschitz except on a set of smaller dimension.

[1] A. Daniilidis and C.H.J. Pang, Continuity and Differentiability of set-valued maps revisited in the light of tame geometry. http://arxiv.org/abs/0905.0373

[2] R.T. Rockafellar and R.J.-B. Wets, Variational Analysis.

Do upper-semicontinuous polyhedral multifunctions have Lipschitz continuous selections? - MathOverflow

Do upper-semicontinuous polyhedral multifunctions have Lipschitz continuous selections?

Answer by CH Jeffrey Pang for Do upper-semicontinuous polyhedral multifunctions have Lipschitz continuous selections?