Font Size: a A A

Research On Methods For Large-Scale Nonlinear Equations And Unconstrained Optimization

Posted on:2009-02-03Degree:DoctorType:Dissertation
Country:ChinaCandidate:H LiuFull Text:PDF
GTID:1480303377969989Subject:Management Science and Engineering
Abstract/Summary:PDF Full Text Request
Nonlinear Optimization is an important branch of Operation Research. However, nonlinear equations are closely related to nonlinear optimization. In this dissertation, Newton methods for large-scale nonlinear equations, limited memory methods for large-scale unconstrained optimization and direct search methods with quadratic interpolation model for unconstrained optimization are systematically explored and some new results are obtained. There are three parts and eight chapters in the thesis.Chapter 1 is introductory. The purposes, significance, contents and its status of this thesis are discussed.Chapter 2 is some preliminary knowledge about the topics of this thesis. Newton method and some modified Newton methods for nonlinear equations are discussed in Section 2.1, truncated Newtom method, trust region Newton method and conjugated gradient methods are explored in Section 2.2, and further the history and the thoughts of direct search methods and three direct search methods named simplex method, pattern search method, line search method are introduced in Section 2.3. The main idea,the development, recent progress and properties of the three methods are also discussed.In Chapter 3, the structure of Jacobian matrix of nonlinear equations are explored, and a new modified Newton method which only uses the partial elements of the Jacobian matrix to obtain the next iteration point is presented. This new method is refered to as incomplete Newton method. The conditions of linear, superlinear and quadratic convergence of incomplete Newton method are given and the local convergence results are analyzed and proved. Some special incomplete Newton algorithms are designed and discussed in detail. Numerical experiments for some special incomplete Newton algorithms are done. The numerical results show that incomplete Newton method is promising for large-scale nonlinear equations with dense Jacobian matrix satisfying some special properties.Limited memory methods for large-scale nonlinear optimization problems are surveyed in Chapter 3. Combined limited memory technique with nonmonotone linear search, two new limited memory methods for large-scale nonlinear optimization are proposed. Convergence results are given and proved. A lot of numerical experiments with standard test functions are done of the two algorithms. The numerical results show that the two algorithms are very efficient for large-scale unconstrained optimization.The direct search algorithms and theory with quadratic interpolation model are discussed from Chapter 5 to Chapter 7. First the source and development of derict search methods with quadratic interpolation model is introduced in Chapter 5. And then, a new class of direct search method based on Lagrange interpolation quadratic model under a new kind of adequateness of the interpolation sets is proposed. The global convergence of this class of algorithms is proved under mild conditions.In order to reduce the linear algebra computation such that large-scale unconstrained optimization problems are solved, a direct search algorithm based on quadratic tridiagonal interpolation model in Chapter 5 is developed. The global convergent property of this algorithm is explored. Compared with general algorithm based on usual quadratic interpolation model, numerical experiments are also done.In Chapter 7, the sensitivity of parmeters in direct search method based on Lagrange quadratic interpolation model is examined. These parmeters are related to the initial radius, the step acceptance and updating of the trust region. According to 610 thousand times numerical experiments of twenty standard test functions, it is shown that the numerical efficiency of the direct search algorithm is very sensitive to the initial radius, and insensitive to the parameters related to the step acceptance and updating of the trust region. Numerical tests show that initial interpolation radius should be equal to initial trust region radius. Recommended ranges of values for initial radius and the values of other parameters are exhibited on the basis of extensive numerical tests, which is beneficial to the implementation of the algorithm and engineering.In the last, all the algorithms developed in the thesis are summarized and some problems that are worthwhile for further research are proposed.
Keywords/Search Tags:large-scale nonlinear equations, incomplete Newton method, unconstained optimization, limited memory methods, nonmonotone linear search, direct search methods, quadratic interpolation model method, parameters analysis
PDF Full Text Request
Related items