Separation of nonconvex sets with general augmenting functions

• 成果类型: Article
• 署名作者: Nedic, Angelia; Ozdaglar, Asuman
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1070.0296
• 发表日期: 2008
• 页码: 587-605
• 关键词: duality; convex

摘要

In this paper, we consider two geometric optimization problems that are dual to each other and characterize conditions under which the optimal values of the two problems are equal. This characterization relies on establishing separation results for nonconvex sets using general concave surfaces defined in terms of convex augmenting functions. We prove separation results for augmenting functions that are bounded from below, unbounded augmenting functions, and asymptotic augmenting functions.