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

Boris S. Mordukhovich, Yixia Song, Shangzhi Zeng, Jin Zhang · 2025

Read Extended SQP Methods in Nonsmooth Difference Programming Applied to Problems with Variational Inequality Constraints by Boris S. Mordukhovich, Yixia Song, Shangzhi Zeng, Jin Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-05609.txt.

Introduction

Boris Mordukhovich, Yixia Song, Shangzhi Zeng, and Jin Zhang developed new solution methods in twenty twenty-five for a hard class of optimization problems. In these problems, the goal and the limits are written as differences of two functions, with no promise that either part is convex. Such forms show up in design and economics but resist standard solvers.

Their methods extend the sequential quadratic approach, solving a chain of simpler convex problems built from slopes and sub-slopes of the true functions. They prove the methods converge for wide families of functions, using a known curve condition. The framework also covers problems with variational inequality limits, recast through gap functions. Tests on network design problems showed the methods work well in practice.

Catalog record

CREATORBoris S. Mordukhovich, Yixia Song, Shangzhi Zeng, Jin Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-05609

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Extended SQP Methods in Nonsmooth Difference Programming Applied to Problems with Variational Inequality Constraints Boris S. Mordukhovich, Yixia Song, Shangzhi Zeng, Jin Zhang 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-Ł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. Keywords Difference programming, Variational inequalities, Extended sequential quadratic methods, Polyak-Łojasiewicz-Kurdyka conditions, Regularized gap functions, Continuous network design problems 1 Introduction Difference-of-convex (DC) programming has emerged as a powerful framework for nonconvex and nonsmooth optimization owing to its ability of modeling complex structures while maintaining computational tractability; see, e.g., [ 3 , 43 ] and the references therein. In this work, we extend this paradigm by investigating a class of constrained difference programming problems formulated as follows: \displaystyle\min_{x\in X}\quad\varphi_{0}(x):=g_{0}(x)-h_{0}(x) (1.1) \displaystyle\text{subject to}\quad{\varphi_{i}(x):=g_{i}(x)-h_{i}(x)\leq 0,\quad i\in\mathcal{I},} where \mathcal{I} is a finite set of indices, X is a nonempty, closed, and convex subset of \mathbb{R}^{n} . The functions g_{i}:\mathbb{R}^{n}\to\mathbb{R} for i\in\{0\}\cup\mathcal{I} are assumed to be continuously differentiable with locally Lipschitzian gradients (i.e., of class {\cal C}^{1,1} ) on X , while the functions h_{i}:\mathbb{R}^{n}\to\overline{\mathbb{R}}:=\left(-\infty,\infty\right] for i\in\{0\}\cup\mathcal{I} are locally Lipschitz continuous and prox-regular over X ; see Section 2 . Additionally, we assume that the objective function \varphi_{0} is bounded from below by a constant m_{\varphi_{0}} over X . The primary objective of this study is to develop efficient numerical methods for solving ( 1.1 ), establish a rigorous convergence analysis for the proposed algorithms, and provide valuable applications. Recall that several classical algorithms exist to solve general constrained nonlinear programming (NLP). Among them, we mention sequential quadratic programming (SQP) methods, interior point methods, and augmented Lagrangian methods; see, e.g., [ 10 , 35 ] for more details. The difference programming model ( 1.1 ) can be viewed as a generalization of DC programming, which has been a well-established topic in optimization with a variety of practical applications; see, in particular, [ 2 , 5 , 16 , 37 , 46 ] and the references therein among various developments on DC-type algorithms. The unconstrained case of ( 1.1 ), where \varphi_{i}(x) for i\in\mathcal{I} are absent, has been extensively investigated in [ 4 ] , where the term “difference programming” has been coined. In that work, the authors propose a novel Newton-type algorithm, RCSN, which effectively exploits second-order information via generalized differentiation techniques to solve such problems. In our work, we address the general setting of ( 1.1 ), where the constraint functions \varphi_{i} for i\in\mathcal{I} are also expressed as differences of functions. The presence of such a structure in both objective and the constraint functions constitute additional analytical and computational challenges, which require the rigorous treatment of feasibility and stationarity conditions. To develop an efficient numerical approach for solving ( 1.1 ), we begin with considering SQP-type algorithms in the setting of smooth NLP problems. Methods of this type include solving a sequence of strongly convex quadratic subproblems to approximate the original one [ 11 , 24 ] . In particular, the extended sequential quadratic method (ESQM), introduced in [ 7 ] for NLPs, serves as an inspiration for one of our algorithmic designs, called CDP-ESQM, to solve ( 1.1 ). Here we do not directly apply ESQM, but rather incorporate certain key ideas from it to develop an iterative framework tailored for constrained difference programming ( 1.1 ). Specifically, at each iteration we construct a strongly convex quadratic programming subproblem, where the problem’s structural properties are incorporated through linear approximations derived from the gradients of g_{i} and limiting/Mordukhovich subgradients of h_{i} for i\in\{0\}\cup\mathcal{I} . Under rather mild assumptions, we establish convergence properties of the proposed CDP-ESQM. Moreover, under the assumption that a limiting subdifferential version of the Polyak-Łojasiewicz-Kurdyka property holds for a suitably designed merit function, we establish global convergence results for CDP-ESQM. Notably, while CDP-ESQM utilizes a backtracking line search, our global convergence results do not rely on the assumption of a unit step size. Subsequently, we consider a class of difference programs with variational inequality (VI) constraints . A variational inequality problem seeks a vector x^{*} such that a given mapping F(x) satisfies \langle F(x^{*}),x-x^{*}\rangle\geq 0\;\mbox{ for all }\;x\in\Omega, (1.2) where \Omega is a feasible set, which often models equilibrium problems in diverse fields of science and technology including machine learning, operations research, economics, optimization, etc.; see [ 15 , 18 , 21 , 34 ] . VIs serve as a unifying tool to describe equilibrium conditions in applications to noncooperative games, market equilibrium models, contact mechanics, and generative adversarial networks. In various real-world models, decision making involves not only satisfying a VI constraint but also optimizing an objective function that leads us to problems of VI-constrained programming. Theoretical research on VI-constrained programming mostly focuses on the development of constraint qualifications and necessary optimality conditions as in [ 45 ] and on the analysis of value function stability in parametric settings; see, e.g., [ 14 , 26 ] . These studies, along with other early contributions, provide fundamental insights into the theoretical properties of VI-constrained programming. In real-world applications, VI-constrained programming has been widely employed in various fields such as optimal shape design, Stackelberg-Cournot-Nash equilibria traffic equilibrium, etc.; see [ 23 , 39 ] . Despite the goal of solving VI-constrained programming problems, the existing research has predominantly focused on a special case where the feasible set \Omega in VI ( 1.2 ) is a cone. Under this condition, problems of VI-constrained programming reduce to mathematical programs with complementarity constraints (MPCCs); see, e.g., [ 15 , Proposition 1.1.3] . The reader may consult with [ 19 , 36 , 40 , 41 ] for various numerical algorithms developed to solve MPCCs. Our aim in this part of the research is developing efficient algorithms to solve problems of difference programming with variational inequality constraints of type ( 1.2 ). To accomplish the goal, we build upon the single-level reformulation approach introduced in [ 28 ] and employ employ the regularized gap function for VI proposed in [ 17 ] . This allows us to reformulate the VI constraint as an inequality constraint given by the difference of two (nonconvex) functions with reducing therefore the VI-constrained problem to the difference programming form ( 1.1 ). Thus the proposed ESQM methods are directly applicable to the VI-constrained difference programming problems under consideration. The results established for such problems by using CDP-ESQM are applied to continuous network design problems . For this class of practical models, we conduct

Read the complete text