Learn · Optimization Theory and Algorithms
Lecture 48 of 82Week 7
Non-Linear Conjugate Gradient method
Prof. Uday K Khankhoje · IIT Madras
Credits and licence
- From
- Optimization Theory and Algorithms, IIT Madras (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Introduction to the course - 1 - Prerequisites, key elements
- Introduction to the course - 2 - Types of problems
- Introduction to the course - 3 - an optimization example to live longer
- Summary of background material - Linear Algebra 1
- Summary of background material - Linear Algebra II
- Summary of background material - Analysis I
- Summary of background material - Analysis II
- Summary of background material - Analysis III
- Summary of background material - Calculus 1
- Summary of background material - Calculus 2
- Summary of background material - Calculus 3
- Example of Multivariate Differentiation
- Gradient of Quadratic form and product rule
- Directional derivative, hessian, and mean value theorem
- Unconstrained optimization - 1 - roadmap of the course and Taylor’s theorem
- Unconstrained optimization - 2 - Identifying a local minima - 1st and 2nd order conditions
- Unconstrained optimization - 3 - proof of 1st order condition (split 3)
- Unconstrained optimization - 4 - overview of algorithms and choosing a descent direction
- Unconstrained optimization - 5 - properties of descent directions - steepest descent direction
- Unconstrained optimization - 6 - properties of descent directions - newton direction
- Unconstrained optimization - 7 - trust region methods
- A MATLAB session
- Introduction to Line Search
- Wolfe conditions
- Strong Wolfe conditions
- Backtracking Line Search
- Line Search - Analysis
- Line Search - Convergence and Rate - 1
- Line Search - Convergence and Rate - 2
- Convergence analysis of a descent algorithm - 1
- Convergence analysis of a descent algorithm - 2
- Implementation of an optimization algorithm in MATLAB
- Conjugate Gradient Methods - Introduction and Proof
- Visualizing Quadratic Forms
- Orthogonality and Conjugacy
- Conjugate Directions Method - Introduction and Proof
- Discussion on doubts
- More on Conjugate Directions Method
- Ways of Generating Conjugate Directions
- Expanding Subspace Theorem
- Discussion on doubts
- Conjugate Gradient Method
- MATLAB implementation on CGM
- Discussion on doubts
- Preconditioned Conjugate Gradient - Part 1
- Preconditioned Conjugate Gradient - Part 2
- Preconditioned Conjugate Gradient - Part 3
- Non-Linear Conjugate Gradient method
- Intro to Newton methods
- Newton methods and convergence
- Checks for positive definite matrices
- Hessian Modification
- Quasi newton methods
- BFGS method
- Least squares problems
- Linear least squares - Part 1
- Linear least squares - Part 2
- Solving least squares using SVD
- Non-linear least squares
- Constrained optimisation
- Single equality constraint
- Single inequality constraint
- Single inequality constraint - part 2
- Two inequality constraints example
- Linearised feasible directions
- Feasible sequences and tangent cone
- LICQ conditions
- KKT conditions (First order necessary conditions)
- Proof sketch for KKT conditions (part 1)
- Proof sketch for KKT conditions (part 2)
- Introduction to Projected gradient descent
- Projected gradient descent and proof of convergence
- Proof of convergence (Part 2)
- Subgradients and subdifferential
- Projection onto l1-ball
- Soft-thresholding example
- Recap of Projection onto l1-ball
- KKT and duality introduction
- Intuition of duality and dual problem
- Proof of concavity of the dual problem
- Proof of concavity of the dual problem - Part 2
- Proof of concavity of the dual problem - Part 3