Do upper-semicontinuous polyhedral multifunctions have Lipschitz continuous selections? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T12:33:24Z http://mathoverflow.net/feeds/question/22263 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/22263/do-upper-semicontinuous-polyhedral-multifunctions-have-lipschitz-continuous-selec Do upper-semicontinuous polyhedral multifunctions have Lipschitz continuous selections? innerproduct 2010-04-22T21:48:09Z 2010-07-27T16:22:18Z <p>We are interested in the following question (definitions and references are given below):</p> <p>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$ ?</p> <p>In general, <i>upper</i> 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.</p> <p>Related Question: Under what <i>mild</i> conditions is a positive answer to the above question guaranteed?</p> <p>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)$.</p> <p>Definitions:</p> <ol> <li>A <i>multifunction</i> is simply a <i>set-valued</i> map.</li> <li>A multifunction $F:R^n \rightarrow R^m$ is said to be <i>upper semicontinuous</i> 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)$.</li> <li>A multifunction is said to be <i>polyhedral</i> if its graph is a polyhedral subset of $R^{n + m}$.</li> </ol> <p>Referenecs:</p> <ol> <li>[FP-1] F. Facchinei and J-S Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems (vol. 1), pp. 138-139.</li> <li>[HP-1] S. Hu and N.S. Papageorgiou, Handbook of Multivalued Analysis (vol. 1), p. 36 and p. 89.</li> <li>[M-1] Ernest Michael, Continuous Selections I, The Annals of Mathematics, Vol. 63, (1956), pp. 361-382.</li> <li>[M-2] Ernest Michael, Continuous Selections II, The Annals of Mathematics, Vol. 64, (1956), pp. 562-580.</li> <li>[M-2] Ernest Michael, Continuous Selections III, The Annals of Mathematics, Vol. 65, (1957), pp. 375-390.</li> </ol> http://mathoverflow.net/questions/22263/do-upper-semicontinuous-polyhedral-multifunctions-have-lipschitz-continuous-selec/28258#28258 Answer by CH Jeffrey Pang for Do upper-semicontinuous polyhedral multifunctions have Lipschitz continuous selections? CH Jeffrey Pang 2010-06-15T14:47:59Z 2010-06-15T15:13:28Z <p>Hi,</p> <p>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. </p> <p>[1] A. Daniilidis and C.H.J. Pang, Continuity and Differentiability of set-valued maps revisited in the light of tame geometry. <a href="http://arxiv.org/abs/0905.0373" rel="nofollow">http://arxiv.org/abs/0905.0373</a></p> <p>[2] R.T. Rockafellar and R.J.-B. Wets, Variational Analysis.</p>