Norm-induced densities and testing the boundedness of a convex set

Alexandre Belloni(bellonimit.edu)

Abstract: In this paper we explore properties of a family of probability density functions, called norm-induced densities, defined as $$f_t(x) = \left\{ \begin{array}{ll} \displaystyle \frac{ e^{-t\|x\|^p}dx}{\int_K e^{-t\|y\|^p}dy}, & x \in K \\ 0, & x \notin K,\\ \end{array}\right. $$ where $K$ is a $n$-dimensional convex set that contains the origin, parameters $t > 0$ and $p > 0$, and $\|\cdot\|$ is any norm. We also develop connections between these densities and geometric properties of $K$ such as diameter, width of the recession cone, and others. Since $f_t$ is log-concave only if $p \geq 1$, this framework also covers non-logconcave densities. Moreover, we establish a new set inclusion characterization for convex sets. This leads to a new concentration of measure phenomena for unbounded convex sets. More precisely, we show that most points of an unbounded convex set are contained in any enlargement of the set's recession cone. In turn, when the recession cone has positive width, most points are actually in the recession cone itself. Finally, these properties are used to develop an efficient probabilistic algorithm to test whether a convex set, represented only by membership oracles (a membership oracle for $K$ and a membership oracle for its recession cone), is bounded or not, where the algorithm reports an associated certificate of boundedness or unboundedness.

Keywords: convex sets; unbounded sets; concentration of measure;

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: IBM Technical Report December/2006

Download: [PDF]

Entry Submitted: 12/26/2006
Entry Accepted: 12/27/2006
Entry Last Modified: 12/26/2006

Modify/Update this entry