Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #98016 (September, 1998)

Broyden-like Methods for Variational Inequality and Nonlinear
by Donghui Li and Masao Fukushima

In this paper, we propose a Broyden-like quasi-Newton method for solving finite-dimensional variational inequality problems. By means of a perturbed Fischer-Burmeister function, we successively approximate the KKT system for a variational inequality problem by a sequence of smooth equations. Based on these approximating equations, we present a Broyden-like method. The method is well defined. We show that under suitable conditions, the proposed method converges to a KKT point of the variational inequality problem globally and superlinearly. In particular, we show that when specialized to a nonlinear complementarity problem, the proposed method converges globally whenever the problem involves a $P_0$ function with Lipschitzian Jacobian. Moreover, if the strict complementarity condition holds, then the convergence rate is superlinear.