Unformatted text preview:

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 27, 2008 Lecture 14 Lecturer: Michel X. Goemans 1 Introduction For this lecture we’ll look at using interior point algorithms for solving linear programs, and more generally convex programs . Developing originally in 1984 by Narendra Karmarkar, there have been many variants (with some of the keywords ’path following’, ’primal-dual’, ’potential reduction’, etc.) on interior point algorithms, especially through the late 80s and early 90s. In the late 90s, people began to realize that interior point algorithms could also be used to solve semidefinite programs (or, even more generally, convex programs). As much as possible, we will discuss linear programming, semidefinite programming, and even a larger class called conic programming in a unified way. 2 Linear Programming We will start with linear programming. Remember that in linear programming, we have: Primal: Given A ∈ Rm×n , c ∈ Rn and b ∈ Rm, find x ∈ Rn: Min c T x s.t. Ax = b, x ≥ 0. Its dual linear program is: Dual: Find y ∈ Rm: Max bT y s.t. AT y ≤ c. We can introduce non-negative slack variables and rewrite this as: Dual: Find y ∈ Rm , s ∈ Rn: Max bT y s.t. AT y + s = c, s ≥ 0. We know that, for a feasible solution, x in the primal, and a feasible solution (y, s) in the dual, we know by complementary slackness that they will both be optimal (for the primal and the dual resp.) iff xT s = 0. Since this is the component-wise product of two non-negative vectors, we can equivalently say: xj sj = 0 ∀j. 2.1 Using the Interior Point Algorithm The interior point algorithm will iteratively maintain a strictly feasible solution in the primal, such that for all values of j, xj > 0. Similarly in the dual, it will maintain a y and an s such that for all values of j, sj > 0. Because of this strict inequality, we can never reach our optimality 14-1� � � condition stated above; however, we’ll get very close, and once we do, we can show that a jump from this non-optimal solution (for either the primal or the dual) to a vertex of improved cost (of the corresponding program) will provide an optimal solution to the (primal or dual) program. In some linear programs, it may not be possible to start with a strictly positive solution. For example, for any feasible solution to the program, it may be that xj = 0, so we may be unable to find a strictly feasible solution with which to start the algorithm. This can be dealt with easily, but we will not discuss this. We’ll assume that the primal and dual both have strictly feasible solutions. 3 Semidefinite Programming As introduced in the previous lecture, in se midefinite programming, our variables are the entries of a symmetric postitive semidefinite matrix X. Let Sn denote the set of all real, symmetric and n × n matrices. For two such matrice s A and B, we define an inner product A B = Aij Bij = T race(AT B) = T race(AB).• i j Semidefinite programming (as a minimization problem) is Min C • X s.t. Ai • X = bi i = 1...m X � 0. Remember that for a symmetric matrix M, M � 0 means that M is positive semidefinite, meaning that all of its (real) eige nvalues λ ≥ 0, or equivalently, ∀x, xT Mx ≥ 0. 3.1 Dual for SDP When working with linear programs, we know the existence of a dual linear program with a strong property: Any feasible dual solution provides a lower bound on the optimum primal value and, if either program is feasible, the optimum primal and optimum dual values are e qual. Does a similar dual for a semidefinite progrm exist? The answer if yes, although we will need some additional condition. We claim that the dual takes the following form. Dual: Find yi ∈ Rn, and S ∈ Sn: Maxy ∈Rm bT y s.t. yiAi + S = C i S � 0. 14-23.1.1 Weak Duality For weak duality, consider any feasible solution x in the primal, and any feasible solution (y, S) in the dual. We have: � � � C • X = yiAi + S • X i � = yi(Ai • X) + S • X i � = yibi + S • X i = bT y + S • X ≥ bT y, the last inequality following from Lemma 1 below. This is true for any primal and dual feasible solutions, and therefore we have z ≥ w, where: z = min{C X : X feasible for primal},• w = max{bT y : (y, S) feasible for dual}. Lemma 1 For any A, B � 0, we have A B ≥ 0.• Proof of Lemma 1: Any positive semidefinite matrix A admits a Cholesvky decomposition: A = V T V for some n × n matrix V . Thus, A • B = T race(AB) = T race(V T V B) = T race(V BV T ), the last inequality following from the fact that, for (not necessarily s ymmetric) square matrices C and D, we have T race(CD) = T race(DC). But V BV T is positive definite (since xT V BV T x ≥ 0 for all x), and thus its trace is nonnegative, proving the result. � A similar lemma was used when we were talking about linear programming, namely that if a, b ∈ Rn with a, b ≥ 0 then aT b ≥ 0. 3.1.2 Strong Duality In general, it’s not true that z = w. Several things can go wrong. In defining z, we wrote: z = min C • X. However, that min is not really a min, but rather an infimum. It might happen that the infimum value can be approached arbitrarily closely but no solution may attain that value prec isely. Similarly in the dual, the supremum may not be attained. In addition, in semidefinite programming, it is possible that the primal may have a finite value, but that the dual may be infeasible. In linear programming, this was not the case. If the primal had a finite feasible value and was bounded, the dual was also finite and with the same value. In semidefinite programming, the primal c an be finite, while the dual may be infeasible or vice versa. In addition, both the primal and dual could be finite, but they could be of differing values. That all said, in the typical case, you do have strong duality (z = w), but only necessarily under certain conditions. 3.1.3 Introducing a Regularity Condition Assume that the primal and dual have a strictly feasible solution. This means that for the primal: ∃X s.t. Ai • X = bi i = (1...m). X � 0. 14-3� ’A � 0’ denotes


View Full Document

MIT 6 854J - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?