In Week 8 we will discuss Primal-Dual Interior Point methods. The point of departure is Newton’s method applied to the LP optimality conditions, and from there we will see how to modify the method in order to take into account the inequalities, and at the same time achieve a certain level of efficiency.

Learning outcomes

  • Understand the ideas leading to primal dual interior point methods.
  • Understand the long-step path-following algorithm.
  • Be able to visualise the central path and the trajectory of the algorithm in different ways.

Tasks and Materials

  • The Lecture notes are available as usual in the Lectures section.
  • Problem Sheet 5 is available in the Assignments section.
  • The solutions to the midterm test are available!

Further reading

  • Lecture 14 and 15: Chapter 5.1-2 of Boyd and Vandenberghe.

Literature

  1. Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
  2. Jorge Nocedal and Stephen J.Wright. Numerical Optimization. Springer, 2006.
  3. Yuri Nesterov. Introductory Lectures on Convex Optimization. A basic course. Springer, 2004.
  4. Aaron Ben-Tal and Akadi Nemirovski. Lectures on Modern Convex Optimization. 2013.