In this week we will begin our study of Linear Programming theory. We will learn an important result, called Farkas’ Lemma, and use it to derive Linear Programming Duality: to any linear programming problem we can associate a dual problem, such that the maximum of the first problem is the minimum of the second. This duality principle is the basis of many of the most powerful algorithms in optimization.

Note: There will be not tutorial class on Tuesday. Instead, you are encouraged to try the midterm test from 2016 within the time constraints. The solutions will be discussed in the Thursday lecture.

Midterm Test: The midterm test will be on November 7, 1pm-1:45pm in Roscoe 2.2 and Roscoe 2.5. You will be split alphabetically into the two rooms, so look out for the signs in front of the lecture rooms.

Learning outcomes

Tasks and Materials

  • A document with important information on the test is available here.
  • The lecture notes and the problem sheet 4 are available in their respective sections.
  • Try to work on Part A and Part B of the problem sheet. Part A will be discussed in class on Thursday.
  • A midterm test from previous year is available. Solutions to appear shortly.

Further reading

  • Chapter 2 of these notes

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.