Bridging local and semilocal stability: A topological approach

This paper establishes a general topological condition under which the semilocal Lipschitz upper semicontinuity modulus of a set-valued mapping is exactly determined by the supremum of its local calmness moduli, thereby enabling precise calculation of semilocal error bounds in various non-convex parametric optimization frameworks.

The Gist

Imagine you are the captain of a ship navigating through a foggy archipelago. Your goal is to understand how much your ship's position (the "solution") might drift if the wind and currents (the "data" or "parameters") change slightly.

In the world of mathematics and optimization, this is called stability analysis. The paper you provided is a breakthrough in figuring out exactly how much your ship might drift, even when the islands (the possible solutions) are shaped in weird, non-smooth ways.

Here is the story of the paper, broken down into simple concepts and analogies.

1. The Two Ways to Measure Drift

The paper tackles a problem with two different ways of measuring "drift":

• The Local View (The "Calmness" Modulus): Imagine you are standing on a specific rock (a specific solution). You ask, "If the wind changes a tiny bit, how far does this specific rock move?" This is easy to calculate. It's like checking the stability of a single anchor.
• The Global View (The "Lipschitz Upper Semicontinuity" Modulus): Now, imagine the entire archipelago shifts. You ask, "If the wind changes, how far does the farthest possible point in the entire group of islands move?" This is much harder to calculate because you have to look at every single rock in the group at once.

The Big Question: Can we figure out the "Global Drift" just by looking at the "Local Drift" of every single rock and picking the worst one?

2. The Old Rule vs. The New Discovery

• The Old Rule (Convexity): In the past, mathematicians knew the answer was "Yes" only if the islands were shaped like perfect, smooth balls or cubes (mathematically, "convex"). If the shape was weird, the local checks didn't add up to the global picture. It was like trying to predict the movement of a crumpled piece of paper by only looking at its corners; the middle might snap somewhere unexpected.
• The New Discovery: This paper says, "You don't need the islands to be perfect balls!" You can have crumpled, jagged, or broken shapes. As long as two specific conditions are met, the Global Drift is exactly equal to the worst-case Local Drift.

3. The Two Magic Conditions

To make this "Local = Global" rule work for messy, non-convex shapes, the paper requires two topological "safety nets":

1. Outer Semicontinuity (The "No Ghosts" Rule):
   Imagine you are watching the islands shift. If a rock suddenly appears out of thin air in the distance as the wind changes, that breaks the rule. "Outer semicontinuity" means the islands can't magically pop into existence far away. If a rock is going to move, it has to move continuously from where it started. There are no "ghost" rocks appearing out of nowhere.

2. Local Compactness (The "No Runaways" Rule):
   Imagine the wind changes slightly. You need to be sure that the islands don't suddenly stretch out to infinity. "Local compactness" ensures that the group of solutions stays within a finite, bounded area. No part of the solution set can "run away" to the horizon at an infinite speed just because of a tiny nudge.

The Analogy: Think of a rubber band.

• If the rubber band is convex (a perfect circle), you know exactly how it stretches.
• If the rubber band is jagged (non-convex), it's usually hard to predict.
• BUT, if you ensure the rubber band doesn't snap off into pieces (Outer Semicontinuity) and doesn't stretch infinitely long (Local Compactness), then you can predict its total stretch just by measuring how much its individual points stretch.

4. Why This Matters (The Real World)

Why do we care about this? Because real-world problems are rarely perfect circles. They are jagged and complex.

The paper shows that this new rule applies to many difficult scenarios:

• Optimization: Finding the best route for a delivery truck when traffic data changes.
• Economics: Predicting market equilibrium when prices fluctuate.
• Engineering: Ensuring a bridge design remains safe even if the material properties vary slightly.

In all these cases, the "solution set" (the set of all possible good answers) is often non-convex. Before this paper, calculating the worst-case scenario for these problems was incredibly difficult, often requiring impossible computations.

5. The Takeaway

The author, J. Camacho, has built a bridge.

• On one side: We have easy-to-calculate "Local" numbers (how much does this specific solution move?).
• On the other side: We have the hard-to-calculate "Global" number (how much does the whole system move?).
• The Bridge: If the system doesn't create "ghost" solutions and doesn't let solutions "run away" to infinity, you can cross the bridge. You can simply take the maximum of all the local numbers, and you will have the exact global answer.

In short: You don't need to check the whole universe to know how much the system will shake. You just need to check the worst-case shake of every individual part, provided the system stays "well-behaved" (no ghosts, no runaways). This turns a nightmare of complex math into a manageable, point-by-point calculation.

Technical Summary

Here is a detailed technical summary of the paper "Bridging local and semilocal stability: A topological approach" by J. Camacho.

1. Problem Statement

The paper addresses a fundamental challenge in variational analysis and mathematical optimization: quantifying the stability of set-valued mappings under data perturbations. Specifically, it investigates the relationship between two distinct measures of stability:

• Local Stability (Calmness): Measured by the calmness modulus ($\text{clm}$), which quantifies the sensitivity of the mapping at a specific point $(y, x)$ in the graph, restricted to a neighborhood. This is often computable via point-based tools like KKT systems or coderivatives.
• Semilocal Stability (Lipschitz Upper Semicontinuity): Measured by the Lipschitz upper semicontinuity modulus ($\text{Lipusc}$), which captures the variation of the entire image set $M(y)$ relative to perturbations in the parameter $y$.

