Bounding Duality Gap for Problems with Separable Objective

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