Abstract

Piecewise polyhedral multifunctions are the set-valued version of piecewise affine functions. We investigate selections of such multifunctions, in particular, the least norm selection and continuous extremal point selections. A special class of piecewise polyhedral multifunctions is the collection of metric projections from the n-dimensional euclidean space endowed with a polyhedral norm to a polyhedral subset K. As a consequence, the two types of selections are piecewise affine selections. Moreover, if we consider the euclidean setting endowed with the 1-norm, then the metric projection has a piecewise affine and quasi-linear extremal point selection when K is a subspace; and if we take the maximum norm then the strict best approximation is a piecewise affine selection for the metric projection onto the polyhedral subset K

Author information

Contact details are reproduced from the original publication and may be historical.

M. Finzel

Mathematisches Institut, Universität Erlangen-Nürnberg, Bismarckstr. 1 1/2, 91054 Erlangen, Germany

W. Li

Dept. of Mathematics and Statistics, Old Dominion University, Norfolk, VA 23529-0077, U.S.A.

References

  1. M. Chen, E. Kuh: Solving piecewise linear equations for resistive networks, Circuit Theory Appl. 3 (1976) 3-24.https://doi.org/10.1002/cta.4490040102Google Scholar
  2. F. Deutsch: A survey of metric selections, in: Fixed Points and Nonexpansive Mappings, ed. by R. C. Sine, Contemporary Mathematics 18 (1983) 49-71.https://doi.org/10.1090/conm/018/728593Google Scholar
  3. F. Deutsch: Linear selections for the metric projection, J. Funct. Anal. 49 (1982) 269-292.https://doi.org/10.1016/0022-1236(82)90070-2Google Scholar
  4. F. Deutsch: A survey of metric selections, in: Approximation Theory, Spline Functions and Applications, ed. by S. P. Singh, Kluwer Academic Publishers (1992) 123-137.https://doi.org/10.1007/978-94-011-2634-2_6Google Scholar
  5. B. Eaves, U. Rothblum: Relationships of properties of piecewise affine maps over ordered fields, Linear Alg. Appl. 55 (1990) 1-63.https://doi.org/10.1016/0024-3795(90)90052-EGoogle Scholar
  6. B. Eaves, H. Scarf: The solution of systems of piecewise linear equations, Math. Oper. Res. 1 (1976) 1-27.https://doi.org/10.1287/moor.1.1.1Google Scholar
  7. F. S. Garnir-Monjoie: Selections continues de multifonctions, Bull. Soc. Roy. Sci. Liege 46 (1977) 51-56.Google Scholar
  8. M. Gowda, M. Sznajder: Nondegeneracy concepts for zeros of piecewise smooth functions, Math. Oper. Res. 23 (1998) 221-238.https://doi.org/10.1287/moor.23.1.221Google Scholar
  9. M. Gowda, M. Sznajder: On the pseudo-Lipschitzian behavior of the inverse of a piecewise affine function, Math. Programming 74, Ser. A (1996) 267-278.https://doi.org/10.1007/BF02592199Google Scholar
  10. J. Guddat, H. Hollatz, F. Nozicka: Theorie der linearen parametrischen Optimierung, Akademie-Verlag, Berlin, 1994.Google Scholar
  11. A. J. Hoffman: Approximate solutions of systems of linear inequalities, J. Res. Nat. Bur. Standards 49 (1952) 263-265.https://doi.org/10.6028/jres.049.027Google Scholar
  12. K. Kuratowski: Introduction to Set Theory and Topology, Pergamon Press, New York, 1972.https://doi.org/10.1016/B978-0-08-016160-0.50005-1Google Scholar
  13. W. Li: A. J. Hoffman's theorem and metric projections in polyhedral spaces, J. Approx. Theory 75 (1993) 107-111.https://doi.org/10.1006/jath.1993.1090Google Scholar
  14. W. Li: The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program, Linear Alg. Appl. 187 (1993) 15-40.https://doi.org/10.1016/0024-3795(93)90125-8Google Scholar
  15. O. L. Mangasarian: Normal solutions of linear programs, Math. Programming Study 22 (1984) 206-216.https://doi.org/10.1007/BFb0121017Google Scholar
  16. O. L. Mangasarian, T. H. Shiau: Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems, SIAM J. Control Optim. 25 (1987) 583-595.https://doi.org/10.1137/0325033Google Scholar
  17. E. Michael: Continuous selections I, Annals of Math. 63 (1956) 361-382.https://doi.org/10.2307/1969615Google Scholar
  18. G. Nürnberger: Schnitte für die metrische Projektion, J. Approx. Theory 20 (1977) 196-219.https://doi.org/10.1016/0021-9045(77)90075-2Google Scholar
  19. T. Ohtsuki, T. Fujisawa, S. Kumagai: Existence theorems and a solution algorithm for piecewise linear resistive networks, SIAM J. Math. Anal. 8 (1977) 69-99.https://doi.org/10.1137/0508005Google Scholar
  20. J. R. Rice: Tchebycheff approximation in a compact metric space, Bull. Amer. Math. Soc. 68 (1962) 405-410.https://doi.org/10.1090/S0002-9904-1962-10822-2Google Scholar
  21. C. T. Rockafellar: Convex Analysis, Princeton University Press, 1970.https://doi.org/10.1515/9781400873173Google Scholar
  22. S. Scholtes: Introduction to piecewise differentiable equations, Preprint 53/1994, Institute für Statistik und Mathematische Wirtschaftstheorie, Universität Karlsruhe, Germany, May, 1994.Google Scholar
  23. J. Sun: On the structure of piecewise quadratic functions, J. Optim. Theory Appl. 72 (1992) 499-510.https://doi.org/10.1007/BF00939839Google Scholar
  24. J. Sun: On piecewise quadratic Newton and trust region problems, Math. Programming 76, Ser. B (1997) 451-467.https://doi.org/10.1007/BF02614393Google Scholar
  25. D. Walkup, R. J-B Wets: A Lipschitzian characterization of convex polyhedra, Proc. Amer. Math. Soc. 23 (1969) 167-173.https://doi.org/10.1090/S0002-9939-1969-0246200-8Google Scholar

Suggested citation

M. Finzel, W. Li. “Piecewise Affine Selections for Piecewise Polyhedral Multifunctions and Metric Projections.” Journal of Convex Analysis 7 (2000), No. 1, 73–94. https://doi.org/10.68381/jca07004

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2000. Rights now held by Banach Press LLC.