最优化理论与方法lec6unconstrained课件

1、Models for trust-region methodsModels for trust-region methodsThe trust-region Newton method has proved to be highly effective in practice Line Search MethodsIntroductionDescent directionThe search direction often has the form:steepest descent method Newtons method quasi-Newton method an approximati

2、on 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, w

3、hich 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 function7 The minimum point of f is to be determined, at least approximately, by me

4、asuring 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 search8Fibonacci search9Golden section search10 If the number N of allowed measurement po

5、ints in a Fibonacci search is made to approach infinity, we obtain the golden section method.The interval of uncertainty at any point in the process has width:Step lengthInexact line search Two Stages : A bracketing phase finds an interval A bisection or interpolation phase computes a good step leng

6、th Termination conditionThe Wolfe conditionsArmijo condition Sufficient decrease condition The Wolfe conditionsThe Wolfe conditionsCurvature condition The Wolfe conditions The Wolfe conditionsThe strong Wolfe conditionsThe existence of the step lengthThe existence of the step length(1)(2)Combining (

7、1) and (2) givesThe strong Wolfe conditions hold in the same interval. The Goldstein conditionsSufficient decrease condition Introduced to control the step length from below The Goldstein conditionsConvergence of line search methodsConvergence of line search methodsZoutendijk Condition Convergence o

8、f line search methodswhile the Lipschitz condition implies thatSubstituting this inequality into the first Wolfe condition, we obtainConvergence of line search methodssumming allConvergence of line search methodsThis limit can be used in turn to derive global convergence results for line search algo

9、rithms. globally convergent Convergence of line search methodsSteepest 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 methodsSteepest descent methods To quantify the rate of

10、 convergence, we introducethe weighted normThe bound of decreaseThe bound of decreaseThe rate-of-convergence behavior of the steepest descent method is essentially the same on general nonlinear objective functions. Quasi-Newton methodsQuasi-Newton methodsConvergence TheoremConvergence TheoremProof. We first show that Convergence TheoremFor the remainder of the