A successive linear programming algorithm for nonsmooth monotone variational inequalities
Giancarlo Bigi and Barbara Panicucci
Summary
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