First- and second-order epi-differentiability in nonlinear programming

Abstract

Problems are considered in which an objective function expressible as a max of finitely many <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C squared"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>C</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{C^2}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> functions, or more generally as the composition of a piecewise linear-quadratic function with a <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C squared"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>C</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{C^2}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> mapping, is minimized subject to finitely many <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C squared"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>C</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{C^2}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> constraints. The essential objective function in such a problem, which is the sum of the given objective and the indicator of the constraints, is shown to be twice epi-differentiable at any point where the active constraints (if any) satisfy the Mangasarian-Fromovitz qualification. The epi-derivatives are defined by taking epigraphical limits of classical first-and second-order difference quotients instead of pointwise limits, and they reveal properties of local geometric approximation that have not previously been observed.