Optimization Theory and Algorithms

ABOUT THE COURSE: 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 industryPREREQUISITES: Linear algebra is a strong pre-requisite.Knowledge of programming is suggested.INDUSTRY SUPPORT: Most data analytics or engineering companies will appreciate this course.

1. Introduction to the course - 1 - Prerequisites, key elements2. Introduction to the course - 2 - Types of problems3. Introduction to the course - 3 - an optimization example to live longer4. Summary of background material - Linear Algebra - 15. Summary of background material - Linear Algebra - 26. Summary of background material - Analysis - 17. Summary of background material - Analysis - 28. Summary of background material - Analysis - 39. Summary of background material - Calculus - 110. Summary of background material - Calculus - 211. Summary of background material - Calculus - 312. Example of multivariate differentiation13. Gradient of Quadratic form and product rule14. Directional derivative, hessian, and mean value theorem15. Unconstrained optimization - 1 - roadmap of the course and Taylor’s theorem16. Unconstrained optimization - 2 - Identifying a local minima - 1st and 2nd order conditions17. Unconstrained optimization - 3 - proof of 1st order condition (split 3)18. Unconstrained optimization - 4 - overview of algorithms and choosing a descent direction19. Unconstrained optimization - 5 - properties of descent directions - steepest descent direction20. Unconstrained optimization - 6 - properties of descent directions - newton direction21. Unconstrained optimization - 7 - trust region methods22. A MATLAB session23. Introduction to Line Search24. Wolfe conditions25. Strong Wolfe conditions26. Backtracking Line Search27. Line Search - Analysis28. Line Search - Convergence and Rate - 129. Line Search - Convergence and Rate - 230. Convergence analysis of a descent algorithm - 131. Convergence analysis of a descent algorithm - 232. Implementation of an optimization algorithm in MATLAB33. Conjugate Gradient Methods - Introduction and Proof34. Visualizing Quadratic Forms35. Orthogonality and Conjugacy36. Conjugate Directions Method - Introduction and Proof37. Discussion on doubts38. More on Conjugate Directions Method39. Ways of Generating Conjugate Directions40. Expanding Subspace Theorem41. Discussion on doubts42. Conjugate Gradient Method43. MATLAB implementation on CGM44. Discussion on doubts45. Preconditioned Conjugate Gradient - Part 146. Preconditioned Conjugate Gradient - Part 247. Preconditioned Conjugate Gradient - Part 348. Non-Linear Conjugate Gradient method49. Intro to Newton methods50. Newton methods and convergence51. Checks for positive definite matrices52. Hessian Modification53. Quasi newton methods54. BFGS method55. Least squares problems56. Linear least squares - Part 157. Linear least squares - Part 258. Solving least squares using SVD59. Non-linear least squares60. Constrained optimisation61. Single equality constraint62. Single inequality constraint63. Single inequality constraint - part 264. Two inequality constraints example65. Linearised feasible directions66. Feasible sequences and tangent cone67. LICQ conditions68. KKT conditions (First order necessary conditions)69. Proof sketch for KKT conditions (part 1)70. Proof sketch for KKT conditions (part 2)71. Introduction to Projected gradient descent72. Projected gradient descent and proof of convergence73. Proof of convergence (Part 2)74. Subgradients and subdifferential75. Projection onto l1-ball76. Soft-thresholding example77. Recap of Projection onto l1-ball78. KKT and duality introduction79. Intuition of duality and dual problem80. Proof of concavity of the dual problem81. Proof of concavity of the dual problem - Part 282. Proof of concavity of the dual problem - Part 3