A path-following framework on fiber bundle for variational inequalities

AI summary

Overview

Research area: Continuous optimization — specifically numerical methods for finite-dimensional variational inequalities (VIs), with connections to interior-point methods, complementarity problems, and differential geometry (fiber bundles).

Technical level: Advanced. The paper combines real analysis (mollification, holomorphic parametric integrals), differential geometry (fiber bundles, sections, singular points), and complementarity/interior-point theory. The numerical section is comparatively accessible, but the convergence theory requires graduate-level background in optimization and analysis.

Scope (one sentence): The paper proposes and analyzes a path-following algorithm for variational inequalities with arbitrary continuous mappings over polytope domains, organized around a geometric object the author calls the fixed-point bundle, and reports numerical results on 6400 random instances up to dimension 1024.

What This Paper Is About

A variational inequality asks for a point $x^\star$ in a convex set $K$ such that $\langle H(x^\star), x' - x^\star\rangle \geq 0$ for every $x'$ in $K$; solutions always exist for continuous $H$ on a compact convex set, but designing an algorithm that provably converges for every such $H$ has remained open. Almost all existing methods (projection, proximal, merit-function, homotopy) require monotonicity, pseudo-monotonicity, or similar structural assumptions, and homotopy methods guarantee that a path exists without guaranteeing that it can be followed through singular points. The goal of this paper is a general-purpose path-following method that drops those assumptions, using the geometry of a specially constructed fiber bundle to handle initialization, path-following, and singularity avoidance in one framework.

Key Contributions

1. A preprocessing reduction from general VI to a smooth VI on a simplex. Any polytope $K$ is written as a linear image $x = V\sigma$ of a simplex $\Delta$, giving $F(\sigma) = V^\top H(V\sigma)$, and $F$ is then smoothed by averaging against a Dirichlet distribution with concentration $\sigma/\epsilon + c$. The paper proves (Proposition 1) that the smoothed map $F_\epsilon$ is real-analytic on $\Delta$, and bounds the resulting gap-function error by $|H(V\sigma)|\epsilon_{\text{set}} + 2\epsilon_{\text{map}}$ from above and $-2\epsilon_{\text{map}}$ from below.

2. Three equivalent characterizations of the path, unified as the fixed-point KKT system (FPKKT). The paper derives the same path equation from a parameterized linear program, from a Brouwer fixed-point map $(\hat\sigma, r, v) = M(\sigma,\mu)$, and from the perturbed KKT conditions of a mixed complementarity problem (MCP). Theorem 2 links $\mu = 0$ FPKKT solutions to VI solutions; Theorem 4 (existence theorem) guarantees FPKKT has a solution for every $\mu > 0$; Theorem 5 proves the three characterizations coincide.

3. The fixed-point bundle as the central innovation. The FPKKT solution set is organized as a fiber bundle over the simplex $\Delta$ with one-dimensional fibers in $\mu$. Two sections of the bundle recover the gap function of $\mathrm{VI}(F,\Delta)$, singular points on each fiber correspond to real eigenvalues of a matrix function $J(\sigma)$, and a parity argument implies the number of nonsingular solutions is odd. The bundle separates motion in $\sigma$ (along the base) from motion in $\mu$ (along the fibers), which is what makes a systematic starting-point choice and singularity avoidance possible.

4. A predictor-corrector algorithm with global convergence guarantees and no monotonicity assumptions. Using bounds established on a compact nonsingular neighborhood $\mathcal{N}_{\tilde\Gamma}(\zeta)$ of the path, the paper proves uniform quadratic convergence of the corrector and a uniform bound on the predictor step length, yielding global linear convergence for nonsingular solutions ($\zeta = 0$) and global linear convergence up to any prescribed precision $\zeta > 0$ for singular solutions. Two closely related regularized Newton correctors are given for practical use.

Main Findings

