Analysis of Convex Relaxations for Nonconvex Optimization
Nonconvex optimizations are ubiquitous in many application fields. One important aspect of dealing with a nonconvex optimization problem is to study its convex relaxation, which is often part of some approximation algorithms that can find quality solutions to the original nonconvex problem. In this dissertation, we analyze two prominent ways of obtaining convex relaxations: Lagrangian duality and semidefinite programming. The difference between the optimal value of the convex relaxation and that of the original problem is measured by the integrality gap or duality gap, which is of central importance in convex relaxation including providing a performance limitation that one can prove for the corresponding approximation algorithm. This dissertation focuses on how to estimate such integrality gap or duality gap more accurately. For convex relaxation with Lagrangian duality, we propose a refinement of the Shapley-Folkman lemma and derive a new estimate for the duality gap of problems with separable objective and linear constraints. The improvement over the existing results is attributed to two sources. First, instead of using a single number measurement, a series of numbers are introduced to characterize the nonconvexity of a function in a potentially much finer manner. Second, we consider all subproblems jointly instead of approximating each subproblem individually as people had done before. We apply our result to the network utility maximization problem in networking and the dynamic spectrum management problem in communication as examples to demonstrate that the new bound can be qualitatively tighter than the existing ones. The idea is also generalized to cases with separable nonlinear constraints, which is illustrated by an application to the network utility maximization problem with traffic split granularity constraints. For convex relaxation with semidefinite programming, we examine two topics: the maximum cut problem and the Shannon capacity of graph. They are likely the two most well-known triumphs that semidefinite programming has in combinatorial optimization. Many semidefinite programming relaxations can be deduced from a systematic approach called the sum-of-squares hierarchy. Naturally, one wonders whether higher-degree sum-of-squares relaxations will provide relaxations with tighter integrality gap, and we study this question for the above two problems in this dissertation. For the maximum cut problem, an instance of integrality gap 0.96 is given first for the degree-4 sum-of-squares relaxation, and we further construct instances as candidates for even looser integrality gap. For the Shannon capacity of graph, we develop general conic programming upper bounds for the Shannon capacity of graph, which include the previous attempts based on sum-of-squares relaxations as special cases, and show that it is impossible to find better upper bounds for the Shannon capacity than the Lovasz number along this way.
convex relaxation; duality gap; nonconvex optimization; semidefinite programming
Wagner, Aaron B.; Udell, Madeleine
Electrical and Computer Engineering
Ph. D., Electrical and Computer Engineering
Doctor of Philosophy
dissertation or thesis