🔢 mathematics

Locally-averaged McCormick relaxations for discretization-regularized inverse problems

This paper proposes a convergent scheme for the global optimization of PDE coefficient identification by combining locally-averaged McCormick relaxations with optimization-based bound tightening and discretization error quantification to effectively regularize the inverse problem.

Original authors: Barbara Kaltenbacher, Paul Manns

Published 2026-03-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Barbara Kaltenbacher, Paul Manns

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 a detective trying to solve a mystery, but you can't see the culprit directly. You only have blurry, noisy security camera footage (the indirect observations) and you know the culprit follows certain rules (like wearing a red hat or being between 5 and 6 feet tall). Your goal is to figure out exactly who the culprit is (the coefficient or parameter).

In the world of mathematics, this is called an Inverse Problem. The problem is that the "camera footage" is often so blurry and the rules so complex that there are thousands of possible culprits that could fit the description. Furthermore, the math behind figuring this out is like trying to find the lowest point in a landscape filled with deep valleys and high peaks (a non-convex problem). If you just start walking downhill from a random spot, you might get stuck in a small valley (a local minimum) and think you've found the bottom, when actually there's a much deeper valley (the global minimum) somewhere else.

This paper proposes a clever new toolkit to solve this mystery reliably, even when the data is noisy. Here is how they do it, broken down into simple concepts:

1. The "Pixelated" Map (Discretization as Regularization)

Imagine trying to draw a perfect circle on a piece of graph paper. You can't draw a smooth curve; you have to use little squares (pixels).

The Trick: Instead of trying to find the culprit's exact shape (which is impossible with blurry data), the authors decide to only look for culprits that look like they are made of blocks (pixels).
Why it helps: This acts as a filter. It stops the detective from chasing ghosts caused by the noise in the camera. By forcing the solution to be "blocky," they automatically smooth out the errors. This is called regularization by discretization.

2. The "Safe Zone" (McCormick Relaxation)

The math gets tricky because the culprit's identity ( $w$ ) and their movement ( $u$ ) are multiplied together in the equations. This multiplication creates a dangerous, curved landscape where it's hard to know if you've found the true bottom.

The Analogy: Imagine you are trying to guess the area of a rectangle where you don't know the exact length or width, only that the length is between 2 and 4, and the width is between 3 and 5. The exact area could be anything, but you know it must be between $2\times3=6$ and $4\times5=20$ .
The Solution: The authors use a technique called McCormick Relaxation. Instead of trying to solve the complex, curved equation directly, they replace it with a set of straight lines (inequalities) that create a "safe box" around the possible answers.
The Result: This turns the scary, curved landscape into a flat, easy-to-navigate plain (a convex problem). Now, finding the "lowest point" is easy and guaranteed to be the best possible answer within that box.

3. The "Group Average" (Locally-Averaged)

Here is the bottleneck: If you try to draw a "safe box" for every single pixel in a high-resolution image, you end up with millions of rules. It would take a supercomputer years to solve.

The Innovation: The authors say, "Let's not look at every single pixel individually. Let's group them into neighborhoods."
The Metaphor: Instead of asking, "What is the exact temperature of every single grain of sand on the beach?" they ask, "What is the average temperature of this bucket of sand?"
The Benefit: By averaging the rules over small neighborhoods, they drastically reduce the number of calculations needed. They get a "good enough" safe box that is much faster to compute, without losing the ability to find the true answer.

4. The "Tightening" Tool (OBBT)

Sometimes, the "safe box" created by the averaging is still a bit too loose. It might include answers that are technically possible but clearly wrong.

The Tool: They use a method called Optimization-Based Bound Tightening (OBBT). Think of this as a pair of calipers. They measure the current "safe box" and squeeze it tighter and tighter, cutting away the impossible corners until the box is as small as possible without cutting off the real answer.
The Payoff: This gives them a very precise "lower bound." In optimization, knowing a tight lower bound is like having a map that tells you, "The treasure is definitely deeper than 100 feet." This helps them guide their search much more effectively.