• Assumption-free global convergence: The framework guarantees global linear convergence for nonsingular solutions and global linear convergence up to any prescribed precision for singular solutions, without imposing monotonicity or similar conditions on $H$. The authors state that, among iterative methods with asymptotic convergence, no prior method guaranteed global convergence for every continuous $H$ on a polytope $K$ without additional assumptions.

• Every instance solved to the target precision: On all 6400 randomly generated instances, with dimensions up to 1024, the algorithm reduced the gap function below $10^{-5}$. The paper does not report per-instance iteration counts, runtimes, or comparison against baseline solvers in the available content.

• Singular points are characterized spectrally: Singular points on each fiber correspond to real eigenvalues of the matrix function $J(\sigma)$, and the bundle structure supplies "fiber jumps" as a mechanism to bypass such points while preserving the path structure — this is the technical device that lets the method continue past singularities rather than terminate.

• Odd count of nonsingular solutions: A parity argument on the bundle implies the number of nonsingular solutions is odd.

• Path existence is established, not assumed: Theorem 4 guarantees that FPKKT admits a solution for every $\mu > 0$, and the Brouwer function is shown to be continuous (Proposition 3). The proof also yields a computable bisection problem, since the scalar $v$ is the unique root of a monotone function $q(v)$ lying in the interval $[-\min_i F_i(\sigma), -\min_i F_i(\sigma) + \mathbf{1}^\top\mu]$.

• Interior-point connection: The path traced by FPKKT is exactly the central path of the MCP with the additional condition $\check\sigma = \sigma$, so the method is equivalently a specialized interior-point method following special central paths.

• Cost of smoothing: Monte Carlo estimation of $F_\epsilon$ and its derivative $F'\epsilon$ is unbiased, with variance bounds $\mathrm{Var}[\hat F{\epsilon,i}] \leq M_F^2/N$ and $\mathrm{Var}[[\hat F'\epsilon]{ij}] < M_F^2\psi_1(c_j)/(\epsilon^2 N)$; attaining Monte Carlo error $\epsilon_{\mathrm{MC}}$ and smoothing error $\epsilon$ requires $N = O(\epsilon_{\mathrm{MC}}^{-2}\epsilon^{-2})$ samples, so cost grows only polynomially in both error parameters.

• Derivative limit behavior: As $\epsilon \to 0$, $F'_\epsilon$ does not converge to $F'(\sigma)$ but to $F'(\sigma)(I - \sigma\mathbf{1}^\top)$; the extra factor is absorbed by idempotence in the algorithm, producing the same effect.

Methodology in Plain English

The strategy has four layers.

First, simplify the domain. Instead of working with an arbitrary polytope, the authors express every point of the polytope as a weighted average of its vertices, which turns the problem into one over a simplex. Then they smooth the map by replacing $H$ at a point with its average over a Dirichlet distribution concentrated near that point. This makes the map infinitely differentiable (in fact real-analytic) while converging uniformly back to the original as the smoothing parameter shrinks. In practice the averages are estimated by Monte Carlo sampling, and derivatives come from a covariance identity ("score function") rather than finite differences.

Second, find the right equation to follow. The authors show that the solution of the VI can be written as a fixed point of a parameterized linear program: solve the LP with the current point plugged in, require that the LP's optimizer equals the current point, and relax the KKT conditions by a parameter $\mu$. This gives FPKKT. They prove that the same equation arises from a Brouwer fixed-point argument (which is what supplies existence for every $\mu > 0$) and from the perturbed KKT conditions of a complementarity problem (which identifies it as a central path).

Third, study the geometry instead of solving the equation directly. The solution set of FPKKT over $(\sigma,\mu)$ is a fiber bundle: the simplex is the base, and above each point sits a one-dimensional fiber in $\mu$. Because the base and fiber directions are separated, the algorithm can choose a starting point on the fiber over a designated initial $\sigma_{\text{init}}$, move along analytic curves on the bundle, and — when it encounters a singular point, detected through real eigenvalues of $J(\sigma)$ — jump to a different fiber rather than stalling. A compact neighborhood of the chosen path is then constructed on which all the needed bounds hold.

