(CS 431) Optimization: Theory and algorithms, 2024
This course will cover theory and algorithms of optimization and is open to CS BTech 3rd year, MnC 3rd year, 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.
Instructors: Dr. Divya Padmanabhan, Dr. Satyanath Bhat TAs: Tina, Krishnaveni
Class Timings: Mon (12 - 1 pm), Thurs (10 - 11 am), Friday (8-9 am) Venue: LT3, Admin Block, IIT Goa
Resources
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
Syllabus
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
Grading
You will be graded based on assignments (25%), a mid-term exam (30%), a final exam (30%) and class participation (15%). The assignments will include programming components and are to be done individually.
You are encouraged to discuss problem solving ideas for the assignments with your classmates. However the submitted assignment must be written/typed individually based on your own understanding.
Collaboration is strictly NOT permitted for the mid-term and final exams. Please approach me if you have any questions.
