Optimization Techniques (M. Stat. 1 year, 2019)
Instructor Arijit Ghosh
Teaching assistant Shankar Ghosh
Description To study the basics of Mathematical Programming.
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences.
Class timings Wednesday and Friday 11:15 - 13:00 hrs.
Syllabus
Introduction to Mathematical Programming
Integer Programming, and Linear Programming (LP) and Semidefinite Programming (SDP) Relaxation
Basic properties of LP
Basics of discrete convex geometry (Helly's Theorem and its relatives) and its applications
The Simplex Method
Strong (and weak) duality of Linear Programming and its applications
Extreme point structures of polytopes and its applications
Lagrangian dual function and Lagrangian dual problem
Basics of convex geometry
Descent methods
Interior Point Method
The Ellipsoid Method
Interior Point Method
References
[AS16] Noga Alon and Joel Spencer, The Probabilistic Method, 4th Edition, Wiley, 2016.
[BO97] Imre Barany and Shmuel Onn, Caratheodory's Theorem: Colourful and Applicable, Bolyai Society Mathematical Studies, 6:11 - 21, 1997.
[BT97] Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, Belmont, Massachusetts, 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.
[K06] Vladlen Koltun, Advanced Geometric Algorithms, Lecture Notes, Stanford University, 2006.
[LGM18] Jesus de Loera, Xavier Goaoc, Frederic Meunier, The Discrete Yet Ubiquitous Theorems of Caratheodory, Helly, Sperner, Tucker and Tverberg, Bulletin of the American Mathematical Society, to appear.
[LY08] David G. Luenberger and Yinyu Ye, Linear and Nonlinear Programming, 3rd Edition, Springer, 2008.
[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.
[S93] Rolf Schneider, Convex Bodies: the Brunn-Minkowski Theory, Cambridge University Press, 1993.
[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.
[TB97] Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM, 1997.
[V03] Vijay Vazirani, Approximation Algorithms, Springer, 2003.
[Z95] Günter M. Ziegler, Lectures on Polytopes, Springer-Verlag, 1995.
Lecture details
Topics covered in Lecture 1 and 2
Introduction to Mathematical Programming.
Introduction to Linear Programming and Integer Linear Programming.
Linear Programming formulation of the largest ball inside a Polytope Problem.
Vertex Cover: ILP formulation, LP relaxation, and Rounding.
Max-Cut: Integer programming formulation, SDP relaxation, and rounding.
Reading materials:
Topics covered in Lecture 3
Theory of Linear Programming
Equational form of Linear Programming
Basic feasible solutions (BFS)
Fundamental Theorem of Linear Programming
Reading materials:
Topics covered in Lecture 4
Fundamental Theorem of Linear Programming (version 2)
Vertices and extreme points of polytopes
Equivalence of BFS, extreme points and vertices
Reading materials:
Topics covered in Lecture 5
Radon's Theorem
Helly's Theorem and its infinitely many sets version
Applications of Helly's Theorem
Center Point Theorem
Rey-Pastor-Santalo's Theorem on Common Transversal of Parallel Segments
Affine separability of two functions using Common Transversal of Parallel Segments Theorem
Reading materials:
Topics covered in Lecture 6
Infinitely many sets version of Helly's Theorem
Application of Helly's Theorem (infinite set version)
Klee’s Theorems on covering by translates
Caratheodory’s Theorem
Colorful Caratheodory’s Theorem
Tverberg's Theorem
Reading materials:
Topics covered in Lecture 7
Hyperplane Separation Theorem (point and convex body case)
Jung's Theorem
Necessary and sufficient condition for the existence of extreme points
Fundamental Theorem of Linear Programming (version 3)
Reading materials:
Chapter 2 from [BV04]
Topics covered in Lecture 8
Revisiting BFS and extreme points
Hyperplane Supporting Theorem
Fourier–Motzkin Elimination
Reading materials:
Topics covered in Lecture 9
Linear Programming Duality, Weak Duality Theorem
Conditions for the feasibility of linear equations
Farkas Lemma and its variants
Proof of The Strong Duality Theorem for Linear Programming
Introduction to Lagrangian Duality via Linear Programming
Reading materials:
Topics covered in Lecture 10
Simplex Method
Reading materials:
Topics covered in Lecture 11
Extreme points of Vertex Cover Polytope and its application to rounding.
Extreme points of Perfect Matching Polytope for bipartite graphs.
Kőnig's Theorem for bipartite graphs using strong duality of LP and extreme point
structure of Maximum Matching Polytope of bipartite graphs.
Reading materials:
Topics covered in Lecture 12 (Guest Lecture by Shankar Ghosh)
Introduction to different solvers
Topics covered in Lectures 13, 14, 15 and 16
Support Vector Machines
Perceptron Algorithm
Mixed Nash Equilibrium and its existence
Metrics and Cuts: Min-(s,t)-cut and Multiway cut
Max-flow Min-cut Theorem via Strong Duality Theorem for Linear Programming
Structure of polyhedra and polytopes
Reading materials:
Section 8.6 from [BV04]
Analysis of Perceptron Algorithm: http://www.cs.cornell.edu/courses/cs4780/2017sp/lectures/lecturenote03.html
Section 8.1 from [MG07]
Chapter 2 from [Z95]
Topics covered in Lectures 17 and 18
Lagrangian dual function and Lagrangian dual problem
Weak duality
Complementary slackness
KKT optimality conditions and strong duality
Slater’s constraint qualification and strong duality
Analysis of Support Vector Machines via strong duality
Reading materials:
Topics covered in Lecture 19
First and second-order conditions for optimality
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:
Topics covered in Lectures 20 and 21
Unconstrained minimization problems
Introduction to descent methods
Gradient descent method and its convergence analysis
Steepest descent method and its convergence analysis
Reading materials:
Sections 9.1 till 9.4 from [BV04]
Topics covered in Lectures 22 and 23
Introduction to subgradients
Descent methods constrained to a convex set
Projected subgradient descent for Lipschitz functions
Gradient descent for smooth functions
Reading materials:
Topics covered in Lectures 24, 25 and 26