A successive linear programming algorithm for nonsmooth monotone variational inequalities

Giancarlo Bigi and Barbara Panicucci


A standard approach for solving a variational inequality is to formulate it as an equivalent optimization problem or to rely upon a family of optimization problems; in this way solution methods for optimization can be exploited. When the feasible region is a polytope, algorithms requiring only the solution of a sequence of linear programs can be devised. In some previous papers different approaches are proposed: a nonconvex gap function is minimized through a descent method exploiting successive polyhedral approximations of the set of maximizers defining the objective function; a complementarity formulation of the variational inequality is considered, leading to an optimization problem which is solved through successive linear approximations with a Frank--Wolfe type procedure. In those procedures the smoothness of the operator is a crucial assumption. In this paper we propose a linear programming based algorithm, which requires just the monotonicity of the operator. To this end we combine a cutting plane procedure for strictly monotone variational inequalities with the Tikhonov regularization technique, resulting in an algorithm for solving nonsmooth monotone variational inequalities subject to linear constraints.
The paper is organized as follows. In Section 2 we review the cutting plane algorithm and we show that it may fail when the operator is not strictly monotone. Afterwards, we provide a regularization of the algorithm which ensures convergence for the monotone case. Since this approach involves the approximate solution of a sequence of strictly monotone variational inequalities, different stopping criteria are also discussed. Finally, the results of preliminary numerical tests are reported in Section 4.

The original paper is available at http://dx.doi.org/10.1080/10556780903157885.

My Home Page