Norm-induced densities and testing the boundedness of a convex set
成果类型：
Article
署名作者：
Belloni, Alexandre
署名单位：
Duke University
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.1070.0292
发表日期：
2008
页码：
235-256
关键词：
摘要：
where K is a n-dimensional convex set that contains the origin, parameters t > 0 and p > 0, and vertical bar vertical bar.vertical bar vertical bar 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.
来源URL：