Numerical Approximation using Relaxed Formulation
Sometimes it is easier to replace an optimization problem with a sequence of relaxed problems whose solutions approximate the solution to the initial problem.
This kind of procedure can be useful when we need to approximate numerically discontinuous functions (in particular the characteristic function). Modica Mortola theorem states that the functionals
converges to the functional
(Recall that is a real function which is positive except for and where it is zero.)
The properties of convergence imply that if we find minimizers for with small we get near to the minimizers of . Intuitively you can see that the second part of forces the minimizer to be near and , while the first part penalizes the “length” of the set where the function “jumps” from to .
The first and the simplest problem that can be attacked like this is the isoperimetric problem. In that case the only thing that is to be done is to find the minimizers for directly keeping in mind that we must impose a volume constraint. The optimization is done in this case using an optimized gradient descent algorithm (LBFGS). The initial condition is chosen random (to let the algorithm the freedom to find the best optimizer it can) and multiplied with a constant such that its volume is . We work on an uniform grid on the unit square . For the gradient approximation we use finite differences and we approximate the integral by the mean of the values in the discretizatioin points. To preserve the volume it is enough to project the gradient at each iteration on the hyperplane . Here are the results obtained: (note that the results were obtained for different values of , and the value of determines the width if the interface region – the yellowish part in the last figure. If is small enough, the interface part becomes invisible, and the result is virtually a characteristic function)
Edouard Oudet has used the ModicaMortola theorem to build a framework in which one could study numerically by relaxation the problem of finding the partition which minimizes the sum of perimeters of all its parts. It has been proved recently by Thomas C. Hales that the optimal partition of the plane into sets of equal volume in the sense that this partition has the least perimeter cost is the partition into regular hexagons. It is no wonder that bees construct hexagonal honeycombs in order to optimize the time and material used.
The relaxed problem in the partitioning case is the following:
MultiPhase ModicaMortola Consider a bounded open set and for consider the space
and define
Then converges to .
Note that this is not an obvious consequence of the ModicaMortola theorem. While the first part, the inequality is a direct consequence, the part is not, and if we consider the recovery sequence for the the ModicaMortola Theorem for then considering we don’t obtain necessarily a recovery sequence, since may not satisfy the sum constraint. So the challenge here is to find a suitable recovery sequence, and this is possible (with some care) using some similar ideas used in the proof of the part of the ModicaMortola theorem using the signed distance function to each set of the partition. To see more details and results regarting the partitioning problem, you can take a look on the website of Edouard Oudet.

April 24, 2013 at 10:53 pmRelaxation of the Anisotropic Perimeter – Part 1  Beni Bogoşel's blog