Hongbo Sun Proposes an Algorithm for Variational Inequalities: 6400 Problems, 1e-5

Hongbo Sun has presented a general-purpose algorithm for variational inequalities (VI) that does not need the mapping to be monotone. The method works with arbitrary continuous mappings on polyhedral domains and guarantees global linear convergence. For nondegenerate solutions the convergence is exact; for degenerate ones, any pre-specified accuracy is reached. On 6400 random problems of dimension up to 1024, the gap fell below 1e-5 in every case.

Why variational inequalities are still considered a hard problem

A variational inequality asks for a point in a feasible set where the vector field offers no improvement in any feasible direction. This formulation covers optimization problems, complementarity problems, saddle-point problems, and game equilibria. That is why VIs regularly surface wherever several participants optimize different objectives at once: in minimax formulations and multi-agent systems.

The problem is that the guarantees of most classical methods rest on monotonicity or similar conditions. Without them, algorithms start to cycle or diverge. In the abstract, the author herself calls the development of general-purpose algorithms with global convergence guarantees a long-standing open problem.

A fiber bundle instead of manual workarounds for singularities

The method is built on path-following: the solution is found by tracking a continuous trajectory from a simple starting point. The weak spot of this approach is well known. At singular points the guarantees break down, and the trajectory can hit a dead end.

Sun first transforms the general VI into a smooth VI on a simplex. He then describes the solution set of the fixed-point KKT system as a fiber bundle over the simplex, called the "fixed-point bundle". The geometry of the bundle separates two kinds of movement: along the base and along the fibers. This lets a single scheme handle three things that are usually solved separately:

• choosing the starting point;
• moving along the trajectory itself;
• bypassing singularities.

At a singular point, the algorithm simply moves along the fiber to a nondegenerate point and continues from there.

What the experiments showed

The evaluation was run on randomly generated problems. Key parameters:

• number of instances: 6400;
• maximum dimension: 1024;
• accuracy reached: gap below 1e-5 on all instances;
• convergence for nondegenerate solutions: global linear, exact;
• convergence for degenerate solutions: global linear to any prescribed accuracy;
• assumptions of monotonicity or similar properties: not required;
• domain: polyhedra that reduce to a simplex;
• code and data: github.com/shb20tsinghua/FiberBundle_VI;
• follow-up: arXiv:2609.16158, where the framework is extended to products of simplices for computing Nash equilibria.

The "in every case" result deserves attention. For an algorithm with no structural assumptions, zero failures across this many random problems matters more in practice than speed on convenient examples.

Where this could be useful and what to check

The work has no direct product application; it is a foundational tool. But the demand for it is clear among those building multi-agent learning, game formulations, and equilibrium problems. For them, the lack of guarantees outside the monotone case remains a constant pain point.

The repository is open, so the first thing practitioners should do is run the method on their own structured problems. Random instances show robustness well, but they do not replace testing on real data, where mappings have their own structure. It is also worth checking how the per-step cost grows at dimensions above 1024, and how the algorithm behaves under very demanding accuracy requirements on degenerate solutions. The next step is already outlined: the extension to products of simplices will open the way to computing Nash equilibria in games with several players.