CS787: Advanced AlgorithmsScribe: David Malec and Xiaoyong Chai Lecturer: Shuchi Chaw laTopic: Minimax Theorem and Semi-Definite Programming Date: October 22 2007In this lecture, we first conclud e our discussion of LP-duality by applying it to prove the Minimaxtheorem. Next we introduce vector programming and semi-definite programming using the Max-Cut problem as a motivating example.16.1 L.P. Duality Applied to the Minimax TheoremThe Minimax Theorem relates to the outcome of two player zero-sum games. Assume we have apayoff matrix A for the game, where columns and rows represent moves that each of the players canemploy (we refer to the players hereafter as the Column Player and the Row Player respectively),and the entries in the matrix represent the payoff for the Row Player. Note that we only need theone matrix to describe the outcome, since in a zero-sum game the payoff to the Column Player andthe payoff to the Row Player must sum to zero. Now, if we call the strategy employed by the RowPlayer x and the strategy employed by the Column Player y, we can express the optimal payoff tothe Row player asmaxxminyxTAy if the Row Player goes first (16.1.1)minymaxxxTAy if the Column Player goes first (16.1.2)The Minimax Theorem says that if we allow the Row Player and Column Player to select probabilitydistributions over the rows and columns of A, respectively, for their strategies, then (16.1.1) is equalto (16.1.2). We can show this by considering a Linear Program for finding (16.1.1), determining itsDual, and then recognizing that the Dual will find (16.1.2). The Minimax Theorem then f ollowsimmediately from the Strong LP-Duality T heorem. Consider the L inear ProgramsPrimal:max t subject tot −XjAijyj≤ 0 ∀i : xiXjyj≤ 1 : syj≥ 0 ∀j1Dual:min s subject tos −XiAijxi≥ 0 ∀j : yjXixi≥ 1 : txi≥ 0 ∀iNote that while technically we require thatPjyj=Pixi= 1, since both are pr obab ility distribu-tions, the relaxations of this cond itions seen in the Primal and Dual Linear Programs are sufficient,sincePjyj< 1 andPixi> 1 correspond to suboptimal values for their respective objectivefunctions.The preceding demonstrates the Minimax Theorem to be true, sin ce with a little thought it can beseen that maximizing t in the Primal Linear Program corresponds exactly to finding the value of(16.1.1), and minimizing s in the Dual Linear Program corresponds exactly to finding the value of(16.1.2); hence, the Strong LP-Duality Theorem gives us that these values are in fact equal.16.2 Max-Cut ProblemSome problems can not be reasonably approximated using Linear Programming, because there isno Linear Programming relaxation that both is of small size and has a good integrality gap. Wecan sometimes use the technique of Semi-Definite Programming to find approximations to suchproblems. We w ill consider the Max-Cut problem as an example of this type of problem. Formally,we can state the Max-Cut Problem as follows:Given: a graph G = (V, E), and a cost function on the edges ce.Goal: Form a partition (V1, V2) of V such thatPe∈E′ceis maximized, where E′= E ∩ (V1× V2).We can form a program for this problem by considering making a variable for each v ∈ V torepresent which of the s ets V1, V2contains it, say xv∈ {0, 1}, where a value of 0 indicates it is inV1and a value of 1 indicates it is in V2. Then an edge (u, v) crosses the partition if and only ifxu6= xv, which is equivalent to the condition |xu−xv| = 1, by the definition of our variables. Thus,we can translate our original goal into an objective function to get the program:maxX(u,v)∈E|xu− xv|c(u,v)subject toxv∈ {0, 1} ∀v ∈ VLooking more closely at this pr ogram, however, we can see that there is a fundamental issue withit — specifically, the objective function makes use of the absolute value function, which isn’t linear.Previously, we have seen cases where we were able to convert an objective function containing anabsolute value into a linear objective fu nction by adding variables and constraints, so it might2seem like we could do so here. The pr oblem with that idea is that our objective function is to bemaximized in this case. Before, we rewrotemin|t|asmin t′subject tot′≥ tt′≥ −tThis worked because we could think in terms of minimizing an upper bound on both t and −t.If we try the same approach with a maximization problem, however, we would be proposing torewritemax|t|asmin t′subject tot′≥ tt′≤ −tThis doesn’t work, because the two constraints on t′conflict at a very basic level. Thus, if we wantto solve this problem, we need to fi nd another way to deal with the issue of nonlinearity in ourprogram instead of trying to make the proposed program linear. So in s tead of focusing on this, wewill instead f ocus on how to make it easier to relax the program, since this is necessary to findingan approximation regardless of our approach. We rewrite our program as an equivalent QuadraticProgram, specificallymaxX(u,v)∈E1 −xuxv2c(u,v)subject toxv∈ {−1, 1} ∀v ∈ VThis is preferable to our previous program, since we can relax the integrality constraint xv∈{−1, 1} ∀v ∈ V to the constraint x2v= 1 ∀v ∈ V .Now, since the Max-Cut Problem is NP-Hard, we can see that this implies that Quadratic Programs,unlike Linear Programs, must be NP-Hard. There are certain types that we can find decentapproximations to in a reasonable amount of time. We consider one such typ e next.316.3 Vector ProgramsA Vector Program is a program over vectors y1, y2, . . . , yn(in general, these vectors are h igh-dimensional), where we write the program in the formmin / maxXi,jcijyi· yjsubject toXi,jAijyi· yj≥ bIn the above expressions, (·) represents taking a dot product. These can be thought of as LinearPrograms in the dot products of the vectors they are over . While we can solve su ch programs, it isimportant to note that we can’t constrain the dimension of the yi— they could end up being veryhigh-dimensional.While we could reinterpret our original program for the Max-Cut Problem as a Vector P rogram,there are some very basic issues with this. Specifically, in order to be able to give a meaningful inter-pretation of the values of the xv, we would need to require that they be essentially one-dimensional;however, as we just noted, we can place no such constraints on the number of dimensions the vectorsin such a program have.16.4 Semi-Definite ProgrammingOne limitation of linear programming is