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

Published

Journal Article

In this paper, we explore properties of a family of probability density functions, called norm-induced densities, defined as f t (x)={e -t||x||p /∫ K e -t||y||p dy, x ∈ K 0, x ∉ K, where K is a n-dimensional convex set that contains the origin, parameters t > 0 and p > 0, and ||·|| 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 ≥ 1, this framework also covers nonlog-concave 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. 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. © 2008 INFORMS.

Full Text

Duke Authors

Cited Authors

  • Belloni, A

Published Date

  • February 1, 2008

Published In

Volume / Issue

  • 33 / 1

Start / End Page

  • 235 - 256

Electronic International Standard Serial Number (EISSN)

  • 1526-5471

International Standard Serial Number (ISSN)

  • 0364-765X

Digital Object Identifier (DOI)

  • 10.1287/moor.1070.0292

Citation Source

  • Scopus