# Optimization Theory and Algorithms

- Institution: IIT Madras
- Department: Electrical Engineering
- Teacher: Prof. Uday K Khankhoje
- Level: Undergraduate
- Language: English
- Subjects: Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/108106478)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/108106478)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

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

1. [Introduction to the course - 1 - Prerequisites, key elements](https://invisiblenetwork.ai/learn/nptel/108106478/f98fc3a45083) (YouTube)
2. [Introduction to the course - 2 - Types of problems](https://invisiblenetwork.ai/learn/nptel/108106478/45eac1991810) (YouTube)
3. [Introduction to the course - 3 - an optimization example to live longer](https://invisiblenetwork.ai/learn/nptel/108106478/83036c5509b9) (YouTube)
4. [Summary of background material - Linear Algebra 1](https://invisiblenetwork.ai/learn/nptel/108106478/53d248631624) (YouTube)
5. [Summary of background material - Linear Algebra II](https://invisiblenetwork.ai/learn/nptel/108106478/370efce8cbad) (YouTube)
6. [Summary of background material - Analysis I](https://invisiblenetwork.ai/learn/nptel/108106478/cfe21491e22b) (YouTube)
7. [Summary of background material - Analysis II](https://invisiblenetwork.ai/learn/nptel/108106478/6e7372ef889d) (YouTube)
8. [Summary of background material - Analysis III](https://invisiblenetwork.ai/learn/nptel/108106478/e097cbdcdd54) (YouTube)
9. [Summary of background material - Calculus 1](https://invisiblenetwork.ai/learn/nptel/108106478/2c8564d42ff0) (YouTube)
10. [Summary of background material - Calculus 2](https://invisiblenetwork.ai/learn/nptel/108106478/da6c294011f9) (YouTube)
11. [Summary of background material - Calculus 3](https://invisiblenetwork.ai/learn/nptel/108106478/39de14cb0b28) (YouTube)
12. [Example of Multivariate Differentiation](https://invisiblenetwork.ai/learn/nptel/108106478/00cb5fac1c30) (YouTube)
13. [Gradient of Quadratic form and product rule](https://invisiblenetwork.ai/learn/nptel/108106478/a6f150876f98) (YouTube)
14. [Directional derivative, hessian, and mean value theorem](https://invisiblenetwork.ai/learn/nptel/108106478/1fb57dbfa849) (YouTube)
15. [Unconstrained optimization - 1 - roadmap of the course and Taylor’s theorem](https://invisiblenetwork.ai/learn/nptel/108106478/9d4d65a75e74) (YouTube)
16. [Unconstrained optimization - 2 - Identifying a local minima - 1st and 2nd order conditions](https://invisiblenetwork.ai/learn/nptel/108106478/4daecc6c2d6b) (YouTube)
17. [Unconstrained optimization - 3 - proof of 1st order condition (split 3)](https://invisiblenetwork.ai/learn/nptel/108106478/5f9f6879cc85) (YouTube)
18. [Unconstrained optimization - 4 - overview of algorithms and choosing a descent direction](https://invisiblenetwork.ai/learn/nptel/108106478/a3ab337a0d7b) (YouTube)
19. [Unconstrained optimization - 5 - properties of descent directions - steepest descent direction](https://invisiblenetwork.ai/learn/nptel/108106478/38cbd0cfe56b) (YouTube)
20. [Unconstrained optimization - 6 - properties of descent directions - newton direction](https://invisiblenetwork.ai/learn/nptel/108106478/94a4ff55992e) (YouTube)
21. [Unconstrained optimization - 7 - trust region methods](https://invisiblenetwork.ai/learn/nptel/108106478/d21d0b08c8fc) (YouTube)
22. [A MATLAB session](https://invisiblenetwork.ai/learn/nptel/108106478/8ec983e548f7) (YouTube)
23. [Introduction to Line Search](https://invisiblenetwork.ai/learn/nptel/108106478/985ff5ec2ab7) (YouTube)
24. [Wolfe conditions](https://invisiblenetwork.ai/learn/nptel/108106478/12793169b3da) (YouTube)
25. [Strong Wolfe conditions](https://invisiblenetwork.ai/learn/nptel/108106478/5330579c5e39) (YouTube)
26. [Backtracking Line Search](https://invisiblenetwork.ai/learn/nptel/108106478/960ab92897de) (YouTube)
27. [Line Search - Analysis](https://invisiblenetwork.ai/learn/nptel/108106478/fb12af0fc265) (YouTube)
28. [Line Search - Convergence and Rate - 1](https://invisiblenetwork.ai/learn/nptel/108106478/ee3cee2fea41) (YouTube)
29. [Line Search - Convergence and Rate - 2](https://invisiblenetwork.ai/learn/nptel/108106478/aa4581a2755a) (YouTube)
30. [Convergence analysis of a descent algorithm - 1](https://invisiblenetwork.ai/learn/nptel/108106478/71236d305687) (YouTube)
31. [Convergence analysis of a descent algorithm - 2](https://invisiblenetwork.ai/learn/nptel/108106478/5f6cd3b816ed) (YouTube)
32. [Implementation of an optimization algorithm in MATLAB](https://invisiblenetwork.ai/learn/nptel/108106478/d527aaff9f5f) (YouTube)
33. [Conjugate Gradient Methods - Introduction and Proof](https://invisiblenetwork.ai/learn/nptel/108106478/4218d86644a8) (YouTube)
34. [Visualizing Quadratic Forms](https://invisiblenetwork.ai/learn/nptel/108106478/8dbc366aa1e3) (YouTube)
35. [Orthogonality and Conjugacy](https://invisiblenetwork.ai/learn/nptel/108106478/290aeb71d7f8) (YouTube)
36. [Conjugate Directions Method - Introduction and Proof](https://invisiblenetwork.ai/learn/nptel/108106478/736ea9ee3180) (YouTube)
37. [Discussion on doubts](https://invisiblenetwork.ai/learn/nptel/108106478/6f4a07ca579f) (YouTube)
38. [More on Conjugate Directions Method](https://invisiblenetwork.ai/learn/nptel/108106478/0fa21196b17e) (YouTube)
39. [Ways of Generating Conjugate Directions](https://invisiblenetwork.ai/learn/nptel/108106478/33e3d187a26b) (YouTube)
40. [Expanding Subspace Theorem](https://invisiblenetwork.ai/learn/nptel/108106478/d76c03d267ba) (YouTube)
41. [Discussion on doubts](https://invisiblenetwork.ai/learn/nptel/108106478/105c70136d6a) (YouTube)
42. [Conjugate Gradient Method](https://invisiblenetwork.ai/learn/nptel/108106478/74c18a0f49c8) (YouTube)
43. [MATLAB implementation on CGM](https://invisiblenetwork.ai/learn/nptel/108106478/e3088753693e) (YouTube)
44. [Discussion on doubts](https://invisiblenetwork.ai/learn/nptel/108106478/b6ec9b870644) (YouTube)
45. [Preconditioned Conjugate Gradient - Part 1](https://invisiblenetwork.ai/learn/nptel/108106478/710cf6cd38af) (YouTube)
46. [Preconditioned Conjugate Gradient - Part 2](https://invisiblenetwork.ai/learn/nptel/108106478/af5fb4f09c28) (YouTube)
47. [Preconditioned Conjugate Gradient - Part 3](https://invisiblenetwork.ai/learn/nptel/108106478/3e681a96c1b4) (YouTube)
48. [Non-Linear Conjugate Gradient method](https://invisiblenetwork.ai/learn/nptel/108106478/c5c5db9d5ff1) (YouTube)
49. [Intro to Newton methods](https://invisiblenetwork.ai/learn/nptel/108106478/466c9708f654) (YouTube)
50. [Newton methods and convergence](https://invisiblenetwork.ai/learn/nptel/108106478/5654c0567310) (YouTube)
51. [Checks for positive definite matrices](https://invisiblenetwork.ai/learn/nptel/108106478/bd509cdeea7a) (YouTube)
52. [Hessian Modification](https://invisiblenetwork.ai/learn/nptel/108106478/50d54d55b22e) (YouTube)
53. [Quasi newton methods](https://invisiblenetwork.ai/learn/nptel/108106478/cd237588bf4f) (YouTube)
54. [BFGS method](https://invisiblenetwork.ai/learn/nptel/108106478/407a326dcd30) (YouTube)
55. [Least squares problems](https://invisiblenetwork.ai/learn/nptel/108106478/6eb1eef33821) (YouTube)
56. [Linear least squares - Part 1](https://invisiblenetwork.ai/learn/nptel/108106478/4f33fac0700b) (YouTube)
57. [Linear least squares - Part 2](https://invisiblenetwork.ai/learn/nptel/108106478/fa0b55d3e20b) (YouTube)
58. [Solving least squares using SVD](https://invisiblenetwork.ai/learn/nptel/108106478/ef25be0f27b3) (YouTube)
59. [Non-linear least squares](https://invisiblenetwork.ai/learn/nptel/108106478/120c12834f12) (YouTube)
60. [Constrained optimisation](https://invisiblenetwork.ai/learn/nptel/108106478/5b42a17c18d2) (YouTube)
61. [Single equality constraint](https://invisiblenetwork.ai/learn/nptel/108106478/10f767e4ebf2) (YouTube)
62. [Single inequality constraint](https://invisiblenetwork.ai/learn/nptel/108106478/27c0331d6a3d) (YouTube)
63. [Single inequality constraint - part 2](https://invisiblenetwork.ai/learn/nptel/108106478/aa9682a5c395) (YouTube)
64. [Two inequality constraints example](https://invisiblenetwork.ai/learn/nptel/108106478/a32821a76370) (YouTube)
65. [Linearised feasible directions](https://invisiblenetwork.ai/learn/nptel/108106478/cacbd81cb6c6) (YouTube)
66. [Feasible sequences and tangent cone](https://invisiblenetwork.ai/learn/nptel/108106478/6619e8d82454) (YouTube)
67. [LICQ conditions](https://invisiblenetwork.ai/learn/nptel/108106478/17418e91ca87) (YouTube)
68. [KKT conditions (First order necessary conditions)](https://invisiblenetwork.ai/learn/nptel/108106478/2169f31154a8) (YouTube)
69. [Proof sketch for KKT conditions (part 1)](https://invisiblenetwork.ai/learn/nptel/108106478/5ced9b6b3e84) (YouTube)
70. [Proof sketch for KKT conditions (part 2)](https://invisiblenetwork.ai/learn/nptel/108106478/3faa4cf546e9) (YouTube)
71. [Introduction to Projected gradient descent](https://invisiblenetwork.ai/learn/nptel/108106478/ad08119f2d41) (YouTube)
72. [Projected gradient descent and proof of convergence](https://invisiblenetwork.ai/learn/nptel/108106478/01b844a2f861) (YouTube)
73. [Proof of convergence (Part 2)](https://invisiblenetwork.ai/learn/nptel/108106478/f0294f6e9f75) (YouTube)
74. [Subgradients and subdifferential](https://invisiblenetwork.ai/learn/nptel/108106478/a6f084df26e2) (YouTube)
75. [Projection onto l1-ball](https://invisiblenetwork.ai/learn/nptel/108106478/7d3fc50869a9) (YouTube)
76. [Soft-thresholding example](https://invisiblenetwork.ai/learn/nptel/108106478/a683ae9e67c6) (YouTube)
77. [Recap of Projection onto l1-ball](https://invisiblenetwork.ai/learn/nptel/108106478/d205b8163eb3) (YouTube)
78. [KKT and duality introduction](https://invisiblenetwork.ai/learn/nptel/108106478/3f5da685092e) (YouTube)
79. [Intuition of duality and dual problem](https://invisiblenetwork.ai/learn/nptel/108106478/0d369be821c0) (YouTube)
80. [Proof of concavity of the dual problem](https://invisiblenetwork.ai/learn/nptel/108106478/61aec2762cc0) (YouTube)
81. [Proof of concavity of the dual problem - Part 2](https://invisiblenetwork.ai/learn/nptel/108106478/9bb9cc5419fa) (YouTube)
82. [Proof of concavity of the dual problem - Part 3](https://invisiblenetwork.ai/learn/nptel/108106478/5a1c20800ec4) (YouTube)