This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Nedic, A. Articles by Ozdaglar, A. Search for Related Content

Separation of Nonconvex Sets with General Augmenting Functions

Angelia Nedi, Asuman Ozdaglar

Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
angelia{at}uiuc.edu
asuman{at}mit.edu

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.

Key Words: augmenting functions; separation of nonconvex sets; recession directions
History: Received: January 30, 2007; revision received: June 5, 2007;