Pseudo-newton Trust Region. Goldstein, Line Search Algorithm And Its Convergence

Seeking fast theoretical convergence and effective algorithms in unconstrained optimization, especially in unconstrained optimization problem, is a very interested research topic for the optimization specialists and engineers. Line search methods and trust region algorithms are two very important efficient methods when applied to unconstrained optimization. In order to fully utilize the advantages of these two methods, more and more new algorithms are proposed,most of them have good numerical results. In this paper we present a new trust region algorithm combining these two methods.Line search methods have been used to be a kind of the most important algorithms to solve unconstrained optimization problems, with the the in-depth study of quasi-Newton algorithm, the study of some non-quasi-Newton algorithm based on the modified Newton equation attract many scholars.In 1991,Ya-Xiang Yuan proposed a modified BFGS algorithm, in 1995,Zhao and Yi proposed a pseudo-Newton-δ algorithm, they proved that the algorithm under Goldstein line search was globally convergent when applied to a general objective function.in 1997,Lanping Chen and Baocong Jiao proposed a new class of non-quasi-Newton algorithms.Although some of these algorithms are not satisfied the quasi-Newton equation,they possess second-degree terminating property,and the sequence of metrics remain symmetric and positive definite,also the global and super-linear convergence properties.Trust region algorithm is a very important kind of numerical calculation methods for nonlinear optimization, which attracts more and more attention of the optimization specialists and engineers, it's easy for the large-scale unconstrained and constrained optimization methods with sparse Hessian matrix, this is because when we used Newton method to the sparse unconstrained problems, it is difficult to maintain the symmetric and positive definite properties of the matrix, but trust region methods can solve this problem by solving a subproblem with a constrained condition.Compared with Line search methods,trust region algorithm not only has a strong convergence , it can deal with pathological problems effectively,and it needs less iterations, but it costs much,and it's difficult to get the iterative points,but for the Line search methods,it is easy. To get the advantages of the two methods, Jorge Nocedal and Ya-xiang Yuan proposed a thought of combining line search method and trust region algorithm to construct a new calculation methods in 1991.Deng proposed a non-monotonous trust region algorithm in 1993, and he proved the superiority of that algorithm. E.Michael Gertz proposed a new trust region algorithm with the line search, this new algorithm not only does not resolve the subproblem but also satisfies the quasi-Newton condition at each iteration and simultaneously maintains a positive-definite approximation to the Hessian of the objective function.Considering the advantages and disadvantages of the above two algorithms, we present a new trust region algorithm with Goldstein rule,based on pseudo-Newton-δ formula.it satisfies the non-quasi-Newton equation,and it's a new class of algorithm for unconstrained optimization.Numerical results show its efficiency.In chapter 1, we first introduce the development of optimization and some extensive optimality conditions which to decide the optimum solution. We review several extensive derivative descent methods of unconstrained programming.In chapter 2, the pseudo-Newton trust region algorithm for unconstrained optimization is investigated. Goldstein line search procedure is introduced, Under the convexity assumption on objective function, the global convergence of this new method is proved, we also present its numerical experiments in order to indicate that this algorithm is very effective.In chapter 3, we presents a new non-quasi-Newton trust region algorithm,and we proved it's global convergence properties.