Level-set based shape optimization: Analysis and algorithms

Prof. Dr. Wolfgang Ring


Level-set techniques provide a versatile and numerically treatable approach for the encoding of geometrical variables together with an implicit update strategy in which geometrical (parametrization independent) features can easily be incorporated. Using the level-set methodology, an open set \(\Omega \subset \mathbb{R}^n\) is linked to an appropriate Lipschitz continuous function \(\varphi\) via the defining relation \(\Omega = \{x \in \mathbb{R}^n \, : \, \varphi(x) < 0 \}\). An update of \(\Omega\) (e.g. in an iterative optimization process) is realized by updating the corresponding level-set function \(\varphi\). This update can be achieved either in the standard vector space setting \(\varphi_h = \varphi_0 + h \, \delta \varphi\) or — more intriguingly, because more geometric — by solving the level-set equation

$$ \varphi_t + F |\nabla \varphi| = 0 $$

with starting value \(\varphi_0\) up to (pseudo)time \(h >0\). We will discuss the unique solvability of the level-set equation using the concept of viscosity solutions and derive continuity and differentiability results for certain functionals depending on the level-set encoded geometric variable \(\Omega\) with respect to the time-parameter in the level-set equation. Doing so, we generalize the classical shape sensitivity calculus to the level-set context.

For optimization problems, it is essential to obtain descent directions for a given cost functional. In the level-set context, the scalar driving function \(F\) in the level-set equation plays the role of a direction of propagation. We shall discuss the importance of the close relation between the choice of an appropriate metric for the directions of perturbation and the obtained descent direction. We shall introduce several metrics and classify them with respect to their geometrical properties and the suitability for the design of fast optimization algorithms. These metrics will generally be variable and need to be adjusted to the current level-set function and the geometrical situation respectively. We include the classical Newton method into this unified approach where the variable metric is constructed using (a positive definite approximation of) the second shape derivative of the given cost functional. The metric also allows to treat the often discussed issue of extension of a scalar descent direction from the boundary \(\partial \Omega\) — which turns out to be its generic domain of definition — to a function on the whole space in a conceptionally unified way.

Numerically, the level-set equation can be treated similarly to a hyperbolic conversation law i.e. shock capturing, direction dependent schemes have to be considered. We introduce a class of essentially non oscillatory (ENO) finite difference schemes and present details on implementational issues such as extraction of local geometrical information from the finite difference approximation of the level-set function on a fixed regular computational grid and the necessity of occasional reinitialization if the level-set function becomes too much distorted during the iterative update process. For the reinitialization we reset the level-set function to the signed distance function of the current geometrical variable. This is achieved by solving the eikonal equation \(|\nabla \varphi| = 1\) with the boundary condition \(\varphi = 0\) on \(\partial \Omega\). We present the fast-marching and fast sweeping methods and compare their implementational complexities and numerical performances.

Date and Place


TUM Mathematik Rutschen Universität der Bundeswehr München Technische Universität Graz Karl-Franzens-Universität Graz Technische Universität München
Impressum  |  Datenschutzerklärung  |  AnregungenCopyright Technische Universität München