🔢 mathematics

The gap between a variational problem and its occupation measure relaxation

This paper resolves an open question regarding occupation measure relaxations of variational problems by proving that classical and relaxed minima coincide when the codomain dimension is one, while demonstrating via counterexamples that a positive gap can arise when both domain and codomain dimensions exceed one or when integral constraints are present.

Original authors: Milan Korda, Rodolfo Rios-Zertuche

Published 2026-05-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Milan Korda, Rodolfo Rios-Zertuche

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a very difficult puzzle. You want to find the absolute best way to arrange a set of tiles to minimize a certain "cost" (like energy or time), but the tiles have to follow strict rules, like fitting together perfectly or following a specific path. This is what mathematicians call a variational problem.

For a long time, solving these puzzles directly has been incredibly hard, especially when the rules are complex and non-linear. Recently, researchers invented a clever trick: instead of looking for a single, perfect arrangement of tiles, they looked at the problem as a "cloud" of possibilities. They turned the puzzle into a Linear Programming problem (a type of math problem that is usually much easier to solve) by using something called occupation measures.

Think of an occupation measure like a heat map. Instead of asking, "Where is the tile exactly?" you ask, "How much time does the tile spend in this spot?" or "What is the probability of the tile being here?" This turns a rigid, jagged problem into a smooth, convex one that computers can handle easily.

The Big Question
The authors of this paper asked a fundamental question: Is this "heat map" trick actually the same as the original puzzle?

If the answer is Yes, then the easy computer solution gives us the exact same answer as the hard, real-world solution.
If the answer is No, then the computer might give us a "cheaper" answer that is impossible to achieve in the real world. This difference is called a gap.

The paper investigates when this gap exists and when it doesn't.

The Main Findings

The authors discovered that the answer depends entirely on the dimensions of the problem, which they describe using two terms: Dimension and Codimension.

1. The "One-Way Street" (No Gap)

The paper proves that if the problem involves a function where the output (the result) is just a single number (like temperature or height), there is no gap.

The Analogy: Imagine you are trying to draw a line on a piece of paper (2D space) to minimize ink usage. Even if the line is wiggly and complex, as long as the line itself is just a single height value at every point, the "heat map" solution is exactly the same as the best possible real line.
The Result: In this specific case (called codimension one), the relaxation is perfect. The computer's "cloud" of possibilities can always be collapsed back into a single, real, smooth function. The authors proved this by showing that any complex "cloud" of measures can be broken down into a stack of simple, smooth sheets (functions), much like slicing a loaf of bread.

2. The "Twisted Double-Decker" (Positive Gap)

However, if the output involves two or more numbers at once (like a vector with an X and Y direction), the paper shows that a gap can appear.

The Analogy: Imagine trying to draw a path on a map where the path needs to twist and turn in a way that creates a "double cover" (like the surface of a complex spiral staircase or a Möbius strip). In the real world, you can't draw a single continuous line that covers both layers of the spiral without breaking or jumping.
The Result: The "heat map" (relaxed solution) can happily exist on both layers of the spiral at the same time, achieving a lower cost. But a real, single continuous line cannot. The computer finds a "cheaper" solution that is mathematically valid in the relaxed world but physically impossible in the classical world. The authors built a specific example of this using a shape similar to the complex square root function, showing that the gap is real and positive.

3. The "Global Rule" Trap

The paper also found that even if you are in the "safe" zone (where the output is just one number), you can create a gap if you add integral constraints.

The Analogy: Imagine you are driving a car (the function). You are allowed to drive anywhere, but you must ensure that your total fuel consumption over the whole trip equals exactly 10 gallons.
The Result: The "heat map" approach might suggest a solution where you drive 90% of the time on a cheap route and 10% on an expensive one, perfectly averaging out to 10 gallons. But in the real world, you might be forced to drive a specific route that doesn't allow for this perfect mix, forcing you to use more fuel. The "average" solution exists in the relaxed world but not in the real world.

Why Does This Matter?

The authors conclude that while the "gap" means the computer solution isn't always the exact same as the real-world solution, the method is still incredibly valuable.

When there is no gap: The computer gives you the perfect answer.
When there is a gap: The computer gives you a lower bound (a "best case scenario"). Even if you can't build that exact solution, the "cloud" solution often represents a more complete picture of the problem than any single broken or discontinuous real-world solution could. It tells you the theoretical limit of how good you can get.

In short, the paper maps out the boundaries of a powerful new mathematical tool. It tells us exactly when we can trust the tool to give us the perfect answer, and when we should expect it to give us a "best possible approximation" that reveals deeper truths about the problem, even if we can't build it physically.

1. Problem Statement

The paper addresses the fundamental question of equivalence (or the absence of a "relaxation gap") between a classical non-convex variational optimization problem and its occupation measure relaxation.

The Classical Problem: Given a domain $\Omega \subset \mathbb{R}^n$ and a target space $Y = \mathbb{R}^m$ , the goal is to minimize a functional:
$\inf_{y \in W^{1,\infty}(\Omega; Y)} \int_{\Omega} L(x, y(x), Dy(x)) \, dx$
subject to nonlinear PDE constraints (inequalities and equalities) and boundary conditions. Here, $L$ is a Lagrangian density convex in the derivative variable $z = Dy$.
The Relaxation: Instead of optimizing over functions $y$ , the problem is relaxed to an infinite-dimensional Linear Program (LP) over the space of Radon measures (occupation measures) $\mu$ on $\Omega \times Y \times Z$ . These measures satisfy a "moment" constraint derived from the fundamental theorem of calculus, ensuring they represent valid derivatives.
The Core Question: Does the infimum of the relaxed measure problem ( $M_r$ $M_{r}$ ) equal the infimum of the classical function problem ( $M_c$ $M_{c}$ )?
- If $M_c = M_r$ , there is no gap, and the relaxation is exact.
- If $M_c > M_r$ , there is a positive gap, meaning the relaxation provides a lower bound that is strictly unattainable by any classical function.

