Affine Linear Constrained Optimization Point Preconditioned Conjugate Gradient Path Method

In this thesis, we propose an affine scaling projected interior method via reduced precondi-tional conjugate gradient path for the linear equality optimization subject to bounds on variables.Conjugate gradient method, which can be easily computed and requires no matrix storage, is one of the most popular and useful method for solving large scale optimization problems. The idea of conjugate gradient path in unconstrained optimization irradiates us to use this method for solving the linear equality optimization subject to bounds on variables. By using the generalized elimination method, the subproblem is equivalent to an unconstrained optimization problem in the null space. The path is defined as linear combination of a sequence of conjugate directions which are obtained by applying conjugate direction method to the approximate quadratic function in the null space. The properties of the path which are similar to the trust region method are important to the proof of the global convergence of the proposed algorithm. It is unlikely that the reduced matrix will be sufficiently sparse, so we develop preconditioners based on an extended system. It is possible the trust region subproblem with the strictly feasible constraint needs to be resolved many times before obtaining an acceptable strict interior feasible step, and hence the total computation for completing one iteration might be expensive and difficult. In order to overcome the difficulties, we introduce an affine scaling matrix, and form the affine scaling reduced preconditional conjugate gradient path to obtain a new accepted step. We use the line search method by employing the backtracking steps at an unsuccessful trial step to obtain a new iterative point. The proposed algorithm not only has global convergence but also local convergence rate.The thesis consists of five parts. In Chapter 1, we summarize the basic concepts and theories of optimization technique. In Chapter 2, based on the structure and properties of the affine scaling reduced preconditional conjugate gradient path, we describe the algorithm which combines the techniques of reduced preconditional technology, conjugate gradient path, interior point, and linear backtracking search strategy. In Chapter 3, based on the good properties of the conjugate gradient path, global convergence and local convergence rate of the proposed method are established under some reasonable conditions. In Chapter 4, numerical results indicate that the algorithm is useful and effective in practice. Finally, Chapter 5 concludes the main results of this thesis and proposes some further research directions about our work.