Lectures & Notes

Course to be administered via Google Classroom — ask us to join

Introduction and background

  1. Introduction to Optimization — 02 Aug — 1

  2. Review of linear algebra, analysis — 03 Aug — 2

  3. Review of convexity, calculus — 07 Aug — 3

  4. Review of calculus — 09 Aug — 4

Notes: Introduction to Optimization and Summary of background material

Unconstrained optimization & Line search methods

  1. Introduction, Taylors theorem, 1st and 2nd order conditions on a stationary point — 10,11 Aug — 5, 6

  2. Properties of descent directions, matlab visualization of gradients — 16 Aug — 6

  3. Line search algorithms, Wolfe conditions, backtracking algorithm — 17 Aug — 7

  4. Line search analysis, convergence — 23 Aug — 8

  5. Line search convergence rate — 24 Aug — 9, matlab

Notes: Unconstrained optimization and Line search methods

Conjugate gradient method

  1. Introduction to the conjugate directions method — 31 Aug — 10

  2. Visualizations and various properties of the CDM — 06 Sep — 11

  3. Conjugate gradient method — 07 Sep — 12, matlab

  4. Preconditioned conjugate gradient method — 13 Sep — 13

  5. Nonlinear conjugate gradient method — 14 Sept — 14

Notes: Conjugate gradient methods

Newton, quasi Newton methods, and Least squares problems

  1. Newton methods, convergence, rate and Hessian modification — 20 Sep — 15

  2. Quasi Newton method — 21 Sep — 16

  3. Least squares problems — 04 Oct — 17

  4. Nonlinear least squares problems — 12 Oct — 18a

Notes: Newton & quasi Newton methods and Least squares problems

Constrained optimization

  1. Terminology, feasible set, active set — 12 Oct — 18b

  2. Equality constrained optimization — 16 Oct — 19

  3. Inequality constrained optimization, linearized feasible directions — 18 Oct — 20

  4. Constraint qualification and first order necessary conditions (KKT) — 19 Oct — 21

  5. Proof sketch of KKT conditions — 25 Oct — 22

  6. Projected gradient descent algorithm — 26 Oct — 23, extra ref

  7. Subgradients and the projection operator on the L1 ball — 01 Nov — 24, extra ref1, ref2.

  8. KKT and duality, geometric interpretation (ref, author unknown) — 02 Nov — 25

  9. Properties of the Lagrangian dual function, solving an example — 06 Nov — 26

Notes: Constrained optimization — first order

Course structure

  • Evaluations — quiz 1 (20), quiz 2 (20), project (25), endsem (35), all exams as per Institute schedule.

  • First day of classes — 02 Aug

  • Tutorial 1 — 21 and 28 Aug 2023 during class

  • Quiz 1 — 30 Aug 2023 from 2 - 3.15p in ESB127/128. One A4 size cheat sheet allowed.

  • Tutorial 2 — 11 Sep 2023 from 5-6p in ESB242.

  • Tutorial 3 — 05 Oct 2023 from 3.30p in CRC, and 09 Oct from 5p in ESB242.

  • Quiz 2 — 11 Oct 2023 from 2 - 3.15p in ESB127. One A4 size cheat sheet allowed.

  • Tutorial 4 — 30 Nov from 5-6p in ESB242.

  • Endsem — 21 Nov from 2-5p, two sided A4 cheat sheet allowed (reuse of older sheets not allowed).

TAs

  1. Sai Dinesh ee20d401

  2. Sai Sanjay Narayanan ep20b031

  3. Anant Goyal ee21d202

  4. Kunchakara Alekhya ee21d006

  5. Aaditya Kumar ee21d411

Course Flyer

Prerequisite

Linear algebra

Broad course contents

  1. Review: linear algebra, analysis, and calculus

  2. Unconstrained optimization - descent directions, line search methods, Wolfe conditions, steepest descent method and its analysis, conjugate gradient method and its analysis, preconditioned conjugate gradient method, extension of the conjugate gradient method to its nonlinear versions, introduction to the Newton and quasi Newton methods, discussion of linear and nonlinear least squares problems

  3. Constrained optimization - first order necessary conditions, Karush–Kuhn–Tucker (KKT) conditions with proof, projected gradient method, subdifferentials and some examples of projection operatations, weak and strong duality, second order necessary conditions (time permitting)

  4. Programming implementations of the above methods

References books

  1. Numerical Optimization by Jorge Nocedal and Stephen J. Wright, Springer, 2006. Available online. Keyword NW

  2. Convex Optimization by Stephen Boyd and Lieven Vandenberghe, Oxford University Press, 2009. Available online. Keyword: BL

Back to Home