Line Search Methods for Unconstrained Optimisation

line Search Methods forUnconstrained OptimisationLecture 8, Numerical Linear Algebra and OptimisationOxford University Computing Laboratory, MT 2007Dr Raphael Hauser Generic FrameworkFor the purposes of this lecture we consider the Unconstrained minimisationproblem(UCM) minx Rnf(x),wheref C1(Rn,R) with Lipschitz continous gradientg(x). In practice, these smoothness assumptions are sometimes violated,butthe algorithms we will develop are still observed to work well. The algorithms we will construct have the common feature that, startingfrom an initial educated guessx0 Rnfor a solution of (UCM), a sequenceof solutions (xk)N Rnis produced such thatxk x Rnsuch that the first and second order necessary optimality conditionsg(x ) = 0,H(x ) 0 (positive semidefiniteness)are satisfied. We usually wish to make progress towards solving (UCM) in every itera-tion, that is, we will constructxk+1so thatf(xk+1)< f(xk)(descent Methods ). In practice we cannot usually computex precisely ( , give a symbolicrepresentation of it, see the LP lecture!)

Generic Line Search Method: 1. Pick an initial iterate x0 by educated guess, set k = 0. 2. Until xk has converged, i) Calculate a search direction pk from xk, ensuring that this direction is a descent direction, that is, [gk]Tpk < 0 if gk 6= 0 , so that for small enough steps away from xk in the direction pk the objective function will be reduced.

Loading..

Tags:

  Methods, Line, Search, Line search methods, Line search

Information

Related search queries