Solving polynomial variational inequality problems via Lagrange multiplier expressions and Moment-SOS relaxations

Jiawang Nie, Defeng Sun, Xindong Tang, Min ZhangarXiv 2023 · DOI · arXiv

Variational Inequality Problems (VIPs) are fundamental tools in mathematical optimization, used to model complex systems ranging from Nash equilibria in economics to contact mechanics in engineering. A VIP involves finding a point $x$ in a feasible set $X$ such that a vector field $F(x)$ satisfies a specific geometric condition relative to all other points in $X$.

While VIPs are powerful, most traditional solvers—such as projection or Newton-type methods—rely on two restrictive assumptions: the feasible set $X$ must be convex, and the mapping $F$ must be monotone. When these conditions fail, standard methods often struggle to converge or become trapped in local optima. This paper introduces a robust numerical framework to solve polynomial VIPs, specifically targeting non-monotone and nonconvex cases where $F$ and the constraints defining $X$ are polynomials.

The Proposed Framework

The authors propose a two-pronged strategy to overcome the limitations of local solvers:

1. Lagrange Multiplier Expressions (LMEs)

In constrained optimization, Lagrange multipliers are typically treated as independent variables, which increases the dimensionality and complexity of the problem. The authors utilize a technique to express these multipliers as polynomial functions of $x$. This "LME trick" significantly reduces the computational burden when applying global optimization tools, as it keeps the search space confined to the original variables of the problem.

2. The Moment-SOS Hierarchy

To handle the global nature of the problem, the authors reformulate the VIP into a sequence of semidefinite programs (SDPs), known as the Lasserre (Moment-SOS) hierarchy. While solving a general polynomial problem is NP-hard, this hierarchy provides a systematic path to the global optimum by solving increasingly accurate convex relaxations. This approach allows the solver to navigate "wiggly" or nonconvex sets $X$ without getting stuck in local minima.

Algorithmic Implementation

The paper details two primary algorithms:

  • Algorithm 3.2 (Single Solution): This algorithm finds a solution by solving a sequence of optimization problems. It employs a "gap function" to verify if a candidate point is a true solution. If the point fails verification, the algorithm adds a new constraint to "cut away" the non-solution and iterates.
  • Algorithm 3.6 (Multiple Solutions): This extends the framework to find multiple or even all solutions by iteratively adding constraints that exclude previously discovered points.

Key Theoretical Insights

One of the most significant contributions of this work is the proof of finite convergence. For "generic" (typical) polynomials, the algorithm is guaranteed to find a solution or mathematically certify that no solution exists within a finite number of steps. This is a rare and powerful guarantee in the field of global optimization, where many methods can only guarantee convergence in the limit.

Furthermore, the method's ability to detect nonexistence is a major advantage over local solvers, which may simply fail to converge without providing a reason. By showing that the underlying optimization problem is infeasible, this framework can provide a certificate of nonexistence for a VIP.

Numerical Performance and Results

The efficiency of the proposed method was evaluated against several benchmarks, including Nonlinear Complementarity Problems (NCPs), Generalized Nash Equilibrium Problems (GNEPs), and randomly generated VIPs.

  • Superiority over PATH: The method was compared to the PATH solver, a standard industry tool for complementarity problems. While PATH is exceptionally fast for monotone problems, it failed on several nonconvex or non-monotone examples where the proposed Algorithm 3.2 succeeded.
  • LME Efficiency: The use of LMEs proved to be a significant performance booster. In one test case, the LME-based approach reached a solution in 0.12 seconds, compared to 2.97 seconds for a "naive" approach that treated multipliers as independent variables.
  • Scalability: Tests on randomly generated ball-constrained VIPs showed high success rates (often 100%) for dimensions up to $n=11$ and degrees up to $d=10$. However, the authors note that computation time increases significantly as $n$ and $d$ grow, a phenomenon known as the "curse of dimensionality."

Conclusion and Future Directions

This research provides a rigorous and effective global solver for polynomial VIPs that lack the standard properties of convexity and monotonicity. While the current implementation is limited to problems with a modest number of variables (typically $n < 20$ for high degrees), the authors suggest that exploiting "sparsity"—where polynomials only involve a few variables at a time—could allow the method to scale to much larger, real-world problems in the future.

Summary updated

Abstract

In this paper, we study variational inequality problems (VIPs) with involved mappings and feasible sets characterized by polynomial functions (namely, polynomial VIPs). We propose a numerical algorithm for computing solutions to polynomial VIPs based on Lagrange multiplier expressions and the Moment-SOS hierarchy of semidefinite relaxations. We also extend our approach to finding more or even all solutions to polynomial VIPs. We show that the method proposed in this paper can find solutions or detect the nonexistence of solutions within finitely many steps, under some general assumptions. In addition, we show that if the VIP is given by generic polynomials, then it has finitely many Karush-Kuhn-Tucker points, and our method can solve it within finitely many steps. Numerical experiments are conducted to illustrate the efficiency of the proposed methods.
BibTeX
@misc{nie2023solving,
  author = {Jiawang Nie and Defeng Sun and Xindong Tang and Min Zhang},
  title = {{Solving polynomial variational inequality problems via Lagrange multiplier expressions and Moment-SOS relaxations}},
  year = {2023},
  eprint = {2303.12036},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.12036},
}
Figure