A class of ``onto'' multifunctions
type: Item
instance of: scholarly article
title: A class of ``onto'' multifunctions
zbMATH Open document ID: 0808.90104
DOI: 10.1007/BF01582154
author: B. Curtis Eaves
author: Uriel G. Rothblum
published in: Mathematical Programming. Series A. Series B
publication date: 1995-03-15T00:00:00Z
review text: The authors generalize the following classical theorem: ``If \(C\) is a compact convex set in \(\mathbb{R}^ n\) and \(f: C\to \mathbb{R}^ n\) is a continuous function that coincides with the identity on the boundary of \(C\), then \(C\subseteq f(C):= \{f(x): x\in C\}\).'' Their generalization allows noncompact sets \(C\), multivalued functions \(f\), and rather general boundary behaviour, but retains the key conclusion, namely, \[ C\subseteq f(C):=\bigcup \{f(x): x\in C\}.\tag{1} \] For any convex subset \(C\) of \(\mathbb{R}^ n\), one may define a multifunction \(\sigma: C\to C\) by taking \(\sigma(x)\) as the smallest face of \(C\) containing \(x\), and call a vector \(c\) in \(\mathbb{R}^ n\) a coercive direction for \(C\) if the set of \(x\) in \(C\) minimizing \(c^ T x\) is nonempty and bounded. Main Theorem: Let \(C\) be a nonempty closed and pointed convex subset of \(\mathbb{R}^ n\). Let \(f: C\to \mathbb{R}^ n\) be a set-valued mapping with nonempty convex values. Assume that \(f\) is upper continuous, in the sense that \(\limsup_{y\to x} f(y)\subseteq f(x)\) for every \(x\) in \(C\). Then a sufficient condition for (1) is that there exist a selection \(s(x)\in f(x)\) for all \(x\in C\) and a coercive direction \(c\) for \(C\) such that (a) \(s(x)\) lies in the affine hull of \(\sigma(x)\) for each \(x\) in \(C\); (b) if \(\| s(x_ k)\|\to\infty\) for some sequence \(\{x_ k\}\) in \(C\), then \(\| x_ k\|\to\infty\); (c) if \(\| x_ k\|\to\infty\) for some sequence \(\{x_ k\}\) in \(C\), then \(c^ T s(x_ k)\to+\infty\). The authors draw a number of interesting corollaries from their main result, including the classical theorem quoted above. They take care to show by example that none of their hypotheses can be discarded, and present a detailed analysis of their theorem's application to the ``congestion attainability problem''. In this problem, a ``Kelly network'' of queues with \(p\) single-server stations and clients divided into \(n\) classes is allowed to c…
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 26E25
Mathematics Subject Classification ID: 90B22
Mathematics Subject Classification ID: 54C60
Mathematics Subject Classification ID: 49J52
zbMATH DE Number: 513285
zbMATH Keywords: multifunction
zbMATH Keywords: homotopy
reviewed by: P. D. Loewen
MaRDI profile type: Publication
cites work: An extension of a theorem of Darroch and Ratcliff in loglinear models and its application to scaling multidimensional matrices
cites work: Q4112523
cites work: A course in triangulations for solving equations with deformations
cites work: Exponential lower bounds for finding Brouwer fixed points
cites work: Rudiments of an average case complexity theory for piecewise-linear path following algorithms
cites work: Convex Analysis
full work available at URL: https://doi.org/10.1007/bf01582154
OpenAlex ID: W1968772202
description: scientific article; zbMATH DE number 513285