On the symmetry function of a convex set |
| |
Authors: | Alexandre Belloni Robert M Freund |
| |
Institution: | (1) IBM T. J. Watson Research Center and MIT, 32-221, 1101 Kitchawan Road, Yorktown Heights, NY 10598, USA;(2) MIT Sloan School of Management, 50 Memorial Drive, Cambridge, MA 02139-4307, USA |
| |
Abstract: | We attempt a broad exploration of properties and connections between the symmetry function of a convex set S ${S \subset\mathbb{R}^n}We attempt a broad exploration of properties and connections between the symmetry function of a convex set S
and other arenas of convexity including convex functions, convex geometry, probability theory on convex sets, and computational
complexity. Given a point , let sym(x,S) denote the symmetry value of x in S:
, which essentially measures how symmetric S is about the point x, and define
x
* is called a symmetry point of S if x
* achieves the above maximum. The set S is a symmetric set if sym
(S)=1. There are many important properties of symmetric convex sets; herein we explore how these properties extend as a function
of sym
(S) and/or sym
(x,S). By accounting for the role of the symmetry function, we reduce the dependence of many mathematical results on the strong
assumption that S is symmetric, and we are able to capture and otherwise quantify many of the ways that the symmetry function influences properties
of convex sets and functions. The results in this paper include functional properties of sym
(x,S), relations with several convex geometry quantities such as volume, distance, and cross-ratio distance, as well as set approximation
results, including a refinement of the L?wner-John rounding theorems, and applications of symmetry to probability theory on
convex sets. We provide a characterization of symmetry points x
* for general convex sets. Finally, in the polyhedral case, we show how to efficiently compute sym(S) and a symmetry point x
* using linear programming. The paper also contains discussions of open questions as well as unproved conjectures regarding
the symmetry function and its connection to other areas of convexity theory.
Dedicated to Clovis Gonzaga on the occasion of his 60th birthday. |
| |
Keywords: | 90C25 65K05 90C27 |
本文献已被 SpringerLink 等数据库收录! |
|