A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition

• URL: http://arxiv.org/abs/2504.03432v2
• Date: Wed, 05 Nov 2025 16:50:41 GMT
• Title: A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition
• Authors: Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm, Brian Hu Zhang,
• Abstract summary: Solving variational inequalities (SVIs) is a foundational problem at the heart of optimization.<n>Most research has focused on carving out specific subclasses that elude those intractability barriers.
• Score: 77.76727425995186
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving variational inequalities (SVIs) is a foundational problem at the heart of optimization. However, this expressivity comes at the cost of computational hardness. As a result, most research has focused on carving out specific subclasses that elude those intractability barriers. A classical property that goes back to the 1960s is the Minty condition, which postulates that the Minty VI (MVI) problem admits a solution. In this paper, we establish the first polynomial-time algorithm -- that is, with complexity growing polynomially in the dimension $d$ and $\log(1/\epsilon)$ -- for solving $\epsilon$-SVIs for Lipschitz continuous mappings under the Minty condition. Prior approaches either incurred an exponentially worse dependence on $1/\epsilon$ or made restrictive assumptions. To do so, we introduce a new variant of the ellipsoid algorithm whereby separating hyperplanes are obtained after taking a gradient descent step from the center of the ellipsoid. It succeeds even though the set of SVIs can be nonconvex and not fully dimensional. Moreover, when our algorithm is applied to an instance with no MVI solution and fails to identify an SVI solution, it produces a succinct certificate of MVI infeasibility. We also show that deciding whether the Minty condition holds is $\mathsf{coNP}$-complete, thereby establishing that the disjunction of those two problems is polynomial-time solvable even though each problem is individually intractable. We provide several extensions and new applications of our main results. Most notably, we obtain the first polynomial-time algorithms for i) globally minimizing a (potentially nonsmooth) quasar-convex function, and ii) computing Nash equilibria in multi-player harmonic games. Finally, in two-player general-sum concave games, we give the first polynomial-time algorithm that outputs either a Nash equilibrium or a strict coarse correlated equilibrium.

Related papers

• Solving Stochastic Variational Inequalities without the Bounded Variance Assumption [8.350639529216876]
  We analyze algorithms for solving variational inequalities (VI) without the bounded variance or bounded domain assumptions.<n>In our setting, this had been obtained with the bounded complexity assumption as not even satisfied for bi min-max problems with an oracle domain.
  arXiv  Detail & Related papers  (2026-02-05T10:44:04Z)
• Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
  We show that $1L 1$ can be used to improve some state-of-the-art problems even for a multilevel Carlo iteration. We provide an analysis for inexact Halperness estimators for $1L 1$ when the only hold with respect to a solution is a new $1L 1$ theory.
  arXiv  Detail & Related papers  (2024-02-07T18:22:41Z)
• Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for Nonconvex Minimax Problems with Coupled linear Constraints [3.4683309709605328]
  We propose algorithms for non minimax problems with deterministic linear constraints under wide settings.<n>The two proposed algorithms are proved to be $tildemathcalO(sp)$ (re. $tildemathcalO(sp)-3)$ (re. $tildemathcalO(sp)-3)$ (re. $tildemathcalO(sp)-3)$).
  arXiv  Detail & Related papers  (2024-01-26T11:22:13Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  We consider monotone variational inequality (VI) problems in multi-GPU settings where multiple processors/workers/clients have access to local dual vectors. Extra-gradient, which is a de facto algorithm for monotone VI problems, has not been designed to be communication-efficient. We propose a quantized generalized extra-gradient (Q-GenX), which is an unbiased and adaptive compression method tailored to solve VIs.
  arXiv  Detail & Related papers  (2023-08-17T21:15:04Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth Nonconvex Minimax Problems with Coupled Linear Constraints [4.70696854954921]
  Non proximal minimax problems have attracted wide attention in machine learning, signal processing many other fields in recent years. We propose DAP algorithm for solving nonsmooth non-strongly concave minimax problems.
  arXiv  Detail & Related papers  (2022-12-09T05:32:30Z)
• A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
  Yang et al. (2023) recently showed how to use first-order gradient methods to solve general variational inequalities. We prove the convergence of this method and show that the gap function of the last iterate of the method decreases at a rate of $O(frac1sqrtK)$ when the operator is $L$-Lipschitz and monotone.
  arXiv  Detail & Related papers  (2022-10-27T17:59:09Z)
• Solving Constrained Variational Inequalities via an Interior Point Method [88.39091990656107]
  We develop an interior-point approach to solve constrained variational inequality (cVI) problems. We provide convergence guarantees for ACVI in two general classes of problems. Unlike previous work in this setting, ACVI provides a means to solve cVIs when the constraints are nontrivial.
  arXiv  Detail & Related papers  (2022-06-21T17:55:13Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  Minimax problems extend beyond the continuous domain to mixed continuous-discrete domains or even fully discrete domains. We introduce the class of convex-submodular minimax problems, where the objective is convex with respect to the continuous variable and submodular with respect to the discrete variable. Our proposed algorithms are iterative and combine tools from both discrete and continuous optimization.
  arXiv  Detail & Related papers  (2021-11-01T21:06:35Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  We investigate online convex optimization in non-stationary environments. We choose the dynamic regret as the performance measure. We show that it is possible to further enhance the dynamic regret by exploiting the smoothness condition.
  arXiv  Detail & Related papers  (2020-07-07T14:10:57Z)
• A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
  We develop an efficient algorithm for solving minimax problems with theoretical general convexnon objective guarantees. We show that the proposed algorithm can be used to solve both noncaveepsilon concave (strongly) and (strongly) convexnonconcave minimax problems.
  arXiv  Detail & Related papers  (2020-06-03T04:00:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.