On the role of semismoothness in nonsmooth numerical analysis: Theory

This paper investigates the role of semismooth derivatives in nonsmooth numerical analysis by exploring their interplay with semismoothness* properties for multifunctions, particularly in the context of solution maps to parametric inclusions, and establishes their coincidence with generalized Jacobians almost everywhere along with consequences for strict proto-differentiability.

The Gist

Imagine you are trying to navigate a rugged, foggy mountain to find the lowest valley (the optimal solution). In the smooth world of calculus, the mountain has gentle slopes, and you can easily calculate the direction to go down using a map (a derivative). But in the real world of "nonsmooth" problems, the mountain is jagged, full of cliffs, boulders, and sharp edges. You can't draw a single smooth line for the slope; it's broken.

This paper is about a new, smarter way to navigate these jagged mountains without needing a perfect map of every single rock.

The Problem: The "Oracle" is Broken

In traditional math, to solve these problems, you need an "Oracle" (a magical helper) that tells you two things at any point:

1. How high you are (the value).
2. The exact slope (the gradient/subgradient).

But often, calculating the exact slope is impossible or too hard because the terrain is too jagged. The authors ask: Do we really need the exact slope? Or can we get away with a "good enough" approximation that still guides us down?

The Solution: The "Semismooth" Compass

The paper introduces a concept called Semismoothness. Think of this not as a perfect map, but as a compass that points generally downhill.

• The Old Way: You need a perfect, smooth road to drive a car. If there's a pothole, you're stuck.
• The New Way (Semismooth): You have an off-road vehicle. The terrain is bumpy, but as long as your suspension (the math) can handle the bumps and the compass (the semismooth derivative) points roughly in the right direction, you can still reach the bottom.

The authors prove that you don't need the exact mathematical slope. You just need a "pseudogradient"—a tool that behaves almost like a slope. As long as this tool follows certain rules (it doesn't jump around wildly), the algorithms will still work and find the solution.

The Three Scenarios

The paper looks at three types of "mountains":

1. Optimization (Finding the lowest point): Like the classic bundle methods mentioned. The authors show you can use a "pseudogradient" instead of a real one.
2. Equations (Finding where a line crosses zero): Usually, you need a matrix (a complex grid of numbers) to solve this. The paper says you can replace that complex matrix with a simpler "semismooth derivative" that does the same job.
3. Inclusions (The "Hidden" Problem): This is the most complex part. Imagine the mountain has hidden caves (constraints) where the ground rules change. The solution isn't just a point; it's a relationship between variables. The authors develop a new tool called SCD (Subspace Containing Derivative).
   • Analogy: If the terrain is a complex 3D maze, the SCD is like a skeleton key. It doesn't show you every wall, but it gives you the essential structure (the "skeleton") needed to navigate the maze without getting lost.

The "Chain Reaction" (The Big Breakthrough)

The most exciting part of the paper is how these tools work together.

Imagine you are building a robot to solve a problem.

• Step 1: You have a machine (a set-valued mapping) that takes an input and spits out a range of possible outputs.
• Step 2: You want to know how the final result changes if you tweak the input.
• The Magic: The authors show that if your machine has this "SCD skeleton" property, you can combine it with other tools (like the objective function) and the result is still a "semismooth" tool.

It's like saying: "If I have a wrench that fits a bolt, and I attach it to a drill, the new tool still fits the bolt." This is huge because usually, when you combine complex math tools, they break or become too messy to use. Here, they stay clean and usable.

The Real-World Test

To prove this isn't just theory, the authors built a "Bilevel Program" (a problem where you are optimizing something that depends on solving another problem first).

• The Setup: They created a tricky math problem with sharp corners and hidden constraints.
• The Result: They used their new "semismooth" compass instead of the traditional, heavy-duty tools. The algorithm (called the BT algorithm) zoomed straight to the solution in just 16 steps.
• The Takeaway: They didn't need the exact, perfect math. They just needed the "good enough" semismooth derivative, and it worked perfectly.

Summary in Plain English

