Convex Optimization (M.Tech CS, 2nd year, 2019)
Convex Optimization (M.Tech CS, 2nd year, 2019)
Instructor Arijit Ghosh
Description To study the basics of Convex Optimization. This is the final module for the course Optimization Techniques (M.Tech CS, 2nd year) taught by Subhas Chandra Nandy.
Syllabus
Lagrangian dual function and Lagrangian dual problem
Basics of convex geometry
Descent methods
Projected subgradient descent
Conditional gradient method
References
[BV04] Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
[B15] Sébastien Bubeck, Convex Optimization: Algorithms and Complexity, Foundations and Trends in Machine Learning, 2015.
[LY08] David G. Luenberger and Yinyu Ye, Linear and Nonlinear Programming, 3rd Edition, Springer, 2008.
[R97] R. Tyrrell Rockafellar, Convex Analysis, Princeton University Press, 1997.
[N04] Yurii Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2004.
Lecture details
Topics covered in Lecture 1
Basic properties of convex functions
First and second-order characterization of convex functions
Applications of first and second-order characterization of convex functions
Reading materials:
Additional reading materials:
Chapter 1 from [N04].
Topics covered in Lecture 2
Properties of strongly convex functions
Unconstrained minimization problems
Introduction to descent methods
Reading materials:
Sections 9.1 till 9.2 from [BV04].
Topics covered in Lectures 3 and 4
Gradient descent method
Steepest descent method
Coordinate-descent algorithm
Reading materials:
Sections 9.2 till 9.4 from [BV04].
Topics covered in Lecture 5
Separation (and supporting) hyperplane theorem for convex bodies
Subgradients
Projected subgradient descent for Lipschitz functions
Properties of beta-smooth functions
Reading materials:
Topics covered in Lectures 6 and 7