On Efficiency Analysis Of Newton-PCG Like Algorithms

In unconstrained optimization, we deal with the standard problem of finding the minimumof a function f: Rn - R. If we assume that the function is twice continuously differentiable,many methods can be aPplied to find the minimum. One of classic methods is Newton'smethod, which is wide used and has penetrated many field8. But one of its disadvantagesis that the cost of solving the Newton equation is large. The reason is that the Choleskifactorization of the Hessian V'f is expensive.One way to get around this difficulty is to modify the original Newton's method as inex-act Newton method. Thanks to the inexact Newton methods theorem discovered by Dembo,Eisenstat and Steihaug in 1982, many ingenious techniques have been proposed in recentyears. A most popular choice is some variant of the lineax conjugate gradient (CG) method.Due to the convergence of CG method is strongly dependent on the condition number ofthe Hessian, the inexact Newton method with CG subiterations will be powerful if these CGsubiterations are replaced by preconditioned CG subiterations with suitable preconditioner.So, a great deal of research work focuses on Newton-PCG(Preconditioned CG method) likemethods. The achievements are presented in the papers such as [2], [10], f11l, f13], [l5l, [161,[18], [21], [23], I261, [271, [29], [30] and so on. Among these paPers, many powerful algo-rithms have been developed. It has been shown by a large amount of numericaI experimentsthat, general1y speaking, they are very successful. However, their 8uccess varies greatly fromproblem to problem [22], and the superiority of them is usually shown by numerical resultsonly.Whether the inexact Newton method with PCG subiterations is more efficient than New-ton's method? If yes, How efficient the inexact Newton method with PCG subiterations canbe compared with Newton's method? Is there theoretical 8upport? If yes, How about thenumerical experiments?In this thesis, we answer the above questions. We show that Newton-PCG like rnethod ismore efficient than Newton's method by theoretical analysis and numerical experiments. Wealso show the superiority by quantitative index from the theoretical point of view.The thesis has the following structure: in ChaPter 1, we look at the evolution of theidea behind the Newton-PCG like methods. In Chapter 2, we present two extensions of thefundamental concepts-convergence order and efficiency index, which are needed to analysis the efficiency. In Chapter 3, we give three new Newton-PCG like algorithms. One is established in the case which Newton's method has high but uncertain order. The other two are concerned with the case in which Newton's method has at least Q-order 2. Then we deeply analysis their efficiency from the theoretical point of view in Chapter 4. In Chapter 5, we give our numerical results on them compared with Newton's method.The contributions of this thesis can be found in Chapter 3, 4 and 5. In Chapter 3, we establish Algorithm CF-PCGI, CF-PCGII and CF-PCGIII. Specially, we get the PCG subit-erations numbers of Algorithm CF-PCGI by comprehensive studying on a one-dimensional optimization problem in section 3.1.1. In Chapter 4, we analysis the theoretical efficiency of the above three algorithms in detail and show the superiority by quantitative index. Finally, the results and conclusions of the numerical experiments in Chapter 5 are also new contributions to the field.