Abstract

By using an axiomatic approach we formalize the concept of size index for closed convex cones in the Euclidean space Rn\mathbb{R}^n. We review a dozen of size indices disseminated through the literature, commenting on the advantages and disadvantages of each choice.

Author information

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

Keywords

  • Convex cone
  • ellipsoidal cone
  • solid angle
  • maximal angle
  • ball-truncated volume
  • canonical volume
  • Gaussian width
  • statistical dimension

Mathematics Subject Classification

28A75, 51M25, 52A20, 52A40

References

  1. D. Amelunxen, M. Lotz, M. B. McCoy, J. A. Tropp: Living on the edge: Phase transitions in convex programs with random data, Inf. Inference 3 (2015) 224–294.https://doi.org/10.1093/imaiai/iau005Google Scholar
  2. A. Belloni, R. M. Freund: A geometric analysis of Renegar’s condition number, and its interplay with conic curvature, Math. Program. 119 (2009) 95–107.https://doi.org/10.1007/s10107-007-0203-8Google Scholar
  3. G. C. Calafiore: Approximation of n-dimensional data using spherical and ellipsoidal primitives, IEEE Trans. Syst., Man., Cybern. 32 (2002) 269–278.https://doi.org/10.1109/TSMCA.2002.1021114Google Scholar
  4. V. Chandrasekaran, B. Recht, P. A. Parrilo, A. S. Willsky: The convex geometry of linear inverse problems, Found. Comput. Math. 12 (2012) 805–849.https://doi.org/10.1007/s10208-012-9135-7Google Scholar
  5. F. H. Clarke, Y. S. Ledyaev, R. J. Stern: Complements, approximations, smoothings and invariance properties, J. Convex Analysis 4 (1997) 189–219.https://doi.org/10.68381/jca04010Google Scholar
  6. F. H. Clarke, Y. S. Ledyaev, R. J. Stern: Invariance, monotonicity, and applications, in: Nonlinear Analysis, Differential Equations and Control, F. H. Clarke et al. (ed.), NATO ASI Ser., Ser. C, Math. Phys. Sci. 528, Kluwer, Dordrecht (1999) 207–305.https://doi.org/10.1007/978-94-011-4560-2_4Google Scholar
  7. M. Epelman, R. M. Freund: A new condition measure, preconditioners, and relations between different measures of conditioning for conic linear systems, SIAM J. Optim. 12 (2002) 627–655.https://doi.org/10.1137/S1052623400373829Google Scholar
  8. D. D. Fisher: Minimum ellipsoids, Math. Comp. 18 (1964) 669–673.https://doi.org/10.1090/S0025-5718-1964-0166905-0Google Scholar
  9. R. M. Freund: On the primal-dual geometry of level sets in linear and conic optimization, SIAM J. Optim. 13 (2003) 1004–1013.https://doi.org/10.1137/S1052623401393645Google Scholar
  10. R. M. Freund, J. R. Vera: Condition-based complexity of convex optimization in conic linear form via the ellipsoid algorithm, SIAM J. Optim. 10 (1999) 155–176.https://doi.org/10.1137/S105262349732829XGoogle Scholar
  11. D. Gourion, A. Seeger: Deterministic and stochastic methods for computing volumetric moduli of convex cones, Comput. Appl. Math. 29 (2010) 215–246.https://doi.org/10.1590/S1807-03022010000200007Google Scholar
  12. D. Gourion, A. Seeger: Solidity indices for convex cones, Positivity 16 (2012) 685–705.https://doi.org/10.1007/s11117-011-0140-xGoogle Scholar
  13. O. Güler: Barrier functions in interior point methods, Math. Oper. Res. 21 (1996) 860–885.https://doi.org/10.1287/moor.21.4.860Google Scholar
  14. R. Henrion, A. Seeger: On properties of different notions of centers for convex cones, Set-Valued Var. Anal. 18 (2010) 205–231.https://doi.org/10.1007/s11228-009-0131-2Google Scholar
  15. R. Henrion, A. Seeger: Inradius and circumradius of various convex cones arising in applications, Set-Valued Var. Anal. 18 (2010) 483–511.https://doi.org/10.1007/s11228-010-0150-zGoogle Scholar
  16. A. Iusem, A. Seeger: Pointedness, connectedness, and convergence results in the space of closed convex cones, J. Convex Analysis 11 (2004) 267–284.https://doi.org/10.68381/jca11018Google Scholar
  17. A. Iusem, A. Seeger: Axiomatization of the index of pointedness for closed convex cones, Comput. Appl. Math. 24 (2005) 245–283.https://doi.org/10.1590/S0101-82052005000200006Google Scholar
  18. A. Iusem, A. Seeger: On pairs of vectors achieving the maximal angle of a convex cone, Math. Program. 104 (2005) 501–523.https://doi.org/10.1007/s10107-005-0626-zGoogle Scholar
  19. A. Iusem, A. Seeger: Measuring the degree of pointedness of a closed convex cone: a metric approach, Math. Nachr. 279 (2006) 599–618.https://doi.org/10.1002/mana.200310380Google Scholar
  20. A. Iusem, A. Seeger: Antipodal pairs, critical pairs, and Nash angular equilibria in convex cones, Optim. Methods Softw. 23 (2008) 73–93.https://doi.org/10.1080/10556780701661427Google Scholar
  21. A. Iusem, A. Seeger: Angular analysis of two classes of non-polyhedral convex cones: the point of view of optimization theory, Comput. Appl. Math. 26 (2007) 191–214.https://doi.org/10.1590/S0101-82052007000200002Google Scholar
  22. A. Iusem, A. Seeger: Antipodality in convex cones and distance to unpointedness, Appl. Math. Lett. 21 (2008) 1018–1023.https://doi.org/10.1016/j.aml.2007.10.018Google Scholar
  23. A. Iusem, A. Seeger: Normality and modulability indices. Part I: Convex cones in normed spaces, J. Math. Anal. Appl. 338 (2008) 365–391.https://doi.org/10.1016/j.jmaa.2007.05.030Google Scholar
  24. M. B. McCoy, J. A. Tropp: From Steiner formulas for cones to concentration of intrinsic volumes, Discrete Comput. Geom. 51 (2014) 926–963.https://doi.org/10.1007/s00454-014-9595-4Google Scholar
  25. J. J. Moreau: Décomposition orthogonale d’un espace hilbertien selon deux cônes mutuellement polaires, C. R. Acad. Sci., Paris 255 (1962) 238–240.Google Scholar
  26. J. Peña, J. Renegar:. Computing approximate solutions for convex conic systems of constraints, Math. Program. 87 (2000) 351–383.https://doi.org/10.1007/s101070050001Google Scholar
  27. J. Ribando: Measuring solid angles beyond dimension three, Discrete Comput. Geom. 36 (2006) 479–487.https://doi.org/10.1007/s00454-006-1253-4Google Scholar
  28. A. Seeger: Epigraphical cones I, J. Convex Analysis 18 (2011) 1171–1196.https://doi.org/10.68381/jca18070Google Scholar
  29. A. Seeger: Epigraphical cones II, J. Convex Analysis 19 (2012) 1–21.https://doi.org/10.68381/jca19001Google Scholar
  30. A. Seeger: Lipschitz and Hölder continuity results for some functions of cones, Positivity 18 (2014) 505–517.https://doi.org/10.1007/s11117-013-0258-0Google Scholar
  31. A. Seeger, M. Torki: Centers and partial volumes of convex cones. I. Basic theory, Beitr. Algebra Geom. 56 (2015) 227–248.https://doi.org/10.1007/s13366-014-0220-8Google Scholar
  32. A. Seeger, M. Torki: Centers and partial volumes of convex cones. II. Advanced topics, Beitr. Algebra Geom. 56 (2015) 491–514.https://doi.org/10.1007/s13366-014-0221-7Google Scholar
  33. A. Seeger, M. Torki: Conic version of Loewner-John ellipsoid theorem, Math. Program. 155 (2016) 403–433.https://doi.org/10.1007/s10107-014-0852-3Google Scholar
  34. C. E. Shannon: Probability of error for optimal codes in a Gaussian channel, Bell Syst. Tech. J. 38 (1959) 611–656.https://doi.org/10.1002/j.1538-7305.1959.tb03905.xGoogle Scholar
  35. R. Stern, H. Wolkowicz: Invariant ellipsoidal cones, Linear Algebra Appl. 150 (1991) 81–106.https://doi.org/10.1016/0024-3795(91)90161-OGoogle Scholar
  36. J. A. Tropp: Convex recovery of a structured signal from independent random linear measurements, in: Sampling Theory, a Renaissance, G. E. Pfander (ed.), Springer, Berlin (2015) 67–101.https://doi.org/10.1007/978-3-319-19749-4_2Google Scholar
  37. D. W. Walkup, R. J.-B. Wets: Continuity of some convex-cone-valued mappings, Proc. Amer. Math. Soc. 18 (1967) 229–235.https://doi.org/10.1090/S0002-9939-1967-0209806-6Google Scholar
  38. M. J. Weber, H. P. Schröcker: Davis’ convexity theorem and extremal ellipsoids, Beitr. Algebra Geom. 51 (2010) 263–274.Google Scholar

Suggested citation

A. Seeger. “On Measures of Size for Convex Cones.” Journal of Convex Analysis 23 (2016), No. 4, 947–980. https://doi.org/10.68381/jca23036

Download BibTeXPublished by Heldermann Verlag.

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