Problems from textbook
Ref.
Exercises
[1]
9.6, 9.10, 11.1, 11.4, 11.6, 11.10
Matlab Assignment
As discussed in class, a large number of primal-dual interior point methods (IPM) are available whose practical efficiency strongly depends on the techniques used to solve their Newton equation system. In this assignment, you will implement a very simple version of interior point method for QP,
Minimize (1)
Subject to .
(a) Derive the KKT conditions of (1) with lagrange multipliers s (for inequality constraint) and y (for equality constraint).
(b) Use logarithmic barrier to eliminate inequality constraints, and rewrite the KKT conditions for the new problem. Hint: Your answer should be in the form given below, where X and S are diagonal matrices with elements of vectors x and s spread across the diagonal, respectively and e ∈Rn is the vector of ones. You see that the only difference with part (a) is a perturbation of the complementarity slackness.
(c) Use the procedure presented in class to show that if (x,y,s) is primal and dual feasible then the duality gap in the barrier subproblem is equal to xTs = nµ, i.e., the term µ controls the distance to optimality.
(d) Primal-dual IPM applies the Newton method to solve the KKT conditions in part (b). To be more precise, it compute the Newton direction and make one step in this direction before reducing the barrier parameter µ. The Newton direction (∆x,∆y,∆s) is computed by solving the following system of linear equations:
Accordingly, the following simple primal-dual IPM for convex quadratic programming is presented. Implement the given algorithm and test your code for a number of random quadratic programs.
(e) The algorithm must guarantee that the error in equation XSe = µe is small. Plot kXSe−µek versus iteration number.
