betaFeedback

WorksMathematics

Parameter-Free First-Order Method for Constrained Variational Inequalities

Abstract

Constrained variational inequalities (VIs) provide a general framework for modeling and solving complementarity and equilibrium problems with functional constraints. In this paper, we propose a parameter-free accelerated operator sliding (PFAOS) method for solving monotone VIs with convex smooth constraints. For a single constraint, PFAOS achieves an operator evaluation complexity of O(1/ε)\mathcal{O}(1/\varepsilon) and a constraint gradient evaluation complexity of O(1/ε)\mathcal{O}(1/\sqrt{\varepsilon}), without requiring prior knowledge of the Lipschitz constant of the VI operator or the smoothness constant of the constraint function. We further extend PFAOS to multiple constraints by incorporating a primal-dual hybrid gradient update, yielding a multi-constrained PFAOS (MC-PFAOS) method that preserves the same evaluation complexities. Finally, numerical experiments are conducted on large-scale games with coupling constraints to validate the efficiency and effectiveness of the proposed algorithms.

Authors are encouraged to submit new papers to INFORMS journals by means of a style file template, which includes the journal title. However, use of a template does not certify that the paper has been accepted for publication in the named journal. INFORMS journal templates are for the exclusive purpose of submitting to an INFORMS journal and are not intended to be a true representation of the article’s final published form. Use of this template to distribute papers in print or online or to submit papers to another non-INFORM publication is prohibited.

Funding: This research was supported by the Air Force Office of Scientific Research grant FA9550-25-1-0278.

Introduction

Many equilibrium models incorporate functional constraints to capture operational and physical restrictions on decentralized decisions. For example, in transportation networks, Wardrop equilibrium route choices could yield network flows subject to traffic-control, network-wide emission, or battery-range constraints [10, 18]. Similar structures arise in communication and computing systems, where users compete for bandwidth under quality-of-service constraints [5]. In supply-chain and oligopoly models, firms may compete in a Cournot equilibrium subject to limited supplier capacities or firm-level resource constraints [3, 2]. These problems can be formulated as constrained variational inequalities (CVIs), where equilibrium solutions are subject to many nonlinear functional constraints. These feasibility requirements pose substantial computational challenges beyond those of unconstrained equilibrium problems.

We consider the CVIs of finding a point x∗∈X~x^* \in\widetilde{X} such that

⟨F(x∗),x∗−x⟩≤0,∀x∈X~:={x∈X:G(x)≤0}.(1)\langle F(x^*),x^*-x\rangle\le0,\quad\forall x\in\widetilde{X}:=\{x\in X:G(x)\le0\}. \tag*{(1)}

Here, X⊆RnX\subseteq\mathbb{R}^n is a compact convex set onto which projection is computationally inexpensive. The operator F:Rn→RnF:\mathbb{R}^n\to\mathbb{R}^n is monotone and Lipschitz continuous with respect to the Euclidean norm, that is, there exists M>0M>0 such that

⟨F(u)−F(v),u−v⟩≥0,∥F(u)−F(v)∥≤M∥u−v∥,∀u,v∈X.\langle F(u)-F(v),u-v\rangle\ge0,\qquad\|F(u)-F(v)\|\le M\|u-v\|,\quad\forall u,v\in X.

The constraint mapping G(x):=(g1(x),…,gm(x))⊤G(x):=(g_1(x),\ldots,g_m(x))^\top consists of convex and differentiable functions gi:Rn→Rg_i:\mathbb{R}^n\to\mathbb{R}, with G(x)≤0G(x)\le0 interpreted componentwise. ∥⋅∥\|\cdot\| denotes the Euclidean norm for vectors and the induced operator norm for matrices Its Jacobian J(x)J(x) has ∇gi(x)⊤\nabla g_i(x)^\top as its iith row. In addition, each gig_i has an L(i)L_{(i)}-Lipschitz continuous gradient on XX, with L(i)>0L_{(i)}>0, so that