The Core Problem:
While it is well-established that $\text{Lipusc}(M(y)) \geq \sup_{x \in M(y)} \text{clm}(M(y, x))$, the reverse inequality (equality) generally fails outside the realm of convex graphs. For non-convex mappings, the semilocal modulus can be strictly larger than the supremum of local moduli, making the exact calculation of global stability bounds intractable. The paper seeks to identify a general topological condition under which these two quantities coincide, thereby allowing semilocal stability to be determined entirely by local data.

2. Methodology

The author employs a topological approach rooted in variational analysis and set-valued analysis. The methodology involves:

• Defining Moduli: Rigorously defining the Lipschitz upper semicontinuity modulus and the calmness modulus using limit superior formulations involving point-to-set distances.
• Topological Hypotheses: Introducing two key conditions:
  1. Outer Semicontinuity (OSC): Defined in the Painlevé-Kuratowski sense (the graph is closed).
  2. Local Compactness: The mapping is locally compact around the nominal parameter (the image of a neighborhood is relatively compact).
• Proof Strategy: The proof of the main theorem relies on a contradiction argument using sequences. By assuming the semilocal modulus is strictly greater than the supremum of local moduli, the author constructs a sequence of perturbed points. Using the local compactness and outer semicontinuity, this sequence is shown to have an accumulation point within the nominal set. This accumulation point allows the "global" variation to be bounded by a "local" variation at that specific point, leading to a contradiction.
• Application to Specific Classes: The theory is applied to various non-convex frameworks by verifying that they satisfy the topological hypotheses (often leveraging properties of semi-algebraic sets and piecewise convex structures).

3. Key Contributions

The paper makes several significant theoretical and practical contributions:

1. General Topological Sufficient Condition (Theorem 1):
   The primary contribution is Theorem 1, which establishes that if a set-valued mapping $M$ is outer semicontinuous (in the Painlevé-Kuratowski sense) and locally compact around a nominal parameter $y$, then:
   $$\text{Lipusc } M(y) = \sup_{x \in M(y)} \text{clm } M(y, x)$$
   This equality holds without requiring the graph of the mapping to be convex.

2. Corollary for Closed Graphs (Corollary 1):
   It is shown that for mappings with a closed graph that are locally compact, the equality holds automatically. This simplifies the application of the theorem to many standard optimization problems.

3. Extension to Non-Convex Frameworks:
   The paper demonstrates that this equality applies to a broad class of non-convex problems where previous results (relying on convexity or polyhedrality) failed. This includes:

   • Piecewise Convex and Semi-Algebraic Mappings: Using real algebraic geometry to prove local compactness for bounded semi-algebraic sets.
   • Full Data Perturbations in Quadratic Programming: Addressing the KKT mapping where cost matrices and constraints vary simultaneously (introducing bilinear terms and non-convexity).
   • Linear Complementarity Problems (LCPs): Under full perturbations of both the matrix and the vector.
   • Linear Semi-Infinite Programming (SIP): Extending stability results to infinite-dimensional constraint systems.
   • Parameterized Sub-Level Sets: Handling non-convex objective functions where sub-level sets may fracture into disconnected components.

4. Key Results

• Exactness of Moduli: The paper proves that for the identified classes of mappings, the difficult-to-compute semilocal modulus is exactly the supremum of the easily computable local calmness moduli.
• Point-Based Formulae: This result enables the derivation of precise, point-based formulae for global error bounds. Practitioners can now calculate the worst-case expansion of a solution set by simply maximizing local sensitivity measures over the nominal solution set.
• Counter-Examples: The paper provides three critical examples (Examples 1, 2, and 3) demonstrating that the topological assumptions (closedness of the nominal set, outer semicontinuity, and local boundedness) are necessary. If any are dropped, the equality between the moduli breaks down.
• Specific Applications:
  • For a parametric quadratic program with full perturbations, the paper derives an exact formula for the stability of the optimal set mapping, a result previously unavailable in the literature.
  • For Linear Semi-Infinite systems, it resolves an open problem regarding full perturbations (both coefficients and RHS), proving the equality holds if the nominal feasible set is bounded.
  • For non-convex sub-level sets, it provides a formula for the Lipschitz modulus based on the maximum reciprocal of the gradient norm at active boundary points.

5. Significance

The significance of this work lies in its ability to bridge the gap between local and global stability analysis in non-convex optimization:

• Computational Tractability: It transforms the problem of estimating global stability (often intractable) into a problem of evaluating local sensitivities (often computable via standard optimization tools like KKT conditions).
• Theoretical Unification: It unifies the stability analysis of diverse problems (LCPs, SIPs, non-convex optimization) under a single topological framework, moving beyond the restrictive assumption of convex graphs.
• Algorithmic Implications: The results provide a rigorous foundation for algorithms dealing with uncertainty, sensitivity analysis, and hierarchical decision-making (e.g., MPECs and bilevel optimization), ensuring that convergence and optimality conditions can be derived with precise quantitative bounds.
• Error Bounds: It offers a new perspective on error bounds, showing that for a wide range of non-convex systems, the global error bound is determined by the "worst-case" local behavior.

In summary, the paper provides a powerful, generalizable tool that allows researchers and practitioners to compute exact semilocal stability measures for complex, non-convex optimization problems by leveraging local information, provided the mapping satisfies standard topological closedness and compactness properties.