Explicit polyhedral approximation of the Euclidean ball

J. Frédéric Bonnans; Marc Lebelle

RAIRO - Operations Research (2010)

  • Volume: 44, Issue: 1, page 45-59
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Frédéric Bonnans, J., and Lebelle, Marc. "Explicit polyhedral approximation of the Euclidean ball." RAIRO - Operations Research 44.1 (2010): 45-59. <http://eudml.org/doc/250858>.

@article{FrédéricBonnans2010,
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. },
author = {Frédéric Bonnans, J., Lebelle, Marc},
journal = {RAIRO - Operations Research},
keywords = {Polyhedral approximation; convex hull; invariance by a group of transformations; canonical cuts; reduction},
language = {eng},
month = {2},
number = {1},
pages = {45-59},
publisher = {EDP Sciences},
title = {Explicit polyhedral approximation of the Euclidean ball},
url = {http://eudml.org/doc/250858},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Frédéric Bonnans, J.
AU - Lebelle, Marc
TI - Explicit polyhedral approximation of the Euclidean ball
JO - RAIRO - Operations Research
DA - 2010/2//
PB - EDP Sciences
VL - 44
IS - 1
SP - 45
EP - 59
AB - 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.
LA - eng
KW - Polyhedral approximation; convex hull; invariance by a group of transformations; canonical cuts; reduction
UR - http://eudml.org/doc/250858
ER -

References

top
  1. A. Schrijver, Theory of linear and integer programming. Wiley (1986).  
  2. C.B. Barber, D.P. Dobkin and H. Huhdanpaa, The quickhull algorithm for convex hulls. ACM Trans. Math. Software22 (1996) 469–483.  
  3. A. Ben-Tal and A. Nemirovski, On polyhedral approximations of the second-order cone. Math. Oper. Res.26 (2001) 193–205.  
  4. J.F. Bonnans, Optimisation continue. Dunod, Paris (2006).  
  5. F. Glineur, Computational experiments with a linear approximation of second-order cone optimization. Faculté Polytechnique de Mons (2000).  
  6. J.B. Hiriart-Urruty and M. Pradel, Les boules. Quadrature (2004).  
  7. 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.  
  8. 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).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.