This course will cover theory and algorithms of optimization and is open to CS MTech and CS PhD and all final year BTech students. The pre-requisites for this course are Linear Algebra and Calculus and the course will be heavy in its mathematical component. There will be a good amount of programming as well.
Instructor: Dr. Divya Padmanabhan TA:
Class Timings: Mon 12-1 pm, Thurs 10-11 am, Fri 8-9 am Venue: LT4, Admin Block, IIT Goa
The following references will be directly relevant for the course.
[LY] David Luenberger and Yinyu Ye, Linear and Non-linear Programming, 3rd Edition, Springer
[CZ] Edwin K P Chong and Stanislaw H. Zak, An Introduction to Optimization, 2nd Edition, Wiley-Interscience Series on Discrete Mathematics and Optimization
[BV] Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press.
Some parts of this course will closely follow Prof. Amir Ali Ahmadi's course ORF:363 Computing and Optimization at Princeton University. You are encouraged to go through this material.
Additional References:
[NW] Jorge Nocedal and Stephen Wright, Numerical Optimization, 2nd Edition, Springer
[RF] R. Fletcher, Practical Methods of Optimization, Wiley
[BT] Bertsimas and Tsitsikilis, Introduction to Linear Optimization, Athena Scientific Publishers.
[HL] Hillier and Lieberman, Introduction to Operations Research
Modelling optimization problems, classes of problems- discrete, continuous, linear, quadratic, unconstrained and constrained, Gurobi solver
Unconstrained optimization: necessary and sufficient conditions, Iterative algorithms: Steepest descent, Newton’s method, Conjugate Gradient, Applications in Machine Learning
Convexity: Convex Sets, Convex functions, Convex Optimization, Farkas Lemma
Linear Programming: Applications in Operations Research: Transportation, Max flow-Min Cut, Simplex Method, LP Duality
Constrained Optimization: Projected Gradient, KKT conditions, Duality, Conditions for Strong Duality, Applications in Machine Learning e.g PCA, SVM
You will be graded based on quizzes (25%), a mid-term exam (30%), a final exam (30%) and class participation (15%).
Collaboration is strictly NOT permitted for quizzes and exams.