| Course Outline | General Information | Study Material | Lectures (classwise) | Assignment |
The course consists of 2 double lectures per week.
The basic thrust of the course would be to study optimization techniques.
The basic course outline is given in this page.
We would assume in this course that you have undergone courses in Design and Analysis of Algorithms, Discrete Mathematics and Linear Algebra.
| Class Timings: | Monday 11:10-12:50, Wednesday 11:10-12:50 Room No. 506, S. N. Bose Bhavan (Library Building) |
| The necessary evil - marks, exam, etc.: | Mid-sem: 30, End-sem: 50, Internal evaluation: 20 |
| Books |
(B1) Understanding and Using Linear Programming Jiří Matoušek and Bernd Gärtner Springer (B2) Linear Programming -- Foundations and Extensions Robert J. Vanderbei Springer (B3) Combinatorial Optimization -- Algorithms and Complexity Christos H. Papadimitriou and Kenneth Steiglitz Dover Publications (B4) Linear and Non-linear Programming David G. Luenberger and Yinyu Ye Springer (B5) Linear Programming Vašek Chvátal W. H. Freeman & Co. Ltd. (B6) Linear Algebra Jin Ho Kwak & Sungpyo Hong Birkhäuser (B7) Approximation Algorithms Vijay V. Vazirani Springer (B8) The Design of Approximation Algorithms David P. Williamson and David B. Shmoys Cambridge (B9) Computational Geometry: Algorithms and Applications Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars Springer Verlag (B10) Algorithm Design J. Kleinberg and Eva Tardos Pearson Education (Indian edition) (B11) Convex Optimization Stephen Boyd and Lieven Vandenberghe Cambridge University Press |
| Web Resources |
(W1) MIT OCW on Optimization Methods (W2) Lecture Notes (by Sanjeev Arora) (W3) Lecture Notes (by Santosh Vempala) (W4) Lecture Notes (by Michael Goemans) (W5) An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (by Jonathan R. Shewchuk) (W6) Lecture Notes by David Mount on Computational Geometry (W7) Lecture slides by J. Kleinberg and E. Tardos |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (01-01-2018) |
Introduction to Mathematical Program: LP, ILP, Non-linear Program, etc. Writing different problems as mathematical program | - | (B1), (B3), (B4), (W1) |
| Lecture 2 (03-01-2018) |
Introduction to Linear Program: Geometric interpretation, feasible region, types of solutions: infeasible and feasible, bounded and unbounded, unique and infinitely many solutions | -- | (B1), (B3), (B4), (W1) |
| Lecture 3 (08-01-2018) |
Line fitting and linear classifiers as an example of LP; Introduction to Integer Linear Program and Maximum Weight Bipartite matching | -- | (B1) |
| Lecture 4 (10-01-2018) |
Tutorial (by Shankar Kumar Ghosh)
| -- | -- |
| Lecture 5 (15-01-2018) |
Vertex Cover and ILP; NP-completeness (not in syllabus) |
-- | (B1), (B10) |
| Lecture 6 (24-01-2018) |
NP-completeness (not in syllabus) | -- | (B10) |
| Lecture 7 (25-01-2018) |
NP-completeness (not in syllabus) Basic Feasible Solution (BFS) of an LP |
-- | (B10), (B1), (B4) |
| Lecture 8 (29-01-2018) |
SIMPLEX | -- | (B1), (B4) |
| Lecture 9 (31-01-2018) |
SIMPLEX | -- | (B1), (B4) |
| Lecture 10 (07-02-2018) |
Low dimensional LP: geometric framework and backward analysis | -- | (B9), (W6) |
| Lecture 11 (08-02-2018) |
Duality | -- | (B1) |
| Lecture 12 (12-02-2018) |
Application of Duality: Matching and vertex cover in bipartite graphs -- Hall's theorem and König's theorem |
-- | (B1) |
| Lecture 13 (14-02-2018) |
Fundamental Theorem of LP | -- | (B1), (B4) |
| 21-02-2018 | Mid Sem Exam | Sketch of model solution | |
| Lecture 14 (05-03-2018) |
Lagrangian framework, dual function, conjugate function, examples | -- | (B11) |
| Lecture 15 (07-03-2018) |
Connection between conjugate and Dual function Slater's Theorem, complementary slackness condition, KKT condition |
-- | (B11) |
| Lecture 16 (12-03-2018) |
Mixed games, Proof of Slater's theorem | -- | (B11) |
| Lecture 17 (19-03-2018) |
Theorems of the alternatives | -- | (B11) |
| Lecture 18 (21-03-2018) |
Properties of convex function, unconstrained minimization condition number |
-- | (B11) |
| Lecture 19 (22-03-2018) |
Gradient descent, proof of convergence rate steepest descent |
-- | (B11) |
| Lecture 20 (26-03-2018) |
Convergence of steepest descent, Newton's method | -- | (B11) |
| Lecture 21 (28-03-2018) |
Newton's method, self concordant function | -- | (B11) |
| Lecture 22 (04-04-2018) |
Network Flows | -- | (B3), (B7) |
| Lecture 23 (05-04-2018) |
Fundamental Theorem of LP: equivalence of BFS and extreme points of the polytope | -- | (B1), (B4), (B10) |
| Lecture 24 (09-04-2018) |
Farkas' Lemma Interior point method |
-- | (W7), (B1), (B4), (B10) |
| Lecture 25 (11-04-2018) |
Interior point method | -- | (B1), (B4), (B10) |