0≤gi(v)−gi(u)−⟨∇gi(u),v−u⟩≤L(i)2∥v−u∥2,∀u,v∈X.0\le g_i(v)-g_i(u)-\langle\nabla g_i(u),v-u\rangle\le\frac{L_{(i)}}{2}\|v-u\|^2,\quad\forall u,v\in X.

We denote the aggregate smoothness constant by L:=(∑i=1mL(i)2)1/2L:=\left(\sum_{i=1}^m L_{(i)}^2\right)^{1/2}.

A point x∗x^* satisfying (1) is called an exact strong (Stampacchia) solution. In contrast, an exact weak (Minty) solution is a point x∗∈X~x^*\in\widetilde{X} satisfying ⟨F(x),x∗−x⟩≤0\langle F(x),x^*-x\rangle\le0 for all x∈X~x\in\widetilde{X}. The exact strong and weak solution sets coincide when FF is continuous and monotone. Our goal is to compute an ε\varepsilon-approximate weak solution, namely, a point xˉ∈X\bar{x}\in X such that

sup⁡x∈X~⟨F(x),xˉ−x⟩≤ε,∥[G(xˉ)]+∥≤ε,(2)\sup_{x\in\widetilde{X}}\langle F(x),\bar{x}-x\rangle\le\varepsilon,\quad\|[G(\bar{x})]_+\|\le\varepsilon, \tag*{(2)}

where [⋅]+[\cdot]_+ denotes the componentwise maximum with zero.

Let ri⁡(C)\operatorname{ri}(C) denote the relative interior of a set CC. We further impose the following assumption such that the CVI problem admits an optimal primal–dual solution pair, which is standard in literature [19]:

ASSUMPTION 1. There exist x∗∈Xx^*\in X and λ∗∈R+m\lambda^*\in\mathbb{R}_+^m such that

⟨F(x∗)+J(x∗)⊤λ∗,x−x∗⟩≥0, ∀x∈X,G(x∗)≤0,⟨λ∗,G(x∗)⟩=0.(3)\langle F(x^*)+J(x^*)^\top\lambda^*,x-x^*\rangle\ge0,\ \forall x\in X,\quad G(x^*)\le0,\quad\langle\lambda^*,G(x^*)\rangle=0. \tag*{(3)}

In addition, Slater’s condition holds: there exists xsl∈ri⁡(X)x^{\mathrm{sl}}\in\operatorname{ri}(X) such that gi(xsl)<0, ∀i=1,…,mg_i(x^{\mathrm{sl}})<0,\ \forall i=1,\ldots,m.

Related Literature and Research Objective

First-order methods for VIs defined over a simple set XX are well studied. For Lipschitz continuous monotone operators FF, mirror-prox [12] and dual extrapolation [13] compute an ε\varepsilon-approximate weak solution using O(1/ε)O(1/\varepsilon) operator evaluations. This dependence on ε\varepsilon is optimal in the worst case, matching the Ω(1/ε)\Omega(1/\varepsilon) lower bound established by Ouyang and Xu [14] for a saddle-point subclass of monotone VIs.

For VIs with functional constraints, however, several research gaps remain in the existing literature. One main challenge is to design first-order methods that avoid repeated projections onto the functionally constrained set X~\widetilde{X}. So far, there are two closely related studies partially closing this gap. Boob et al. [1] develop adaptive operator extrapolation methods that, in the smooth setting, achieve ε\varepsilon-accuracy in both the weak VI gap and constraint violation using O(1/ε)O(1/\varepsilon) evaluations of both the operator and the constraint gradients. Alternatively, Zhang et al. [17] develop a primal gradient-descent method using local quadratic programs. Without requiring Lipschitz continuity of the operator or information about optimal multipliers, their method achieves these accuracy guarantees in O(1/ε2)O(1/\varepsilon^2) iterations. This leaves a fundamental question: can we design first-order methods that require fewer oracle evaluations and provide sharper constraint-violation bounds without relying on local quadratic programs?

