E0 230 (3:1) Computational Methods of Optimization

Department of Computer Science and Automation ( CSA )
Indian Institute of Science ( IISc ), Bangalore


Class Timing : Every Tuesday & Thursday,   8- 9.30am,  August- November, 2019.

Class Room : EE Department, Room No. B 308

Course Instructor : Prof. Chiranjib Bhattacharyya [ chiru AT iisc.ac.in ]

TA : Tony Gracious [tonygracious AT iisc.ac.in], Shivika Narang [shivika AT iisc.ac.in]

Announcements

  • Date for 2nd mid-term test has been changed to 1st November (10-11.30am).
  • Homework 2 due date is 29th October, 2019.
  • There will be no clas on 15th and 17th October.
  • There will be extra classes on 4th Oct (9-10.30am) and 5th Oct (8-11am). No class on 1st Oct.
  • Change in date for 1st mid-term test : 9-10.30am, Sunday 22nd September, 2019.
  • Correction in Q4(i) of HomeWork 1: take the domain to be [-5, 5]x[-5, 5].
  • There will be extra classes on 11th Sept (5-6:30pm) and 13th Sept (5:15-6:45pm). There will be no class on 19th Sept.
  • Homework 1 due date is 12th September, 2019.
  • Please sign up for the course Google group here or email to the TA with subject line "Add to CMO group".

Reference Books

  • R. Fletcher:   Practical Methods of Optimization (Volume 1 &2)
  • David G. Luenberger, Yinyu Ye:   Linear and Nonlinear Programming
  • Yu. Nesterov:   Introductory Lectures on Convex Programming [Download Link]

Home works

Exam Dates

  • 1st mid-term Test: 9-10.30am, Sunday, 22nd September, 2019.
  • 2nd mid-term Test: 10-11.30am, Friday, 1st November, 2019.
  • 3rd mid-term Test: 9-10.30am, Friday, 22nd November, 2019.
  • Final Exam: 2pm, Wednesday, 27th November, 2019.

Lecture Schedule

  • 08/08/19:   Motivating Problems -   Stigler's diet problem,   Chicory and Coffee
  • 13/08/19:   Mathematical Preliminaries: Chap 2 of Principles of Mathematical Analysis book by W. Rudin
  • 20/08/19:   Weierstrass Theorem, Taylor series, small-oh notation.
  • 22/08/19:   Multivariate Taylor Series, Local/Golobal Minima.
  • 27/08/19:   Coercive function, Necessary and Sufficient condition for unconstrained Optimization.
  • 29/08/19:   Necessary and Sufficient conditions for unconstrained Optimization.
  • 03/09/19:   Descent methods, Exact line search. Ref: Chap 2 of Fletcher's book, Chap 8 of Luenberger's book.
  • 05/09/19:   Minimization of convex functions by steepest descent (Ref: Chap 8 of Luenberger's book), Inexact line search (Ref: Chap 2 of Fletcher's book).
  • 11/09/19:   Inexact line search (Ref: Chap 2 of Fletcher's book).
  • 12/09/19:   Global convergence Theorem (Ref: Chap 2 of Fletcher's book), Rate of convergence of Steepest descent (Ref: Sec 1.2 in Nesterov's book)
  • 13/09/19:   Coordinate Descent (Gauss-Southwell) and Conjugate Gradient Algorithms. Ref: Luenberger's book.
  • 17/09/19:   Conjugate Gradient Algorithm (Continued).
  • 22/09/19:   1st mid-term Test. (9am-10.30)
  • 24/09/19:   Conjugate Gradient Algorithm (Continued).
  • 26/09/19:   Conjugate Gradient Algorithm (Continued).
  • 03/10/19:   Newton's method (Ref: Chap 1 in Nesterov's book).
  • 04/10/19:   Quasi Newton Methods: (Ref: Book by Fletcher).
  • 05/10/19:  : Quasi Newton Methods (continued), Constrained Optimisation: Projection onto a convex set (Ref: Book by Luenberger).
  • 22/10/19:   Farka's Lemma (Ref: Book by Fletcher).
  • 24/10/19:   KKT conditions (Ref: Book by Fletcher).
  • 29/10/19:   KKT conditions, Gradient Projection.
  • 31/10/19:   Gradient Projection.
  • 01/11/19:   2nd mid-term Test. (10am-11.30)
  • 05/11/19:   Active Set Methods for Convex QP.
  • 06/11/19:   Active Set Methods for Convex QP, Duality (Ref: Book by Fletcher).
  • 18/11/19:   Duality.
  • 19/11/19:   Linear Programming (ref: Luenberger's book).
  • 20/11/19:   Linear Programming (ref: Luenberger's book), Subgradients.
  • 21/11/19:   Subgradient Projection. (reference link)
  • 22/11/19:   3rd mid-term Test. (9am-10.30)
  • 27/11/19:   Final Exam (at 2pm)