EE5121: Convex Optimisation

January – May 2015

This is a post-graduate course, aimed at giving a rigorous introduction to optimisation theory and algorithms.

Instructor: Krishna Jagannathan, Assistant Professor

TAs: Sreelakshmi PM <ee13s015@ee.iitm.ac.in>; Geetha C <ee13s041@ee.iitm.ac.in>; Arjun Bhagoji <arjunbhagoji@gmail.com>; Jainam Doshi <ee10b058@ee.iitm.ac.in>;

Slot: D

Location: ESB 350

Course Moodle

Pre-requisites: A good foundation in linear algebra and real-analysis over Euclidean spaces

References:

1. Ben-Tal and Nemirovski, Lectures on Modern Convex Optimization, available here. 

2. Boyd and Vandenberghe, Convex Optimization, available here.

Course Contents:

Convex Analysis

o Convex sets, cones, inner and outer descriptions

o Topological properties

o Polyhedral sets and representations

o Some main theorems (Caratheodory, Krein-Milman...)

o Separating and Supporting Hyperplanes

o Convex functions, Jensen's inequality

o Gradient inequality

o Maxima and minima of convex functions

o Sub-gradients

Linear Programming

o Structural properties, theorem on alternative

o LP Duality

o Some applications in classification (machine learning), compressed sensing, network flows...

The Art of Posing Convex Programs:

o Conic programs, geometric programs (GPs), semi-definite programs (SDPs)

Convex Programming:

o Convex theorem on alternative

o Lagrangian, Duality

o Optimality conditions (KKT Conditions, saddle points)

Basic Algorithms:

o Gradient descent

o Sub-gradient, conjugate-gradient

o Newton's method, quasi-Newton methods