In Week 7 we will get a first taste of interior point methods for solving linear programming problems. 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.
- 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.
- There is no problem sheet this week. Instead, have a look at the overview article by Margaret Wright
- The midterm test with solutions is available in the Assignemnts section.
- Lecture 11: Chapter 14 of Nocedal and Wright.
- Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
- Jorge Nocedal and Stephen J.Wright. Numerical Optimization. Springer, 2006.
- Yuri Nesterov. Introductory Lectures on Convex Optimization. A basic course. Springer, 2004.
- Aaron Ben-Tal and Akadi Nemirovski. Lectures on Modern Convex Optimization. 2013.