Learn · NPTEL

Course10810647882 lectures

Optimization Theory and Algorithms

Prof. Uday K Khankhoje · IIT Madras

Start with lecture 1 At NPTEL

About

This course will introduce the student to the basics of unconstrained and constrained optimization that are commonly used in engineering problems. The focus of the course will be on contemporary algorithms in optimization. Sufficient the oretical grounding will be provided to help the student appreciate the algorithms better. Illustrative programming assignments will also be provided to deepen understanding of the subject matter.

Intended audience: Senior undergraduate students, graduate students, engineering and data science, AI-ML related industry

Prerequisites: Linear algebra is a strong pre-requisite.Knowledge of programming is suggested.

Lectures

Week 1

  1. Introduction to the course - 1 - Prerequisites, key elements YouTube
  2. Introduction to the course - 2 - Types of problems YouTube
  3. Introduction to the course - 3 - an optimization example to live longer YouTube
  4. Summary of background material - Linear Algebra 1 YouTube
  5. Summary of background material - Linear Algebra II YouTube
  6. Summary of background material - Analysis I YouTube
  7. Summary of background material - Analysis II YouTube

Week 2

  1. Summary of background material - Analysis III YouTube
  2. Summary of background material - Calculus 1 YouTube
  3. Summary of background material - Calculus 2 YouTube
  4. Summary of background material - Calculus 3 YouTube
  5. Example of Multivariate Differentiation YouTube
  6. Gradient of Quadratic form and product rule YouTube
  7. Directional derivative, hessian, and mean value theorem YouTube

Week 3

  1. Unconstrained optimization - 1 - roadmap of the course and Taylor’s theorem YouTube
  2. Unconstrained optimization - 2 - Identifying a local minima - 1st and 2nd order conditions YouTube
  3. Unconstrained optimization - 3 - proof of 1st order condition (split 3) YouTube
  4. Unconstrained optimization - 4 - overview of algorithms and choosing a descent direction YouTube
  5. Unconstrained optimization - 5 - properties of descent directions - steepest descent direction YouTube
  6. Unconstrained optimization - 6 - properties of descent directions - newton direction YouTube
  7. Unconstrained optimization - 7 - trust region methods YouTube
  8. A MATLAB session YouTube

Week 4

  1. Introduction to Line Search YouTube
  2. Wolfe conditions YouTube
  3. Strong Wolfe conditions YouTube
  4. Backtracking Line Search YouTube
  5. Line Search - Analysis YouTube
  6. Line Search - Convergence and Rate - 1 YouTube
  7. Line Search - Convergence and Rate - 2 YouTube

Week 5

  1. Convergence analysis of a descent algorithm - 1 YouTube
  2. Convergence analysis of a descent algorithm - 2 YouTube
  3. Implementation of an optimization algorithm in MATLAB YouTube
  4. Conjugate Gradient Methods - Introduction and Proof YouTube
  5. Visualizing Quadratic Forms YouTube
  6. Orthogonality and Conjugacy YouTube
  7. Conjugate Directions Method - Introduction and Proof YouTube
  8. Discussion on doubts YouTube

Week 6

  1. More on Conjugate Directions Method YouTube
  2. Ways of Generating Conjugate Directions YouTube
  3. Expanding Subspace Theorem YouTube
  4. Discussion on doubts YouTube
  5. Conjugate Gradient Method YouTube
  6. MATLAB implementation on CGM YouTube
  7. Discussion on doubts YouTube
  8. Preconditioned Conjugate Gradient - Part 1 YouTube
  9. Preconditioned Conjugate Gradient - Part 2 YouTube
  10. Preconditioned Conjugate Gradient - Part 3 YouTube

Week 7

  1. Non-Linear Conjugate Gradient method YouTube
  2. Intro to Newton methods YouTube
  3. Newton methods and convergence YouTube
  4. Checks for positive definite matrices YouTube
  5. Hessian Modification YouTube
  6. Quasi newton methods YouTube

Week 8

  1. BFGS method YouTube
  2. Least squares problems YouTube
  3. Linear least squares - Part 1 YouTube
  4. Linear least squares - Part 2 YouTube
  5. Solving least squares using SVD YouTube
  6. Non-linear least squares YouTube

Week 9

  1. Constrained optimisation YouTube
  2. Single equality constraint YouTube
  3. Single inequality constraint YouTube
  4. Single inequality constraint - part 2 YouTube
  5. Two inequality constraints example YouTube
  6. Linearised feasible directions YouTube

Week 10

  1. Feasible sequences and tangent cone YouTube
  2. LICQ conditions YouTube
  3. KKT conditions (First order necessary conditions) YouTube
  4. Proof sketch for KKT conditions (part 1) YouTube
  5. Proof sketch for KKT conditions (part 2) YouTube
  6. Introduction to Projected gradient descent YouTube

Week 11

  1. Projected gradient descent and proof of convergence YouTube
  2. Proof of convergence (Part 2) YouTube
  3. Subgradients and subdifferential YouTube
  4. Projection onto l1-ball YouTube
  5. Soft-thresholding example YouTube
  6. Recap of Projection onto l1-ball YouTube

Week 12

  1. KKT and duality introduction YouTube
  2. Intuition of duality and dual problem YouTube
  3. Proof of concavity of the dual problem YouTube
  4. Proof of concavity of the dual problem - Part 2 YouTube
  5. Proof of concavity of the dual problem - Part 3 YouTube

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Madras
Department
Electrical Engineering
Teacher
Prof. Uday K Khankhoje
Level
Undergraduate
Language
English
Subjects
Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed