IND ENG 160 Lecture Notes - Lecture 7: Backtracking, Gradient Descent, Stationary Point

• School: Berkeley
• Department: Industrial Engineering And Operations Research
• Course: IND ENG 160
• Professor: Javad Lavaei

Document Summary

The two main challenges in algorithms are deciding the direction, and the step size. Generally, you choose the direction rst, and then the step size. There are three main algorithms we will look at: gradient: x = f (x)t, newton"s method : use a taylor approximation of the function, solve the quadratic to update. X = 2f (x(k 1)) 1 f (x(k 1))t : steepest descent: this is not technically part of the course, but it is basically using di erent norms to de ne the downward direction. These are only algorithms for nding the direction in which to search. We can use either exact line search or backtracking to nd the best step size after nding direction. We already talked about the straight line search. The line search will give you the best value possible, but most op- timization solvers out there do not want the sub-problems to be optimization problems, even though univariate optimization is easy.