Our work is motivated by results from smooth convex optimization, which suggest that faster constraint-gradient bounds may be attainable. For an O(1)O(1) number of constraints, Xu [16] obtain O~(1/ε)\widetilde{O}(1/\sqrt{\varepsilon}) first-order evaluation complexity for finding ε\varepsilon-approximate Karush–Kuhn–Tucker (KKT) points, where O~\widetilde{O} suppresses logarithmic factors. For the multiple-constraint case, Zhang and Lan [19] achieve O(1/ε)O(1/\sqrt{\varepsilon}) evaluation complexity for objective accuracy and feasibility. These optimization results suggest that O(1/ε)O(1/\sqrt{\varepsilon}) constraint-gradient complexity may also be attainable for monotone CVIs. However, the worst-case Ω(1/ε)\Omega(1/\varepsilon) operator lower bound discussed above applies even without functional constraints. Achieving the desired O(1/ε)O(1/\sqrt{\varepsilon}) constraint-gradient bound therefore requires separating the two oracle costs. Gradient sliding [7] provides a way to achieve such separation by reusing gradient information across multiple updates involving another component. For structured VIs whose operator is the sum of a smooth convex gradient and a Lipschitz continuous monotone component, Lan and Ouyang [9] obtain O(1/ε)O(1/\sqrt{\varepsilon}) gradient evaluations and O(1/ε)O(1/\varepsilon) evaluations of the monotone component. However, in CVIs, the smooth functions define the feasible set rather than an additive component of the operator. Extending this separation to CVIs therefore requires controlling constraint violation together with the weak VI gap.

Another feature we seek is parameter-free, meaning that the algorithm can adapt to unknown Lipschitz constant of the operator and smoothness constants of the constraint functions while retaining the same complexity bounds. The adaptive golden ratio algorithm Malitsky [11] and past-extragradient methods Ene and Nguyen [4] compute ε\varepsilon-approximate weak solutions to Lipschitz continuous monotone VIs on bounded domains using O(1/ε)O(1/\varepsilon) operator evaluations, without prior knowledge of the Lipschitz constant. However, these methods require proximal updates over the feasible domain, so applying them directly to CVIs retains the difficulty of projecting onto X~\tilde{X}. Adaptive extensions are also available for convex composite optimization Wu et al. [15] and convex optimization with functional constraints Zhang and Lan [19].

In summary, our objective is to design first-order algorithms that compute an ε\varepsilon-approximate weak solution to monotone CVIs with convex smooth functional constraints using O(1/ε)O(1/\varepsilon) operator evaluations and O(1/ε)O(1/\sqrt{\varepsilon}) constraint-gradient evaluations, without projections onto X~\tilde{X} or prior knowledge of Lipschitz constant MM, smoothness constant LL, or a uniform bound on ∥J(x)∥\lVert J(x)\rVert over XX.

Organization and Main Results

The remainder of this paper is organized as follows. § 2 introduces the parameter-free accelerated operator sliding method (PFAOS) for the single-constraint case. PFAOS achieves O(1/ε)O(1/\varepsilon) operator and O(1/ε)O(1/\sqrt{\varepsilon}) constraint-gradient evaluation complexities without prior knowledge of the Lipschitz constant of FF or the smoothness constant of GG or projections onto X~\tilde{X}. These bounds retain the optimal operator-complexity order for unconstrained VIs while improving the existing constraint-gradient complexity of CVIs from O(1/ε)O(1/\varepsilon) to O(1/ε)O(1/\sqrt{\varepsilon}). § 3 extends PFAOS to the multi-constrained parameter-free accelerated operator sliding method (MC-PFAOS) for solving the multi-constraint case. MC-PFAOS attains O(1/ε)O(1/\varepsilon) operator and O(1/ε)O(1/\sqrt{\varepsilon}) Jacobian evaluation complexities without projections onto X~\tilde{X} or prior knowledge of the Lipschitz or smoothness constants or a uniform bound on ∥J(x)∥\lVert J(x)\rVert over XX. To the best of our knowledge, these results substantially improve the complexity bounds established for CVI algorithms, including those assuming known smoothness parameters [1, 17].

