Variable Inequality Problem Affine Interior Point Trust Region Methods And Applications

Variational inequality problem arises from mathematical physics problems and nonlinear programming. It has been widely used to formulate and study various equilibrium models arising in economics, operations research, transportation problems and regional sciences for a long time. The effective solution for variational inequality problem is becoming a main field of approaches for variational inequality problem because it plays an important role in mathematical programming. Since it is rather difficult to solve variational inequality problem directly, many indirect methods have been developed, in which one important branch is transforming variational inequality problem into equivalent (un)constrained optimization problems.The study of theory and methods of nonlinear (un)constrained optimization is composed of two parts, i.e., global convergence and local convergent rate. Both line search technique and trust region strategy are well-accepted methods in the optimization in order to assure global convergence. At the same time, accompany with the development of computer and the perfect of software, numerical experiments of optimization problems are becoming more and more feasible and effective.This thesis is devoted to studying systematically the algorithms of monotone variational inequality problem, including with box constraints, linear constraints, nonlinear constraints and general convex constraints. By employing various merit functions introduced by Fukushima and Peng et al., we transform variational inequality problem into equivalent (un)constrained optimization problems and then propose several efficient affine scaling interior trust region algorithms with nonmonotonic line search technique for solving optimization problems.By introducing affine scaling matrices in the process of formulating trust region subproblem, we will technically overcome difficulties imposed by box constraints, linear equality and inequality constraints. Then we formulate an appropriate quadratic function and trust region subproblem only with general elliptic constraints. A feasible direction is obtained by solving trust region subproblem and further a new accepted iterative step can be obtained by nonmonotonic line search technique because sufficient decrease of the objective function values can be guaranteed. Furthermore, the global convergence and local quadratic convergent rate of the proposed algorithm are established under some reasonable conditions.Both optimal path method and modified gradient curvilinear technique are the most popular methods in unconstrained optimization. Because it is convenient to construct these paths and it can be easily programmed and computed, these curvilinear path techniques have become important methods for solving large-scale optimization problems. In this thesis, we introduce the affine scaling matrix to generate an affine scaling optimal path of optimization problem with linear equality and inequality constraints. Employing both the affine scaling optimal path search strategy and line search technique, we will find an acceptable trial step length along the iterative direction which is strictly feasible and makes the objective function nonmonotonically decreasing. Since optimal path is constructed from trust region subproblem, it has good convergent properties. Here, we show that the proposed algorithm not only has the global convergence, but also has local quadratic convergent rate.Basing on the merit function about unconstrained optimization problem of variational inequality problem proposed by Peng, we reformulate variational inequality problem with linear inequality constraints as equivalent constrained optimization problem. We also present modified gradient path and affine scaling interior method for solving trust region subproblem. By searching the step along the path instead of the trust region strategy and using interior backtracking line search technique, the trust region subproblem can be approximately solved. Under some reasonable conditions, the global convergence is established. Further, the algorithm also has local superlinear convergence property if linearized variational inequality subproblem in the algorithm is further considered.Projected gradient algorithm is a kind of significant method for solving convex constrained optimization problem. We employ approximate projected gradient algorithm for trust region sub-problem produced by monotone variational inequality problem subject to convex constraints. One important advantage of this algorithm is that we can avoid solving trust region subproblem repeatedly. Theoretical analysis are given which prove that the proposed algorithm is globally convergent and has a local quadratic convergence rate under some reasonable conditions. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.It is well known that variational inequality problem, optimization problem and Karush-Kuhn-Tucker (KKT) system have closely relationship, specially general nonlinear constraints variational inequality problem can also be transformed into KKT system. On the one hand, we consider to reformulate KKT conditions of variational inequality problem with nonlinear constraints as an equivalent constrained optimization problem, and present an affine scaling interior trust region algorithm. On the other hand, we propose an affine scaling interior Levenberg-Marquardt (L-M) method for KKT system. Firstly, we transform KKT system into an equivalent constrained optimization problem with its variable to be nonnegative. Then we propose an nonmonotonic affine scaling L-M algorithm with backtracking interior point technique for solving this optimization problem. Both of the two proposed algorithms guarantee global convergence and possess local superlinear convergent rate under suitable conditions.Finally, we conclude the main new research results of this thesis and propose some further research direction about our work.