Abstract
We introduce and study decompositions of finite sets as well as coverings of their convex hulls, and use these objects to develop various estimates of and formulas for the “hull-volume” of the sets (i.e., the volume of their convex hull). We apply our results to the convergence analysis of the “iterate-sets” associated with each iteration of a reduce-or-retreat optimization method (including pattern-search methods like Nelder–Mead as well as model-based methods).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Levy, A.B.: Descent and convergence in reduce-or-retreat optimization methods. Preprint (2011)
McKinnon, K.I.M.: Convergence of the Nelder–Mead simplex method to a nonstationary point. SIAM J. Optim. 9, 148–158 (1998)
Grünbaum, B.: Convex Polytopes. Wiley, New York (1967)
Ziegler, G.M.: Lectures on Polytopes. Springer, New York (1995)
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Thomas, R.: Lectures in Geometric Combinatorics. The American Mathematical Society, Providence (2006)
Lagarias, J.C., Reeds, J.A., Wright, M.H., Wright, P.E.: Convergence properties of the Nelder–Mead simplex method in low dimensions. SIAM J. Optim. 9, 112–147 (1998)
Martini, H.: A new view on some characterizations of simplices. Arch. Math. 55, 389–393 (1990)
Lee, C.W.: Regular Triangulations of Convex Polytopes. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, pp. 443–456. Am. Math. Soc., Providence (1991)
Lawrence, J.: Polytope volume computation. Math. Comput. 57, 259–271 (1991)
Allgower, E.L., Schmidt, P.H.: Computing volumes of polyhedra. Math. Comput. 46, 171–174 (1986)
Lasserre, J.B.: An analytical expression and an algorithm for the volume of a convex polyhedron in ℝn. J. Optim. Theory Appl. 39, 363–377 (1983)
Cohen, J., Hickey, T.: Two algorithms for determining volumes of convex polyhedra. J. Assoc. Comput. Mach. 26, 401–414 (1979)
von Hohenbalken, B.: Finding simplicial subdivisions of polytopes. Math. Program. 21, 233–234 (1981)
Scheinberg, K., Toint, Ph.L.: Self-correcting geometry in model-based algorithms for derivative-free unconstrained optimization. SIAM J. Optim. 20, 3512–3532 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Horst Martini.
Rights and permissions
About this article
Cite this article
Levy, A.B. Hull-Volume with Applications to Convergence Analysis. J Optim Theory Appl 153, 633–649 (2012). https://doi.org/10.1007/s10957-011-9959-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-011-9959-3