Source-linked AI summary
A path-following framework on fiber bundle for variational inequalities
Hongbo Sun
TL;DR
General VIs on polytopes lack unconditional global convergence guarantees for arbitrary continuous mappings. The paper preprocesses them to smooth simplex VIs and follows paths on a fixed-point bundle; it reports global linear convergence guarantees and success on 6,400 random problems.
Problem
Existing iterative VI methods generally require monotonicity or similar assumptions, and no existing method guarantees global convergence for every continuous mapping on a polytope without additional assumptions.
Source: §1 · p. 2Method
The framework preprocesses the VI into a smooth simplex VI and follows paths on a fixed-point bundle that integrates initialization, path-following, and singularity avoidance.
Source: §1 · p. 3, §8 · p. 26Results
The algorithm guarantees global linear convergence to nonsingular solutions and up to any prescribed precision for singular solutions, and succeeds on 6,400 randomly generated problems up to dimension 1,024.
Source: §8 · p. 26Takeaways & Limitations
The framework provides global linear convergence guarantees for continuous-map VIs on polytopes without additional assumptions.
Source: §8 · p. 26A point satisfying FPKKT at μ = 0 is not necessarily a VI solution; it must be a limit point as μ → 0+.
Source: §3.3 · p. 10
Abstract
from arXiv · showhide
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.
1 Introduction
The paper targets global convergence for continuous variational inequalities on polytopes without structural assumptions, using simplex preprocessing and a fixed-point-bundle path-following framework. It reports global linear convergence guarantees and success on 6,400 random instances.
1 Introduction
- The approach preprocesses a general continuous VI on a polytope into a smooth VI on a simplex, then follows paths characterized by the fixed-point KKT system.The paper relates these paths to special central paths.Source: §1 · p. 3
- The fixed-point bundle separates motion along the simplex base from motion along fibers, integrating initialization, path-following, and fiber jumps to bypass singular points.Singular points on each fiber correspond to real eigenvalues of J(σ).Source: §1 · p. 3
- The framework guarantees global linear convergence for nonsingular solutions and up to any prescribed precision for singular solutions, without monotonicity or similar assumptions.The algorithm drives the gap function to the prescribed precision ζ.Source: §1 · p. 3
- The algorithm reduced the gap function below 10^-5 on all 6,400 randomly generated instances, with dimensions up to 1,024.Source: §1 · p. 3
2 Preprocessing: smooth VI over simplex
Preprocessing converts a continuous VI on a polytope into a smooth VI on a simplex. Dirichlet averaging supplies a real-analytic map, while approximation and sampling analyses describe the accuracy and computational cost of this reduction.
2 Preprocessing: smooth VI over simplex
- Every polytope is represented as a linear image of a simplex, transforming the VI into one on the simplex with mapping F(σ) = V^⊤H(Vσ).Source: §2 · pp. 3–4
2.1 Dirichlet smoothing
- Dirichlet averaging smooths the continuous simplex mapping into a real-analytic function, with concentration parameter σ/ε + c and approximation error controlled by ε.The paper establishes real-analyticity for every ε > 0.Source: §2.1 · p. 4
2.2 Numerical evaluation via Monte Carlo sampling
- Monte Carlo estimates of the smoothed mapping and its derivative are unbiased, and the required sample count scales as O(ε^-2_MC ε^-2).The cost increases polynomially in the inverse smoothing error and inverse Monte Carlo error.Source: §2.2 · p. 6
2.3 Approximation error to the original VI
- The gap approximation error between the smoothed simplex VI and the original VI is bounded by the set approximation error ε_set and mapping approximation error ε_map.The set error accounts for inner polytope approximation of a general compact convex set.Source: §2.3 · pp. 6–7
3 Three equivalent characterizations regarding the paths
The paper characterizes the paths for the smooth simplex VI through equivalent formulations involving linear programming, Brouwer fixed points, and mixed complementarity. These formulations connect VI solutions to paths that exist for positive μ and lead toward solutions as μ approaches zero.
3 Three equivalent characterizations regarding the paths
- The three equivalent characterizations reveal the path structure through linear programming, Brouwer fixed points, and mixed complementarity, with FPKKT serving as their common system.Source: §3 · p. 7, §3.3 · p. 10
3.1 Linear programming form and path equation
- FPKKT combines the perturbed KKT conditions of a parameterized linear program with the fixed-point condition σ = σ̂, and at μ = 0 characterizes VI solutions.Solutions at every μ > 0 form a path leading toward VI solutions.Source: §3.1 · pp. 7–8
3.2 Brouwer fixed-point form and path existence
- For every μ > 0, a Brouwer fixed point exists, guaranteeing a solution of FPKKT and hence existence of paths as μ approaches zero.Source: §3.2 · p. 9
3.3 Mixed complementarity problem form and central path
- FPKKT is the distinguished central path of a mixed complementarity problem, and its positive-μ paths lead to VI solutions as μ approaches zero.A point satisfying FPKKT at μ = 0 is not necessarily a VI solution; it must be a limit point from μ > 0.Source: §3.3 · pp. 9–10
4 Fiber bundle as the solution space of FPKKT
The solution set of FPKKT is treated as a geometric fiber bundle over the simplex, linking paths to VI solutions. Its structure separates base-space motion from fiber motion and supports path construction and singularity analysis.
4 Fiber bundle as the solution space of FPKKT
- Viewing the FPKKT solution set geometrically reveals a fiber bundle that unifies starting-point selection, path-following, and singularity avoidance.Paths on the bundle as μ → 0+ lead to solutions of the simplex VI.Source: §4 · p. 10, §4.1 · p. 12
4.1 The fixed-point bundle
- Over each σ, admissible μ values form an affine one-dimensional family, and their union defines the fixed-point bundle over the simplex.The projection maps each point in the total space to its base σ.Source: §4.1 · p. 10
4.2 Differential properties
- Fiber motion separates from base motion, and singular points on each fiber correspond to real eigenvalues of J(σ).Each fiber contains at most n − 1 singular points.Source: §4.1 · p. 11, §4.2 · pp. 13–14
4.1 The fixed-point bundle
- The fixed-point bundle equation G(σ, μ) = 0 describes its points, while the section μ̌(σ) links the bundle to the VI gap and its solutions.Solutions correspond to zeros of μ̌(σ) and to limit points of paths as μ → 0+.Source: §4.1 · pp. 11–12
5 Paths on the fixed-point bundle
The fixed-point bundle provides paths from designated starting points to VI solutions, with fiber jumps that bypass singularities. A compact nonsingular neighborhood supports path-following, with precision-dependent guarantees when the solution is singular.
5.2 The path
- At a singular point, a fiber jump changes µ while keeping σ fixed, moving to a nonsingular point and switching to a curve with a different starting point.The construction avoids nonzero singular points; a singular solution at (σ⋆, 0) may remain an unavoidable intersection.Source: §5.1 · p. 14, §5.2 · p. 15, Figure 2 · p. 16
- From any designated starting point, a finite-segment path exists that avoids singularities except possibly at a singular solution.The path is formed from analytic-curve segments and fiber jumps.Source: §5 · p. 14, §5.2 · p. 15
6 Path-following on the fixed-point bundle
The section develops a predictor-corrector method on the fixed-point bundle, combining tangent-path motion, feasibility correction, and fiber-based singularity avoidance. It gives two regularized Newton correctors and proves global linear convergence up to a prescribed gap precision.
6.1 The predictor-corrector framework
- Predictor steps follow the bundle tangent, first jumping along a fiber to avoid singularities, while correctors restore the fixed-point bundle equation at fixed µ.The practical predictor uses ut = ±µ̂t to follow the analytic curve selected by the fiber jump.Source: §6.1 · p. 19
6.2 Corrector derived from perturbed KKT conditions
- Regularized Newton corrector (6.2) stabilizes small-singular-value steps by adding δH, trading quadratic convergence for linear convergence at rate δH/(smin^2(JG) + δH).The unregularized step can appear unstable when smin(JG) is too small.Source: §6.2 · p. 20
6.3 Corrector derived from barrier problem
- The barrier-MCP derivation supplies a second regularized Newton corrector, (6.5), which also mixes Newton and gradient steps.The derivation treats σ as the optimization variable and uses (r, v) as intermediate variables.Source: §6.3 · pp. 20–21
6.4 The global linear convergence proof
- The convergence proof combines quadratic convergence of Newton correction with bounded predictor-induced residual changes, keeping iterates in the correction region.The outer path parameter converges linearly to zero, and sufficiently many correction steps can be limited to O(log t).Source: §6.4 · pp. 22–24
- The algorithm globally linearly reduces the gap to prescribed precision ζ, with ζ = 0 for nonsingular targets and ζ > 0 for singular targets.For general VI(H, K), the same guarantee holds after preprocessing; if H is continuously differentiable at the target solution, ζ can be 0.Source: §6.4 · p. 25
7 Numerical experiments
The experiments test two regularized Newton correctors on randomly generated neural-network VIs across varying dimensions and depths. Both variants succeeded on all 6400 instances at the required precision of 10^-5.
7 Numerical experiments
- The tests use two network families: [n, n, n] with n from 2 to 1024, and [256] × d with depth from 2 to 8.Each data point uses 200 randomly generated instances, with randomly generated starting points.Source: §7 · p. 25
- 6400 of 6400 instances reached the required 10^-5 precision; Table 1 reports mean and median solving statistics for both corrector variants.The tested problems use tanh-activated neural networks and include dimensions up to 1024.Source: §7 · pp. 25–26, Table 1 · p. 25
- For architecture [n, n, n], iteration counts first rise and then fall as n increases, while for [256] × d they fall as depth d increases.The authors attribute the depth trend to Xavier initialization decreasing function complexity as depth increases.Source: §7 · p. 26
8 Conclusion
The conclusion presents a path-following framework for finite-dimensional VIs with continuous functions and compact convex domains, using simplex preprocessing for smooth cases. Its fixed-point bundle organizes initialization, path-following, and singularity avoidance, with convergence guarantees and experiments supporting its scope.
8 Conclusion
- The framework covers finite-dimensional VIs with general continuous functions and compact convex domains by handling smooth simplex VIs after preprocessing.Source: §8 · p. 26
- The fixed-point bundle geometrizes paths solving smooth simplex VIs and separates base motion from fiber motion to unify initialization, path-following, and singularity avoidance.Source: §8 · p. 26
- Without assumptions, the method converges globally linearly to nonsingular solutions and to any prescribed precision for singular solutions; experiments succeeded on 6400 problems up to dimension 1024.Source: §8 · p. 26
- The current method uses an inner simplex approximation and analytic smoothing; tighter integration of preprocessing with path-following could improve practical performance.Source: §8 · p. 26