Descent Method

• When the descent direction is opposite to gradient is is called gradient descent.
• We also have steepest descent and newton’s algorithm
• In this post we will focus on line search
• Term is called ‘line search’ because step size t determines where along the line {x + t ∇ x } next iterate will be. (ray search would be more appropriate term)

 

Fixed Step Size

• Here we keep the step size (t) constant for all the iteration
• Our solution many not converge if t is too large
• If can take a lot of time if t is too small

 

 

Exact line search

• It is used when cost of minimizing problem with one variable (s) is less than computing direction (∇ x)

 

Backtracking Line Search

• Exact line search has to solve optimization problem and become computational inefficient
• This is most widely used in practice.
• Here we don’t find optimal value of t, but some approximation

 

Demo of Convergence

 

 

 

References

• Youtube series on unconstrained minimization : https://www.youtube.com/watch?v=-kwZhTPAhIQ
• Wonderful lecture series by IISC professor Shirish Shevade :  https://nptel.ac.in/courses/106108056/
• Evergreen book : Convex optimization by Boyd