Bounding duality gap for separable problems with linear constraints

Madeleine Udell () and Stephen Boyd ()
Additional contact information
Madeleine Udell: California Institute of Technology
Stephen Boyd: Stanford University

Computational Optimization and Applications, 2016, vol. 64, issue 2, No 2, 355-378

Abstract: Abstract We consider the problem of minimizing a sum of non-convex functions over a compact domain, subject to linear inequality and equality constraints. Approximate solutions can be found by solving a convexified version of the problem, in which each function in the objective is replaced by its convex envelope. We propose a randomized algorithm to solve the convexified problem which finds an $$\epsilon $$ ϵ -suboptimal solution to the original problem. With probability one, $$\epsilon $$ ϵ is bounded by a term proportional to the maximal number of active constraints in the problem. The bound does not depend on the number of variables in the problem or the number of terms in the objective. In contrast to previous related work, our proof is constructive, self-contained, and gives a bound that is tight.

Keywords: Duality gap; Shapley–Folkman theorem; Separable problems; Convex relaxation; Randomized algorithms (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-015-9819-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:64:y:2016:i:2:d:10.1007_s10589-015-9819-4

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-015-9819-4

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().