最优化-lec6 Models for trust-region methods 最优化理论与方法课件（英文版－南京大学）.pptVIP

Convergence of line search methods Steepest descent methods Now we consider the ideal case, in which the objective function is quadratic and the line searches are exact. symmetric and positive definite Steepest descent methods Steepest descent methods To quantify the rate of convergence, we introduce the weighted norm The bound of decrease The bound of decrease The rate-of-convergence behavior of the steepest descent method is essentially the same on general nonlinear objective functions. Quasi-Newton methods Quasi-Newton methods ▲ ▲ Convergence Theorem Convergence Theorem Proof. We first show that Convergence Theorem For the remainder of the proof we need to look ahead to the proof of quadratic convergence of Newton’s method. Convergence Theorem Convergence Theorem Convergence Theorem Convergence Theorem Models for trust-region methods Models for trust-region methods The trust-region Newton method has proved to be highly effective in practice Line Search Methods Introduction Descent direction The search direction often has the form: steepest descent method Newton’s method quasi-Newton method an approximation to the Hessian Step length The process of determining the minimum point on a given line is called line search, which are really procedures for solving one-dimensional minimization problems The popular methods for resolving the line search problem include the Fibonacci and Golden section search, which have a certain degree of theoretical elegance. The method determines the minimum value of a function f over a closed interval [c1, c2]. f is assumed unimodal, that is, it has a single relative minimum. 单峰函数 Unimodal function * The minimum point of f is to be determined, at least approximately, by measuring the value of f at a certain number of points. How to successively select N measurement points so that we can determine the smallest possible region of uncertainty in which the minimum must lie. Fibonacci search * Fibonacci search