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.
This is an automated message from the Librarian Bot. I found the following papers similar to this paper.
The following papers were recommended by the Semantic Scholar API
- The fixed-point bundle method over product-of-simplex domains arising from game equilibria (2026)
- Acceleration for Affine-coupling problems (2026)
- Joint Structure Identification and Newton Acceleration via Proximal Line Search for Nonconvex Optimization (2026)
- Residual Feedback for Transformed-State Equilibrium Seeking via General Variational Inequalities (2026)
- Interior-point proximal methods for nonsmooth optimization in Hilbert spaces with cone-ordered constraints (2026)
- Obtaining Game-Stationary Points for Smooth Nonconvex-Nonconcave Minimax Problems via First-Order Methods (2026)
- First-Order Optimization under Uniform Nondegeneracy: Geometry, Computation, and Information (2026)
Please give a thumbs up to this comment if you found it helpful!
If you want recommendations for any Paper on Hugging Face checkout this Space
You can directly ask Librarian Bot for paper recommendations by tagging it in a comment: @librarian-bot recommend
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