A Projection-Free Algorithm for Variational Inequalities in Hilbert Spaces with Strong Convergence
Abstract
Summary: We study variational inequalities governed by a point-to-set maximal monotone operator in a real Hilbert space and constrained by a convex inequality (C={x\in\Hi:c(x)\le0}), where the defining function (c) is continuous and not necessarily differentiable. The proposed method uses only projections onto intersections of half-spaces and avoids the metric projection onto (C). Feasibility is handled by subgradient cuts and, when a trial operator point is infeasible, by a Slater correction based on a fixed strictly feasible point. The variational inequality is represented by Minty-type separating half-spaces generated at feasible graph points of the operator, and a Haugazeau half-space is added to obtain best-approximation convergence. Under a Slater-corrected feasible-separation condition, together with explicit exact, approximate and finite-candidate oracle realisations, the whole sequence converges strongly to (P_{S^*}(x^0)), the projection of the initial point onto the solution set. We also derive best-iterate (O(N^{-1/2})) residual estimates for the step residual, feasibility violation and Minty gap. The analysis is stated directly for point-to-set maximal monotone operators, while the concrete oracle realisations include finite-dimensional single-valued models. We record the consequences of strong monotonicity in the point-to-set setting and provide numerical comparisons on nonsmooth and large-scale constraints, including maxima of convex quadratics, a discretised optimal-control problem, mixed-norm sparse recovery, a Cournot–Nash capacity equilibrium, and a genuine point-to-set (\ell_1)-subdifferential example.
