Hostname: page-component-848d4c4894-wzw2p Total loading time: 0 Render date: 2024-06-03T07:05:04.980Z Has data issue: false hasContentIssue false
  • English
  • Français

Explicit polyhedral approximation of the Euclidean ball

Published online by Cambridge University Press:  08 February 2010

J. Frédéric Bonnans  and
Marc Lebelle
J. Frédéric Bonnans
Affiliation:
INRIA-Saclay and Centre de Mathématiques Appliquées, École Polytechnique, 91128 Palaiseau, France ; Frederic.Bonnans@inria.fr
Marc Lebelle
Affiliation:
Commissariat à l'Energie Atomique, Direction de la Protection et de la Sûreté Nucléaire, Service Sûreté Nucléaire, Centre de Fontenay aux Roses, B.P. No 6, 92265 Fontenay aux Roses Cedex, France; marc.lebelle@cea.fr
Get access

Abstract

We discuss the problem of computing points of IRn whose convex hull contains the Euclidean ball, and is contained in a small multiple of it. Given a polytope containing the Euclidean ball, we introduce its successor obtained by intersection with all tangent spaces to the Euclidean ball, whose normals point towards the vertices of the polytope. Starting from the L∞ ball, we discuss the computation of the two first successors, and give a complete analysis in the case when n=6.

Keywords

Polyhedral approximationconvex hullinvariance by a group of transformationscanonical cutsreduction
Type
Research Article
Information
RAIRO - Operations Research , Volume 44 , Issue 1 , January 2010 , pp. 45 - 59
Copyright
© EDP Sciences, ROADEF, SMAI, 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

A. Schrijver, Theory of linear and integer programming. Wiley (1986).
Barber, C.B., Dobkin, D.P. and Huhdanpaa, H., The quickhull algorithm for convex hulls. ACM Trans. Math. Software 22 (1996) 469–483. CrossRef
Ben-Tal, A. and Nemirovski, A., On polyhedral approximations of the second-order cone. Math. Oper. Res. 26 (2001) 193–205. CrossRef
J.F. Bonnans, Optimisation continue. Dunod, Paris (2006).
F. Glineur, Computational experiments with a linear approximation of second-order cone optimization. Faculté Polytechnique de Mons (2000).
J.B. Hiriart-Urruty and M. Pradel, Les boules. Quadrature (2004).
G. Nemhauser and L. Wolsey, Integer and combinatorial optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., New York (1999). Reprint of the 1988 original, A Wiley-Interscience Publication.
G.L. Nemhauser, A.H.G. Rinnoy Kan and M.J. Todd, editors. Optimization, Handbooks in Operations Research and Management Science, Vol. 1, North-Holland, Amsterdam (1989).