Optimization Techniques (M.Tech CS, 2022-23)
Instructor Arijit Ghosh
Status Ongoing
Description To study the basics of Mathematical Programming
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences
Class timings Tuesdays and Fridays from 11:00 am - 1:15 pm
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
Topics covered in Lecture 1 (2 Aug.'22)
Course details
Introduced the standard notations
Introduction to Mathematical Programming
Introduction to Unconstrained Optimization
Reading materials:
Topics covered in Lecture 2 (5 Aug.'22)
Spectral decomposition of symmetric, positive definite, and positive semidefinite matrices (only statements)
Definitions related to mathematical programming
Optimal value and optimal solution
Feasible solution and feasible region/set
Some applications of unconstrained optimization:
Facility Location problem and Geometric Median problem
Minimum enclosing ball problem
Least squares problem
Introduction to Linear Programs (LP) and Integer Linear Programs (ILP)
2-factor approximation to Vertex Cover problem (VC) via LP relaxation to ILP
A combinatorial approach to getting 2-factor approximation to VC via maximal matching
Reading materials:
Topics covered in Lecture 3 (9 Aug.'22)
Convex sets and convex functions
Simple properties of convex sets and convex functions
Intersection of convex sets
Maxima of two convex functions
Sublevel sets of convex functions
Sum of two convex functions
Definition of a norm, and norms as a convex functions
Introduction to Convex Programs
Examples of convex programs
Linear Regression
Linear Regression with penalties
Reading materials:
Sections 2.1, 3.1, and 4.1 from [BV04]
Sections 7.4 and B.1 from [LY08]
Wikipedia entry on Linear Regression
Wikipedia entry on LASSO
Topics covered in Lecture 4 (12 Aug.'22)
Revisiting linear regression with penalties
Support Vector Machine (SVM)
LP formulation of Linear Classifier
Robust Linear Classifier and its different programming formulations
Reading materials:
Section 8.6 from [BV04]
Wikipedia entry on SVM
Wikipedia entry on Linear Regression
Wikipedia entry on LASSO
Topics covered in Lecture 5 (19 Aug.'22)
Feasibility question vs. solving a mathematical program
Certificate of feasibility, infeasibility, and optimality
Solving a bounded convex program using feasibility oracle for convex programs
Types of LPs: General and Equational forms
Procedure for converting LP into an equivalent LP in equational form with polynomial blowup
Basic feasible solutions (BFS) for LPs in equational form and their properties
Statement of Fundamental Theorem of Linear Programming (version 1)
Reading materials:
Topics covered in Lecture 6 (23 Aug.'22)
Proof of Fundamental Theorem of Linear Programming (version 1)
Fundamental Theorem of Linear Programming (version 2)
Recall some useful definitions from discrete and convex geometry:
Convex hulls
Polyhedrons and polytopes
Vertices and extreme points of convex sets
Equivalence of BFS and vertices of LPs in equational form
Reading materials:
Topics covered in Lecture 7 (24 Aug.'22)
Equivalence of BFS and extreme points of LPs in equational form
Some useful definitions and simple observations about
Convex combinations
Affine combinations and affine hull
Affine dependence
Affine space
Equivalence between two different definitions of convex hulls (and affine hulls)
Connections between affine geometry and linear algebra
Radon's Theorem and its linear algebraic proof
Statement of Helly's Theorem (finite version)
Helly's Theorem for Halfspaces (to be proved later using strong duality of LPs), and proving the general Helly's Theorem (finite version) using this result
Discussion on the infinite version of Helly's Theorem
Reading materials:
Topics covered in Lecture 8 (26 Aug.'22)
Finite Intersection Property (FIP) and compact sets
Steps to derive Helly's Theorem (finite version) using Helly's Theorem for Halfspaces
First, show the result for polyhedrons
Using the result that polytopes are also polyhedrons (will be proved later) prove the result for polytopes
Reduce Helly's Theorem (finite version) to Helly's Theorem for polytopes
Steps to derive general Helly's Theorem using the finite version of Helly's Theorem
We first show that any finite subcollection has a non-empty intersection using Helly's Theorem (finite version)
Using the above result and non-empty intersection property of families of compact sets satisfying FIP, we complete the proof
Reading materials:
Topics covered in Lecture 9 (30 Aug.'22)
Definition of a Center Point of a point set
Rado's Center Point Theorem
Carathéodory's Theorem about convex hulls, and its proof using Fundamental Theorem of LP
Statements of Separating Hyperplane Theorems
Reading materials:
Topics covered in Lecture 10 (2 Sept.'22)
Separating Hyperplane Theorem (Version 1:compact and closed set case)
Definitions from convex geometry: interior, boundary, and closure of convex sets
Supporting Hyperplane Theorem, and its proof using Separating hyperplane Theorem (Version 1)
Separating Hyperplane Theorem (Version 2: general case)
Reading materials:
Topics covered in Lecture 11 (6 Sept.'22)
Definitions and simple properties of Cones and Conic Hulls
Equivalence between two different definitions of conic hulls
Using Fundamental Theorem of LP we prove
Carathéodory's Theorem about conic hulls
Finitely generated conic hull is a closed set
Introduction to Strong Alternatives
Gaussian Elimination through the lens of strong alternatives
Farkas Lemma (Variants 1 and 2) from Hyperplane Separation Theorem (point and convex body case)
Reading materials:
Topics covered in Lecture 12 (7 Sept.'22)
Dual Linear Programs (LP)
Weak Duality Theorem for LP
Statement of Strong Duality Theorem for LP
Proving Farkas Lemma (Variant 1) using Strong Duality Theorem for LP
Complementary slackness and optimality
Reading materials:
Topics covered in Lecture 13 (9 Sept.'22)
Proof of Strong Duality of LP using Farkas Lemmas
Farkas Lemma (Variant 3)
Clark's Theorem
Reading materials:
Topics covered in Lecture 14 (13 Sept.'22)
Proof of Helly's Theorem for halfspaces via strong duality of LP
Helly's Theorem for convex sets (finite version) using Radon's Theorem
Fractional vertex cover and maximum matching problems
Statement of Kőnig's Theorem about bipartite graphs
Reading materials:
Topics covered in Lecture 15 (16 Sept.'22)
Basic feasible solutions (BFS) of a polyhedron
Equivalence between BFS, extreme points, and vertices of polyhedra
Existence of an extreme point in a polyhedron
Face of a polyhedron
Extreme point a face of a polyhedron is also an extreme point of the polyhedron
Reading materials:
Additional reading materials:
Chapters 1, 2, and 3 from [Z95]
Topics covered in Lecture 16 (11 Oct.'22)
Minkowski sum of convex sets
Recession cones and its properties
Representation of pointed polyhedra (Weyl-Minkowski's Theorem)
Fundamental Theorem of Linear Programs (version 3)
Reading materials:
Topics covered in Lecture 17 (12 Oct.'22)
Fourier-Motzkin's Elimination Technique for solving LP
Applications of Fourier-Motzkin's Elimination Technique:
Linear transformation of a polyhedron is also a polyhedron
Minkowski sum of two polyhedra is also a polyhedron
Polytopes are bounded polyhedra
Reading materials:
Topics covered in Lecture 18 (14 Oct.'22)
Integral polyhedra
Totally Unimodular Matrix (TUM), and its properties
Proof of König's Theorem using properties of LP
Introduction to Simplex Method
Reading materials:
Topics covered in Lecture 19 (18 Oct.'22)
Optimality criterion for BFS
Degenerate BFS and degenerate LP
Mathematical foundation of the simplex method
Reading materials:
Topics covered in Lecture 20 (21 Oct.'22)
Correctness of simplex method
Pivoting rules
Time complexity to perform a single pivot step
Termination of simplex method using Bland's rule
Klee-Minty cube and convergence of simplex method
Finding starting BFS using simplex method
Reading materials:
Topics covered in Lecture 21 (25 Oct.'22)
Recall finding a BFS using simplex method
Lagrangian Multipliers
Dual function and dual program
Weak duality
Complementary slackness
KKT conditions
Reading materials:
Topics covered in Lecture 22 (28 Oct.'22)
Statements of 1st and 2nd order characterizations of convex functions
KKT conditions and strong duality of convex programs
Slater's Theorem for strong duality of convex programs
Reading materials:
Additional reading materials:
Chapter 3 from [BV04]
Topics covered in Lecture 23 (1 Nov.'22)
Proof of 1st and 2nd order characterizations of convex functions
Optimality criterion for a feasible solution to a convex program
Optimality criterion for a feasible solution to a convex program with only affine constraints
Reading materials:
Sections 3.1 and 4. 2 from [BV04]
Topics covered in Lecture 24 (2 Nov.'22)
Epigraph of a convex function
Convex envelope of a function
Mathematical programs with linear objective functions
Reducing convex programs to equivalent convex programs with linear objective functions
Minimizing linear objective function over a compact set
Reading materials:
Chapters 3 and 4 from [BV04]
Topics covered in Lecture 25 (4 Nov.'22)
Black-box framework for convergence analysis of convex programs
Center of gravity method for solving convex programs
Reading materials:
Section 2.1 in Chapter 2 from [B15]
Topics covered in Lecture 26 (11 Nov.'22)
Properties of Ellipsoids
Finding feasible solutions to convex programs using Ellipsoid Method
Ellipsoid algorithm for convex programs, and its convergence rate
Reading materials:
Section 2.2 from [B15]
Topics covered in Lecture 27 (15 Nov.'22)
Projected Gradient Descent Method for constrained programs
L-Lipschitz function and its properties
Convergence rate of projected gradient descent method for L-Lipschitz objective functions
β-smooth functions and its properties
Reading materials:
Sections 3.1 and 3.2 from [B15]