5. The Grand Strategy: Balancing the Scales

The paper proves mathematically that if you balance three things correctly, you will find the true culprit as the camera gets clearer:

Noise Level: How blurry the camera is.
Pixel Size: How small your "blocks" are.
Averaging Size: How big your "neighborhoods" are.

If you make the pixels too small for a blurry camera, you get confused by the noise. If you make them too big, you miss the details. The authors provide a recipe to pick the perfect pixel size for any level of noise.

The Real-World Test

They tested this on a computer simulation (like a fake medical scan).

Without their trick: If they just guessed a starting point, the computer got stuck in a "local valley" and gave a wrong answer.
With their trick: They used the "safe box" and "tightening" to find a great starting point. Then, they let a standard solver finish the job.
The Result: Their method found the correct answer almost every time, and as the "camera" got less blurry, the answer got closer and closer to the truth.

Summary

This paper is about building a smart, blocky map for a detective.

They turn a messy, impossible problem into a clean, blocky one.
They build a "safe box" around the answer using straight lines instead of curves.
They group pixels to save time.
They squeeze the box tight to get a precise estimate.
They prove that if you balance your map size with the amount of noise, you will always find the truth.

It's a way to turn a chaotic, confusing puzzle into a solvable one, ensuring that even with imperfect data, we can find the best possible solution.

1. Problem Statement

The paper addresses the global optimization of coefficient identification in Partial Differential Equations (PDEs). Specifically, it focuses on recovering a spatially varying coefficient $w$ (e.g., a potential) in an elliptic PDE from indirect, noisy observations of the state $u$ .

Mathematical Formulation: The problem is modeled as an inverse problem where the state $u$ satisfies $Au + f_0 uw = f_1$ , with $A$ being a linear elliptic operator. The goal is to minimize the discrepancy between observed data $y^\delta$ and the model output $Tu$, subject to the PDE constraint and box constraints on $w$ .
Challenges:
1. Non-convexity: The dependence of the state $u$ on the coefficient $w$ is bilinear, rendering the optimization problem non-convex. Gradient-based methods (like L-BFGS-B) can only find local minima, which may be far from the global optimum.
2. Ill-posedness: Inverse problems are inherently ill-posed; small noise in data can lead to large errors in the solution.
3. Global Optimization Cost: Standard global optimization methods (like spatial branch-and-bound) require tight dual bounds (lower bounds for minimization). Computing these bounds for PDE-constrained problems is computationally prohibitive due to the infinite-dimensional nature of the constraints and the sheer number of McCormick inequalities required to relax the bilinear term $uw$.

2. Methodology

The authors propose a framework that combines discretization regularization, McCormick relaxations, and local averaging to create a computationally tractable approach for generating dual bounds.

A. Discretization Regularization

Instead of solving the continuous problem directly, the coefficient $w$ is restricted to a finite-dimensional subspace $V_h$ (piecewise constants on a mesh with size $h$ ). This serves a dual purpose:

It makes the problem finite-dimensional and solvable.
It acts as a regularization technique, where the mesh size $h$ is coupled with the noise level $\delta$ to ensure convergence as $\delta \to 0$ .

B. McCormick Relaxation

To handle the non-convex bilinear term $uw$, the authors introduce an auxiliary variable $z \approx uw$ and replace the equality with a set of linear inequalities known as McCormick envelopes.

Standard McCormick inequalities require bounds on $u$ and $w$ ( $u_\ell \le u \le u_u$ , etc.).
The relaxation transforms the non-convex problem into a convex minimization problem with linear constraints.

C. Local Averaging (The Core Innovation)

A major bottleneck in standard McCormick relaxations is the number of linear inequalities, which scales with the number of discretization nodes. For fine grids, this is computationally intractable.

