MIT 6 972 Algebraic techniques and semide nite optimization February 14 2006 Lecture 3 Lecturer Pablo A Parrilo Scribe Pablo A Parrilo In this lecture we will discuss one of the most important applications of semide nite programming namely its use in the formulation of convex relaxations of nonconvex optimization problems We will present the results from several di erent but complementary points of view These will also serve us as starting points for the generalizations to be presented later in the course We will discuss rst the case of binary quadratic optimization since in this case the notation is simpler and perfectly illustrates many of the issues appearing in more complicated problems Afterwards a more general formulation containing arbitrary linear and quadratic constraints will be presented 1 Binary optimization Binary or Boolean quadratic optimization is a classical combinatorial optimization problem In the version we consider we want to minimize a quadratic function where the decision variables can only take the values 1 In other words we are minimizing an inde nite quadratic form over the vertices of an n dimensional hypercube The problem is formally expressed as minimize xT Qx s t xi 1 1 1 where Q S n There are many well known problems that can be naturally written in the form above Among these we mention the maximum cut problem MAXCUT discussed below the 0 1 knapsack the linear quadratic regulator LQR control problem with binary inputs etc Notice that we can model the Boolean constraints using quadratic equations i e x2i 1 0 xi 1 1 These n quadratic equations de ne a nite set with an exponential number of elements namely all the n tuples with entries in 1 1 There are exactly 2n points in this set so a direct enumeration approach to 1 is computationally prohibitive when n is large already for n 30 we have 2n 109 We can thus write the equivalent polynomial formulation minimize xT Qx s t x2i 1 2 We will denote the optimal value and optimal solution of this problem as f and x respectively It is well known that the decision version of this problem is NP complete e g GJ79 Notice that this is true even if the matrix Q is positive de nite i e Q 0 since we can always make Q positive de nite by adding to it a constant multiple of the identity this only shifts the objective by a constant Example 1 MAXCUT The maximum cut MAXCUT problem consists in nding a partition of the nodes of a graph G V E into two disjoint sets V1 and V2 V1 V2 V1 V2 V in such a way to maximize the number of edges that have one endpoint in V1 and the other in V2 It has important practical applications such as optimal circuit layout The decision version of this problem does there exist a cut with value greater than or equal to K is NP complete GJ79 We can easily rewrite the MAXCUT problem as a binary optimization problem A standard formu lation for the weighted problem is the following 1 wij 1 yi yj yi 1 1 4 i j max 3 1 3 where wij is the weight corresponding to the i j edge and is zero if the nodes i and j are not connected The constraints yi 1 1 are equivalent to the quadratic constraints yi2 1 We can easily convert the MAXCUT formulation into binary quadratic programming Removing the constant term and changing the sign the original problem is clearly equivalent to min wij yi yj 4 2 yi 1 1 1 i j Semide nite relaxations Computing good solutions to the binary optimization problem given in 2 is a quite di cult task so it is of interest to produce accurate bounds on its optimal value As in all minimization problems upper bounds can be directly obtained from feasible points In other words if x0 Rn has entries equal to 1 it always holds that f xT0 Qx0 of course for a poorly chosen x0 this upper bound may be very loose To prove lower bounds we need a di erent technique There are several approaches to do this but as we will see in detail in the next sections many of them will turn out to be exactly equivalent in the end Indeed many of these di erent approaches will yield a characterization of a lower bound in terms of the following primal dual pair of semide nite programming problems minimize Tr QX s t Xii 1 X 0 maximize Tr s t Q diagonal 5 In the next sections we will derive these SDPs several times in a number of di erent ways Let us notice here rst that for this primal dual pair of SDP strong duality always holds and both achieve their corresponding optimal solutions why 1 2 Lagrangian duality A general approach to obtain lower bounds on the value of general non convex minimization problems is to use Lagrangian duality As we have seen the original Boolean minimization problem can be written as minimize xT Qx 6 s t x2i 1 0 For notational convenience let diag 1 n Then the Lagrangian function can be written as L x xT Qx n i x2i 1 xT Q x Tr i 1 For the dual function g inf x L x to be bounded below we need the implicit constraint that the matrix Q must be positive semide nite In this case the optimal value of x is zero and thus we obtain a lower bound given by the solution of the SDP maximize Tr s t Q 0 This is exactly the dual side of the SDP in 5 3 2 7 1 E2 E1 0 1 1 0 1 Figure 1 The ellipsoids E1 and E2 1 3 Underestimator of the objective A di erent but related interpretation of the SDP relaxation 5 is through the notion of an underestimator of the objective function Indeed the quadratic function xT x is an easily optimizable function that is guaranteed to lie below the desired objective xT Qx To see this notice that for any feasible x we have xT Qx xT x n ii xi2 Tr i 1 where The rst inequality follows from Q The second equation holds since the matrix is diagonal Finally the third one holds since xi 1 1 There is also a nice corresponding geometric interpretation For simplicity we assume without loss of generality that Q is positive de nite Then the problem 2 can be intepreted as nding the largest value of for which the ellipsoid x Rn xT Qx does not contain a vertex of the unit hypercube Consider now the two ellipsoids in Rn de ned by E1 x Rn xT Qx Tr E2 x Rn xT x Tr The principal axes of ellipsoid E2 are aligned with the coordinates axes since is diagonal and furthermore its boundary contains all the vertices of the unit hypercube Also it is easy to see that the condition Q implies E1 E2 With these facts it is easy to understand the related …