Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-28T13:25:45.525Z 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 ; [email protected]
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; [email protected]
Get access

Abstract

We discuss the problem of computing points of IR n whoseconvex hull contains the Euclidean ball, and is containedin a small multiple of it. Given a polytope containing the Euclidean ball, we introduce its successor obtained by intersectionwith all tangent spaces to the Euclidean ball, whose normalspoint towards the vertices of the polytope. Starting from the L ∞ ball,we discuss the computation of the two first successors, andgive 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).