Source-linked AI summary
Second-order subdifferential calculus with applications to tilt stability in optimization
B. S. Mordukhovich, R. T. Rockafellar
TL;DR
The paper tackles the limited development of second-order generalized differentiation needed for variational analysis and constrained optimization. It develops coderivative-based calculus for full and partial second-order subdifferentials, analyzes qualification conditions, and computes key cases. The resulting tools yield tilt-stability characterizations for nonlinear and extended nonlinear programs.
Problem
Second-order generalized differentiation still requires substantial development, although it is needed for optimization, sensitivity, and related variational problems.
Method
The paper develops chain rules and qualification conditions for coderivative-based full and partial second-order subdifferentials, computes major amenable cases, and applies them to constrained optimization.
Results
For a general class of nonlinear programs, strong second-order optimality is necessary and sufficient for tilt stability of local minimizers, equivalent there to Robinson’s strong regularity.
Takeaways & Limitations
The calculus supports complete tilt-stability characterizations for important constrained optimization problems, including nonlinear and extended nonlinear programs.
Takeaways & Limitations
The second-order chain-rule inclusion can be strict even for simple strongly amenable compositions without a full-rank condition.
Abstract
from arXiv · showhide
The paper concerns the second-order generalized differentiation theory of variational analysis and new applications of this theory to some problems of constrained optimization in finitedimensional spaces. The main attention is paid to the so-called (full and partial) second-order subdifferentials of extended-real-valued functions, which are dual-type constructions generated by coderivatives of frst-order subdifferential mappings. We develop an extended second-order subdifferential calculus and analyze the basic second-order qualification condition ensuring the fulfillment of the principal secondorder chain rule for strongly and fully amenable compositions. The calculus results obtained in this way and computing the second-order subdifferentials for piecewise linear-quadratic functions and their major specifications are applied then to the study of tilt stability of local minimizers for important classes of problems in constrained optimization that include, in particular, problems of nonlinear programming and certain classes of extended nonlinear programs described in composite terms.
1 Introduction
The paper addresses the continuing development needs of second-order generalized differentiation by building calculus for second-order subdifferentials and applying it to constrained optimization. Its main achievements concern chain rules, qualification conditions, computations for amenable functions, and tilt-stability characterizations.
- Motivation: Second-order generalized differentiation remains less developed than first-order theory despite applications to optimization, sensitivity, and related problems.The paper adopts the derivative-of-derivative approach, defining second-order constructions through coderivatives of first-order subdifferential mappings.
- Main contributions: The paper develops refined equality- and inclusion-type chain rules for full and partial second-order subdifferentials.The inclusion rules are obtained for broad classes of strongly amenable compositions through a quadratic penalty approach.
- Main contributions: It analyzes a second-order qualification condition required for chain rules of strongly amenable compositions.The condition is automatically satisfied under full-rank inner Jacobians and for C1,1 outer functions, but can be restrictive for extended-real-valued outer functions.
- Main contributions: The authors calculate second-order subdifferentials for major fully amenable function classes and apply the results to necessary optimality conditions.The applications include nonlinear programming and extended nonlinear programming represented through amenable compositions.
- Applications: For a general class of nonlinear programs, strong second-order optimality is necessary and sufficient for tilt stability of local minimizers.In these settings, tilt stability is equivalent to Robinson’s strong regularity of the associated variational inequalities.
2 Basic Definitions and Preliminaries
This section introduces the generalized differential constructions underlying the paper, including limiting subdifferentials, normal cones, coderivatives, and second-order subdifferentials. It emphasizes their nonconvex character and the resulting difficulty of extending first-order calculus to second order.
- First-order constructions: The basic limiting subdifferential is generally nonconvex but enjoys comprehensive calculus rules, unlike the regular subdifferential.The regular sum-rule inclusion can fail even for |x| and −|x| at zero, motivating the limiting construction.
- Normal cones and coderivatives: Normal cones and coderivatives are defined through limiting geometric constructions and may be nonconvex.Convexification can substantially enlarge basic normal cones and create difficulties for coderivative-based analysis.
- Second-order subdifferentials: The second-order subdifferential is generated by the coderivative of the first-order subdifferential mapping.For smooth functions it reduces to the Hessian applied to the chosen direction, while C1,1 functions admit a corresponding generalized representation.
- Partial constructions: Partial second-order constructions extend the framework to functions of multiple variable blocks and are useful in applications.They retain the coderivative-based scheme while using different first-order subdifferential choices.
- Second-order calculus: Second-order calculus is difficult because first-order subdifferential rules are generally inclusions, whereas coderivatives lack monotonicity.The paper therefore develops new chain rules, including a quadratic-penalty approach for strongly amenable compositions.
3 Second-Order Subdifferential Chain Rules
This section develops exact and inclusion-type second-order subdifferential chain rules for compositions, with full-rank conditions yielding equalities and qualification conditions supporting broader strongly amenable cases. It also shows that inclusion formulas can be strict without suitable rank or qualification assumptions.
- Full-rank chain rules: Theorem 3.1 gives exact partial second-order chain-rule formulas when the inner mapping’s partial Jacobian satisfies a full-rank condition.The result covers compositions with continuously differentiable inner mappings and provides formulas for the partial second-order subdifferentials.
- Proof strategy: The proof handles the square case through an inverse mapping and reduces the general m<n case to it by augmenting the inner mapping with a linear mapping to obtain full rank.The resulting normal-cone relation is transformed into the second-order chain rule by differentiating the associated representation.
- Qualification-based inclusions: Without the full-rank requirement, the paper derives inclusion-type chain rules for strongly amenable compositions under second-order qualification conditions.The qualification condition excludes the alternative in the normal-cone description that would invalidate the chain-rule inclusion.
- Qualification-based inclusions: The partial chain-rule equality combines the second-order curvature term of the scalarized inner mapping with the coderivative contribution from the outer function.The displayed formula has the form ∇^2_xx⟨v,h⟩(x̄,w̄)u + ∇_xh(x̄,w̄)^*∂^2θ(z̄,v)(∇_xh(x̄,w̄)u).
- Limits of inclusion formulas: Example 3.5 shows that the inclusion can be strict: its right-hand set may be nonempty even when the left-hand second-order subdifferential is empty.The example uses a linear inner mapping and a piecewise linear convex outer function, and its second-order qualification condition fails.
4 Analysis of the Basic Second-Order Qualification Condition and Calculating Second-Order Subdifferentials
The section analyzes the basic second-order qualification condition and develops exact chain rules and calculation formulas for major fully amenable compositions. These results cover piecewise linear and piecewise linear-quadratic outer functions and efficiently compute second-order subdifferentials.
- Qualification condition and local reduction: The analysis shows that the qualification condition can yield the full-rank setting needed for an exact second-order subdifferential chain rule.A local reduction identifies a suitable active subspace and reduces the composition to a full-rank representation.
- Qualification condition and local reduction: The local reduction lemma transforms the relevant subspace into active coordinates, where only the locally active components affect the implication.Inactive components can be omitted without loss in the reduced representation.
- Scope of the calculation: The paper notes that a finite union of subspaces is generally insufficient for applying the local reduction lemma, motivating a single common subspace for all relevant multipliers.This limitation is addressed for piecewise linear outer functions in fully amenable compositions.
- Piecewise linear outer functions: For convex piecewise linear outer functions, the qualification condition gives the exact second-order chain rule for fully amenable compositions.The result applies when the outer function is convex and piecewise linear.
- Piecewise linear-quadratic outer functions: For a major piecewise linear-quadratic subclass, the paper calculates the outer second-order subdifferential and establishes the exact chain rule.The formulas apply under the stated qualification condition and include piecewise linear functions when the quadratic term vanishes.
5 Applications to Tilt Stability in Nonlinear and Extended Nonlinear Programming
The section applies second-order subdifferential calculus to tilt stability in composite constrained optimization, including ENLP and NLP. Under qualification and regularity assumptions, positive-definiteness characterizes tilt-stable minimizers, while NLP specializes this to SSOC under LICQ.
- Extended nonlinear programming: For ENLP, the composite formulation represents constrained optimization through an outer extended-real-valued function and its feasible domain.The feasible set is the inverse image of the domain of the outer function, and the model includes ordinary nonlinear programming as a special case.
- General constrained problems: Under full rank, smoothness, prox-regularity, subdifferential continuity, and a unique multiplier, tilt stability is equivalent to positive-definiteness of the mapping T.The mapping combines the Hessian of the multiplier-weighted constraint mapping with the outer second-order subdifferential.
- Nonlinear programming: For nonlinear programming under LICQ, SSOC is necessary and sufficient for tilt stability of local minimizers.The result establishes both directions using the equivalence between the positive-definiteness condition and SSOC.
- Scope and regularity: For NLP, LICQ is essential to the stated SSOC characterization, and even the relevant second-order qualification condition leads to LICQ in this representation.The paper also relates tilt stability under these assumptions to strong regularity of the KKT variational inequality.
- Fully amenable compositions: For fully amenable composite problems satisfying the second-order qualification condition, the same positive-definiteness criterion characterizes tilt stability using calculated outer second-order subdifferentials.The formulas come from the piecewise linear and piecewise linear-quadratic cases developed earlier.
- Sufficient conditions: The inclusion-type chain rule provides a sufficient condition for tilt stability when positive-definiteness transfers from T to the full second-order subdifferential.This gives a sufficient, rather than necessarily equivalent, criterion in the stated setting.