Stratification for Nonlinear Semidefinite Programming

This paper introduces a stratification framework for nonlinear semidefinite programming that leverages the geometry of nonsmooth KKT systems to establish new regularity conditions and develop a globally convergent Gauss–Newton algorithm with local quadratic convergence.

The Gist

Here is an explanation of the paper "Stratification for Nonlinear Semidefinite Programming," translated into everyday language using analogies.

The Big Picture: Navigating a Bumpy Mountain

Imagine you are trying to find the lowest point in a vast, complex landscape (a mountain range). In math, this is called optimization. You want to find the "valley" where your cost is lowest.

Usually, these landscapes are smooth hills. If you are on a smooth hill, you can easily roll a ball down to the bottom using standard tools (like Newton's method).

However, Nonlinear Semidefinite Programming (NLSDP) is different. The landscape here is full of sharp edges, cracks, and jagged rocks. It's not a smooth hill; it's a craggy, broken terrain. Because of these jagged edges, the standard tools break. If you try to roll a ball down a crack, it gets stuck or bounces unpredictably.

This paper introduces a new way to navigate this broken terrain. Instead of trying to smooth out the whole mountain, the authors say: "Let's break the mountain into smooth layers."

The Core Idea: The "Stratification" Map

The authors use a technique called Stratification. Think of the jagged mountain not as one chaotic mess, but as a stack of different "floors" or strata.

• The Floors (Strata): Imagine the mountain is made of layers of glass. Each layer is perfectly smooth, but the layers sit on top of each other at different heights.
  • Floor 1: The very top, where the glass is thick and solid.
  • Floor 2: A slightly lower layer where the glass has a few cracks.
  • Floor 3: The bottom layer where the glass is very thin.
• The Magic: On any single floor, the ground is perfectly smooth. You can walk easily. The problem is only that you might need to jump between floors to get to the very bottom.

In math terms, the "jaggedness" comes from the fact that the numbers (eigenvalues) in the problem can be positive, negative, or exactly zero. The authors group all the points where the numbers have the same "pattern" (e.g., 3 positive, 2 negative, 1 zero) into a single smooth floor.

The Problem with Old Methods

Before this paper, mathematicians tried to solve these problems using "Strong" rules. They assumed the mountain was perfectly smooth everywhere or that the cracks were very specific and rare.

• The Issue: In real life, the cracks are everywhere. The "Strong" rules often fail because the mountain is too broken. It's like trying to use a ruler to measure a crumpled piece of paper; the ruler doesn't fit.

The New Solution: The Stratified Gauss-Newton Method

The authors built a new robot (an algorithm) called the Stratified Gauss-Newton (SGN) method. Here is how it works, step-by-step:

1. Walk on the Current Floor: The robot looks at where it is standing. It figures out which "smooth floor" (stratum) it is on. It then takes a smart step down that specific floor, just like a hiker walking down a smooth slope.
2. The "Normal" Jump: Sometimes, the robot realizes it's stuck on a floor that doesn't lead to the bottom. It needs to jump to a different floor. The robot has special "jumping boots" (normal directions) that allow it to leap to an adjacent floor without getting stuck in the cracks.
3. The "Eigenvalue" Correction: This is the robot's superpower. As it walks, it constantly checks the "vibration" of the ground (the eigenvalues). If it detects a number getting dangerously close to zero (a sign it's about to hit a crack or change floors), it automatically adjusts its position to land perfectly on the new, correct floor. It's like a self-correcting GPS that knows exactly which layer of the mountain you are on.

Why This is a Big Deal

1. It works where others fail:
Old methods required the mountain to be "non-degenerate" (perfectly smooth and well-behaved). This new method works even when the mountain is messy and degenerate. It's like having a hiking guide that can navigate a landslide, whereas old guides would just say, "You can't go here."

2. It's fast:
Once the robot figures out which floor the solution is on, it zooms to the bottom incredibly fast (quadratic convergence). It doesn't just crawl; it sprints once it finds the right path.

