pith. sign in

arxiv: 2606.22869 · v1 · pith:MGG5DG4Enew · submitted 2026-06-22 · 🧮 math.OC

A Variable-Metric Non-monotone Line Search Method for Mixed Variational Inequalities and Equilibrium Problems

Mohammed Alshahrani This is my paper

Pith reviewed 2026-06-26 07:57 UTC · model grok-4.3

classification 🧮 math.OC
keywords variational inequalitiesmixed variational inequalitiesequilibrium problemsgap functionsvariable metric methodsnon-monotone line searchconvergence analysis
0
0 comments X

The pith

A variable-metric scaled projection step that coincides with the Fukushima gap maximizer drives global convergence and R-linear rate for strongly monotone variational inequalities.

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

The paper develops a gap-function method for variational inequalities, mixed variational inequalities, and equilibrium problems that combines a variable-metric scaled projection with a modified non-monotone Armijo line search. The central construction uses the fact that the projection step is exactly the point that maximizes the regularized gap, so the same direction serves both algorithmic and gap-measurement roles. For operators that are strongly monotone and Lipschitz continuous the analysis yields global convergence together with an R-linear rate that follows directly from the contraction property and an explicit gap error bound; the result holds for both fixed metrics and metrics whose change is controlled. Numerical tests on controlled instances confirm the predicted rates and compare the performance against standard extragradient and gap-descent schemes.

Core claim

The scaled projection step is exactly the maximizer that defines the Fukushima regularized gap, so the search direction is simultaneously the algorithmic step and the gap-defining direction. For variational and mixed variational inequalities with a strongly monotone, Lipschitz operator the method therefore converges globally and at an R-linear rate under a fixed or controlled-change variable metric; the rate follows from the strong-monotonicity contraction and the resulting explicit gap error bound. For equilibrium problems the method yields global convergence together with a gap error bound.

What carries the argument

The variable-metric scaled projection step, which is simultaneously the algorithmic update and the maximizer of the Fukushima regularized gap function.

If this is right

  • The method converges globally to a solution of variational inequalities, mixed variational inequalities, and equilibrium problems.
  • An R-linear rate holds whenever the operator is strongly monotone and Lipschitz continuous.
  • An explicit gap error bound follows from the contraction induced by strong monotonicity.
  • The convergence guarantees remain valid when the variable metric is fixed or changes in a controlled manner.

Where Pith is reading between the lines

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

  • The same structural identity between projection and gap maximizer might be reusable for designing gap-based methods on other classes of equilibrium-type problems not treated in the paper.
  • Numerical comparison on ill-conditioned instances could show whether the variable-metric scaling yields practical speed-ups beyond the theoretical guarantees already proved.

Load-bearing premise

The operator that defines the variational inequality must be strongly monotone and Lipschitz continuous.

What would settle it

A concrete instance with a strongly monotone Lipschitz operator on which the observed convergence rate is slower than R-linear, or on which the method fails to converge, would contradict the stated rate and global-convergence claims.

Figures

Figures reproduced from arXiv: 2606.22869 by Mohammed Alshahrani.

