Characterizations of Strong Variational Sufficiency in General Models of Composite Optimization
Boris S. Mordukhovich, Peipei Tang, Chengjing Wang · 2025
Read Characterizations of Strong Variational Sufficiency in General Models of Composite Optimization by Boris S. Mordukhovich, Peipei Tang, Chengjing Wang (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-2507-09522.txt.
Introduction
Boris Mordukhovich, Peipei Tang, and Chengjing Wang pin down a strength trait in twenty twenty-five. Strong variational sufficiency is a trait of opt tasks of late. It counts for the math of such tasks, for solve tools, and for real use. The team takes on composite opt tasks, a broad class with a layered build.
They give full marks for strong low points. One path uses a broad form of the strong second order test. The next path uses a sign test on a broad Hessian of the augmented Lagrangian at that point. A new second order form states the test for cases that are not convex and have layers, and the marks cover a wide range of tasks. They can be put to work for cases that are not polyhedral. The tests tell you when a claimed low point is a strong one.
Catalog record
| CREATOR | Boris S. Mordukhovich, Peipei Tang, Chengjing Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-09522
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Characterizations of Strong Variational Sufficiency in General Models of Composite Optimization Boris S. Mordukhovich, Peipei Tang, Chengjing Wang Abstract This paper investigates a recently introduced notion of strong variational sufficiency in optimization problems whose importance has been highly recognized in optimization theory, numerical methods, and applications. We address a general class of composite optimization problems and establish complete characterizations of strong variational sufficiency for their local minimizers in terms of a generalized version of the strong second-order sufficient condition (SSOSC) and the positive-definiteness of an appropriate generalized Hessian of the augmented Lagrangian calculated at the point in question. The generalized SSOSC is expressed via a novel second-order variational function, which reflects specific features of nonconvex composite models. The imposed assumptions describe the spectrum of composite optimization problems covered by our approach while being constructively implemented for nonpolyhedral problems that involve the nuclear norm function and the indicator function of the positive-semidefinite cone without any constraint qualifications. Keywords: variational analysis, composite optimization, strong variational sufficiency, generalized differentiation, second-order characterizations, parabolic regularity Mathematics Subject Classification (2020) 49J52, 49J53, 90C31 1 Introduction The notion of variational and strong variational sufficiency for local minimizers of general optimization problems written in the unconstrained extended-real-valued format was introduced by Rockafellar [ 19 ] . It is closely related to Rockafellar’s notion of (strong) variational convexity of lower semicontinuous (l.s.c.) functions [ 20 ] meaning that the subdifferential graph of the function in question locally behaves as the subgradient mapping associated with some (strongly) convex l.s.c. function. Both notions of variational sufficiency and variational convexity, as well as their strong counterparts, reflect “primal-dual” perspectives of local optimality. These properties enhance our understanding of optimization models by demonstrating how their objective functions can exhibit convex-type features even in more complex settings. Moreover, they provide a robust theoretical foundation for the development of numerical algorithms to efficiently solve nonsmooth and nonconvex optimization problems. In this paper, we mainly concentrate on the study of strong variational sufficiency for local minimizers of the following problem of (constrained) composite optimization \displaystyle(COP)\qquad\min_{x\in\mathcal{R}^{n}}f_{0}(x)+g(F(x)) under the standing assumptions : f_{0}:\mathcal{R}^{n}\rightarrow\mathcal{R} and F:\mathcal{R}^{n}\rightarrow\mathcal{R}^{m} are {\cal C}^{2} -smooth mappings, and g:\mathcal{R}^{m}\rightarrow\overline{\mathcal{R}}:=\mathcal{R}\cup\{\infty\} is an l.s.c. convex function. The class of optimization problems in form (COP) is very broad including linear and nonlinear programs, second-order cone and positive-semidefinite programs, etc. In the nondegenerate case where the Jacobian matrix of F is of full rank at the reference point, the second-order characterization of strong variational sufficiency for local optimality in COPs is obtained in [ 6 ] . In the (polyhedral) case of nonlinear programs (NLPs), the aforementioned nondegeneracy condition reduces to the classical linear independence constraint qualification (LICQ), and the characterization of [ 6 ] is explicitly formulated via the classical strong second-order sufficient condition (SSOSC). We also mention the abstract quadratic bundle characterizations in [ 22 ] formulated in the SSOSC form as well in the case of NLPs. For the class of (nonpolyhedral) nonlinear semidefinite programs (SDPs), characterizations of strong variational sufficiency were developed in [ 26 ] via the corresponding version of SSOSC. Moreover, the obtained results for strong variational sufficiency were used for establishing local convergence rates for numerical algorithms of the proximal, augmented Lagrangian, and Newtonian types; see [ 7 , 19 , 21 , 26 ] . Major open questions remain about explicit characterizations of strong variational sufficiency for general nonpolyhedral composite optimization problems in terms of their given data, and particularly about the equivalence between strong variational sufficiency for local optimality in (COP) and appropriate versions of SSOSC. This paper develops an efficient approach to resolve such issues based on advanced machinery of variational analysis and second-order generalized differentiation. Our main goal is to reveal general assumptions on the initial data of (COP) that ensure the desired equivalence of strong variational sufficiency for local optimality to the newly formulated SSOSC and the related positive-definiteness of a certain generalized Hessian of the augmented Lagrangian function associated with (COP) without any constraint qualification. Furthermore, we specifically illustrate the fulfillment of the most involved assumption in our analysis with constructive calculations in the two major nonpolyhedral cases: when g is either the indicator function of the positive-semidefinite cone, or the nuclear norm function. The obtained calculations lead us to explicit characterizations of strong variational sufficiency in the corresponding COPs, where the crucial case of nuclear norm-based problems has never been considered in the literature. The rest of the paper is organized as follows. Section 2 presents the needed preliminaries from variational analysis and generalized differentiation together with the formulation and discussion of the major assumptions on the data of (COP) to provide desired characterizations. In Section 3 , we evaluate the limiting coderivative of the proximal mapping that is broadly used in what follows. Section 4 introduces a novel second-order variational function, which is used in the formulation and investigation of the generalized SSOSC for the composite problem (COP). Section 5 contains the main results on characterizing strong variational sufficiency for (COP). The concluding remarks and some topics of the future research are discussed in Section 6 . Finally, Appendix A presents explicit calculations of all the ingredients involving into the major assumptions and characterizations for the SDP cone and nuclear norm functions in (COP). Throughout the paper, we use the standard notation of finite-dimensional variational analysis and generalized differentiation; see, e.g., [ 15 , 23 ] . Recall that the closed unit ball in \mathcal{R}^{m} is denoted by \mathbb{B}_{\mathcal{R}^{m}} , while \mathbb{B}(x,\varepsilon):=\{u\in\mathcal{R}^{m}\,|\,\|u-x\|\leq\varepsilon\} for some x\in\mathcal{R}^{m} and \varepsilon>0 . For a set C\subset\mathcal{R}^{m} , the indicator function \delta_{C} of C is defined by \delta_{C}(x):=0 if x\in C and \delta_{C}(x):=\infty . Given a point x\in\mathcal{R}^{m} , we use \operatorname{\Pi}_{C}(x) to denote the projection of x onto C . For a sequence \{x^{k}\} , the notation x^{k}{\stackrel{{\scriptstyle C}}{{\rightarrow}}}x means that x^{k}\rightarrow x with x^{k}\in C , while x^{k}{\stackrel{{\scriptstyle N}}{{\rightarrow}}}x indicates that x^{k}\rightarrow x with k\in N\subset\mathbb{N}:=\{1,2,\ldots\} . The smallest cone containing C is \operatorname{pos}C=\{0\}\cup\{\lambda x\,|\,x\in C,\,\lambda>0\} with \operatorname{pos}C:=\{0\} if C=\emptyset . The intersection of all the convex sets containing C is called the convex hull of C and is denoted by \operatorname{conv}C . For a nonempty closed convex cone C , the polar cone of C is C^{\circ}:=\{y\,|\,\langle x,y\rangle\leq 0\;\mbox{ for all }\;x\in C\} , and the gauge of C is \gamma_{C}(x):=\inf\{\lambda\geq 0\,|\,x\in\lambda C\} provided that 0\in C . The notation \operatorname{Diag}(x) signifies the diagonal matrix with vector x on the diagonal. Denote the n\times n identity matrix as I_{n} , where the subscript is omitted if the dimension is evident from the context. For a given matrix A\in\mathcal{R}^{m\times n} , let \operatorname{ker}(A):=\{x\in\mathcal{R}^{n}\,|\,Ax=0\} , and let A^{\dagger} stand for the Moore-Penrose inverse of A . Given index sets \alpha\subset\{1,\ldots,m\} and \beta\subset\{1,\ldots,n\} , denote by A_{\alpha\beta} the |\alpha|\times|\beta| submatrix of A obtained by removing all the rows of A not in \alpha and all the columns of A not in \beta . For a set-valued mapping/multifunction S\colon\mathcal{R}^{n}\rightrightarrows\mathcal{R}^{m} , the (Painlevé-Kuratowski) outer limit of S at \bar{x} is \mathop{{\rm Lim}\,{\rm sup}}_{x\to\bar{x}}S(x):=\big\{y\in\mathcal{R}^{m}\;\big|\;\exists\,x_{k}\to\bar{x},\;\exists\,y_{k}\to y\;\mbox{ with }\;y_{k}\in S(x_{k})\big\}, (1) while the standard upper limit of scalars are denoted by ‘ \limsup ’. Finally, we use ‘ \subset ’ to indicate that the set on the left-hand side is smaller than or equal