A linearly convergent algorithm for variational inequalities based on fiber bundle

The variational inequality (VI) problem is a fundamental mathematical framework for many classical problems. This paper introduces an algorithm that applies to arbitrary finite-dimensional VIs with general compact convex sets and general continuous functions. The algorithm guarantees global linear convergence to an approximate solution without requiring any assumptions, including the typical monotonicity. Our approach adapts the interior point framework by introducing a primal-dual unbiased central path, which we structure geometrically as a fiber bundle termed the fixed-point bundle. Within the fixed-point bundle, VI solutions are characterized as the zero points of its canonical section, and the algorithm is formalized as a line search on the fixed-point bundle. In experiment, the algorithm is tested on 2000 randomly generated 100-dimensional VIs, and it works in every single case.

Article

Download

View PDF