Next, we provide two complementary results that relax the requirements needed to implement PFAOS and MC-PFAOS. § 4 modifies the first-iteration search for both methods to allow an arbitrarily small initial estimate while preserving the same optimal complexities. § 5 develops an automatic stopping rule for both methods that requires no knowledge of the diameter of the set XX while preserving these complexities. Section 6 reports numerical experiments on large-scale games with coupling constraints, and Section 7 concludes the paper.

Parameter-free Accelerated Operator Sliding (PFAOS)

Algorithm 1 presents the PFAOS method for solving the monotone CVI in (2) with a single constraint (m=1m=1). For notational simplicity, we write g:=g1g := g_1, throughout this section.

Overview of PFAOS

References

  1. [1]Boob D, Deng Q, Khalafi M (2026) First-order methods for stochastic variational inequality problems with function constraints. Math. Oper. Res. .arxiv.org/abs/2304.04778
  2. [2]Caldentey R, Haugh MB (2024) Multimarket Cournot equilibria with heterogeneous resource-constrained firms. Oper. Res. 72(3):940–956.DOI
  3. [3]Cho SH, Tang CS (2014) Capacity allocation under retail competition: Uniform and competitive allocations. Oper. Res. 62(1):72–80.
  4. [4]Ene A, Nguyen HL (2022) Adaptive and universal algorithms for variational inequalities with optimal convergence. Proc. AAAI Conf. Artificial Intelligence 36(6):6559–6567.
  5. [5]Johari R, Tsitsiklis JN (2004) Efficiency loss in a network resource allocation game. Math. Oper. Res. 29(3):407–435.
  6. [6]Kotsalis G, Lan G, Li T (2020) Simple and optimal methods for stochastic variational inequalities, I: Operator extrapolation. arXiv:2011.02987 .arxiv.org/abs/2011.02987
  7. [7]Lan G (2016) Gradient sliding for composite optimization. Math. Programming 159(1):201–235.arxiv.org/abs/1406.0919
  8. [8]Lan G (2020) First-Order and Stochastic Optimization Methods for Machine Learning (Cham, Switzerland: Springer).DOI
  9. [9]Lan G, Ouyang Y (2021) Mirror-Prox sliding methods for solving a class of monotone variational inequalities. arXiv preprint arXiv:2111.00996.arxiv.org/abs/2111.00996
  10. [10]Larsson T, Patriksson M (1999) Side constrained traffic equilibrium models—analysis, computation and applications. Transportation Res. Part B: Methodological 33(4):233–264.DOI
  11. [11]Malitsky Y (2020) Golden ratio algorithms for variational inequalities. Math. Programming 184:383–410.
  12. [12]Nemirovski A (2004) Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1):229–251.DOI
  13. [13]Nesterov Y (2007) Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Programming 109(2-3):319–344.DOI
  14. [14]Ouyang Y, Xu Y (2021) Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Math. Programming 185(1):1–35.
  15. [15]Wu Y, Ouyang Y, Zhang Z, Luo Q (2026) Universal and parameter-free gradient sliding for composite optimization. arXiv preprint arXiv:2603.23492 .arxiv.org/abs/2603.23492
  16. [16]Xu Y (2022) First-order methods for problems with O(1) functional constraints can have almost the same convergence rate as for unconstrained problems. SIAM J. Optim. 32(3):1759–1790.arxiv.org/abs/2010.02282
  17. [17]Zhang L, He N, Muehlebach M (2025) Primal methods for variational inequality problems with functional constraints. Math. Programming .DOI
  18. [18]Zhang X, Rey D, Waller ST, Chen N (2019) Range-constrained traffic assignment with multi-modal recharge for electric vehicles. Netw. Spat. Econ. 19(2):633–668.DOI
  19. [19]Zhang Z, Lan G (2022) Solving convex smooth function constrained optimization is almost as easy as unconstrained optimization. arXiv preprint arXiv:2210.05807.arxiv.org/abs/2210.05807

Paper details

vlnc:W_npbn593d
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT

View statement
Looking for related papers…
Contents