This paper is about relaxing the rules.

Mathematicians have been trying to solve jagged, broken problems for decades, insisting on perfect, exact derivatives. This paper says, "Stop trying to be perfect."

Instead, use Semismooth Derivatives. These are like "rough drafts" of slopes that are mathematically proven to be good enough to guide algorithms to the solution. The authors provide the rulebook for how to create these rough drafts, how to combine them, and how to use them to solve complex, real-world problems that were previously too difficult to crack.

The Metaphor:

• Old Math: You need a laser-guided GPS to walk down a cliff. If the signal drops, you fall.
• This Paper: You just need a sturdy hiking boot and a compass that points generally down. Even if the path is rocky and the view is foggy, you will still get to the bottom, and you'll get there faster because you aren't waiting for a perfect signal.

Technical Summary

Here is a detailed technical summary of the paper "On the role of semismoothness in nonsmooth numerical analysis: Theory" by Helmut Gfrerer and Jiří V. Outrata.

1. Problem Statement

The paper addresses the numerical solution of nonsmooth optimization problems, equations, and inclusions. A central challenge in these fields is that exact subgradients or generalized Jacobians (e.g., Clarke subdifferentials) are often difficult to compute or do not exist in infinite-dimensional settings.

While classical semismooth Newton methods rely on the existence of a generalized Jacobian, recent developments suggest that it suffices to have a semismooth derivative—a mapping satisfying a specific semismoothness property—rather than the exact generalized derivative. The paper investigates:

1. The theoretical foundations of semismooth derivatives for single-valued mappings.
2. The interplay between semismoothness and the semismooth* property for multifunctions (set-valued mappings).
3. The application of these concepts to Implicit Programming (ImP) approaches for solving optimization problems with equilibrium constraints (e.g., bilevel programming and MPECs), where the objective function is defined via a solution map to a parametric inclusion.

The core problem is to establish conditions under which one can construct an "oracle" (a mapping providing derivative-like information) that ensures the convergence of bundle methods or Newton-type algorithms, even when the exact Clarke subgradient is unavailable or the solution map is set-valued.

2. Methodology

The authors employ tools from variational analysis and generalized differentiation, specifically focusing on:

• $\Psi$-semismoothness: A generalization of semismoothness where a mapping $F$ is approximated by a set-valued mapping $\Psi$ (a "Newton map") rather than the Clarke generalized Jacobian.
• SCD (Subspace Containing) Derivatives: A framework for differentiating multifunctions where the derivative is a set of subspaces (generalizing the B-Jacobian). This includes the limiting coderivative and the SC derivative ($S^*F$).
• Graphically Lipschitzian Mappings: Mappings whose graphs can be transformed into the graphs of Lipschitz single-valued mappings via a diffeomorphism.
• Chain Rules and Composition: Analyzing how semismoothness properties are preserved under composition of functions and solution maps.

The methodology involves proving that:

1. Single-valued mappings possessing a semismooth derivative are Gowda-semismooth (G-semismooth) and strictly differentiable almost everywhere.
2. For graphically Lipschitzian mappings, the SCD-semismooth* property is equivalent to the G-semismoothness of the transformed single-valued mapping.
3. Solution maps to inclusions inherit semismoothness properties from the underlying set-valued mapping $F$ under specific qualification conditions.

3. Key Contributions

A. Theory of $\Psi$-Semismoothness for Single-Valued Mappings

• Equivalence: The authors prove that a single-valued mapping $F$ possesses a semismooth derivative $\Psi$ on an open set $\Omega$ if and only if $F$ is G-semismooth (semismooth in the sense of Gowda) on $\Omega$.
• Strict Differentiability: They show that such mappings are strictly differentiable almost everywhere (a.e.).
• Coincidence with Generalized Jacobians: The semismooth derivative $\Psi$ coincides with the Clarke generalized Jacobian almost everywhere.
• Closure Property: The generalized Jacobian is contained within the convex hull of the closure of the semismooth derivative ($\text{cocl}\Psi$). This allows for the construction of oracles using $\text{cocl}\Psi$ even if $\Psi$ is not convex or closed.