Figure 1
Figure 1. Figure 1: Global convergence. SGFM on the affine variational inequality (Problem 1) from the five starting points of Section 6.4. The residual reaches 10−6 from every start with a common asymptotic slope [PITH_FULL_IMAGE:figures/full_fig_p026_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: R-linear rate. The residual of SGFM on Problem 1 is a straight line on a logarithmic scale (Theorem 5.7). 26 [PITH_FULL_IMAGE:figures/full_fig_p026_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Best-iterate floor as the operator weakens. SGFM on the weakly monotone family (Problem 3) at ρ = 10−1 ,10−2 ,10−3 . The strongly monotone member (ρ = 10−1 ) converges, while smaller ρ approach the O(1/√ N) floor of Corollary 5.6. 6.6 The variable metric On a badly conditioned operator the metric decides the speed, and the diagonal metric wins when the conditioning lies on the diagonal [PITH_FULL_IMAGE:fi… view at source ↗
Figure 4
Figure 4. Figure 4: Variable metric. SGFM with the diagonal Dk and with Dk = I (SGFM-Eucl) on the affine operator conditioned at 103 . The diagonal metric is about an order of magnitude faster and keeps the R-linear rate of Theorem 5.13. 6.7 The modified non-monotone line search On these smooth strongly monotone problems the non-monotone line search neither speeds the method up nor slows it down, as the construction predicts … view at source ↗
Figure 5
Figure 5. Figure 5: Modified versus monotone line search. SGFM and its monotone variant (η = 0) on Problem 1. The residual curves coincide, so the non-monotone terms do not change the rate. 28 [PITH_FULL_IMAGE:figures/full_fig_p028_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The moving-average reference Tk against the gap gα(xk ) for SGFM on Problem 1. The gap decreases monotonically, so Tk tracks it and the relaxation stays dormant. 6.8 Merit equivalence The gap and the D-gap measure progress in the same way [PITH_FULL_IMAGE:figures/full_fig_p029_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Merit equivalence. The gap gα along the SGFM iterates and the D-gap along the Bigi–Passacantando iterates on the equilibrium problem (Problem 6). Both vanish R-linearly, consistent with Proposition 5.11. 29 [PITH_FULL_IMAGE:figures/full_fig_p029_7.png] view at source ↗
read the original abstract

We propose a scaled gap-function method for variational inequalities, mixed variational inequalities, and equilibrium problems over a closed convex set. The method drives a gap function to zero by combining a variable-metric scaled projection step with a modified non-monotone Armijo line search. The construction rests on a structural identity: the scaled projection step is exactly the maximizer that defines the Fukushima regularized gap, so the search direction is simultaneously the algorithmic step and the gap-defining direction. For variational and mixed variational inequalities with a strongly monotone, Lipschitz operator we establish global convergence and an R-linear rate, under a fixed or a controlled-change variable metric. The rate follows from the strong-monotonicity contraction and the resulting explicit gap error bound. For equilibrium problems we obtain global convergence and a gap error bound (Mastroeni's gap). Numerical experiments on controlled problems confirm the convergence guarantees and the predicted rate, and compare the method with standard extragradient and gap-descent methods. The combination of variable-metric scaling, a modified non-monotone line search, and gap-function descent appears to be new for these problem classes.

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.

Referee Report

0 major / 3 minor

Summary. The paper proposes a scaled gap-function method for variational inequalities (VI), mixed variational inequalities (MVI), and equilibrium problems over closed convex sets. It combines a variable-metric scaled projection step (which coincides with the maximizer of the Fukushima regularized gap) with a modified non-monotone Armijo line search. For VI and MVI with strongly monotone Lipschitz operators, global convergence and an R-linear rate are claimed under fixed or controlled-change variable metrics, with the rate derived from the strong-monotonicity contraction and an explicit gap error bound. For equilibrium problems, global convergence and a gap error bound are established. Numerical experiments on controlled problems validate the claims and compare against extragradient and gap-descent methods.

Significance. If the stated convergence results hold, the work contributes a new algorithmic framework that integrates variable-metric scaling, non-monotone line search, and gap-function descent for these problem classes. The structural identity between the scaled projection and the gap maximizer is a useful observation that enables the descent and rate arguments. The numerical validation and explicit rate under standard assumptions add practical value.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'controlled-change variable metric' is used without a precise statement of the condition; this should be defined or referenced to the relevant theorem early in the paper.
  2. [Numerical experiments] The numerical section would benefit from explicit reporting of the variable-metric update rule and the specific values of the control parameters used in the experiments.
  3. [Method description] Notation for the gap function and the scaled projection should be introduced consistently before the main algorithmic description.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment and recommendation of minor revision. The provided summary correctly reflects the paper's contributions, including the structural identity between the scaled projection and the Fukushima gap maximizer, the convergence and rate results under strong monotonicity, and the numerical comparisons.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's convergence claims rest on the standard external assumptions of strong monotonicity and Lipschitz continuity of the operator to derive contraction and the explicit gap error bound. The structural identity between the scaled projection and the Fukushima gap maximizer is presented as an algebraic fact enabling the descent direction, not as a self-referential definition. No derivation step reduces a prediction or rate to a fitted parameter or self-citation chain; the analysis is self-contained against these standard operator properties without internal redefinition or load-bearing self-reference.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are described in the abstract; the method relies on standard assumptions of strong monotonicity and Lipschitz continuity that are external to the paper.

pith-pipeline@v0.9.1-grok · 5725 in / 1145 out tokens · 21629 ms · 2026-06-26T07:57:08.871686+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 33 canonical work pages · 1 internal anchor

  1. [1]

    From optimization and variational inequalities to equilibrium problems

    E. Blum and W. Oettli. “From optimization and variational inequalities to equilibrium problems”.The Mathematics Student63.1-4 (1994), pp. 123–145

    1994

  2. [2]

    Facchinei and J.-S

    F. Facchinei and J.-S. Pang, eds.Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Series in Operations Research and Financial Engineering. New York, NY: Springer, 2004.doi:10.1007/b97543

    work page doi:10.1007/b97543 2004

  3. [3]

    Merit functions: a bridge between optimization and equilibria

    M. Pappalardo, G. Mastroeni, and M. Passacantando. “Merit functions: a bridge between optimization and equilibria”.4OR12.1 (Mar. 2014), pp. 1–33.doi: 10.1007/s10288-014- 0256-5

    work page doi:10.1007/s10288-014- 2014

  4. [4]

    The extragradient method for finding saddle points and other problems

    G. M. Korpelevich. “The extragradient method for finding saddle points and other problems”. Ekonomika i Matematicheskie Metody12.4 (1976), pp. 747–756

    1976

  5. [5]

    The Subgradient Extragradient Method for Solving Variational Inequalities in Hilbert Space

    Y. Censor, A. Gibali, and S. Reich. “The Subgradient Extragradient Method for Solving Variational Inequalities in Hilbert Space”.Journal of Optimization Theory and Applications148.2 (Feb. 2011), pp. 318–335.doi:10.1007/s10957-010-9757-3

    work page doi:10.1007/s10957-010-9757-3 2011

  6. [6]

    A New Projection Method for Variational Inequality Problems

    M. V . Solodov and B. F. Svaiter. “A New Projection Method for Variational Inequality Problems”.SIAM Journal on Control and Optimization37.3 (Jan. 1999), pp. 765–776.doi: 10.1137/S0363012997317475

    work page doi:10.1137/s0363012997317475 1999

  7. [7]

    Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems

    M. Fukushima. “Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems”.Mathematical Programming53.1 (Jan. 1992), pp. 99–110.doi:10.1007/BF01585696

    work page doi:10.1007/bf01585696 1992

  8. [8]

    Gap Functions for Equilibrium Problems

    G. Mastroeni. “Gap Functions for Equilibrium Problems”.Journal of Global Optimization27.4 (Dec. 2003), pp. 411–426.doi:10.1023/A:1026050425030. 32

    work page doi:10.1023/a:1026050425030 2003

  9. [9]

    Q. H. Ansari, F. Babu, D. R. Sahu, and J. C. Yao.A Scaled Gradient Modified Non-monotone Line Search Method for Constrained Optimization Problems. Apr. 2026.doi: 10.48550/arXiv. 2604.28110

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv 2026

  10. [10]

    A Nonmonotone Line Search Technique and Its Application to Unconstrained Optimization

    H. Zhang and W. W. Hager. “A Nonmonotone Line Search Technique and Its Application to Unconstrained Optimization”.SIAM Journal on Optimization14.4 (Jan. 2004), pp. 1043–1056. doi:10.1137/S1052623403428208

    work page doi:10.1137/s1052623403428208 2004

  11. [11]

    Incorporating nonmonotone strategies into the trust region method for unconstrained optimization

    N.-z. Gu and J. -t. Mo. “Incorporating nonmonotone strategies into the trust region method for unconstrained optimization”.Computers & Mathematics with Applications55.9 (May 2008), pp. 2158–2172.doi:10.1016/j.camwa.2007.08.038

    work page doi:10.1016/j.camwa.2007.08.038 2008

  12. [12]

    A memory gradient method based on the nonmonotone technique

    Y. Ou and Y. Liu. “A memory gradient method based on the nonmonotone technique”. Journal of Industrial and Management Optimization13.2 (2016), pp. 857–872.doi: 10.3934/ jimo.2016050

    2016

  13. [13]

    Modified nonmonotone Armijo line search for descent method

    Z. Shi and S. Wang. “Modified nonmonotone Armijo line search for descent method”. Numerical Algorithms57.1 (May 2011), pp. 1–25.doi:10.1007/s11075-010-9408-7

    work page doi:10.1007/s11075-010-9408-7 2011

  14. [14]

    A Nonmonotone Line Search Technique for Newton’s Method

    L. Grippo, F. Lampariello, and S. Lucidi. “A Nonmonotone Line Search Technique for Newton’s Method”.SIAM Journal on Numerical Analysis23.4 (Aug. 1986), pp. 707–716.doi: 10.1137/0723046

    work page doi:10.1137/0723046 1986

  15. [15]

    A scaled gradient projection method for constrained image deblurring

    S. Bonettini, R. Zanella, and L. Zanni. “A scaled gradient projection method for constrained image deblurring”.Inverse Problems25.1 (Jan. 2009), p. 015002.doi: 10.1088/0266-5611/25/ 1/015002

    work page doi:10.1088/0266-5611/25/ 2009

  16. [16]

    Variable metric forward–backward splitting with applications to monotone inclusions in duality

    P . L. Combettes and B. C. V˜u. “Variable metric forward–backward splitting with applications to monotone inclusions in duality”.Optimization63.9 (Sept. 2014), pp. 1289–1318.doi: 10.1080/02331934.2012.733883

    work page doi:10.1080/02331934.2012.733883 2014

  17. [17]

    An Inertial Forward-Backward Algorithm for Monotone In- clusions

    D. A. Lorenz and T. Pock. “An Inertial Forward-Backward Algorithm for Monotone In- clusions”.Journal of Mathematical Imaging and Vision51.2 (Feb. 2015), pp. 311–325.doi: 10.1007/s10851-014-0523-2

    work page doi:10.1007/s10851-014-0523-2 2015

  18. [18]

    On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators

    C. D. Dang and G. Lan. “On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators”.Computational Optimization and Applications60.2 (Mar. 2015), pp. 277–310.doi: 10.1007/s10589-014-9673- 9

    work page doi:10.1007/s10589-014-9673- 2015

  19. [19]

    A New Descent Method for Symmetric Non-monotone Variational Inequalities with Application to Eigenvalue Complementarity Problems

    F. Abdi and F. Shakeri. “A New Descent Method for Symmetric Non-monotone Variational Inequalities with Application to Eigenvalue Complementarity Problems”.Journal of Opti- mization Theory and Applications173.3 (June 2017), pp. 923–940.doi: 10.1007/s10957-017- 1100-9

    work page doi:10.1007/s10957-017- 2017

  20. [20]

    L. Deng, R. Hu, and Y. Fang.A linesearch projection algorithm for solving equilibrium problems without monotonicity in Hilbert spaces. Mar. 2021.doi:10.48550/arXiv.2006.04022

    work page doi:10.48550/arxiv.2006.04022 2021

  21. [21]

    D-gap functions and descent techniques for solving equilibrium problems

    G. Bigi and M. Passacantando. “D-gap functions and descent techniques for solving equilibrium problems”.Journal of Global Optimization62.1 (May 2015), pp. 183–203.doi: 10.1007/s10898-014-0223-x

    work page doi:10.1007/s10898-014-0223-x 2015

  22. [22]

    On the convergence properties of scaled gradient projection methods with non-monotone Armijo–like line searches

    S. Crisci, F. Porta, V . Ruggiero, and L. Zanni. “On the convergence properties of scaled gradient projection methods with non-monotone Armijo–like line searches”.ANNALI DELL’UNIVERSITA’ DI FERRARA68.2 (Nov. 2022), pp. 521–554.doi: 10.1007/s11565-022- 00437-2

    work page doi:10.1007/s11565-022- 2022

  23. [23]

    Equivalence of variational inequality problems to unconstrained minimization

    J.-M. Peng. “Equivalence of variational inequality problems to unconstrained minimization”. Mathematical Programming78.3 (Sept. 1997), pp. 347–355.doi:10.1007/BF02614360

    work page doi:10.1007/bf02614360 1997

  24. [24]

    Unconstrained Optimization Reformulations of Variational Inequality Problems

    N. Yamashita, K. Taji, and M. Fukushima. “Unconstrained Optimization Reformulations of Variational Inequality Problems”.Journal of Optimization Theory and Applications92.3 (Mar. 1997), pp. 439–456.doi:10.1023/A:1022660704427

    work page doi:10.1023/a:1022660704427 1997

  25. [25]

    Error bounds in mathematical programming

    J.-S. Pang. “Error bounds in mathematical programming”.Mathematical Programming79.1 (Oct. 1997), pp. 299–332.doi:10.1007/BF02614322. 33

    work page doi:10.1007/bf02614322 1997

  26. [26]

    Kurdyka-Łojasiewicz inequality and error bounds of D-Gap functions for nonsmooth and nonmonotone variational inequality problems

    M. H. Li, K. W. Meng, and X. Q. Yang. “Kurdyka-Łojasiewicz inequality and error bounds of D-Gap functions for nonsmooth and nonmonotone variational inequality problems”.Journal of Global Optimization93.3 (Nov. 2025), pp. 833–860.doi:10.1007/s10898-025-01558-6

    work page doi:10.1007/s10898-025-01558-6 2025

  27. [27]

    L. Zhao, D. Zhu, and S. Zhang.New Classes of Non-monotone Variational Inequality Problems Solvable via Proximal Gradient on Smooth Gap Functions. Oct. 2025.doi: 10.48550/arXiv.2510. 12105

    work page doi:10.48550/arxiv.2510 2025

  28. [28]

    A Two-Step Proximal Point Algorithm for Nonconvex Equilibrium Problems with Applications to Fractional Programming

    A. Iusem, F. Lara, R. T. Marcavillaca, and L. H. Yen. “A Two-Step Proximal Point Algorithm for Nonconvex Equilibrium Problems with Applications to Fractional Programming”.Journal of Global Optimization90.3 (Nov. 2024), pp. 755–779.doi:10.1007/s10898-024-01419-8

    work page doi:10.1007/s10898-024-01419-8 2024

  29. [29]

    An extragradient projection method for strongly quasiconvex equilibrium problems with applications

    F. Lara, R. T. Marcavillaca, and L. H. Yen. “An extragradient projection method for strongly quasiconvex equilibrium problems with applications”.Computational and Applied Mathematics 43.3 (Mar. 2024), p. 128.doi:10.1007/s40314-024-02626-5

    work page doi:10.1007/s40314-024-02626-5 2024

  30. [30]

    Convergence and error bound of a D-gap function based Newton-type algorithm for equilibrium problems

    L. Zhang, S.-Y. Wu, and S.-C. Fang. “Convergence and error bound of a D-gap function based Newton-type algorithm for equilibrium problems”.Journal of Industrial and Management Optimization6.2 (2010), pp. 333–346.doi:10.3934/jimo.2010.6.333

    work page doi:10.3934/jimo.2010.6.333 2010

  31. [31]

    New convergence results for the scaled gradient projection method

    S. Bonettini and M. Prato. “New convergence results for the scaled gradient projection method”.Inverse Problems31.9 (Aug. 2015), p. 095008.doi: 10.1088/0266- 5611/31/9/ 095008

    work page doi:10.1088/0266- 2015

  32. [32]

    H. H. Bauschke and P . L. Combettes.Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics. Cham: Springer International Publishing, 2017.doi: 10.1007/978-3-319-48311-5

    work page doi:10.1007/978-3-319-48311-5 2017

  33. [33]

    On Strongly Quasiconvex Functions: Existence Results and Proximal Point Algo- rithms

    F. Lara. “On Strongly Quasiconvex Functions: Existence Results and Proximal Point Algo- rithms”.Journal of Optimization Theory and Applications192.3 (Mar. 2022), pp. 891–911.doi: 10.1007/s10957-021-01996-8

    work page doi:10.1007/s10957-021-01996-8 2022

  34. [34]

    Extragradient algorithms extended to equilibrium problems

    D. Quoc Tran, M. Le Dung, and V . H. Nguyen. “Extragradient algorithms extended to equilibrium problems”.Optimization57.6 (Dec. 2008), pp. 749–776.doi: 10 . 1080 / 02331930601122876

    2008

  35. [35]

    J. M. Ortega and W. C. Rheinboldt.Iterative Solution of Nonlinear Equations in Several Variables. Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, Jan. 2000. doi:10.1137/1.9780898719468

    work page doi:10.1137/1.9780898719468 2000

  36. [36]

    Strongly Quasiconvex Functions: What We Know (So Far)

    S.-M. Grad, F. Lara, and R. T. Marcavillaca. “Strongly Quasiconvex Functions: What We Know (So Far)”.Journal of Optimization Theory and Applications205.2 (Mar. 2025), p. 38.doi: 10.1007/s10957-025-02641-4

    work page doi:10.1007/s10957-025-02641-4 2025

  37. [37]

    Extension of newton and quasi-Newton methods to systems of PC1 equations

    M. Kojima and S. Shindo. “Extension of newton and quasi-Newton methods to systems of PC1 equations”.Journal of the Operations Research Society of Japan29.4 (1986), pp. 352–375

    1986

  38. [38]

    Dual extragradient algorithms extended to equilibrium problems

    T. D. Quoc, P . N. Anh, and L. D. Muu. “Dual extragradient algorithms extended to equilibrium problems”.Journal of Global Optimization52.1 (Jan. 2012), pp. 139–159.doi: 10.1007/s10898-011-9693-2. 34

    work page doi:10.1007/s10898-011-9693-2 2012