Solution: The authors introduce local averaging. They partition the domain $\Omega$ into sub-domains $Q_\tau^i$ (with size $\tau$ ).
Instead of enforcing McCormick inequalities pointwise everywhere, they enforce them on the locally averaged quantities: $(P_\tau u)(P_\tau w)$ , where $P_\tau$ is a projection operator.
This reduces the number of inequality constraints significantly (scaling with $N_\tau$ rather than the full grid resolution) while maintaining the convexity of the relaxation.

D. Optimization-Based Bound Tightening (OBBT)

The initial bounds for $u$ and $w$ derived from PDE theory are often too conservative (loose), leading to weak dual bounds. The authors employ OBBT, an iterative procedure that solves linear programs to tighten these bounds, thereby improving the quality of the McCormick relaxation without solving the full non-convex problem.

3. Key Contributions

Theoretical Convergence Analysis:
- The paper proves that the proposed scheme is a valid regularization method.
- It establishes convergence rates for the reconstructed coefficient $w$ as the noise level $\delta \to 0$ , provided the discretization parameters $h(\delta)$ and $\tau(\delta)$ are chosen according to specific balancing rules derived from the error analysis.
- The analysis quantifies the trade-off between approximation error, discretization error, and propagated noise.
Locally-Averaged Relaxation Framework:
- The authors introduce a novel relaxation $(McC_{\delta\tau})$ that replaces pointwise McCormick inequalities with locally averaged ones. This makes the computation of dual bounds feasible for problems with meaningful discretization resolutions.
Dual Bounds for Global Optimization:
- The method provides rigorous approximate lower bounds (dual bounds) for the global minimum. These bounds are essential for certifying global optimality or for initializing local solvers close to the global solution.
Error Balancing Strategy:
- The paper derives explicit conditions on the mesh sizes $h$ and $\tau$ relative to the noise level $\delta$ to achieve optimal convergence rates.

4. Numerical Results

The authors conducted numerical experiments on a 1D elliptic PDE benchmark problem (recovering a potential from boundary/interior measurements).

Setup: They compared three initialization strategies for a local solver (L-BFGS-B):
1. O: Initialized with the solution of the locally-averaged McCormick relaxation with OBBT (tight bounds).
2. P: Initialized with the relaxation without OBBT (conservative bounds).
3. N: Initialized with a constant function (no bound information).
Findings:
- Performance: Strategy O consistently yielded the lowest reconstruction errors and suboptimality gaps.
- Convergence: As noise $\delta$ decreased, the reconstruction error for Strategy O decreased at a rate consistent with the theoretical predictions (approx. $O(\delta^{1/5})$ for the specific test case). Strategies P and N failed to show a clear downward trend as noise decreased, often getting stuck in poor local minima.
- Efficiency: While OBBT added computational cost (increasing runtime by an order of magnitude compared to P), it was significantly cheaper than running a full spatial branch-and-bound algorithm. The convex relaxation $(McC_{\delta\tau})$ itself was solved very quickly.
- Robustness: The method was robust to variations in noise levels, provided the mesh sizes were balanced according to the theoretical derivation.

5. Significance

This paper makes a significant contribution to the field of inverse problems and global optimization:

Bridging the Gap: It successfully bridges the gap between the theoretical need for global optimization in PDE-constrained inverse problems and the practical limitations of computational cost.
Regularization Theory: It rigorously demonstrates that discretization combined with convex relaxation can serve as a regularization strategy, providing convergence guarantees that are often missing in heuristic global optimization approaches.
Practical Applicability: By using local averaging, the authors make the computation of dual bounds feasible for problems that were previously considered too large for rigorous global optimization techniques.
Guidance for Practitioners: The paper provides concrete guidelines on how to choose discretization parameters ( $h, \tau$ ) relative to noise levels to ensure stable and accurate reconstructions, moving beyond trial-and-error approaches.

In summary, the paper proposes a mathematically rigorous and computationally efficient framework for solving non-convex inverse problems by leveraging locally-averaged McCormick relaxations, proving that this approach yields convergent solutions and high-quality initializations for local solvers.