pith. sign in

arxiv: 2504.05609 · v2 · submitted 2025-04-08 · 🧮 math.OC

Extended SQP Methods in Nonsmooth Difference Programming Applied to Problems with Variational Inequality Constraints

Boris S. Mordukhovich , Yixia Song , Shangzhi Zeng , Jin Zhang This is my paper

Pith reviewed 2026-05-22 21:04 UTC · model grok-4.3

classification 🧮 math.OC
keywords difference programmingsequential quadratic programmingvariational inequalitiesPolyak-Łojasiewicz-Kurdyka propertynonsmooth optimizationglobal convergencesemialgebraic functionsnetwork design
0
0 comments X

The pith

Extended SQP methods converge globally for nonsmooth difference programming problems when the Polyak-Łojasiewicz-Kurdyka property holds.

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

This paper develops novel variants of the extended sequential quadratic programming method for constrained difference programming problems in which both the objective and the constraints are expressed as differences of functions without any convexity requirement. At each iteration the algorithms form and solve a strongly convex quadratic subproblem obtained by linearizing the data via gradients and subgradients. Global convergence to stationary points is proved by invoking the Polyak-Łojasiewicz-Kurdyka property, which is known to hold for semialgebraic functions and other broad classes. The same algorithmic framework is then applied to difference programs that contain variational inequality constraints after these are rewritten with regularized gap functions. Numerical results on continuous network design problems confirm practical efficiency.

Core claim

The paper shows that the proposed extended SQP algorithms converge globally for constrained difference programming problems under the Polyak-Łojasiewicz-Kurdyka property and that the identical framework solves difference programs with variational inequality constraints once the latter are recast via regularized gap functions.

What carries the argument

The extended sequential quadratic programming iteration that builds and solves strongly convex quadratic subproblems from linear approximations of the difference-structured objective and constraints using gradients and subgradients.

If this is right

  • The methods apply without change to any semialgebraic difference program.
  • Variational inequality constraints become directly treatable by substitution with regularized gap functions.
  • Global convergence is obtained without convexity assumptions on the component functions.
  • The same algorithmic template covers continuous network design problems and similar equilibrium-constrained tasks.

Where Pith is reading between the lines

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

  • The reformulation technique may allow other equilibrium or complementarity constraints to be handled inside the difference programming setting.
  • Verification of the Polyak-Łojasiewicz-Kurdyka property for additional nonsmooth function classes would immediately enlarge the guaranteed convergence domain.
  • The quadratic subproblem construction could be adapted to inexact or stochastic gradient information while preserving the convergence argument.

Load-bearing premise

The functions appearing in the objective and constraints satisfy the Polyak-Łojasiewicz-Kurdyka property.

What would settle it

A concrete difference programming instance whose functions violate the Polyak-Łojasiewicz-Kurdyka property and on which the algorithm sequence fails to approach any stationary point.

Figures

Figures reproduced from arXiv: 2504.05609 by Boris S. Mordukhovich, Jin Zhang, Shangzhi Zeng, Yixia Song.

