MIT OpenCourseWarehttp://ocw.mit.edu 6.854J / 18.415J Advanced Algorithms Fall 2008��For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.18.415/6.854 Advanced Algorithms September 24, 2001 Lecture 4 Lecturer: Michel X. Goemans Scribe: Reina Riemann 1 LP Duality Last time, we proved the strong duality theorem. Let P and D be the following pair of dual linear programs: (P) z* = min{cT x : Ax = b,x 2 O), (D) w*=ma~{b~~:~~~<c). Theorem 1 (Strong duality) If P or D is feasible then z* =w*. 1.1 Rules for Taking Dual Problems We can also express the strong duality theorem for linear programs in other forms. This is described in the main lecture notes. For example, if the primal linear program is: Tz = min cl XI+ cTx2+cFx3 s.t. -41x1 + 42x2 + 43x3 = bl A2151 + A2252 + A2323 2 b2 A31~1+A32~2+A33~3 < b3 XI> 0, x2 < 0, X3 UIS, where Aij is a mtrix of size mi x nj (and thus xj E Enj) and UIS denotes no restrictions ("unrestricted in sign7') on these variables, then the dual is: w = max blTyl + bFy2 + bT3 Y3 where thus yi E Rmi,and strong duality holds between them. 2 Size of LP In order to be able to discuss the complexity for solving a linear program, we need first to discuss the size of the input. We assume that every integer data is given in binary encoding, thus for n E Z,we needbits, for uE ZP, we need bits, and for A E Znxm,we need bits. As a result, to represent all the data of a linear program, we need a size equal to The above size is not very convenient when proving the complexity of a linear program-ming algorithm. Instead, we will be considering another size, defined by where detmax= max 1 det(A') I over all submatrices A' of A, bmax = maxi lbi 1 and cmax= maxj Icj1. In the next proposition, we show that L is smaller than size(LP), which implies that if we can prove that an algorithm has a running time polynomially bounded in terms of L then it will certainly be polynomial in size(LP) as well. Proposition 2 L < size(LP). The proof of the proposition is in the lecture notes. In the proof, the following key lemma is needed. Lemma 3 If A E Znxn then idet(A)I 5 2size(A)-n2-1. Proof: Recall that for A = [al,aa, ...,ak],I det (A)I can be visualized as the volume of the parallelipiped spanned by the column vectors. Hence, From the definition of L, the following remark follows; this is what we will need mostly when analyzing running times or sizes. Remark 1 didmax * bmax * cmax * 2mfn < 2L.3 Complexity of LP Here is the decision problem corresponding to linear programming. LP: Given A, b, c, A, is there an x :Ax = b, x 20, cTx 5 A? To show that LP is in NP, we need to be able to provide a concise (i.e. polynomially bounded in the size of the input) certificate for yes instances. A feasible point of cost less or equal to X will clearly be a certificate, but will it be concise? Claim 4 LP E NP We now show that if we take not just any feasible solution, but a basic feasible solution, then its size will be polynomially bounded in the size of the input. Theorem 5 Let x be a vertex (or basic feasible solution) of Ax = b, x 20. Then xi = F. for i=l,...,n where pi,q E N and pi < 2L and q < 2L. Proof: Since x is a vertex, then x is a basic feasible solution with basis B such that XB = ~ilband XN =0 (notice that As is square). By Cramer's rule: where cof (A) is a matrix whose entries are all determinants of submatrices of A. Letting q = det (Ag), we get that q 5 detmax < 2L and pi 5 m detmax bmax < 2L. Now, to prove Claim 4, for yes instances, the certificate will be a vertex of {x : Ax = b,x 2 0) such that cTx 5 A. However, to be precise, we also have to deal with the case in which the LP is unbounded, since in that case, there might not be any such vertex. But in that case, we can give a certificate of unboundedness by (i) exhibiting a vertex of {x : Ax = b, x 20) (showing it is not empty, and it is concise by the above theorem) and (ii) showing that the dual feasible region {y : 5 c) is empty by using Farkas' lemma and exhibiting a vertex of Ax = b, x 2 0, cTx = -1 which is also concise by the above theorem. Thanks to duality, we can also show that: Claim 6 LP E co-NP. Indeed, for no instances, we can use strong duality and exhibit a basic feasible solution of ATy 5 c s.t. bTy > X (or show that {x 2 0 : Ax = 6) is empty using Farkas' lemma). In the case when {x : Ax = b, x 20) is feasible, the correctness follows from strong duality saying that min{cTx: Ax = b,x > 0) = rnax{bTy : ~ ~ y5 c). Thus, LP E NP nco -NP which makes it likely to be in P. And indeed, LP was shown to be polynomially solvable through the ellipsoid algorithm. The Ellipsoid algorithm was proposed by the Russian mathematician Shor in 1977 for general convex optimization problems, and applied to linear programming by Khachyan in 1979.Figure 1: One iteration of the ellipsoid algorithm. 4 The Ellipsoid Algorithm The problem being considered by the ellipsoid algorithm is: Given a bounded convex set P E Rn find x E P. We will see that we can reduce linear programming to finding an x in P = {x E Rn: Cx 5 d). The ellipsoid algorithm works as follows. We start with a big ellipsoid E that is guar-anteed to contain P. We then check if the center of the ellipsoid is in P. If it is, we are done, we found a point in P. Otherwise, we find an inequality cTx 5 diwhich is satisfied by all points in P (for example, it is explicitly given in the description of P) which is not satisfied by our center. One iteration of the ellipsoid algorithm is illustrated in Figure 1. The ellipsoid algorithm is the following. Let Eo be an ellipsoid containing P while center ak of Ek is not in P do: -Let cTx 5 cTak be such that {x :cTx 5 cTak)2 P -Let Ek+lbe the minimum volume ellipsoid containing Ekn{x : cTx 5 cTak} -k+k+l The ellipsoid algorithm has the important property that the ellipsoids contructed shrink in volume asthe algorithm proceeds; this is stated precisely in the next lemma. This means that if the set P has positive volume, we will eventually find a point in P. We will need to deal with the case when P has no volume (i.e. P has just a single point), and also discuss when we …