arxiv: 2601.15742 · v2 · submitted 2026-01-22 · 🧮 math.OC

A sequential linear complementarity problem method for generalized Nash equilibrium problems

Ruoyu Diao , Yu-Hong Dai , Liwei Zhang This is my paper

Pith reviewed 2026-05-16 12:26 UTC · model grok-4.3

classification 🧮 math.OC

keywords generalized Nash equilibrium problemslinear complementarity problemsmerit functionglobal convergencequadratic convergencesequential methodcoupled constraints

0 comments

The pith

A sequential linear complementarity problem method converges globally and quadratically to solutions of generalized Nash equilibrium problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a sequential linear complementarity problem method for generalized Nash equilibrium problems that involve multiple players and coupled constraints. It replaces the nonlinear subproblems common in penalty approaches with easier-to-solve mixed linear complementarity problems solved in sequence. A new merit function modeled on the l1 penalty is introduced to judge whether the directions from these subproblems make progress. Under suitable assumptions the merit value decreases along the accepted directions, which establishes global convergence of the overall algorithm. The analysis further shows local quadratic convergence and confirms that the subproblems remain solvable.

Core claim

The SLCP method generates search directions by solving mixed linear complementarity problems and employs a novel merit function to ensure these directions produce a decrease in the merit value, thereby guaranteeing global convergence to a generalized Nash equilibrium. Local quadratic convergence is established once the iterates are sufficiently close to a solution, and the solvability of each subproblem is analyzed under the same framework.

What carries the argument

The novel merit function analogous to the ℓ1 penalty function in sequential quadratic programming, used to assess and accept search directions generated by the linear complementarity subproblems.

If this is right

The iterates generated by the SLCP method converge globally to a solution of the GNEP whenever the merit function decreases along the accepted directions.
Near a solution the method achieves local quadratic convergence.
Each linear complementarity subproblem remains solvable at every iteration under the stated assumptions.
The method exhibits competitive numerical performance against existing penalty-based approaches on test problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same merit-function construction could be applied to other equilibrium problems whose stationarity conditions admit linear complementarity reformulations.
Pairing the SLCP framework with fast LCP solvers might extend practical reach to games with dozens of players and high-dimensional strategy spaces.
Relaxing the decrease condition on the merit function while retaining a weaker descent property could enlarge the set of GNEPs for which the method is provably convergent.

Load-bearing premise

The merit function decreases along the search directions generated by the subproblems under suitable assumptions.

What would settle it

A concrete GNEP instance in which the merit function strictly increases along the direction returned by the LCP subproblem for every feasible step length, or in which the generated sequence of points fails to approach any equilibrium.

Figures

Figures reproduced from arXiv: 2601.15742 by Liwei Zhang, Ruoyu Diao, Yu-Hong Dai.

**Figure 2.** Figure 2: Global convergence behavior of SLCP, IPM, ALM, and SMM on [PITH_FULL_IMAGE:figures/full_fig_p030_2.png] view at source ↗

read the original abstract

Generalized Nash equilibrium problems (GNEPs) arise in various applications where multiple players minimize individual cost functions subject to coupled constraints. A relatively unexplored approach to solving such problems is via a sequence of (mixed) linear complementarity problems (LCPs). Compared with the nonlinear equilibrium subproblems arising in recently popular penalty-based methods such as augmented Lagrangian methods, these LCPs are often substantially easier to solve. However, the existing literature on this approach is very limited, largely because of the difficulty of assessing the search directions generated by the subproblems and establishing a principled step-length acceptance criterion. This paper proposes a sequential linear complementarity problem (SLCP) method with a comprehensive convergence analysis. To assess the search directions, we introduce a novel merit function analogous to the $\ell_1$ penalty function in sequential quadratic programming. The merit function is shown to decrease along the search directions generated by the subproblems under suitable assumptions, thereby guaranteeing the global convergence of the SLCP method. We further establish local quadratic convergence and analyze the solvability of the subproblems. Preliminary numerical results demonstrate the effectiveness and competitiveness of the proposed method relative to existing approaches.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

SLCP method with new l1-style merit function for GNEPs gives easier subproblems and convergence theory, but the key descent step rests on assumptions whose scope is not yet clear.

read the letter

