Indian Institute of Information Technology, Allahabad

Department of Information Technology

Course Syllabus  

1. Name of the Course: Convex Optimization

2. LTP structure of the course: 2-1-1

3. Objective of the course: The course aims to introduce students to modern convex optimization and its applications in fields such as machine learning. The course is designed to cover practical modelling aspects, algorithm analysis and design, and the theoretical foundations of the subject. The focus however is on topics which might be useful for machine learning researchers.

4. Outcome of the course: On completion of the course, students should be able to
recognize and formulate convex optimization problems as they arise in practice;know a range of algorithms for solving linear, quadratic and semi definite programming problems, and evaluate their performance; understand the theoretical foundations and be able to use it to characterise optimal solutions to optimization problems in Machine Learning.

5. Course Plan:

Component

Unit

Topics for Coverage  

Component 1

Unit 1

Convex Analysis: Convex Sets, Convex Functions, Calculus of convex functions
Optimality of Convex Programs: 1st order nec. and suff. conditions, KKT conditions
Duality: Lagrange and Conic duality

Unit 2

 Standard Convex Programs and Applications
Linear and Quadratic Programs
Conic Programs: QCQPs, SOCPs, SDPs.

Component 2

Unit 3

Optimization Techniques
Smooth Problems: Gradient descent, Stochastic gradient descent, Newton's methods, Interior Point method.
Nonsmooth Problems: Subgradient descent

Unit 4

Online convex optimization

Non-convex optimization: Adom and other variants.

6. Text Book: S.Boyd and L.Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Available at http://www.stanford.edu/~boyd/cvxbook/

7. References:

R.T.Rockafellar. Convex Analysis. Princeton University Press, 1996.
A.Nemirovski. Lectures On Modern Convex Optimization (2005). Available at
www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf
Y.Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, 2004