3. It's robust:
The paper proves that even if you start far away from the solution, this robot will eventually find the right floor and get to the bottom. It won't get lost in the cracks.

A Simple Analogy: The Puzzle Box

Imagine a puzzle box with many layers.

• Old Method: Tries to force the box open by shaking it hard. If the box is jammed (degenerate), it breaks.
• This Paper's Method: Realizes the box is made of sliding trays. It gently slides the trays (strata) to find the right alignment. Once the trays are aligned (identifying the active stratum), the box pops open instantly.

Summary

This paper takes a very difficult, jagged mathematical problem and says, "Don't fight the jaggedness. Instead, organize the jaggedness into smooth layers." By doing this, they created a new algorithm that is:

• Smarter: It knows how to jump between layers.
• Faster: It zooms to the solution once it finds the right layer.
• Stronger: It works on problems that were previously considered too broken to solve efficiently.

It's a new map for a broken world, turning a chaotic mess into a series of manageable, smooth steps.

Technical Summary

Here is a detailed technical summary of the paper "Stratification for Nonlinear Semidefinite Programming" by Bao, Ding, Feng, and Li.

1. Problem Statement

The paper addresses Nonlinear Semidefinite Programming (NLSDP) problems of the form:
$$\min_{x \in X} f(x) \quad \text{s.t.} \quad g(x) \in S^n_+$$
where $X$ is a Euclidean space, $f$ and $g$ are twice continuously differentiable, and $S^n_+$ is the cone of symmetric positive semidefinite matrices.

Core Challenge:
The Karush–Kuhn–Tucker (KKT) system for NLSDP is inherently nonsmooth due to the metric projection operator $\Pi_{S^n_+}$ onto the semidefinite cone. This operator is not Fréchet differentiable at matrices with zero eigenvalues. Consequently:

• Classical smooth Newton methods cannot be directly applied.
• Standard semismooth Newton methods rely on strong regularity assumptions (e.g., Constraint Nondegeneracy and Strong Second-Order Sufficient Conditions) that often fail in degenerate regimes (e.g., when solutions are not isolated or multipliers are not unique).
• Existing "weak" regularity conditions (introduced by Feng et al.) lacked a unified geometric interpretation and a complete global convergence theory.

2. Methodology: Inertia Stratification

The authors propose a stratification framework to decompose the nonsmooth problem into a union of smooth manifolds.

A. Inertia Stratification of $S^n$

The space of symmetric matrices $S^n$ is decomposed into disjoint smooth manifolds (strata) based on the inertia (the number of positive, zero, and negative eigenvalues) of a matrix.

• A stratum $M_{p,q}$ consists of matrices with exactly $p$ positive and $q$ negative eigenvalues.
• Key Insight: The metric projection $\Pi_{S^n_+}$ is $C^\infty$-smooth when restricted to any fixed stratum $M_{p,q}$. This allows the nonsmooth KKT mapping to be treated as a smooth mapping on a manifold.

B. Lifting to Primal-Dual Space

The stratification is lifted to the primal-dual space $X \times S^n$ via the mapping $G(z) = g(x) + y$. This induces a stratification of the solution space where the KKT mapping $F(z)$ becomes smooth on each stratum $\tilde{M}_{p,q}$.

C. Variational Analysis

The authors develop a stratum-wise variational analysis:

1. Stratum-Restricted Strong Metric Regularity: They define a localized version of strong metric regularity restricted to a specific stratum.
2. Equivalence to Weak Conditions: They prove that on a fixed stratum, this restricted regularity is equivalent to two verifiable "weak" conditions:
   • Weak Strict Robinson Constraint Qualification (W-SRCQ): A relaxed version of the classical SRCQ.
   • Weak Second-Order Condition (W-SOC): A relaxed version of the classical S-SOSC.
