Convex and quasiconvex truncations of nonconvex functions

This paper investigates nonconvex real-valued functions whose truncations become quasiconvex or convex beyond a certain level, with a specific focus on $C^2$-smooth functions whose level sets lie within the positive definite region of their Hessian matrices, demonstrating the injectivity of their restricted gradients in that region.

The Gist

Imagine you are hiking in a very strange, mountainous landscape. Some parts of this land are smooth and bowl-shaped (like a perfect valley), while other parts are jagged, bumpy, or even shaped like a saddle. In math, we call these shapes convex (the bowl) and non-convex (the messy stuff).

Usually, if a landscape is bumpy, you can't easily predict how a ball will roll down it. But what if we decided to "flatten out" the bottom of the map? What if we said, "Okay, we don't care about the messy parts below a certain height; let's just pretend everything below that line is flat"?

This paper, written by Cornel Pintea, is about finding that specific "magic line" on a bumpy map where, if you ignore everything below it, the remaining landscape becomes perfectly smooth and predictable.

Here is the breakdown of the paper's ideas using simple analogies:

1. The "Truncation" (The Flat Floor)

Imagine you have a 3D model of a mountain range that is full of weird dips and holes.

• The Problem: The whole thing is messy. You can't roll a ball down it reliably because it might get stuck in a small hole or roll into a weird valley.
• The Solution (Truncation): Imagine you take a giant, flat table and slide it up from the bottom of the model. Everything below the table is chopped off and replaced by the flat surface of the table.
• The Goal: The author asks: "How high do I need to lift this table so that the rest of the mountain (everything above the table) becomes a perfect, smooth bowl?"

2. The Two "Magic Levels"

The paper defines two specific heights for this table:

• The Quasi-Convex Level ($sql$): This is the height where the remaining shape is "good enough." If you draw a line between any two points on the remaining mountain, the path between them never dips below the line. It's like a "safe zone" where you won't fall into a hidden pit.
• The Convex Level ($scl$): This is a stricter height. Here, the shape isn't just safe; it's perfectly smooth and bowl-shaped. If you roll a ball here, it will always roll straight down to the bottom without getting stuck.

The paper investigates the relationship between these two levels. Usually, you need to lift the table higher to get the "perfect bowl" ($scl$) than you do to get the "safe zone" ($sql$).

3. The "Hessian" (The Curvature Sensor)

To understand why the mountain becomes smooth at a certain height, the author uses a tool called the Hessian Matrix.

• Analogy: Think of the Hessian as a "curvature sensor" attached to every point on the mountain.
  • If the sensor says "Positive," the ground is curving upward like a bowl (safe for rolling).
  • If it says "Negative" or "Zero," the ground is flat, a saddle, or curving downward (dangerous).
• The Discovery: The author found that for these special mountains, once you lift your "flat table" above a certain height (specifically, above the highest point where the curvature sensor goes bad), the entire remaining mountain is made only of "Positive" curvature. It's all bowls, no saddles.

4. The "Gradient" (The Compass)

The Gradient is like a compass that always points straight down the steepest slope.

• The Problem: On a bumpy mountain, two different hikers starting at different spots might have their compasses pointing in the exact same direction, even though they are in different places. This makes it impossible to tell where they are just by looking at their compass.
• The Result: The paper proves that if you lift your "flat table" high enough (above the "Convex Level"), the compass becomes unique.
  • Analogy: Imagine a giant funnel. If you are anywhere inside the funnel, the direction "down" points to a unique spot. No two places have the exact same "down" direction.
  • The author proves that for these specific mountains, once you are above the magic height, every single point has a unique "down" direction. You can never get confused about where you are based on the slope.

5. The Real-World Example: The Lemniscate

The author uses a specific shape called the Lemniscate of Bernoulli (it looks like a figure-eight or a peanut shell) to demonstrate this.

• If you look at the whole peanut shell, it's bumpy and has a weird dip in the middle.
• However, if you cut off the bottom part of the peanut (the "truncation"), the top part becomes a perfect, smooth bowl.
• The paper calculates exactly where to make that cut. It turns out the "magic height" is determined by the highest point of the "bad curvature" zone.

Summary: Why Does This Matter?

In the real world, we often deal with messy, non-smooth data (like stock markets, weather patterns, or machine learning models).

• Optimization: If you are trying to find the lowest point (the best solution) in a messy system, you usually get stuck in local traps.
• The Takeaway: This paper tells us that if we ignore the messy "bottom" of the problem and focus only on the "top" (above a certain threshold), the problem suddenly becomes easy to solve. The landscape becomes predictable, the paths become unique, and we can find the best solution without getting lost.

In a nutshell: The paper is a guidebook for finding the "sweet spot" on a bumpy hill where, if you just ignore the bottom, the rest of the hill turns into a perfect, easy-to-navigate slide.

Technical Summary

Here is a detailed technical summary of the paper "Convex and Quasiconvex Truncations of Nonconvex Functions" by Cornel Pintea.

1. Problem Statement

The paper investigates non-convex real-valued functions $f: \mathbb{R}^n \to \mathbb{R}$ that exhibit convex or quasiconvex behavior only above a certain threshold level. Specifically, the author addresses the following questions:

• Under what conditions do the sublevel sets of a non-convex function become convex (or quasiconvex) starting from a specific level $q$?
• How can one quantify the "deviation" of a function from convexity or quasiconvexity using the smallest such level?
• What are the relationships between the geometry of the function's Hessian matrix (specifically the region where it is positive definite) and the convexity of its truncations?
• To what extent is the gradient of such a function injective on these high-level sets?

