Goemans-Williamson Max-Cut Algorithm | The Practical Guide to Semidefinite Programming (4/4)

in the previous videos we have seen a few applications of semi-definite programming today we will take a look at a different problem called max cut this is really my favorite application which is the reason why i left it for last this innocent looking problem that has to do with catching graphs in two pieces is in fact an np-hard problem which in layman's terms means that if you could solve it efficiently you get a million dollar price at the risk of disappointing some of you i must say that we will not be solving the maxcus problem exactly today but we will see an approximation algorithm based on semi-definite programming with an approximation ratio of 87 what does approximation mean in this context and how does it work and where is this 87 percent coming from and how does it all relate to the famous p equal np question well i guess that's what we're here to find out so where is max cut let's forget about the max part for now what does it mean to cut a graph for that you first need a graph or in other terms a bunch of notes and edges between them to cut the graph you need to color each node with either one of two colors for example either blue or red the value of the cut is then the number of broken edges or in other terms edges that have their endpoints colored with two different colors to make things a little bit more formal we assign to each node a variable x i that encodes the color of that note for example we can take one to mean blue and -1 to mean red the nice thing about this encoding is that for two nodes i and j x i times x j equals to one if and only if x i equals x j and equals to minus one otherwise so if you wanna know whether an edge is broken by the cut or not we can look at the quantity 1 minus x i times x j over 2 which is like a binary variable it's equal to 1 if the edge is broken by the cut and 0 otherwise with this notation the value of a cut of a graph like this one is given by the sum of the quantity one minus x i x j over two and the max cut problem as the name indicates is about finding suitable values for the variables x i to make this quantity as large as possible this innocent looking problem is actually notoriously difficult to solve especially for graphs with a large number of nodes and edges the best algorithms that we know of today that solve this problem are not that different from the naive algorithm that tries every possible combination of colors and picks the best one and there are two to the n such combinations so this algorithm becomes quickly infeasible in fact if you can find an algorithm whose running time is bounded by some power of n instead of two to the n you would automatically solve the p equal np question one of the millennium price problems that comes amongst other things with a million dollar cash prize and a legendary status in the math and computer science communities so fair to say we will not be solving this problem exactly today but we can try to find approximate solutions and by that i mean find the cat whose value is at least a half or three quarters or more generally some constant c of the value of the maximum cut this constant c is called the approximation ratio the closest it is to one the better the approximation algorithm is let's start with something basic what if we assign colors randomly to the nodes what approximation ratio can we achieve with this simple algorithm well this is a probabilistic algorithm so its performance will vary but on average each edge has probability one half to be broken by the cut and probability one half not to be in expectation each edge will then count as one half towards the value of the cut and if we sum across edges we get a cut whose value is half the number of the edges and in particular it's at least half the value of the maximal cut can we do better than 50 the answer is yes by using semi-definite programming gomens and williamson were able to achieve an approximation ratio of 87 percent and is their method that i want to share with you today their method can actually be applied to any integer optimization problem or in other words any optimization problem where the decision variables can take only two values one and minus one the method is called a semi-definite relaxation because of the following idea instead of allowing only the two scalar values one and minus one for each variable x i we will allow each x i to be a vector of norm one and whenever we have a product of an x i with some x j we'll replace that with x i transpose x j and by doing this relaxation we actually get a semi-definite program this is because if you take the matrix of all inner products and let's call it x for example this matrix is positive semi-definite and we can rewrite our optimization problem in terms of this matrix x alone if this step seems unclear to you make sure to rewatch the second video of this series which explains this step in more details and unlike integer programs we have very efficient solvers for semi-definite programs so we can solve this problem to get the optimal matrix x to which we apply the square root operation to get the vector as x i but remember at the end of the day to get a cut we need the x i's to be

scalars so how do we go from unit vectors to scalars this step is called rounding and it's usually the most challenging step in any semi-definite relaxation gomens and williamson proposed a very elegant way to do it since the vectors have norm1 we can view them as points on the sphere from there we can simply generate a random hyperplane and assign the value -1 to all the vectors that fall on one side and the value plus one to the others concretely you do this by generating the normal vector to this hyperplane from a gaussian distribution for example and consider its inner product with each one of the vectors x i if the inner product is negative you assign the value minus one and if it's positive you assign plus one and that's it this is actually one of those things that is easier to do than to explain so let's jump to python and see how this is done so let's say that the graph is given to you as a list of edges and we want to find a good cut for this graph using gomez and williamson's method we are going to solve a semi-definite program so let's import cvx pi declare our matrix x to be positive semi-definite and set the diagonals to 1 because we want unit vectors and set our objective function appropriately after calling the solve method we obtain the following positive summary definite matrix x to which we apply the matrix square root function to get our vectors x i keep in mind that these vectors would have the same dimension as the matrix x which is 5 in this case but we plot them here in three dimensions just for illustrative purposes we then generate a random hyperplane and pick labels for our nodes according to which side they fall on of this hyperplane and finally after all of this work this is the cut that you get and you can check that the value of this particular cat is equal to 5. to summarize what we have seen so far we first modified the original problem to make it about vectors then we rounded those vectors back to scalars but the big question now is how does the solution to the modified problem relate to the original problem in other words how good is the cut that we obtained by the gomen and williamson's method the exact analysis is a bit outside the scope of this video but i will give you the main intuition here so you can get an appreciation for this method and if you want you can look at the references included in the description for more details let's focus on one edge at the time for example the edge between node i and node j for these two nodes we have two vectors x i and s j that were returned by our semi-definite program and we rounded them by looking at which side of this random hyperplane they fall on here's a question for you what is the probability that the rounding leads to different labels for these two notes which would lead to this edge being part of the cut when you think about this question for some time you realize that it has to do with the angle theta between x i and x j if the random hyperplane falls inside this angle the two nodes will have different labels otherwise they will share the same label so the probability that they get different labels is theta over pi the sum of these probabilities across edges is the expectation of the value of the cut that we obtained by this rounding technique how does this quantity relate to our modified objective function or more precisely how does theta i j over pi relate to 1 minus x i transpose x j over 2. since x i and x j are unit vectors their inner product is equal to cosine of so the question now is how does theta over pi relate to 1 minus cos theta over 2 can we bound the ratio between the two actually let's plot this ratio as a function of data you can see that it has a minimum somewhere here which is equal to approximately 0. 87 this means that the cut that we get after the rounding procedure is at least 87 percent of the value of the objective value of our semi-definite program which was itself a relaxation of the original max cat problem in other words gomen and williamson's method is an approximation algorithm with an approximation ratio of 87 percent which is very neat this is really the stage of the art this is the best algorithm that we know of that runs in polynomial time this ratio of 87 percent seems like an arbitrary numerical constant and morally you would expect that with a little bit of work we should be able to do better but assuming the unique game conjecture which is a widely believed conjecture in computer science this approximation ratio is probably the best possible in the sense that if you could achieve an approximation ratio of even 88 then that would imply that p equal np and all the consequences that would follow if this does not blow your minds i don't know it will this is saying that unless p equal np which would be some earth shattering used this simple algorithm based on semi-definite programming is not only good it is actually the best possible algorithm which goes to show you the true power hidden behind this seemingly naive question that we asked in the beginning of this series about how to define positive matrices this is a good place to end this series now that we have come a full circle i must emphasize here of course that my goal of this series is not to give a

full overview of everything that's going to be done with semi-definite programming that would make this video the longest on youtube by far but i tried to present few illustrative examples from completely different fields so that hopefully you could appreciate the breadth of applications that are possible with semi-definite programming as usual if you like the video please make sure to like and subscribe and see you next time