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 October 10, 2001 Lecture 8 Lecturer: Michel X. Goernans Scribe: Jelena Spasojevic Interior Point Algorithm Wrap Up In last lecture we were discussing the Interior Point Algorithm. Our goal was to optimize barrier problem BP(p): min cTx -p Cln xj subject to Ax = b, x > 0 To find p-center one had to solve some quadratic constraints, thus the algorithm discussed in class was using full Newton steps. In this way we get approximate p-center. In order to asses the run time of algorithm let us take a look at how does our proximity measure, a(x,s, p) change with: x ex +Ax, s ts + As. We proved the following theorem. Theorem 1 If a(x, s,p) < a < 1, then Thus, as a corollary we get: 2 2 a(x, s,p) < -+-a(x +Ax, s + As, p) < ~(x,S, p) < -,3 3 i.e., proximity measure decreases after the Newton step. Therefore, if we continue this process, we will converge to the p-center. However, in order to find the solution of the linear program, we need to find the p-center for p =0. Therefore, after each step, we also change the value of p: p ep(1-0). We showed the following: Theorem 2 If a(x,s,p) = a and xTs =np, then Therefore, the algorithm is as follows: Initialization: Start with (x(O),do),p(O))such that do),p(O)) 5 i.Refer to the handout to see in more detail how we can do this. The point is that we can choose this starting point in such a way that p(O) 5 26L,where L is the length of the program. While p >_ 6 do: -Find Ax, As by solving the Newton step equations.-Let x tx + Ax, s ts + As, p tp(1- 8) where 8 = &. We can prove the following. Theorem 3 In the above algorithm, if before the Newton step the centrality measure a is at most i,then after the Newton step and changing p, we still have o < i. Proof: If a(x, s, p) 5 i then by Theorem 1: o(x +Ax, s +As, p) 5 (1/2)2 --: 21 -12 4' Now let us change p tp(1-Q), where 8 = A.Using Theorem 2 we get a(x+Ax, s+As, p(1-8)) 5 What is the number of iterations that we have to make? Suppose we start at p(O) = 26L. After k iterations we have p 5 (1-Therefore, in order to have p 5 c, we need k = O(fi(L +ln a)). How do we choose c? We know that at any point because of duality gap: xTs = np. Given that we stop when p < r then we have xTs < nr, i.e., the duality gap is smaller than nr at the end of the algorithm. The following theorem allows us to stop as soon as duality gap is smaller than & and take any vertex below as the solution. Suppose that when we stop there are two vertices of the original linear program for which the above duality gap condition holds. These two vertices, x('), x(~),both satisfy Ax = b, x 2 0. Theorem 4 If cTx(') # c~x(~)then where L is the size of the initial linear program. Proof: We have that A is a matrix with integer entries and b is a vector with integer entries. Then we can express: r1 r2 rnx(l)= (- Pl P2-&)T and x(~)= (-, -, ...,-), q ' q '"" 4 S SS vi,j : q,s,pi,qj E and q,s,pi,qj 1zL by the theorem we had in a previous lecture. Assume c is a vector with integer entries as well. Then: lCTX(') -CTx(2)I1-= integer integer integer 1 1 -I=[- -I>->-. 4 S 22L qs qs Now choose c so that nr < 2 ~ ~ ~=This implies k. O(JiiL). As the number of steps in the ellipsoid algorithm was O(n2L) we can see that interior algorithm has much smaller number of iterations. Also, in ellipsoid algorithm we were reducing the volume of the ellipsoid by a small factor. Here there are tons of small tricks to reduce p well and to start with p that is not so big. One could also dox tz + 2Ax, s ts +2As to make it more appealing in practice. Often in actual implementations the number of iterations is independent of the size of the program. By choosing E so that ne < 2-2L, we know that every vertex below the current solution is an optimum solution of the linear program. But How do we find such a vertex? In previous lectures we had a Lemma saying that for every z in a polyhedron P, there is always a vertex of P below it of value less than it. In fact, the proof of this lemma provides an algorithm for finding such a vertex. At this moment we stop with linear programming to go on to network flows. To recapitulate we have seen two main classes of linear programming algorithms: Ellipsoid: has the advantage that it only requires us to provide a separation subroutine, rather than listing all the constraints of the linear program. Interior Point Method: has the advantage that it is much faster than the ellipsoid algorithm. Variants of this algorithm are actually used in practice. A major open question in linear programming is if there exists a strongly polynomial time linear programming algorithm, i.e., one whose running time does not depend on the size of numbers but only on dimensions n,rn. Network Flows A network flow problem that we will consider in more detail is: Given network (graph) and quantity of flow allowed on each edge (capacity) and cost, our goal is to find a flow of minimum cost that satisfies some circulation properties (to be defined later). This problem can be seen as a linear programming problem. However, we will use the structure of this problem to build faster algorithms and will be able to give a strongly polynomial time algorithm that solves this problem (i.e., its running time will depend only on the number of edges and vertices in the graph, and not on the numerical values in the input). Problems Being Considered in Network Flows There are many problems that can be considered as Network Flow problems. Here's a list of some of them: Shortest path problem Bipartite matching problem Maximum flow problem Minimum-cost flow problem: This problem is more general than the above problems, there exist a strongly polynomial algorithm for it and we can also reduce other problems to this one. This is the very reason we will focus on this one. a Multicommodity flow problemNotations We will use directed graph G = (V,E)to represent a network. We will use the Goldberg-Tarjan notation. Description of our network model follows: We are given a bi-directed graph G = (V,E),i.e., for every v,w E V, (v,w)E EJ(w,v)E E. On every edge (v,w) E Ethere is a capacity u(v,w).(u:E+Z) On every edge (v,w)E E there is a