In Week 11 we will introduce an application of convex optimization to machine learning. We introduce the popular concept of Support Vector Machines (SVM) and how they are related to convex optimization, and discuss some applications and extensions. We then move on to introduce the class of semidefinite programming problems. Semidefinite Programming (SDP) is a generalization of Linear Programming that has become increasingly popular due to a large number of applications in engineering and control, but also as a tool to solve difficult combinatorial problems.

Learning outcomes

  • Understand the idea of Support Vector Machines and their relation to convex optimization.
  • Know different variants of SVMs and some applications.
  • Understand the idea of Semidefinite Programming as and extension of Linear Programming.

Tasks and Materials

  • The lecture notes and problem sheets are available in their respective sections.

Further reading

Literature

  1. Bernd Gärtner, Jiří Matoušek. Approximation Algorithms and Semidefinite Programming. Springer, 2012
  2. Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.