The Research On Path-following Algorithms For A Class Of Complementary Problem

The complementary problem is an important optimization problem. It is applied in many models of society or economy, such as economy analysis, traffic equilibrium. Therefore, it is significant to study the algorithms for solving complementary problem. The thesis mainly deals with two kinds of complementary problem, which consist P-matrix nonmonotonic linear complementary problem and uniform P-function nonlinear complementary problem. A few path-following algorithms are presented in this paper. Its convergence is analyzed in detail and its numerical experiment is obtained by MATLAB.The whole thesis consists of five chapters. In chapter one, many basis knowledge are introdued. The wide-neighborhood path-following algorithms are presented in chapter two and four for different complementary problem. In generally, chapter two and three belong to linear complementary problem, however, the chapter four belongs to nonlinear complementary problem. The chapter five will be the summary and to the future forecast which will work to this paper.The formulation and the present studying situation of linear complementary problem are briefly introduced in chapter one. In order to obtain interior point algorithms for linear complementary problem, basic knowledge and theory of linear complementary problem are discussed in this chapter, including fundamental concepts, duality theory and the proof of the exist theory of solution. In addition, the sorts of linear complementary problem and the particular solutions for linear complementary problem are given in operation research in this chapter.In chapter two, N_∞(β) and N_∞~- (β) wide-neighborhood feasible and infeasible path-following algorithms for P-matrix nonmonotonic linear complementary problem is presented. The success promotes the narrow neighborhood to the wide neighborhood in nonmonotonic linear complementary problem. Its convergence is analyzed in detail and its numerical experiment is obtained.In chapter three, a generalized path-following algorithms for P-matrix nonmonotonic linear complementary problem is presented. Its convergence is analyzed and its numerical experiment is obtained.In chapter four, N _∞(β) and N_∞~- (β) wide-neighborhood feasible and infeasible path-following algorithms for uniform P-function nonlinear complementary problem is presented. The success promotes the narrow neighborhood to the wide neighborhood in nonmonotonic linear complementary problem. Its convergence is analyzed in detail and its numerical experiment is obtained.The chapter five is the summary and to the future forecast which will work to this paper.