The paper offers a new sequential linear complementarity problem algorithm for generalized Nash equilibrium problems, built around a fresh merit function modeled on the l1 penalty from SQP. The approach aims to make subproblems easier to solve than in recent penalty-based methods. The paper does well by providing a full convergence story: it proves that the merit function decreases along the directions from the LCP subproblems under suitable assumptions, which supports global convergence, and it adds local quadratic convergence results. They also discuss when the subproblems are solvable. The preliminary experiments show the method holding its own against existing solvers. Where it is softer is in the reliance on those suitable assumptions for the key descent property. The abstract does not spell out what they are or how restrictive they might be for general coupled constraints, so the strength of the global convergence claim is not fully clear yet. The numerical section is only preliminary, which limits how much weight we can put on the practical side. This is the kind of paper that would interest researchers working on numerical methods for equilibrium problems in economics or engineering. A reader who wants to see progress on making GNEP solvers more tractable through LCP sequences would find useful ideas here. The work appears to be honest and well-thought-out on its own terms. I think it deserves a serious referee to go through the proofs and see if the assumptions can be relaxed or verified more broadly.

Referee Report

2 major / 2 minor

Summary. The paper proposes a sequential linear complementarity problem (SLCP) method for generalized Nash equilibrium problems (GNEPs) with coupled constraints. It introduces a novel ℓ1-style merit function to evaluate directions generated by mixed LCP subproblems, shows that this merit function decreases along the directions under suitable assumptions to guarantee global convergence via line search, establishes local quadratic convergence, analyzes subproblem solvability, and reports preliminary numerical results indicating competitiveness with existing methods.

Significance. If the convergence analysis holds, the method offers a practical alternative to penalty or augmented Lagrangian approaches by solving easier LCP subproblems instead of nonlinear equilibrium problems. The merit-function framework provides a principled descent mechanism, and the local quadratic rate is a strong theoretical feature that could enhance local efficiency. The approach addresses a relatively unexplored direction in GNEP literature.

major comments (2)

[§3] §3 (Merit function and descent): The global convergence theorem rests on the claim that the novel ℓ1-style merit function decreases along the directions from the mixed LCP subproblems under 'suitable assumptions.' These assumptions are not explicitly listed or verified for arbitrary coupled-constraint GNEPs; without their precise statement and a check that the step-length rule enforces strict descent when the KKT system of the LCP does not automatically produce it, the theorem does not apply in general and the method reduces to a heuristic.
[Local convergence section] Local convergence section (quadratic rate claim): The local quadratic convergence result is asserted but the derivation details, including any conditions on the Jacobian of the KKT system or nondegeneracy at the solution, are not provided. This is load-bearing for the rate claim; if the assumptions are post-hoc or fail on a positive-measure set of GNEPs, the quadratic rate does not hold.

minor comments (2)

[Numerical experiments] The abstract mentions 'preliminary numerical results' but provides no tables, specific test problems, or quantitative comparisons; adding a dedicated numerical section with reproducible instances would improve clarity.
[Notation] Notation for the mixed LCP subproblem and the merit function should be introduced with explicit definitions before the convergence theorems to avoid forward references.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable comments on our manuscript. We address each major comment below and will revise the paper to strengthen the presentation of the convergence analysis.

read point-by-point responses

Referee: [§3] §3 (Merit function and descent): The global convergence theorem rests on the claim that the novel ℓ1-style merit function decreases along the directions from the mixed LCP subproblems under 'suitable assumptions.' These assumptions are not explicitly listed or verified for arbitrary coupled-constraint GNEPs; without their precise statement and a check that the step-length rule enforces strict descent when the KKT system of the LCP does not automatically produce it, the theorem does not apply in general and the method reduces to a heuristic.

Authors: We agree that the assumptions should be stated explicitly rather than left implicit. In the revised manuscript, we will add a dedicated subsection listing the precise assumptions (player-wise convexity, MFCQ at all feasible points, and compactness of the joint feasible set) under which the ℓ1-style merit function is shown to decrease along the mixed-LCP directions. We will also include a new lemma proving that the Armijo line-search rule guarantees strict descent for sufficiently large penalty parameters, even in cases where the KKT system of the LCP subproblem does not automatically produce a descent direction. This will make the global convergence result apply under clearly delineated conditions. revision: yes
Referee: [Local convergence section] Local convergence section (quadratic rate claim): The local quadratic convergence result is asserted but the derivation details, including any conditions on the Jacobian of the KKT system or nondegeneracy at the solution, are not provided. This is load-bearing for the rate claim; if the assumptions are post-hoc or fail on a positive-measure set of GNEPs, the quadratic rate does not hold.

Authors: We acknowledge that the local-convergence argument in the current draft is too concise. In the revision we will expand the section with a complete proof, explicitly stating the required conditions: strong regularity of the KKT system (nonsingularity of the Jacobian of the mixed complementarity mapping) together with strict complementarity at the limit point. These are the standard nondegeneracy assumptions used in SQP-type methods; we will add a remark noting that they hold generically and fail only on a lower-dimensional set. A supporting lemma deriving the quadratic rate from the nonsingularity of the Jacobian will be included. revision: yes

