- 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/2006Entry Accepted: 12/27/2006Entry Last Modified: 12/26/2006Modify/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 Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.