Optimization Techniques (M.Tech CS & M.Stat, 2025-26)
Optimization Techniques (M.Tech CS & M.Stat, 2025-26)
Instructor Arijit Ghosh
Status Will begin from January 2026
Description To study the basics of mathematical programming with a focus on convex optimization
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences
Class timings TBA
Syllabus
Introduction to Mathematical Programming
Linear Programming (LP), Integer Linear Programming (ILP), and Semidefinite Programming (SDP)
Basic properties of LP
Basics of discrete convex geometry (Helly's Theorem and its relatives) and its applications
Vertices and extreme points of convex sets
Structural results on polytopes and polyhedra
Strong (and weak) duality of Linear Programming and its applications
Unimodular Matrix
Applications of LP
Support Vector Machine and Classification Problems
The Simplex Method
Perceptron Algorithm
Fourier–Motzkin Elimination Method
A brief introduction to Complexity Theory: NP-completeness, NP-hardness, Approximation algorithms, Hardness of approximation, etc.
Rounding LP relaxations of ILP to get integral solutions
Lagrangian dual function and Lagrangian dual problem
Basics of convex geometry and convex functions
Convex Programming
Descent Methods
Gradient Descent Method
Projected Gradient Descent Method
Conditional Gradient Descent Method
Center of Gravity Method
The Ellipsoid Method
Interior Point Method
Introduction to Conic programming (if time permits)
SDP and its applications (if time permits)
Submodular Optimization (if time permits)
Multiplicative Weight Update method (if time permits)
Online convex optimization (if time permits)
Mirror Descent (if time permits)
Stochastic Gradient Descent (if time permits)
References
[AS16] Noga Alon and Joel Spencer, The Probabilistic Method, 4th Edition, Wiley, 2016
[ALS15] Nina Amenta, Jesús A. De Loera, and Pablo Soberón, Helly's Theorem: New Variations and Applications, 2015
[BO97] Imre Barany and Shmuel Onn, Caratheodory's Theorem: Colourful and Applicable, Bolyai Society Mathematical Studies, 6:11 - 21, 1997
[B10] Alexander Barvinok, Combinatorics of Polytopes, Lecture Notes, Univ. Michigan, 2010
[BT97] Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
[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
[F09] Friedrich Eisenbrand, Introduction to Discrete Optimization, Lecture Notes, EPFL, 2009
[FV14] Robert M. Freund and Jorge Vera, Fundamentals of Nonlinear Optimization: A Constructive Approach, book in progress
[H18] Moritz Hardt, Convex Optimization and Approximation, Lecture Notes, UC Berkeley, 2018
[K06] Vladlen Koltun, Advanced Geometric Algorithms, Lecture Notes, Stanford University, 2006
[LGM19] Jesus de Loera, Xavier Goaoc, Frederic Meunier and Nabil Mustafa, The Discrete Yet Ubiquitous Theorems of Caratheodory, Helly, Sperner, Tucker and Tverberg, Bulletin of the American Mathematical Society, 56: 415-511, 2019
[LY08] David G. Luenberger and Yinyu Ye, Linear and Nonlinear Programming, 3rd Edition, Springer, 2008
[Mpi-10] Nicole Megow, Kurt Mehlhorn and Julián Mestre, Optimization, Lecture Notes, Max Planck Institute for Informatics, 2010.
[MG07] Jiří Matoušek and Bernd Gärtner, Understanding and Using Linear Programming, Springer, 2007
[M02] Jiří Matoušek, Lectures on Discrete Geometry, Springer, 2002
[R97] R. Tyrrell Rockafellar, Convex Analysis, Princeton University Press, 1997
[R20] Thomas Rothvoss, Discrete Optimization, Lecture Notes, University of Washington, 2020
[S93] Rolf Schneider, Convex Bodies: The Brunn-Minkowski Theory, Cambridge University Press, 1993
[SB18] Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge Univ. Press, 2018
[MU05] Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005
[WS11] David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011
[W14] David P. Williamson, Mathematical Programming, Lecture Notes, Cornell University, 2014.
[TB97] Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM, 1997
[V21] Nisheeth K. Vishnoi, Algorithms for Convex Optimization, Cambridge University Press, 2021
[V03] Vijay Vazirani, Approximation Algorithms, Springer, 2003
[Y18] Yurii Nesterov, Lectures on Convex Optimization, Springer, 2018
[Z95] Günter M. Ziegler, Lectures on Polytopes, Springer-Verlag, 1995
Lecture details
TBA