  We consider a class of optimization problems with Cartesian variational
inequality (CVI) constraints, where the objective function is convex and the
CVI is associated with a monotone mapping and a convex Cartesian product set.
This mathematical formulation captures a wide range of optimization problems
including those complicated by the presence of equilibrium constraints,
complementarity constraints, or an inner-level large scale optimization
problem. In particular, an important motivating application arises from the
notion of efficiency estimation of equilibria in multi-agent networks, e.g.,
communication networks and power systems. In the literature, the iteration
complexity of the existing solution methods for optimization problems with CVI
constraints appears to be unknown. To address this shortcoming, we develop a
first-order method called averaging randomized block iteratively regularized
gradient (aRB-IRG). The main contributions include: (i) In the case where the
associated set of the CVI is bounded and the objective function is
nondifferentiable and convex, we derive new non-asymptotic suboptimality and
infeasibility convergence rate statements in a mean sense. We also obtain
deterministic variants of the convergence rates when we suppress the randomized
block-coordinate scheme. Importantly, this paper appears to be the first work
to provide these rate guarantees for this class of problems. (ii) In the case
where the CVI set is unbounded and the objective function is smooth and
strongly convex, utilizing the properties of the Tikhonov trajectory, we
establish the global convergence of aRB-IRG in an almost sure and a mean sense.
We provide the numerical experiments for computing the best Nash equilibrium in
a networked Cournot competition model.