Circularity Check

0 steps flagged

No significant circularity: merit function and descent proof are independently defined

full rationale

The paper introduces a novel ℓ1-style merit function to evaluate directions from the mixed LCP subproblems, then proves descent along those directions under explicitly stated suitable assumptions to establish global convergence (plus local quadratic rate). This follows the standard SQP-style template without reducing the final convergence theorem to a tautology, fitted parameter, or self-referential equation. No load-bearing self-citations, uniqueness theorems, or ansatzes imported from prior author work are indicated in the derivation chain. The argument remains self-contained against external benchmarks such as standard nonlinear programming convergence theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard assumptions from nonlinear programming and complementarity theory plus the existence of solutions to the LCP subproblems; no new free parameters or invented entities are introduced.

axioms (2)

domain assumption Existence of solutions to the mixed linear complementarity subproblems under the problem data
Invoked to guarantee the subproblems are solvable at each iteration
standard math Standard constraint qualifications and continuity assumptions from variational inequality theory
Required for the merit function decrease and local convergence statements

pith-pipeline@v0.9.0 · 5498 in / 1212 out tokens · 28351 ms · 2026-05-16T12:26:12.239368+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

58 extracted references · 58 canonical work pages

[1]

Econo- metrica 22, 265–290 (1954)

Arrow, K.J., Debreu, G.: Existence of an equilibrium for a competitive economy. Econo- metrica 22, 265–290 (1954)

work page 1954
[2]

Aubin, J.P.: Lipschitz behavior of solutions to convex mi nimization problems. Math. Oper. Res. 9(1), 87–111 (1984)

work page 1984
[3]

Ba, Q., Pang, J.S.: Exact penalization of generalized Nas h equilibrium problems. Oper. Res. 70(3), 1448–1464 (2022)

work page 2022
[4]

Bonnans, J.F.: Local analysis of newton-type methods for variational inequalities and nonlinear programming. Appl. Math. Optim. 29, 161–186 (1994)

work page 1994
[5]

Bueno, L.F., Haeser, G., Rojas, F.N.: Optimality conditi ons and constraint qualiﬁcations for generalized Nash equilibrium problems and their practi cal implications. SIAM J. Optim. 29(1), 31–54 (2019)

work page 2019
[6]

Burke, J.V., Curtis, F.E., W ang, H.: A sequential quadrat ic optimization algorithm with rapid infeasibility detection. SIAM J. Optim. 24(2), 839–872 (2014)

work page 2014
[7]

SIAM, Philadelphia (2009)

Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complem entarity Problem. SIAM, Philadelphia (2009)

work page 2009
[8]

SIAM, Philadelphia (2021)

Cui, Y., Pang, J.S.: Modern Nonconvex Nondiﬀerentiable O ptimization. SIAM, Philadelphia (2021)

work page 2021
[9]

De Luca, T., Facchinei, F., Kanzow, C.: A semismooth equat ion approach to the solution of nonlinear complementarity problems. Math. Program. 75(3), 407–439 (1996) A sequential LCP method for GNEPs 37

work page 1996
[10]

De Luca, T., Facchinei, F., Kanzow, C.: A theoretical and numerical comparison of some semismooth algorithms for complementarity problems. Comp ut. Optim. Appl. 16(2), 173–205 (2000)

work page 2000
[11]

Debreu, G.: A social equilibrium existence theorem. Pro c. Natl. Acad. Sci. 38(10), 886–893 (1952)

work page 1952
[12]

Diao, R., Dai, Y.H., Zhang, L.: Stability for Nash equili brium problems. Math. Oper. Res. (2025)

work page 2025
[13]

Dolan, E.D., Mor´ e, J.J.: Benchmarking optimization so ftware with performance proﬁles. Math. Program. 91, 201–213 (2002)

work page 2002
[14]

In: Mathematical Programming with Data Pertu rbations, pp

Dontchev, A., Rockafellar, R.: Characterizations of li pschitzian stability in nonlinear programming. In: Mathematical Programming with Data Pertu rbations, pp. 65–82. CRC Press, Boca Raton, FL, USA (2020)

work page 2020
[15]

Dontchev, A.L., Rockafellar, R.T.: Characterizations of strong regularity for variational inequalities over polyhedral convex sets. SIAM J. Optim. 6(4), 1087–1105 (1996)

work page 1996
[16]

