5
$\begingroup$

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:

  1. A multifunction is simply a set-valued map.
  2. 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)$.
  3. A multifunction is said to be polyhedral if its graph is a polyhedral subset of $R^{n + m}$.

Referenecs:

  1. [FP-1] F. Facchinei and J-S Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems (vol. 1), pp. 138-139.
  2. [HP-1] S. Hu and N.S. Papageorgiou, Handbook of Multivalued Analysis (vol. 1), p. 36 and p. 89.
  3. [M-1] Ernest Michael, Continuous Selections I, The Annals of Mathematics, Vol. 63, (1956), pp. 361-382.
  4. [M-2] Ernest Michael, Continuous Selections II, The Annals of Mathematics, Vol. 64, (1956), pp. 562-580.
  5. [M-2] Ernest Michael, Continuous Selections III, The Annals of Mathematics, Vol. 65, (1957), pp. 375-390.
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Not quite sure why this got a downvote... $\endgroup$
    – Yemon Choi
    Apr 22, 2010 at 21:57
  • 2
    $\begingroup$ Maybe I misunderstood the definitions, but isn't the multi-function which is 0 on $(-\infty,0]$ and 1 on $[1,+\infty)$ a counter-example? (Hopefully the description is clear - it's hard to write formulae with sets here.) $\endgroup$
    – Sergei Ivanov
    Apr 22, 2010 at 22:12
  • $\begingroup$ Unless you made a typo in your example ($[1,+\infty)$ should be $[0,+\infty)$?), it seems to me that it is already Lipschitz continuous. $\endgroup$
    – innerproduct
    Apr 23, 2010 at 1:02
  • 1
    $\begingroup$ Yes, sorry, it meant to be 1 on $[0,+\infty)$. $\endgroup$
    – Sergei Ivanov
    Apr 23, 2010 at 5:35
  • 2
    $\begingroup$ We can even make our graph connected by taking F(x) = {0} for x<0, F(0) = [0,1], and F(x) = {1} for x>0. It illustrates why upper semicontinuity is not the right property to insure continuous selection. $\endgroup$
    – Gerald Edgar
    Jun 15, 2010 at 15:03

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.