Fourth, follow the path with a predictor-corrector scheme. The corrector is a regularized Newton iteration (two variants are provided); the predictor extrapolates along the path. The bounds from the neighborhood give uniform quadratic convergence of the corrector and a uniform predictor step length, which together translate into linear decrease of the gap function — down to zero when the solution is nonsingular, and down to a user-chosen precision $\zeta$ when it is singular.

Why This Matters

Impact on research. The paper's claim is structural: it says that a whole class of problems previously believed to need monotonicity-type assumptions can be handled by path-following if the path is organized as a bundle rather than as a curve in the ambient space. It also builds an explicit bridge between three literatures that are usually treated separately — homotopy/continuation methods, interior-point methods, and complementarity theory — by showing their path equations coincide here. The parity result (odd number of nonsingular solutions) and the identification of singular points with real eigenvalues of $J(\sigma)$ are reusable geometric facts.

Real-world applications (domains where VIs are the standard modeling language, as listed in the paper's introduction):

• Traffic assignment: equilibrium route choice on networks, where the mapping is typically asymmetric and not monotone.
• Game theory and economics: Nash equilibrium and market equilibrium computation, where monotonicity frequently fails.
• Contact mechanics: frictional contact problems, which are classically formulated as complementarity or VI problems.
• Machine learning: VI formulations of minimax and equilibrium learning problems.
• Fluid flow: VI formulations of flow problems with obstacles or constraints.

Industry relevance. The guarantees are unconditional, which matters for deployment: a solver that either converges to a certified gap or reports a precision-limited answer is easier to trust than one whose convergence depends on an unverifiable monotonicity property of the input map. The reported result — reaching $10^{-5}$ gap on all 6400 random instances at dimensions up to 1024 — is evidence of practical robustness, and the released code and data at the linked GitHub repository lower the barrier to adoption and replication.

Future Directions

• Scaling the smoothing step. Monte Carlo evaluation costs $O(\epsilon_{\mathrm{MC}}^{-2}\epsilon^{-2})$ samples, which grows quickly when high accuracy in the original map is required; variance reduction, quasi-Monte Carlo, or deterministic quadrature over the simplex are natural remedies. The paper does not report wall-clock timings, so the practical cost at dimension 1024 relative to established solvers is an open empirical question.

• Exploiting problem structure. The framework deliberately assumes nothing about $H$, which makes it general but also means it does not exploit monotonicity, sparsity, or separable structure when those are present. Hybridizing with projection or proximal steps for structured instances is an obvious next step.

• Sharpening the singular case. The theory gives linear convergence up to a prescribed precision $\zeta > 0$ when the solution is singular, but not convergence to the singular solution itself. Whether the bundle's local geometry (the eigenvalue structure of $J(\sigma)$ at the singular point) permits a refined analysis, or an acceleration scheme, is unresolved.

• Extending the base space. The construction relies on the domain being a simplex with a Dirichlet kernel. Whether the bundle framework carries over to other base manifolds or to infinite-dimensional VIs is not addressed and would test how essential the simplex structure really is.

Target Audience

Graduate students and researchers in continuous optimization, complementarity and variational inequality theory, and interior-point methods will get the most from this paper, particularly those interested in continuation/homotopy methods or in applying differential-geometric tools to algorithm design. Readers focused on applications should treat Sections 2 and 7 (preprocessing and experiments) as the entry points, since the convergence theory in Sections 4–6 assumes comfort with fiber bundles and real-analytic arguments. Practitioners seeking a drop-in solver will find the reported precision results and released code useful, but should note that the experiments section is where the empirical case is made and that the paper does not report comparisons with alternative solvers in the available content.

Authors’ abstract

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.