  


Norminduced 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 norminduced 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 logconcave only if $p \geq 1$, this framework also covers nonlogconcave 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 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  