Optimization Techniques
Optimization Techniques
(M.Tech CS & M.Stat, 2nd Sem. 2025-26)
(M.Tech CS & M.Stat, 2nd Sem. 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 11:15 AM - 1:05 PM on Mondays and Thursdays
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, and 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
Topics covered in Lecture 1 (5 January 2026)
Course introduction
Introduction to Mathematical Programming
Definitions related to mathematical programming: Optimal value, optimal solution, feasible solution, and feasible region/set
Introduction to Unconstrained Optimization
Some applications of unconstrained optimization:
Facility Location problem and Geometric Median problem
Minimum Enclosing Ball problem
Least Squares problem (and Linear Regression)
Linear regression with penalties
Introduction to Linear Programs (LP) and Integer Linear Programs (ILP)
Remark on the polytime solvability of LP and NP-hardness of ILP
Applications of LP and ILP
Vertex Cover (problem) and its 2-factor approximation
Remark on Half-Integrality of the fractional VC problem
Support Vector Machine (SVM) and LP formulation of Linear Classifier
Reading materials:
Topics covered in Lecture 2 (8 January 2026)
Testing the feasibility of constrained programs using unconstrained programs
Convex sets, convex combinations, and convex hulls
Affine dependence/independence, affine combination, and affine hulls
Different equivalent definitions of affine/linear independence
Three results from combinatorial convex geometry:
Radon's Theorem
Helly's Theorem (finite collection case)
Carathéodory's theorem about convex hulls
Reading materials:
Topics covered in Lecture 3 (22 January 2026)
Finite intersection property and compact sets
Infinite version of Helly’s theorem for convex sets
Remarks on infinite Helly-type theorems: necessity of closedness and boundedness assumptions
Definition of the center point of a point set, and Rado’s center point theorem
Pointwise approximation of a function by a linear function
Rey–Pastor–Santaló theorem on common transversals of segments
Definition of the Minkowski sum of subsets of Euclidean space
Reading materials:
Chapter 1 from [M02]
Chapters 1 and 4 from [K06]
Wikipedia entry on finite intersection property
Topics covered in Lecture 4 (28 January 2026)
Properties of convex sets
Relation between convex hulls and convex combination
Convex hull of a compact set is also a compact set
Relation between Minkowski sum and convex hull
Klee's theorem on covering/intersecting a collection of sets by a translate of a convex set
Linear programs (LP) in general form and equational form
Converting LP into an LP in equational form
Basic feasible solutions (BFS) of LP in equational form, and their properties
Reading materials:
Topics covered in Lecture 5 (29 January 2026)
Recalled the definition of BFS of LP in equational form
Fundamental Theorem of Linear Programming (for LP in equational form)
More definitions from convex geometry:
Polyhedra and polytopes
Vertices and extreme points of convex sets
Equivalence of BFS and vertices of LPs in equational form
Reading materials: