Welcome to Week 4! In this week we will begin our study of convex optimization problems with constraints. We will encounter what is probably the most important result about convex sets: that we can fit a hyperplane between any closed and bounded convex set, and any point not in that set. We then meet the most basic form of constraint sets, polyhedra, and the associated optimization problems, known as linear programming. Polyhedra are geometric objects with a rich history in art and science, and are certainly interesting objects in their own right.

Learning outcomes

  • Understand the Hyperplane Separation Theorem for bounded convex sets.
  • Understand convex polytopes and their properties.
  • Know how to identify convex polyhedra in terms of their vertices or defining equations.

Tasks and Materials

  • The lecture notes for Lecture 7 and Lecture 8 can be found as usual under Lectures
  • Try to work on Part B (you can check your solutions with the ones given) and have a look at Part A of Problem Sheet 3 before the tutorial class. Problem sheet 4 will be released during the week.

Further reading

  • Lecture 8: Chapter 2 of these notes, Sections 1.1-1.3 of (4)

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.