Studies On Efficient Algorithms For Finite-dimensional Variational Inequality And Complementarity Problems

Finite-dimensional variational inequality and complementarity problem are a classof important mathematical programming problems. Their numerical methods are stud-ied in this thesis.For finite-dimensional nonlinear complementarity problem (denoted by NCP), itcan be reformulated as a nonsmooth system of equations. Based on smoothing ideas,the nonsmooth equation is approximated by a family of parameterized smooth equa-tions by introducing a new smoothing function. A smoothing Newton method is pro-posed for the solution of the parameterized smooth equations. Under appropriateassumptions, it is proved that the algorithmic sequence globally and quadratically con-verges to a solution of NCP. Numerical results also show that this algorithm is e?cient.Secondly, based on a reformulation of NCP as a system of nonsmooth equationsby using the generalized Fischer-Burmeister function, a smoothing trust region al-gorithm with line search is proposed for solving general (not necessarily monotone)nonlinear complementarity problems. Global convergence and, under a nonsingularityassumption, local superlinear/quadratic convergence of the algorithm are established.In particular, it is proved that a unit step size is always accepted after a finite numberof iterations. Extensive numerical results indicate that this algorithm is practicallyefficient and promising.For finite-dimensional variational inequality (denoted by VI), a new quasi-Newtonalgorithm for the solution of general box constrained variational inequality problemis proposed. It is based on a reformulation of VI as a nonsmooth system of equa-tions by using the median operator. Without smoothing approximation, the proposedquasi-Newton algorithm is directly applied to solve this class of nonsmooth equations.Under appropriate assumptions, it is proved that the algorithmic sequence globallyand superlinearly converges to a solution of general variational inequality. Extensivenumerical results show that this new algorithm works quite well.