3. Geometric Interpretation: The W-SRCQ is interpreted geometrically via transversality. This interpretation proves that W-SRCQ is stable along a stratum and generic in the ambient space.
4. Across-Strata Propagation: They analyze how these properties propagate across adjacent strata. They show that classical strong-form conditions (like Constraint Nondegeneracy) are equivalent to the local uniform validity of the weak conditions across a neighborhood.

3. Algorithm: Stratified Gauss–Newton (SGN)

Based on this theory, the authors propose a Stratified Gauss–Newton (SGN) method to minimize the nonsmooth least-squares merit function $\phi(z) = \frac{1}{2}\|F(z)\|^2$.

The algorithm integrates three mechanisms to handle the nonsmoothness and stratum transitions:

1. Tangential Steps (Stratum LM): Computes a Levenberg–Marquardt step tangent to the current stratum $\tilde{M}_{p,q}$ using the explicit manifold differential. This ensures descent while staying on the current smooth manifold.
2. Normal Steps (Escape): Uses explicitly constructed normal directions (derived from the gradient of the merit function projected onto the normal bundle of the stratum) to escape "bad" strata where the solution does not lie. These steps are accepted without line search if they reduce the merit function.
3. Eigenvalue-Triggered Correction: When eigenvalues of $G(z)$ become small (near zero), a correction mechanism projects the iterate onto a lower-dimensional stratum to align with the active inertia. This ensures the algorithm identifies the correct active manifold.

4. Key Results and Theoretical Guarantees

A. Regularity and Convergence

• Global Convergence: The SGN method is proven to converge globally to a Directionally Stationary (D-stationary) point of the merit function.
• Local Quadratic Convergence: If the limit point is a KKT pair satisfying the W-SOC and the Strict Robinson Constraint Qualification (SRCQ) (a stronger condition than W-SRCQ but weaker than classical nondegeneracy), the method:
  1. Identifies the active stratum in finite steps.
  2. Achieves local quadratic convergence.
• Necessity of Conditions: The paper proves that if the W-SOC and W-SRCQ fail, every element of the Clarke generalized Jacobian is singular, making superlinear convergence impossible for standard semismooth Newton methods.

B. Comparison with Classical Theory

• Weaker Assumptions: The required conditions (W-SOC + SRCQ) are strictly weaker than the classical Constraint Nondegeneracy + S-SOSC. This allows the method to solve degenerate problems where classical Newton methods fail or stall.
• Geometric Insight: The paper establishes that classical strong regularity is equivalent to the uniform validity of weak conditions over a neighborhood, providing a deeper understanding of why degeneracy breaks standard convergence.

5. Numerical Experiments

The authors tested the SGN method on several instances:

• Degenerate Cases: Problems where classical SOSC fails (non-isolated solutions) but W-SOC holds. The algorithm successfully identified the active stratum and achieved quadratic convergence.
• Violation Cases: A case where W-SOC holds but SRCQ fails. The algorithm converged globally but only linearly, confirming the theoretical necessity of the stronger condition for quadratic rates.
• Comparison: The method outperformed standard semismooth Newton approaches in degenerate regimes where the latter failed to execute or converged slowly due to singular generalized Jacobians.

6. Significance and Contributions

1. Theoretical Framework: Introduces a rigorous stratification framework for NLSDP, bridging the gap between nonsmooth analysis and smooth manifold optimization.
2. New Regularity Conditions: Provides exact characterizations of regularity in terms of W-SOC and W-SRCQ, offering a geometric interpretation via transversality.
3. Algorithmic Innovation: Develops the first globally convergent Newton-type method for NLSDP that explicitly handles stratum transitions and achieves quadratic convergence under significantly weaker assumptions than the literature.
4. Practical Impact: Offers a viable solution strategy for degenerate SDP problems arising in robotics, control, and structural optimization, where standard nondegeneracy assumptions are frequently violated.

In summary, this work transforms the approach to NLSDP by viewing the nonsmooth KKT system through the lens of stratified geometry, enabling robust algorithms that function effectively even in highly degenerate regimes.