Dontchev, A.L., Rockafellar, R.T.: Implicit Functions and Solution Mappings, vol. 543. Springer, New York (2009)

work page 2009
[17]

Dreves, A.: Finding all solutions of aﬃne generalized Na sh equilibrium problems with one-dimensional strategy sets. Math. Methods Oper. Res. 80(2), 139–159 (2014)

work page 2014
[18]

Dreves, A.: Computing all solutions of linear generaliz ed Nash equilibrium problems. Math. Methods Oper. Res. 85(2), 207–221 (2017)

work page 2017
[19]

Dreves, A., Facchinei, F., Fischer, A., Herrich, M.: A ne w error bound result for gen- eralized Nash equilibrium problems and its algorithmic app lication. Comput. Optim. Appl. 59(1), 63–84 (2014)

work page 2014
[20]

Dreves, A., Facchinei, F., Kanzow, C., Sagratella, S.: O n the solution of the kkt con- ditions of generalized Nash equilibrium problems. SIAM J. O ptim. 21(3), 1082–1108 (2011)

work page 2011
[21]

Drud, A.: Conopt: A grg code for large sparse dynamic nonl inear optimization problems. Math. Program. 31(2), 153–191 (1985)

work page 1985
[22]

Facchinei, F., Fischer, A., Piccialli, V.: Generalized Nash equilibrium problems and newton methods. Math. Program. 117(1), 163–194 (2009)

work page 2009
[23]

4or 5(3), 173–210 (2007)

Facchinei, F., Kanzow, C.: Generalized Nash equilibriu m problems. 4or 5(3), 173–210 (2007)

work page 2007
[24]

Facchinei, F., Kanzow, C.: Generalized Nash equilibriu m problems. Ann. Oper. Res. 175(1), 177–211 (2010)

work page 2010
[25]

Facchinei, F., Kanzow, C.: Penalty methods for the solut ion of generalized Nash equi- librium problems. SIAM J. Optim. 20(5), 2228–2253 (2010)

work page 2010
[26]

Facchinei, F., Lampariello, L.: Partial penalization f or the solution of generalized Nash equilibrium problems. J. Global Optim. 50(1), 39–57 (2011)

work page 2011
[27]

Springer, New York (2003)

Facchinei, F., Pang, J.S.: Finite-Dimensional Variati onal Inequalities and Complemen- tarity Problems, Part II. Springer, New York (2003)

work page 2003
[28]

Fischer, A.: A newton-type method for positive-semideﬁ nite linear complementarity problems. J. Optim. Theory Appl. 86(3), 585–608 (1995)

work page 1995
[29]

: A globally convergent lp-newton method

Fischer, A., Herrich, M., Izmailov, A.F., Solodov, M.V. : A globally convergent lp-newton method. SIAM J. Optim. 26(4), 2012–2033 (2016)

work page 2012
[30]

Pesquisa Operacional 34(3), 521–558 (2014)

Fischer, A., Herrich, M., Sch¨ onefeld, K.: Generalized Nash equilibrium problems-recent advances and challenges. Pesquisa Operacional 34(3), 521–558 (2014)

work page 2014
[31]

Fukushima, M.: Restricted generalized Nash equilibria and controlled penalty algorithm. Comput. Manag. Sci. 8(3), 201–218 (2011)

work page 2011
[32]

SIAM Rev

Gill, P.E., Murray, W., Saunders, M.A.: Snopt: An sqp alg orithm for large-scale con- strained optimization. SIAM Rev. 47(1), 99–131 (2005)

work page 2005
[33]

Han, S.P.: A globally convergent method for nonlinear pr ogramming. J. Optim. Theory Appl. 22(3), 297–309 (1977)

work page 1977
[34]

In: Selected Papers Of Alan J Hoﬀman: With Commentary, pp

Hoﬀman, A.J.: On approximate solutions of systems of lin ear inequalities. In: Selected Papers Of Alan J Hoﬀman: With Commentary, pp. 174–176. W orld Scientiﬁc, Singapore (2003)

work page 2003
[35]

Izmailov, A.F., Solodov, M.V.: Inexact josephy–newton framework for generalized equa- tions and its applications to local analysis of newtonian me thods for constrained opti- mization. Comput. Optim. Appl. 46(2), 347–368 (2010) 38 R. Diao et al

work page 2010
[36]

Springer, Cham (2014)

Izmailov, A.F., Solodov, M.V.: Newton-Type Methods for Optimization and Variational Problems. Springer, Cham (2014)

work page 2014
[37]