2. Methodology and Definitions

The author employs tools from convex analysis, differential geometry, and Morse theory. Key definitions and concepts include:

• Truncation: For a function $f$ and a level $q \in \mathbb{R}$, the truncation is defined as $T_q(f)(x) = \max\{q, f(x)\}$.
• Smallest Convexity/Quasiconvexity Levels:
  • $scl(f)$: The infimum of levels $q$ such that $T_q(f)$ is convex.
  • $sql(f)$: The infimum of levels $q$ such that $T_q(f)$ is quasiconvex.
  • These values serve as quantitative measures of how far a function is from being globally convex or quasiconvex.
• Hessian Regions:
  • $Hess^+(f) = \{x \in \mathbb{R}^n \mid H_f(x) \text{ is positive definite}\}$.
  • $h_{max}(f) = \max \{f(x) \mid x \in \mathbb{R}^n \setminus Hess^+(f)\}$.
  • $\nu_{max}(f) = \max \{f(x) \mid x \in C(f)\}$, where $C(f)$ is the critical set of $f$.
• Assumptions: The analysis primarily focuses on $C^2$-smooth functions where the complement of the positive definite Hessian region ($\mathbb{R}^n \setminus Hess^+(f)$) and the critical set $C(f)$ are bounded. The functions are often assumed to be norm-coercive ($\lim_{\|x\|\to\infty} f(x) = +\infty$).

3. Key Contributions and Results

A. Relations Between Convexity Levels and Hessian Geometry

The paper establishes rigorous inequalities linking the smallest convexity level ($scl$) and quasiconvexity level ($sql$) to the maximum value of the function outside the positive definite Hessian region ($h_{max}$).

• Theorem 3.1: If $f$ is a $C^2$-smooth truncated quasiconvex function with bounded $C(f)$ and $\mathbb{R}^n \setminus Hess^+(f)$, then $f$ is truncated convex, and:
  $$sql(f) \le scl(f) \le \max\{sql(f), h_{max}(f)\}$$
  This result implies that once the function's value exceeds $h_{max}(f)$, the sublevel sets are entirely contained within the region where the Hessian is positive definite, ensuring convexity.

• Corollary 3.1 & 3.2: Under specific conditions (e.g., $n \in \{2, 3\}$ and norm-coercivity), the paper proves that $scl(f) \le h_{max}(f)$. If additionally $sql(f) \ge h_{max}(f)$, then equality holds:
  $$sql(f) = scl(f) = h_{max}(f)$$
  This equality signifies that the transition to convexity occurs exactly when the function leaves the "non-convex" region of its Hessian.

B. Injectivity of the Gradient

A major contribution is the proof of the injectivity of the gradient restricted to high-level sets.

• Theorem 4.1: Let $f$ be a $C^2$-smooth truncated convex function such that $scl(f)$ is a regular value and $f^{-1}(scl(f), +\infty) \subseteq Hess^+(f)$. Then, the restriction of the gradient $\nabla f$ to the set $f^{-1}(scl(f), +\infty)$ is one-to-one (injective).
  • Methodology: The proof utilizes the Gale-Nikaidô criterion for global injectivity on convex domains and properties of maximal monotone operators (Rockafellar). It leverages the fact that on the set where $f > scl(f)$, the function coincides with its convex truncation, and the Hessian is positive definite.

C. Case Study: Product of Squared Distance Functions

The paper provides a concrete example using the function:
$$f_a(x, y) = (x^2 + y^2)^2 - 2a^2(x^2 - y^2)$$
This function represents the product of squared distances to two points minus a constant.

• Results: For this function, $scl(f_a) = sql(f_a) = h_{max}(f_a) = 3a^4$.
• Geometry: The level sets are Cassini ovals. The paper demonstrates that the sublevel sets become convex exactly at the level $3a^4$, which corresponds to the maximum value of the function on the boundary of the positive definite Hessian region.
• Injectivity Limit: The paper shows that the injectivity of $\nabla f_a$ fails if the domain is extended below $3a^4$, proving that the set$f^{-1}(scl(f), +\infty)$ is the largest overlevel set where the gradient is injective for this specific function.

4. Significance and Implications

1. Quantifying Non-Convexity: The paper introduces $scl(f)$ and $sql(f)$ as precise metrics for the "degree" of non-convexity. This allows for the classification of non-convex functions that are "locally" or "asymptotically" convex.
2. Hessian-Convexity Connection: It rigorously connects the algebraic property of the Hessian (positive definiteness) with the geometric property of sublevel sets (convexity). It proves that for a broad class of functions, convexity of sublevel sets is guaranteed once the function values exceed the maximum value attained in the "bad" Hessian region.
3. Global Injectivity: The results on gradient injectivity are significant for optimization and inverse problems. They guarantee that on high-level sets, the gradient mapping is invertible, which is crucial for the convergence of gradient-based algorithms and the uniqueness of solutions in certain inverse problems.
4. Open Problems: The paper concludes by identifying open questions regarding:
   • The extension of these results to less regular functions ($C^1$ or continuous).
   • Whether the boundedness of the critical set is a redundant hypothesis.
   • The exact valence (number of pre-images) of the gradient on the entire positive definite region, relating it to the number of connected components of the Hessian region.

Conclusion

Cornel Pintea's work provides a theoretical framework for understanding how non-convex functions can possess convex structures at high energy levels. By defining truncation levels and relating them to the Hessian matrix, the paper offers new insights into the geometry of non-convex landscapes, with specific applications to the injectivity of gradients and the structure of level sets in optimization theory.