An Augmented Lagrangian Approach to Conically Constrained Non-monotone
  Variational Inequality Problems
Lei Zhao Daoli Zhu Shuzhong Zhang
In this paper we consider a non-monotone (mixed) variational inequality model
with (nonlinear) convex conic constraints. Through developing an equivalent
Lagrangian function-like primal-dual saddle-point system for the VI model in
question, we introduce an augmented Lagrangian primal-dual method, to be called
ALAVI in the current paper, for solving a general constrained VI model. Under
an assumption, to be called the primal-dual variational coherence condition in
the paper, we prove the convergence of ALAVI. Next, we show that many existing
generalized monotonicity properties are sufficient -- though by no means
necessary -- to imply the above mentioned coherence condition, thus are
sufficient to ensure convergence of ALAVI. Under that assumption, we further
show that ALAVI has in fact an $o(1/\sqrt{k})$ global rate of convergence where
$k$ is the iteration count. By introducing a new gap function, this rate
further improves to be $O(1/k)$ if the mapping is monotone. Finally, we show
that under a metric subregularity condition, even if the VI model may be
non-monotone the local convergence rate of ALAVI improves to be linear.
Numerical experiments on some randomly generated highly nonlinear and
non-monotone VI problems show practical efficacy of the newly proposed method.