Figure 1
Figure 1. Figure 1: Performance comparison of objective values and feasibility for demand scenario [PITH_FULL_IMAGE:figures/full_fig_p028_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Evolution of the penalty parameter over iterations for demand scenario [PITH_FULL_IMAGE:figures/full_fig_p028_2.png] view at source ↗
read the original abstract

This paper explores a new class of constrained difference programming problems, where the objective and constraints are formulated as differences of functions, without requiring their convexity. To investigate such problems, novel variants of the extended sequential quadratic method are introduced. These algorithms iteratively solve strongly convex quadratic subproblems constructed via linear approximations of the given data by using their gradients and subgradients. The convergence of the proposed methods is rigorously analyzed by employing, in particular, the Polyak-\L ojasiewicz-Kurdyka property that ensures global convergence for various classes of functions in the problem formulation, e.g., semialgebraic ones. The original framework is further extended to address difference programming problems with variational inequality (VI) constraints. By reformulating VI constraints via regularized gap functions, such problems are naturally embedded into constrained difference programming that leads us to direct applications of the proposed algorithms. Numerical experiments for the class of continuous network design problems demonstrate the efficiency of the new methods.

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

1 major / 1 minor

Summary. The paper proposes novel variants of extended sequential quadratic programming (SQP) methods for nonsmooth difference-of-convex programming problems in which both the objective and constraints are expressed as differences of (not necessarily convex) functions. The algorithms solve strongly convex quadratic subproblems at each iteration using linear approximations based on gradients and subgradients. Global convergence is claimed via the Polyak-Łojasiewicz-Kurdyka (PLK) property, which is known to hold for semialgebraic and related function classes. The framework is extended to difference programs with variational inequality constraints by embedding them through regularized gap functions, and numerical results on continuous network design problems are reported.

Significance. If the convergence analysis is correct, the work supplies a systematic SQP-style framework for a broad class of nonsmooth DC programs that includes VI constraints, with direct applicability to network design and related equilibrium problems. The explicit use of the PLK property to obtain global convergence for semialgebraic data is a technically attractive feature that aligns with existing literature on nonsmooth DC optimization.

major comments (1)
  1. [Abstract] Abstract: the claim that 'the convergence of the proposed methods is rigorously analyzed by employing, in particular, the Polyak-Łojasiewicz-Kurdyka property' is asserted without any derivation, error bound, or explicit verification step supplied in the provided text. Because this property is load-bearing for the global-convergence statement, the manuscript must contain the detailed argument (including how the PLK inequality is verified or inherited for the regularized-gap reformulation of the VI constraints) before the central claim can be accepted.
minor comments (1)
  1. The notation 'Polyak-Łojasiewicz-Kurdyka' should be introduced once with a precise definition or reference and then used consistently; the current abstract spelling contains a typographic artifact ('-Ł ojasiewicz').

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the constructive comment on the abstract and convergence claims. We address the point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that 'the convergence of the proposed methods is rigorously analyzed by employing, in particular, the Polyak-Łojasiewicz-Kurdyka property' is asserted without any derivation, error bound, or explicit verification step supplied in the provided text. Because this property is load-bearing for the global-convergence statement, the manuscript must contain the detailed argument (including how the PLK inequality is verified or inherited for the regularized-gap reformulation of the VI constraints) before the central claim can be accepted.

    Authors: The abstract is a concise summary; the full manuscript contains the detailed convergence analysis in Sections 3–5. There we establish global convergence of the extended SQP iterates under the PLK inequality when the data are semialgebraic (invoking the known fact that semialgebraic functions satisfy the PLK property with a suitable exponent). For the VI-constrained case, the regularized gap function is a composition of continuous semialgebraic operations (inner products, maxima, and the strongly convex regularizer), hence remains semialgebraic whenever the original mapping is; the PLK property is therefore inherited directly by the reformulated difference program. We will add an explicit clarifying paragraph (or remark) immediately after the statement of the main convergence theorem to spell out this inheritance step and will slightly expand the abstract to reference the relevant sections. revision: partial

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's derivation chain relies on external analytic tools such as the Polyak-Łojasiewicz-Kurdyka property (applicable to semialgebraic and similar function classes) for global convergence guarantees of the proposed extended SQP methods, and on the standard reformulation of VI constraints via regularized gap functions to embed them into the difference programming setting. Neither step reduces to a self-definition, a fitted input renamed as prediction, or a load-bearing self-citation chain; the central claims remain independent of the algorithm outputs and rest on established variational analysis results outside the present work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central convergence claim rests on the Polyak-Łojasiewicz-Kurdyka property holding for the problem functions; this is an external analytic assumption rather than a derived result.

axioms (1)
  • domain assumption The Polyak-Łojasiewicz-Kurdyka property holds for the functions in the problem formulation (or the functions are semialgebraic).
    Invoked to guarantee global convergence of the proposed algorithms.

pith-pipeline@v0.9.0 · 5707 in / 1280 out tokens · 46721 ms · 2026-05-22T21:04:13.967749+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

43 extracted references · 43 canonical work pages

  1. [1]

    Transportation Research Part B: Methodological 13, 19–32 (1979)

    Abdulaal, M., LeBlanc, L.J.: Continuous equilibrium network design models. Transportation Research Part B: Methodological 13, 19–32 (1979)

    work page 1979

  2. [2]

    In: Advanced Computational Methods for Knowledge Engineering, pp

    An, L.T.H., Ngai, H.V., Tao, P.D.: DC programming and DCA for general DC programs. In: Advanced Computational Methods for Knowledge Engineering, pp. 15–35. Springer, Cham (2014)

    work page 2014

  3. [3]

    Annals of Operations Research 133, 23–46 (2005)

    An, L.T.V., Tao, P.D.: The DC (difference of convex functions) programming and DCA re- visited with DC models of real-world nonconvex optimization problems. Annals of Operations Research 133, 23–46 (2005)

    work page 2005

  4. [4]

    Mathematical Programming, DOI 10.1007/s10107-024-02142-8 (2024)

    Arag´ on-Artacho, F.J., Mordukhovich, B.S., P´ erez-Aros, P.: Coderivative-based semi- Newton method in nonsmooth difference programming. Mathematical Programming, DOI 10.1007/s10107-024-02142-8 (2024)

    work page doi:10.1007/s10107-024-02142-8 2024

  5. [5]

    Arag´ on-Artacho, F.J., Vuong, P.T.: The boosted difference of convex functions algorithm for nonsmooth functions. SIAM J. Optim. 30, 980–1006 (2020)

    work page 2020

  6. [6]

    Mathematical Programming 137, 91–129 (2013)

    Attouch, H., Bolt´ e, J., Svaiter, B.F.: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel method. Mathematical Programming 137, 91–129 (2013)

    work page 2013

  7. [7]

    Journal of Opti- mization Theory and Applications 156, 183–212 (2013)

    Auslender, A.: An extended sequential quadratically constrained quadratic programming algorithm for nonlinear, semidefinite, and second-order cone programming. Journal of Opti- mization Theory and Applications 156, 183–212 (2013)

    work page 2013

  8. [8]

    SIAM, Philadelphia, PA (2017)

    Beck, A.: First-Order Methods in Optimization. SIAM, Philadelphia, PA (2017)

    work page 2017

  9. [9]

    https://optimization- online.org/2025/02/(2025)

    Bento, G., Mordukhovich, B.S., Mota, T., Nesterov, Y.: Convergence of descent op- timization algorithms under Polyak-Lojasiewicz-Kurdyka conditions. https://optimization- online.org/2025/02/(2025)

    work page 2025

  10. [10]

    Athena Scientific, Belmont, MA (2016)

    Bertsekas, D.P.: Nonlinear Programming, 3rd edition. Athena Scientific, Belmont, MA (2016)

    work page 2016

  11. [11]

    Acta Numerica 4, 1–51 (1995)

    Boggs, P.T., Tolle, J.W.: Sequential quadratic programming. Acta Numerica 4, 1–51 (1995)

    work page 1995

  12. [12]

    SIAM Journal on Optimization 18, 556–572 (2007) 29

    Bolt´ e, J., Daniilidis, A., Lewis, A.S., Shiota, M.: Clarke subgradients of stratifiable func- tions. SIAM Journal on Optimization 18, 556–572 (2007) 29

    work page 2007

  13. [13]

    Journal of Convex Analysis 2, 117–144 (1995)

    Clarke, F.H., Stern, R.J., Wolenski, P.R.: Proximal smoothness and the lower- C2 property. Journal of Convex Analysis 2, 117–144 (1995)

    work page 1995

  14. [14]

    Springer, New York (2003)

    Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)

    work page 2003

  15. [15]

    arXiv:2412.05697 (2024)

    Ferreira, O.P., Mordukhovich, B.S., Santos, W.M.S., Souza, J.C.O.: An inexact boosted difference of convex algorithm for nondifferentiable functions. arXiv:2412.05697 (2024)

    work page arXiv 2024

  16. [16]

    Mathematical Programming 53, 99–110 (1992)

    Fukushima, M.: Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Mathematical Programming 53, 99–110 (1992)

    work page 1992

  17. [17]

    In: Proceedings of the International Conference on Learning Representations (ICLR), Arlington, WI (2019)

    Gidel, G., Berard, H., Vignoud, G., Vincent, P., Lacoste-Julien, S.: A variational in- equality perspective on generative adversarial networks. In: Proceedings of the International Conference on Learning Representations (ICLR), Arlington, WI (2019)

    work page 2019

  18. [18]

    Journal of Optimization Theory and Applications 166, 234–256 (2015)

    Guo, L., Lin, G.H., Ye, J.J.: Solving mathematical programs with equilibrium constraints. Journal of Optimization Theory and Applications 166, 234–256 (2015)

    work page 2015

  19. [19]

    In: Proceedings of the 9th International Symposium on Transportation and Traffic Theory, pp

    Harker, P.T., Friesz, T.L.: Bounding the solution of the continuous equilibrium network design problem. In: Proceedings of the 9th International Symposium on Transportation and Traffic Theory, pp. 75–96. VNU Science Press, Delft, Netherlands (1984)

    work page 1984

  20. [20]

    Springer, Cham (2014)

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

    work page 2014

  21. [21]

    SIAM, Philadelphia, PA (2000)

    Kinderlehrer, D., Stampacchia, G.: An Introduction to Variational Inequalities and Their Applications. SIAM, Philadelphia, PA (2000)

    work page 2000

  22. [22]

    Karimi, J

    H. Karimi, J. Nutini and M. Schmidt, Linear convergence of gradient and proximal-gradient methods under the Polyak- Lojasiewicz condition, In: Machine Learning and Knowledge Dis- covery in Databases, Part 1, pp. 795–811. Springer, Cham, Switzerland (2016)

    work page 2016

  23. [23]

    In: System Modelling and Optimization, pp

    Ko˘ cvara, M., Outrata, J.V.: A nondifferentiable approach to the solution of optimum design problems with variational inequalities. In: System Modelling and Optimization, pp. 364–373. Springer, Berlin, Heidelberg (1992)

    work page 1992

  24. [24]

    SIAM Journal on Optimization 11, 656–674 (2001)

    Lawrence, C., Tits, A.: A computationally efficient feasible sequential quadratic program- ming algorithm. SIAM Journal on Optimization 11, 656–674 (2001)

    work page 2001

  25. [25]

    SIAM Journal on Control and Optimization 40, 699—-23 (2001)

    Lucet, Y., Ye, J.J.: Sensitivity analysis of the value function for optimization problems with variational inequality constraints. SIAM Journal on Control and Optimization 40, 699—-23 (2001)

    work page 2001

  26. [26]

    Mathematical Programming 34, 142–162 (1986)

    Marcotte, P.: Network design problem with congestion effects: a case of bilevel program- ming. Mathematical Programming 34, 142–162 (1986)

    work page 1986

  27. [27]

    Springer, Berlin (2006)

    Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation, I: Basic Theory, II: Applications. Springer, Berlin (2006)

    work page 2006

  28. [28]

    Springer, Cham, Switzerland (2018)

    Mordukhovich, B.S.: Variational Analysis and Applications. Springer, Cham, Switzerland (2018)

    work page 2018

  29. [29]

    Springer, Cham, Switzerland (2024)

    Mordukhovich, B.S.: Second-Order Variational Analysis in Optimization, Variational Sta- bility, and Control: Theory, Algorithms, Applications. Springer, Cham, Switzerland (2024)

    work page 2024

  30. [30]

    Springer, Cham, Switzerland (2022) 30

    Mordukhovich, B.S., Nam, N.M.: Convex Analysis and Beyond, Volume I: Basic Theory. Springer, Cham, Switzerland (2022) 30

    work page 2022

  31. [31]

    Mordukhovich, B.S., Nam, N.M.: An Easy Path to Convex Analysis and Applications, 2nd edition, Springer, Cham, Switzerland (2023)

    work page 2023

  32. [32]

    Kluwer Academic Publishers, Dordrecht, Netherland (1993)

    Nagurney, A.: Network Economics: A Variational Inequality Approach. Kluwer Academic Publishers, Dordrecht, Netherland (1993)

    work page 1993

  33. [33]

    Springer, New York (2006)

    Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edition. Springer, New York (2006)

    work page 2006

  34. [34]

    Kluwer Academic Publishers, Dordrecht, Netherland (1998)

    Outrata, J.V., Ko˘ cvara, M., Zowe, J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints. Kluwer Academic Publishers, Dordrecht, Netherland (1998)

    work page 1998

  35. [35]

    Mathematics of Operations Research 42, 95–118 (2017)

    Pang, J.S., Razaviyayn, M., Alvarado, A.: Computing B-stationary points of nonsmooth DC programs. Mathematics of Operations Research 42, 95–118 (2017)

    work page 2017

  36. [36]

    Springer, Berlin (1998)

    Rockafellar, R.T., Wets, R.J-B.: Variational Analysis. Springer, Berlin (1998)

    work page 1998

  37. [37]

    SIAM Journal on Optimization 35, 369–399 (2025)

    Samadi, S., Yousefian, F.: Improved guarantees for optimal Nash equilibrium seeking and bilevel variational inequalities. SIAM Journal on Optimization 35, 369–399 (2025)

    work page 2025

  38. [38]

    SIAM Journal on Optimization 11(4), 918–936 (2001)

    Scholtes, S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM Journal on Optimization 11(4), 918–936 (2001)

    work page 2001

  39. [39]

    SIAM Journal on Optimization 20, 2504–2539 (2010)

    Steffensen, S., Ulbrich, M.: A new relaxation scheme for mathematical programs with equilibrium constraints. SIAM Journal on Optimization 20, 2504–2539 (2010)

    work page 2010

  40. [40]

    Transportation Science 21, 254–263 (1987)

    Suwansirikul, C., Friesz, T.L., Tobin, R.L.: Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problem. Transportation Science 21, 254–263 (1987)

    work page 1987

  41. [41]

    Acta Mathematica Vietnamica 22, 289—355 (1997)

    Tao, P.D., An, L.T.H.: Convex analysis approach to DC programming: theory, algorithms, and applications. Acta Mathematica Vietnamica 22, 289—355 (1997)

    work page 1997

  42. [42]

    SIAM Journal on Optimization 10, 943–962 (2000)

    Ye, J.J.: Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints. SIAM Journal on Optimization 10, 943–962 (2000)

    work page 2000

  43. [43]

    Mathematical Programming 198, 1583–1616 (2023) 31

    Ye, J.J., Yuan, X., Zeng, S., Zhang, J.: Difference of convex algorithms for bilevel programs with applications in hyperparameter selection. Mathematical Programming 198, 1583–1616 (2023) 31

    work page 2023