Global Newton methods for nonlinear programs and variational inequalities: A B-differentiable equation approach

This dissertation presents a modified damped Newton algorithm for solving general variational inequality problems with nonlinear programs and nonlinear complementarity problems as special cases. When these three mathematical problems are formulated as a system of equations, the traditional Newton method will fail because of the presence of some inherent nondifferentiability. The proposed modified damped Newton method, however, insures global convergence and locally quadratic convergence under the assumption of regularity. Numerical experiments show that the algorithm is very efficient and outperforms the traditional Newton method. The research in this dissertation is motivated by J. S. Pang\u27s recent work and is different from his in several respects. It uses a different formulation which makes the structure simpler and is able to exploit the derivative information from both the primal functions and dual variables. In the context of convex nonlinear programming, this formulation maintains the convexity of the subproblems. A significant improvement of this modified algorithm over the basic damped Newton algorithm is that it relaxes the regularity condition to some extent. Under the assumption of weak regularity and some very mild conditions, the modified algorithm is guaranteed to attain a descent direction. Hence, this new algorithm is often suitable for many applications and is shown to preform quite well on an extensive set of test examples