In Week 7 we will get a first taste of algorithms for solving linear programming problems. In particular, the main idea of interior point methods for solving linear programming problems is introduced. We first introduce the standard form of linear programming, on which we will base our discussion. We will derive a system of equations with additional inequalities that constitutes optimality conditions for the linear programming problem. This system of equations can, in principle, be solved using a method such as Newton’s method. We discuss some of the challenges involved.

Learning outcomes

  • Understand the standard form of a linear programming problem.
  • Understand the derivation of the optimality conditions for linear programming.
  • Know how to apply the multi-dimensional version of Newton’s method.

Tasks and Materials

  • The PDF notes for Lecture 11 are available in the lectures section.
  • Have a look at the overview article by Margaret Wright
  • The midterm test with solutions will be made available in the Assignemnts section throughout the week.

Further reading

  • Lecture 11: Chapter 14 of Nocedal and Wright.

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.