Parabolic second-order tangent sets of semialgebraic sets and applications to polynomial optimization

Technical Summary: Parabolic Second-Order Tangent Sets of Semialgebraic Sets and Applications to Polynomial Optimization

Problem Statement
First-order tangent cones, while fundamental in variational analysis and constrained optimization, fail to capture curvature, second-order activation of constraints, or branchwise feasible behaviors. These features are critical in degenerate polynomial optimization problems where standard first-order models are insufficient. The paper addresses the need for a rigorous, algebraically checkable framework for second-order local analysis of semialgebraic sets. Specifically, it investigates the parabolic second-order tangent set, which characterizes the second-order corrections $w$ in feasible expansions of the form $x(t) = \bar{x} + tu + \frac{1}{2}t^2w + o(t^2)$, and seeks to determine when this geometric object coincides with an algebraic model derived from the gradients and Hessians of the defining constraints.

Methodology
The paper operates within the category of basic closed semialgebraic sets $S = \{x \in \mathbb{R}^n : g_i(x) = 0, h_j(x) \leq 0\}$. The methodology proceeds through the following steps:

1. Definitions: The authors define three variants of the second-order tangent set at a point $\bar{x}$ in direction $u$:

   • The outer parabolic tangent set ($T^{2,out}_S$), defined via sequential limits.
   • The inner parabolic tangent set ($T^{2,in}_S$), defined via universal quantification over sequences.
   • The arc-generated tangent set ($T^{2,arc}_S$), defined via the existence of semialgebraic arcs.
   • The algebraic second-order linearized set ($L^2_S$), defined by the equality and inequality constraints on $w$ derived from Taylor expansions of the active constraints.

2. Regularity Conditions: The core of the methodology introduces algebraic parabolic regularity. This condition requires two properties at $(\bar{x}, u)$:

   • Directional Rank Stability: The rank of the gradient matrix of the second-order active family remains constant along feasible arcs approaching $\bar{x}$ in direction $u$.
   • Parabolic Arc-Realizability: Every formally admissible second-order correction $w \in L^2_S(\bar{x}; u)$ is realized by an actual semialgebraic arc.

3. Stratification: For singular sets, the paper utilizes finite $C^2$ semialgebraic stratifications. It decomposes the tangent set of a singular set into the union of tangent sets of the closures of the selected strata (branches) that approach the point with the given direction.

Key Contributions and Results

• Algebraic Characterization: The paper establishes that under the condition of algebraic parabolic regularity, the outer, inner, and arc-generated parabolic tangent sets coincide with the algebraic second-order linearized set:
  $$T^{2,out}_S(\bar{x}; u) = T^{2,in}_S(\bar{x}; u) = T^{2,arc}_S(\bar{x}; u) = L^2_S(\bar{x}; u).$$
  This result transforms an abstract geometric object into a finite system of linear and quadratic equations/inequalities involving gradients and Hessians.

• Explicit Formulas: The authors derive exact formulas for specific classes of sets:

  • Smooth Hypersurfaces: The tangent set is defined by a single linear equation involving the Hessian of the defining polynomial.
  • Regular Complete Intersections: The tangent set is the kernel of a linear map involving the Jacobian and the second derivative of the mapping.
  • Smooth Inequality Systems: Under linear independence of gradients, the tangent set is the polyhedral set defined by the active constraints.
  • Stratified Sets: A formula is provided where the tangent set of a singular set is the union of the tangent sets of the relevant strata closures.

• Optimization Applications:

  • Second-Order Necessary Conditions: If $\bar{x}$ is a local minimizer, then for every critical direction $u$ and every $w \in T^2_S(\bar{x}; u)$, the quadratic form $Q_f(\bar{x}; u, w) = \nabla f(\bar{x})w + u^T \nabla^2 f(\bar{x})u$ must be non-negative. Under algebraic parabolic regularity, this test reduces to checking $w \in L^2_S(\bar{x}; u)$.
  • Quadratic Growth: The paper provides sufficient conditions for quadratic growth (i.e., $f(x) \geq f(\bar{x}) + c\|x-\bar{x}\|^2$). If $Q_f$ is strictly positive on the algebraic linearized set for all unit critical directions, quadratic growth holds.
  • Lagrangian Multipliers: The results yield criteria involving Lagrange multipliers where the second-order term of the objective function is compared against the Hessian of the Lagrangian, adjusted for the curvature of active inequality constraints.

Significance and Claims
The paper claims to make second-order constructions algebraically checkable for semialgebraic feasible sets. Its significance lies in bridging the gap between variational analysis (which often deals with limiting objects) and real algebraic geometry (which offers finite, computable structures).

The authors emphasize that their approach detects features that first-order tangent cones miss:

• Curvature: Distinguishing between flat and curved feasible branches.
• Flatness: Identifying cases where constraints are "flat" (e.g., $y \geq x^4$) such that second-order conditions are necessary for local minimality but insufficient for quadratic growth.
• Branch Dependence: Handling singular sets (like cusps or tacnodes) where different branches may have different second-order behaviors, requiring branchwise analysis rather than a single linearized equation.
• Failure of Quadratic Scaling: Highlighting cases (like cusps $y^2 = x^3$) where the standard parabolic scaling $t^2$ is insufficient to capture the first nontrivial correction, necessitating higher-order or fractional-order analysis.

The work is presented as a local complement to global algebraic methods (such as Lasserre's moment-SOS hierarchy or gradient-ideal approaches), providing precise local optimality tests that are computable via polynomial algebra. The paper concludes modestly, noting that while it resolves the second-order case under regularity, questions regarding higher-order or fractional-order analogues for singular branches (e.g., Puiseux exponents) and the connection to global certificates remain open.