Study On The Algorithms For Variational Inequalities And Related Problems

Variational inequality, nonlinear complementarity problem and maximal monotoneinclusion problem have been widely studied due to their extensive application back-grounds. These problems have very closely relationships, nonlinear complementarity prob-lem is a special case of variational inequality, and variational inequality is a special caseof inclusion problem. Projection methods are considered as a kind of efcient methods tosolve these problems. They do not involve the derivative information of underlying func-tions and other complicated operations, and are ft for the large-scale problems whosefeasible regions are comparatively simple. This thesis considers the projection methodsfor variational inequalities, nonlinear complementarity problems and maximal monotoneinclusion problems, and mainly concentrates on the design of algorithms, convergenceanalyses and numerical implementations. The author’s major contributions are outlinedas follows:1. Korpelevich extragradient method is one of the efcient methods for variational in-equalities. Motivated by this method, a modifed prediction-correction projection methodis presented for variational inequalities. Under the assumption that the underlying func-tion is co-coercive, the global convergence of the proposed algorithm is established. Undersome suitable assumptions, the method is proved to be convergent linearly. Some prelim-inary computational results are reported, which indicated that the proposed method isefcient.2. A LQP method for solving variational inequalities on the polyhedra is presented.Firstly, by adding a Lagrange multiplier, translate the variational inequality on the poly-hedra to a variational inequality on the frst octant. Then, solve the equivalent prob-lem instead of the original problem by proposing a LQP prediction-correction projectionmethod. Under the assumptions that the underlying function is continuous and monotone,global convergence of the method is proved. Numerical results show that the proposedmethod is viable and efcient.3. Nonlinear complementarity problem is a special kind of variational inequalitywith the feasible region is the frst octant. It is an important optimization problem.Based on the classical LQP method, two projection methods are presented for solvingnonlinear complementarity problems. Under the assumptions that the underlying functionis continuous and pseudomonotone, the global convergence of the proposed methods areestablished respectively. Some preliminary computational results are reported. 4. Proximal point algorithm is a classical method for maximal monotone inclusionproblems. It is simple, but hard to implement. Based on the proximal point algorithm, aprediction-correction projection algorithm for fnding zeros of maximal monotone opera-tors in Euclidean spaces is presented. The proposed method adopts the inexact proximalpoint algorithm as prediction step, and uses a convex combination of the current iterationas correction step. Some existing methods can be thought of the special cases of the pro-posed method. Only under the assumption that the solution set is nonempty, the methodis proved to be global convergent. Numerical results show that the method is viable andefcient．5. By combining the proximal subproblem with a convex combination of the cur-rent iteration, a projection algorithm for fnding zeros of maximal monotone operators inHilbert spaces is presented. Compared with some existing methods, the proposed methodtakes advantage of more information on the current iterations. Only under the assump-tion that the solution set is nonempty, the method is proved to be convergent strongly.For practical implementation, two applications of the proposed algorithm, the convexprogramming problems and the generalized variational inequalities, are presented. Atthe same time, a Mann-type algorithm is proposed and its weak convergence analysis isestablished.