While it was known that a gap could exist in general, the specific conditions under which the gap vanishes or appears were not fully resolved, particularly regarding the dimensions of the domain ( $n$ ) and codomain ( $m$ ).

2. Methodology

The authors employ tools from Geometric Measure Theory, Sobolev space analysis, and Convex Optimization.

Superposition Principle: The central methodological innovation is proving that when the codimension is 1 ( $m=1$ ), any relaxed occupation measure $\mu$ can be decomposed (superposed) into a convex combination of classical functions in the Sobolev space $W^{1,\infty}(\Omega)$ .
Hardt-Pitts Decomposition: The proof draws inspiration from the Hardt-Pitts decomposition of normal currents. The authors adapt this theory to the setting of occupation measures, utilizing the structure of sets with finite perimeter (De Giorgi's theory) to construct a "height function" $\rho$ from which the decomposing functions $\phi_r$ are derived.
Counterexamples: To demonstrate the existence of gaps, the authors construct explicit counterexamples using topological obstructions (specifically, double-covering structures similar to Riemann surfaces) and integral constraints.

3. Key Contributions and Results

The paper establishes a complete characterization of the relaxation gap based on the dimensions $n$ (domain) and $m$ (codomain):

A. No Gap in Codimension One ( $m=1$ )

Theorem 2.2 & 2.4: If the dimension of the codomain is 1 ( $m=1$ ), regardless of the dimension of the domain ( $n \ge 1$ ), there is no relaxation gap ( $M_c = M_r$ ).

Mechanism: The authors prove that any relaxed measure $\mu$ satisfying the occupation measure constraints can be written as:
$\int \phi \, d\mu = \int_{\mathbb{R}} \left( \int_{\Omega} \phi(x, \phi_r(x), D\phi_r(x)) \, dx \right) d\nu(r)$
where $\phi_r \in W^{1,\infty}(\Omega)$ and $\nu$ is a probability measure.
Implication: Since the Lagrangian $L$ is convex in $z$ , Jensen's inequality implies that the integral of $L$ against the measure $\mu$ is greater than or equal to the integral against one of the specific functions $\phi_r$ in the superposition. Thus, the minimum over measures is achieved by a classical function.
Extension: This result is extended to Optimal Control problems (Theorem 2.7), showing equivalence even when control variables are present, provided the effective Lagrangian remains convex in the state derivative.

B. Positive Gap in Higher Dimensions ( $n > 1, m > 1$ )

Theorem 3.1: If both the domain dimension ( $n$ ) and codomain dimension ( $m$ ) are greater than 1, a positive gap may exist ( $M_c > M_r$ ).

Construction: The authors construct a specific Lagrangian $L$ of class $C^{1,1}_{loc}$ that is strictly convex in $z$ . The example involves a set-valued map $f(x)$ that behaves like a "double cover" (analogous to the complex square root function $\sqrt{z}$ ).
Topological Obstruction: The relaxed measure can "split" the mass between the two branches of the double cover (e.g., $u_0$ and $u_1$ ) to achieve a lower energy. However, no single continuous (or even weakly differentiable) function $y(x)$ can traverse both branches simultaneously without a discontinuity or infinite energy cost.
Significance: This proves that the convexity of $L$ in $z$ alone is insufficient to guarantee no gap when $n, m > 1$ .

C. Positive Gap with Integral Constraints

Section 4: The authors show that even if $n=1$ or $m=1$ (where the unconstrained gap is zero), the introduction of global integral constraints (e.g., $\int H(x, y, Dy) dx = 0$ ) can induce a positive gap.

Mechanism: Integral constraints restrict the feasible set of classical functions more severely than the set of measures. A measure can satisfy the integral constraint by averaging over different classical solutions (e.g., spending 90% of time on solution A and 10% on solution B), whereas a classical function must commit to a single trajectory.

4. Significance and Implications

Theoretical Justification: The paper provides a rigorous mathematical foundation for the use of occupation measure relaxations. It clarifies exactly when these methods are guaranteed to find the global optimum of the original non-convex problem (specifically when $m=1$ ).
Algorithmic Value: Even in cases where a gap exists ( $n, m > 1$ ), the authors argue that the relaxed solution remains valuable. The measure-valued solution often represents a "conceptually satisfactory" object (e.g., capturing multi-valued behavior or microstructures) that classical functions cannot represent. Algorithms based on the moment-sum-of-squares hierarchy (Lasserre hierarchy) remain powerful tools for approximating these lower bounds.
Connection to Geometric Measure Theory: The work bridges the gap between variational calculus and the theory of currents and sets of finite perimeter, offering a new perspective on the decomposition of measures into functions.
Practical Guidance: For engineers and scientists using these methods, the results serve as a guide:
- If the problem is scalar-valued ( $m=1$ ), the relaxation is exact.
- If the problem is vector-valued ( $m>1$ ) in a multi-dimensional domain, one must be cautious of potential gaps, especially if integral constraints are involved.

In summary, Korda and Ríos-Zertuche resolve a long-standing open question by proving that the relaxation gap vanishes for scalar-valued problems (codimension 1) but can persist in higher dimensions due to topological constraints, while also highlighting the utility of measure-valued solutions even when gaps exist.