B. Generalization to Multifunctions: $\Gamma$-semismooth* and SCD-semismooth*

• New Definitions: The paper introduces $\Gamma$-semismooth* and SCD-semismooth* properties. These generalize the standard semismooth* property (defined via limiting coderivatives) by allowing the use of approximating sets $\Gamma$ (such as the graph of the SC derivative) instead of the exact limiting coderivative.
• Graphically Lipschitzian Equivalence: A major theoretical result establishes that a graphically Lipschitzian mapping is SCD-semismooth* if and only if its transformed single-valued counterpart is G-semismooth.
• Strict Proto-differentiability: As a byproduct, the authors show that SCD-semismooth* mappings are strictly proto-differentiable almost everywhere, and their SC derivative is a singleton a.e., simplifying computation.

C. Semismoothness of Solution Maps (ImP Approach)

• Solution Map Analysis: The paper derives conditions under which the solution map $S(x) = \{y \mid 0 \in F(x,y)\}$ of a parametric inclusion is semismooth.
• Chain Rule for ImP: For an optimization problem $\min \phi(x, \sigma(x))$ where $\sigma$ is a selection of the solution map, the authors provide a constructive formula for a semismooth derivative of the reduced objective $\theta(x)$.
• SCD Simplification: In the case where $F$ is an SCD mapping, the construction of the semismooth derivative for the solution map simplifies significantly. The derivative is constructed directly from the adjoint SC derivative ($S^*F$) of the underlying mapping $F$, avoiding the need for complex limiting coderivative calculations.

4. Key Results

1. Theorem 3.8: Establishes that if $F$ is $\Psi$-semismooth on $\Omega$, then $F$ is locally Lipschitz, strictly differentiable a.e., and $\text{conv}\nabla F(x) \subseteq (\text{cocl}\Psi)(x)$.
2. Proposition 4.2 & Corollary 4.3: Proves the equivalence between SCD-semismooth* and G-semismoothness for graphically Lipschitzian mappings and confirms that such mappings are strictly proto-differentiable a.e.
3. Theorem 5.3 & Corollary 5.10: Provides the main result for the Implicit Programming approach. If the underlying mapping $F$ is SCD-semismooth* and satisfies a qualification condition, then any continuous selection $\sigma$ of the solution map is semismooth. The semismooth derivative of the composite objective $\theta(x) = \phi(x, \sigma(x))$ can be explicitly constructed using the SC derivatives of $F$ and the derivative of $\phi$.
4. Algorithmic Implication: The paper demonstrates that Bundle-Trust region (BT) algorithms can converge to stationary points even when the oracle returns elements of a semismooth derivative (or pseudogradient) rather than the exact Clarke subgradient, provided the semismoothness holds on a neighborhood (not just at the solution).

5. Significance

• Bridging Theory and Practice: The paper bridges the gap between abstract variational analysis (limiting coderivatives) and practical numerical algorithms (bundle methods, Newton methods). It justifies the use of "approximate" derivatives (semismooth derivatives) that are easier to compute but sufficient for convergence.
• Extension of ImP: It significantly extends the applicability of the Implicit Programming approach. Previously, ImP required the solution map to be single-valued and Lipschitz. This work allows for set-valued solution maps and nonsmooth constraints, provided the underlying mapping has the SCD property.
• Computational Efficiency: By utilizing SC derivatives instead of limiting coderivatives, the paper offers a computationally tractable path for solving complex bilevel programs and MPECs. The SC derivative acts as a "skeleton" for the coderivative, retaining necessary information while being easier to calculate.
• Theoretical Unification: It unifies various notions of semismoothness (Gowda, Norkin, Qi-Sun, semismooth*) under a single framework, clarifying their relationships and showing that they are often equivalent in the context of graphically Lipschitzian mappings.

The paper concludes with an academic example of a bilevel program where the proposed method successfully computes a solution using the BT algorithm, demonstrating that the theoretical constructs are implementable and effective.