  


Symmetry Points of Convex Set: Basic Properties and Computational Complexity
Alexandre Belloni (bellonimit.edu) Abstract: Given a convex body S and a point x \in S, let sym(x,S) denote the symmetry value of x in S: sym(x,S):= max{t : x + t(x  y) \in S for every y \in S}, which essentially measures how symmetric S is about the point x, and define sym(S):=\max{sym(x,S) : x \in S }. We call x^* a symmetry point of S if x^* achieves the above supremum. These symmetry measures are all invariant under invertible affine transformation and/or change in norm, and so are of interest in the study of the geometry of convex sets. In this study we demonstrate various properties of sym(x,S), including relations with convex geometry quantities like volume, distance and diameter, and crossratio distance. When S is polyhedral of the form {x : Ax \le b}, there is an interiorpoint algorithm that will compute an approximation of sym(S) in O(m^1.5 ln(m / \epsilon)) iterations of Newton's method. Keywords: convex geometry, symmetry, polytope, computational complexity Category 1: Convex and Nonsmooth Optimization Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: MIT Operations Research Center Working Paper OR36904 Download: [PDF] Entry Submitted: 07/23/2004 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  