Abstract

This paper studies global and local behavior of graph-convex set-valued mappings in finite-dimensional vector spaces. This is done in terms of recession mappings and graphical derivatives which are set-valued mappings whose graphs are convex cones. The main results are chain rules for computing the recession mapping and the graphical derivative of a composition of two set-valued mappings. The results on graph-convex mappings are applied to K-convex functions which are vector-valued generalizations of extended-real-valued proper convex functions. Many generalizations of classical results in convex analysis are obtained, along with a generalization of subdifferential calculus, in which the differential behavior of a function is described by a sublinear mapping that resembles the classical Jacobian. A particular advantage of this approach is that it leads to simple chain rules for compositions of vector-valued convex functions. The generality is reflected in the fact that most of the classical rules for computing recession functions and subdifferentials are obtained as special cases of the given chain rules. Some applications to mathematical programming and matrix analysis are given

Author information

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

Teemu Pennanen

Dept. of Mathematics, University of Washington, Seattle, WA 98195-4350, U.S.A.

References

  1. J.-P. Aubin, I. Ekeland: Applied Nonlinear Analysis, John Wiley & Sons, 1984.Google Scholar
  2. J.-P. Aubin, H. Frankowska: Set-Valued Analysis, Birkhäuser, 1990.Google Scholar
  3. J. M. Borwein: Multivalued convexity and optimization: A unified approach to inequality and equality constraints, Math. Programming 13 (1977) 183-199.https://doi.org/10.1007/BF01584336Google Scholar
  4. J. M. Borwein: Automatic continuity and openness of convex relations, Proc. Amer. Math. Soc. 99(1) (1987) 49-55.https://doi.org/10.1090/S0002-9939-1987-0866428-4Google Scholar
  5. J. M. Borwein: Super efficiency in vector optimization, Trans. Amer. Math. Soc. 338(1) (1993) 105-122.https://doi.org/10.1090/S0002-9947-1993-1098432-5Google Scholar
  6. C. Davis: All convex invariant functions of Hermitian matrices, Archiv der Mathematik 8 (1957) 276-278.https://doi.org/10.1007/BF01898787Google Scholar
  7. S. Friedland: Inverse eigenvalue problems, Linear Algebra Appl. 17 (1977) 15-51.https://doi.org/10.1016/0024-3795(77)90039-8Google Scholar
  8. S. Friedland: Convex spectral functions, Linear and Multilinear Algebra 9 (1981) 299-316.https://doi.org/10.1080/03081088108817381Google Scholar
  9. G. H. Golub, C. F. Van Loan: Matrix Computations, John Hopkins Univ. Press, Baltimore, 1983.Google Scholar
  10. J.-B. Hiriart-Urruty, M. Moussaoui, A. Seeger, M. Volle: Subdifferential calculus without qualification conditions, using approximate subdifferentials: a survey, Nonlinear Analysis 24(12) (1995) 1727-1754.https://doi.org/10.1016/0362-546X(94)00221-3Google Scholar
  11. J.-B. Hiriart-Urruty, D. Ye: Sensitivity analysis of all eigenvalues of a symmetric matrix, Numer. Math. 70 (1995) 45-72.https://doi.org/10.1007/s002110050109Google Scholar
  12. R. A. Horn, C. R. Johnson: Matrix Analysis, Cambridge University Press, Cambridge, 1985.https://doi.org/10.1017/CBO9780511810817Google Scholar
  13. R. A. Horn, C. R. Johnson: Topics in Matrix Analysis, Cambridge University Press, Cambridge, 1991.https://doi.org/10.1017/CBO9780511840371Google Scholar
  14. S. S. Kutateladze: Convex operators, Russian Math. Surveys 34(1) (1979) 181-214.https://doi.org/10.1070/RM1979v034n01ABEH002874Google Scholar
  15. V. L. Levin: Subdifferentials of convex mappings and composite functions, Siberian Math. J. 13 (1972) 903-909.https://doi.org/10.1007/BF00971866Google Scholar
  16. A. S. Lewis: The convex analysis of unitarily invariant matrix functions, J. Convex Analysis 2(1) (1995) 173-183.https://doi.org/10.68381/jca02012Google Scholar
  17. A. S. Lewis: Convex analysis on the Hermitian matrices, SIAM J. Optim. 6 (1996) 164-177.https://doi.org/10.1137/0806009Google Scholar
  18. A. S. Lewis: Group invariance and convex matrix analysis, SIAM J. Matrix Anal. Appl. 17(4) (1996) 927-949.https://doi.org/10.1137/S0895479895283173Google Scholar
  19. A. W. Marshall, I. Olkin: Inequalities: Theory of Majorization and its Applications, Academic Press, New York, 1979.Google Scholar
  20. B. S. Mordukhovich: Metric approximations and necessary conditions for general classes of nonsmooth extremal problems, Soviet Math. Dokl. 22(2) (1980) 526-530.Google Scholar
  21. B. S. Mordukhovich: Generalized differential calculus for nonsmooth and set-valued mappings, J. Math. Anal. Appl. 183 (1994) 250-288.https://doi.org/10.1006/jmaa.1994.1144Google Scholar
  22. B. S. Mordukhovich, Y. Shao: Nonconvex differential calculus for infinite-dimensional multifunctions, Set-Valued Anal. 4(3) (1996) 205-236.https://doi.org/10.1007/BF00419366Google Scholar
  23. M. L. Overton: Large-scale optimization of eigenvalues, SIAM J. Optim. 2(1) (1992) 88-120.https://doi.org/10.1137/0802007Google Scholar
  24. K. L. Overton, R. S. Womersley: Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrix, Math. Programming 62 (1993) 321-357.https://doi.org/10.1007/BF01585173Google Scholar
  25. T. Pennanen: Dualization of generalized equations of maximal monotone type, to appear in SIAM J. Optim.Google Scholar
  26. T. Pennanen, J. Eckstein: Generalized Jacobians of vector-valued convex functions, Rutcor Research Reports (1997) 6-97.Google Scholar
  27. S. M. Robinson: Regularity and stability for convex multivalued functions, Math. Oper. Res. 1(2) (1976) 130-143.https://doi.org/10.1287/moor.1.2.130Google Scholar
  28. R. T. Rockafellar: A Monotone convex analogue of linear algebra, In: W. Fenchel (ed.): Proceedings of the Colloquium on Convexity, Copenhagen (1965) 261-276.Google Scholar
  29. R. T. Rockafellar: Convex Analysis, Princeton University Press, 1970.https://doi.org/10.1515/9781400873173Google Scholar
  30. R. T. Rockafellar: Conjugate Duality and Optimization, SIAM, 1974.https://doi.org/10.1137/1.9781611970524Google Scholar
  31. R. T. Rockafellar, R. J-B Wets: Variational Analysis, Springer-Verlag, 1998.https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  32. A. Seeger: Convex analysis of spectrally defined matrix functions, SIAM J. Optim. 7(3) (1997) 679-696.https://doi.org/10.1137/S1052623495288866Google Scholar
  33. A. Shapiro: First and second order analysis of nonlinear semidefinite programs, Math. Programming 77 (1997) 301-320.https://doi.org/10.1007/BF02614439Google Scholar
  34. L. I. Trudzik: Continuity properties of vector-valued convex functions, J. Austral. Math. Soc. (Series A) 36(3) (1984) 404-415.https://doi.org/10.1017/S1446788700025453Google Scholar
  35. L. Vandenberghe, S. Boyd: Semidefinite programming, SIAM Review 38(1) (1996) 49-95.https://doi.org/10.1137/1038003Google Scholar

Suggested citation

T. Pennanen. “Graph-Convex Mappings and K-Convex Functions.” Journal of Convex Analysis 6 (1999), No. 2, 235–266. https://doi.org/10.68381/jca06015

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 1999. Rights now held by Banach Press.