Homotopy JFNK Method For Solving Nonlinear Programming

Homotopy continuous method has already become a convergent algorithm with wide range which is widely used in nonlinear programming. It could be commendable to get the KKT point of the original nonlinear programming problem through constructing an appropriate homotopy, and after tracking its numerical path. However, with the scale of the problems to be increasing, its algorithmic efficiency urgently needs to be improved.JFNK method has been developing into one kind of high-efficient algorithm specially for solving large-scale and sparse nonlinear equations with two significant advantages:The first one is that the computation cost could be highly reduced due to the fact that Krylov subspace iteration method is employed for solving Newton equations inexactly; And the second one is that it is only required for the product of Jacobian matrix and vector which could be replaced by the difference of vector function when using Krylov subspace iteration method. Therefore, the storage capacity could be greatly economized because there is no need to form or store the Jacobian matrix.This paper brings Jacobian-Free Newton-GMRES method into three homotopy methods which are selected as CHIP, ACH and FACH, aiming to eliminate some drawbacks of the low efficiency such as "excessively solving" caused by traditional Newton-PLU method in the corrector stage of the path tracking process. Within JFNK, three typical algorithms:GMRES, BICGSTAB and TFQMR are chosen from the Krylov subspace methods which are adopted to conduct Comparative experiments with traditional Newton-PLU method in CUTEr-Matlab test environment under Linux platform. The numerical results demonstrate that the execution efficiencies of the improved homotopy methods have been greatly improved. And the JFNK method with GMRES performs best compared with its counterparts embedded with BICGSTAB and TFQMR in the three Krylov subspace methods. Consequently, these homotopy methods embedded by JFNG are well worthwhile to be generalized to the engineering application.The structure of this thesis is arranged as follows:The first chapter introduces the research background, the significance of selected topic, the phylogeny of homotopy method and the current research situation; The second chapter presents three homotopy methods, providing theoretical foil and algorithmic support for the follow-up studies; In Chapter 3, Combining with inexact Newton method and Krylov subspace methods, we propose the modified homotopy methods embedded with JFNK method as a subroutine for its corrector phase. The fourth chapter provides the numerical experiments, as part of the whole thesis.Firstly, we recount the configuration process of CUTEr test environment and under which comparative experiments are conducted on the homotopy methods before and after the improvement. Finally, conclusion part presents a short introduction to the main achievements made in this paper.