A path-following framework on fiber bundle for variational inequalities
Abstract
A path-following framework on a fixed-point fiber bundle achieves global linear convergence for variational inequalities with continuous mappings over polytopes without monotonicity assumptions.
Developing general-purpose algorithms with global asymptotic convergence guarantees for variational inequalities (VIs) remains a longstanding challenge. This paper proposes a path-following framework for finite-dimensional VIs with arbitrary continuous mappings and polytope domains. The approach first transforms a general VI into a smooth VI on a simplex. Its key innovation is to formulate the resulting problem on a fiber bundle, called the fixed-point bundle, whose geometric structure enables the systematic integration of initialization, path-following, and singularity avoidance. Without imposing monotonicity or similar assumptions, the framework guarantees global linear convergence for nonsingular solutions and global linear convergence up to any prescribed precision for singular solutions. In numerical experiments, the algorithm attained a precision of 10^{-5} on all 6400 randomly generated instances, with dimensions up to 1024. Code and data are available at https://github.com/shb20tsinghua/FiberBundle_VI.
Community
This paper presents a general-purpose path-following algorithm that solves general variational inequalities with continuous mappings and polytope domains to arbitrary precision, achieving global linear convergence: exact for nonsingular solutions, and up to any prescribed precision for singular ones.
The key insight is to view the solution set of a fixed-point KKT system as a fiber bundle (the "fixed-point bundle") over the simplex, whose geometry separates motion along the base from motion along the fibers. This unifies starting point selection, path-following, and singularity avoidance: at a singular point, where existing path-following guarantees break down, the algorithm simply jumps along the fiber to a nonsingular point and continues.
Experiments on 6400 random instances with dimensions up to 1024 reduce the gap below 1e-5 in every case; code and data are available at https://github.com/shb20tsinghua/FiberBundle_VI.
A follow-up (arXiv:2609.16158) extends the framework to product-of-simplex domains for Nash equilibrium computation.
Get this paper in your agent:
hf papers read 2606.00778 Don't have the latest CLI?
curl -LsSf https://hf.co/cli/install.sh | bash Models citing this paper 0
No model linking this paper
Datasets citing this paper 0
No dataset linking this paper
Spaces citing this paper 0
No Space linking this paper
Collections including this paper 0
No Collection including this paper