×

Piecewise affine selections for piecewise polyhedral multifunctions and metric projections. (English) Zbl 0996.90072

Authors’ summary: Piecewise polyhedral multifunctions are the set-valued version of piecewise affine functions. We investigate selections of piecewise polyhedral multifunctions, the least norm selection and continuous extremal point selections. A special class of piecewise polyhedral multifunctions is the collection of metric projections \(\Pi _{K,P}\) from \({\mathbb R}^{n}\) (endowed with a polyhedral norm \(\left\|\cdot\right\|_{P}\)) to a polyhedral subset \(K\) of \({\mathbb R}^{n}.\) As a consequence, the two types of selections are piecewise affine selections for \(\Pi _{K,P}.\) Moreover, if \(\Pi _{K,\infty}\) and \(\Pi _{K,1}\) are the metric projection onto \(K\) in \({\mathbb R}^{n}\) endowed with the \(\ell_{\infty}\)-norm and the \(\ell_{1}\)-norm, respectively, we prove that \(\Pi _{K,1}\) has a piecewise affine and quasi-linear extremal point selection when \(K\) is a subspace, and that the strict best approximation sba\(_{K}(x)\) of \(x\) in \(K\) is a piecewise affine selection for \(\Pi _{K,\infty}.\)

MSC:

90C31 Sensitivity, stability, parametric optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
52B99 Polytopes and polyhedra
54C65 Selections in general topology