Interior Hybrid Variable Metric Proximal Method For Linear Monotone Complementarity Problem

Optimization is also called mathematical programming, which is an important branch of operations research. The optimization problem can be divided into constrained optimization problem and unconstrained optimization problem according to the range of feasible domain. In the daily life, the vast majority of problems are constrained opti-mization problems. Therefore, this thesis mainly deals with a class of problems related to constrained optimization problems: linear monotone complementarity problem. In this thesis, we first introduce the classical variational inequality problem and the linear monotone complementarity problem, and the relationship between the linear complemen-tarity problem and the monotone inclusion problem under appropriate conditions. Then we study the interior point method of linear monotone complementary problem, and a interior proximal method with hybrid variable metric technique is mainly discussed. At last, we summarize the application of the algorithm in some optimization problems.The whole thesis can be divided into the following three chapters.In the first chapter ,we mainly introduces the variational inequality problem and the complementarity problem, and introduces several existing kinds of internalized methods on the variational inequality problem and their advantages and disadvantages, then gives the concepts, definitions and symbolic representations involved in this thesis.In the second chapter, we mainly study the interior point method of linear monotone complementary problem. This kind of the methods has a lot, Most of them solve the problem by transforming the original problem into the monotone inclusion problem by introducing a quadratic logarithmic barrier function. But, when the solution of the linear monotonic complementarity problem is unbounded or there is a non-positive component,the nonlinear quadratic logarithmic function will be meaningless. In this thesis, we consider the infeasible path-following methods based on the quadratic logarithmic barrier function, apply Newton steps to iteration. In this way, the algorithm can still be executed when the solution of the original problem is unbounded or non-positive, and it is easy to find the initial point to satisfy the central path. On the other hand, we introduce the error term and give the approximate solution of the subproblem under appropriate conditions.It is proved that the approximate solution of the subproblem is in the logarithmic center path. At the same time, we prove that all the iterative points generated by interior point proximal method with hybrid variable metric technique are interior point, and the convergence analysis of the algorithm is given.Chapter 3, practical application. This chapter mainly introduces the application of interior hybrid variable metric proximal method in some optimization problems. T-wo practical examples are given, one is the solution to the least squares problem of nonnegative constraint and the other is the solution of the saddle points problem of convex-concave function.Upon the completion of this thesis, I have come up with a new research work (see appendix).