Izmailov, A.F., Solodov, M.V.: Newton-type methods: A b roader view. J. Optim. Theory Appl. 164, 577–620 (2015)

work page 2015
[38]

Jordan, M.I., Lin, T., Zampetakis, M.: First-order algo rithms for nonlinear generalized Nash equilibrium problems. J. Mach. Learn. Res. 24(38), 1–46 (2023)

work page 2023
[39]

Josephy, N.: Quasi-newton methods for generalized equa tions. Ph.D. thesis, University of Wisconsin, Madison, WI, USA (1979)

work page 1979
[40]

Kanzow, C., Steck, D.: Augmented lagrangian methods for the solution of generalized Nash equilibrium problems. SIAM J. Optim. 26(4), 2034–2058 (2016)

work page 2034
[41]

Kanzow, C., Steck, D.: Augmented lagrangian and exact pe nalty methods for quasi- variational inequalities. Comput. Optim. Appl. 69(3), 801–824 (2018)

work page 2018
[42]

Kanzow, C., Steck, D.: Quasi-variational inequalities in banach spaces: theory and aug- mented lagrangian methods. SIAM J. Optim. 29(4), 3174–3200 (2019)

work page 2019
[43]

In: International W orkshop on Internet a nd Network Economics, pp

Kesselman, A., Leonardi, S., Bonifaci, V.: Game-theore tic analysis of internet switching with selﬁsh users. In: International W orkshop on Internet a nd Network Economics, pp. 236–245. Springer, Hong Kong, China (2005)

work page 2005
[44]

Kim, J.G.: A new lagrangian-based ﬁrst-order method for nonconvex constrained opti- mization. Oper. Res. Lett. 51(3), 357–363 (2023)

work page 2023
[45]

Mathiesen, L.: Computational experience in solving equ ilibrium models by a sequence of linear complementarity problems. Oper. Res. 33(6), 1225–1250 (1985)

work page 1985
[46]

Mathiesen, L.: An algorithm based on a sequence of linear complementarity problems applied to a walrasian equilibrium model: An example. Math. Program. 37(1), 1–18 (1987)

work page 1987
[47]

Monteiro, R.D., Pang, J.S.: A potential reduction newto n method for constrained equa- tions. SIAM J. Optim. 9(3), 729–754 (1999)

work page 1999
[48]

Mordukhovich, B.S., Outrata, J.V.: Coderivative analy sis of quasi-variational inequal- ities with applications to stability and optimization. SIA M J. Optim. 18(2), 389–412 (2007)

work page 2007
[49]

Murtagh, B.A., Saunders, M.A.: Large-scale linearly co nstrained optimization. Math. Program. 14(1), 41–72 (1978)

work page 1978
[50]

In: Algorithms for C onstrained Minimization of Smooth Nonlinear Functions, pp

Murtagh, B.A., Saunders, M.A.: A projected lagrangian a lgorithm and its implementa- tion for sparse nonlinear constraints. In: Algorithms for C onstrained Minimization of Smooth Nonlinear Functions, pp. 84–117. Springer, Berlin, Heidelberg (2009)

work page 2009
[51]

Spr inger, New York (2006)

Nocedal, J., W right, S.J.: Numerical Optimization. Spr inger, New York (2006)

work page 2006
[52]

Cambridge University Press, New York, NY, USA (201 0)

Palomar, D.P., Eldar, Y.C.: Convex Optimization in Sign al Processing and Communi- cations. Cambridge University Press, New York, NY, USA (201 0)

work page
[53]

Pang, J.S., Fukushima, M.: Quasi-variational inequali ties, generalized Nash equilibria, and multi-leader-follower games. Comput. Manag. Sci. 2(1), 21–56 (2005)

work page 2005
[54]

Robinson, S.M.: Strongly regular generalized equation s. Math. Oper. Res. 5(1), 43–62 (1980)

work page 1980
[55]

Rockafellar, R.T.: Convex Analysis, vol. 28. Princeton University Press, Princeton, NJ, USA (1997)

work page 1997
[56]

Rockafellar, R.T., W ets, R.J.B.: Variational Analysis , vol. 317. Springer, Berlin, Hei- delberg (2009)

work page 2009
[57]

Schiro, D.A., Pang, J.S., Shanbhag, U.V.: On the solutio n of aﬃne generalized Nash equilibrium problems with shared constraints by lemke’s me thod. Math. Program. 142(1), 1–46 (2013)

work page 2013
[58]

Schittkowski, K.: Nlpql: A fortran subroutine solving c onstrained nonlinear program- ming problems. Ann. Oper. Res. 5(2), 485–500 (1986)

work page 1986