Optimization Online


Symmetry Points of Convex Set: Basic Properties and Computational Complexity

Alexandre Belloni (belloni***at***mit.edu)
Robert M. Freund (rfreund***at***mit.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 cross-ratio distance. When S is polyhedral of the form {x : Ax \le b}, there is an interior-point 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 OR-369-04

Download: [PDF]

Entry Submitted: 07/23/2004
Entry Accepted: 07/23/2004
Entry Last Modified: 07/23/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society