1

OPTIMAL DESIGN OF STRUCTURES (MAP 562)

G. ALLAIRE

July 6-17th, 2015

Department of Applied Mathematics, Ecole Polytechnique
LECTURE IV

TOPOLOGY OPTIMIZATION
BY THE LEVEL SET METHOD

CIMPA Summer School on Current Research in Finite Element

Methods, IIT Mumbai

G. Allaire, Ecole Polytechnique Optimal design of structures

 2

✞ ☎
Classical numerical algorithm
✝ ✆
☞ The boundary is parametrized by control nodes x which are moved with a
speed proportional to the shape derivative (t > 0 descent step)
Z
J ′ (Ω)(θ) = j θ · n ds ⇒ xk+1 = xk − t j n
Γ

☞ This is a Lagrangian algorithm !

☞ Iterative algorithm: the shape derivative of an initial domain is computed
by solving a p.d.e., then the domain is deformed.
☞ In general it merely converges to a local minimum.
☞ Strong influence of the initial guess and of the mesh.
☞ No topology changes.
☞ May require remeshing which is very costly or difficult in 3-d.

G. Allaire, Ecole Polytechnique Optimal design of structures

 3

FRONT PROPAGATION BY LEVEL SET

More general problem: how to move a hypersurface x(t) according to a given

velocity ~v (t, x).

Lagrangian approach: let us solve o.d.e.’s

dx


 = ~v (t, x(t))
dt

x(0) = x0


Γ(0) = {x0 } ⇒ Γ(t) = {x(t)}

☞ Reversible method: to go back in time, change the velocity sign !
☞ Shape tracking method.

G. Allaire, Ecole Polytechnique Optimal design of structures

 4

☞ Problems with self-intersection and singularity !

☞ How to handle a velocity ~v which depends on the surface through its
normal, mean curvature, etc. ?
☞ How to devise an Eulerian approach ?
☞ Make the evolution irreversible.

G. Allaire, Ecole Polytechnique Optimal design of structures

 5

✞ ☎
✝The level set method of Osher and Sethian ✆

Shape capturing method on a fixed mesh of a “large” box D.

A shape Ω is parametrized by a level set function

 ψ(x) = 0 ⇔ x ∈ ∂Ω ∩ D


ψ(x) < 0 ⇔x∈Ω


ψ(x) > 0 ⇔ x ∈ (D \ Ω)


The normal n to Ω is given by ∇ψ/|∇ψ| and the curvature H is the

divergence of n. These formulas make sense everywhere in D on not only on
the boundary ∂Ω.

G. Allaire, Ecole Polytechnique Optimal design of structures

 6

G. Allaire, Ecole Polytechnique Optimal design of structures

 7

✞ ☎
Hamilton Jacobi equation
✝ ✆

Assume that the shape Ω(t) evolves with a normal velocity V (t, x). Then
 
ψ t, x(t) = 0 for any x(t) ∈ ∂Ω(t).

Deriving in t yields
∂ψ ∂ψ
+ ẋ(t) · ∇x ψ = + V n · ∇x ψ = 0.
∂t ∂t
 
(The same is true for any level set ψ t, x(t) = C.)
Since n = ∇x ψ/|∇x ψ| we obtain
∂ψ
+ V |∇x ψ| = 0.
∂t
This Hamilton Jacobi equation is posed in the whole box D, and not only on
the boundary ∂Ω, if the velocity V is known everywhere.

G. Allaire, Ecole Polytechnique Optimal design of structures

 8

✞ ☎
Example
✝ ✆

Choice of the velocity: ~v = (α − βH)~n with ~n =normal vector, H =mean

curvature
V = α − βH.
We deduce  
∂ψ ∇ψ
+ α|∇ψ| − β|∇ψ| div = 0.
∂t |∇ψ|
which is equivalent to
 
∂ψ ∇ψ ∇ψ
+ α|∇ψ| − β ∆ψ − (∇∇ψ) · = 0.
∂t |∇ψ| |∇ψ|
This Hamilton-Jacobi equation admits a unique viscosity solution global in
time (Crandall-Lions).

G. Allaire, Ecole Polytechnique Optimal design of structures

 9

✞ ☎
Invariance with respect to the extension out of the surface
✝ ✆

The only meaningfull information if the level set ψ(t) = 0. It should not
depend on the choice of extended initial data ψ0 such that Γ(0) = {ψ0 = 0}.

Lemma. Let z → h(z) be an increasing function such that h(0) = 0. If ψ is a

H-J solution for the initial data ψ0 , then h(ψ) is a solution for h(ψ0 ) too.
Formal proof. Multiply the H-J equation by h′ (ψ) ≥ 0 which can be put
inside the absolute values.

Consequence: the level set h(ψ)(t) = 0 is the same whatever the choice of the
function h.

Cf. works of Barles, Chen-Giga-Goto, Evans-Spruck.

G. Allaire, Ecole Polytechnique Optimal design of structures

 10

✞ ☎
Example of an explicit solution
✝ ✆

c=1 c=−1
∂ψ
Take α = c, β = 0 ⇒ + c|∇ψ| = 0.
∂t
A viscosity solution is ψ(t, x) = d(x, Γ0 ) − c t with d(x, Γ0 ) the signed
distance to the initial surface. Irreversible solution !
Conclusion: some corners remain corners, others get rounded !
We must have numerical schemes preserving this property.

G. Allaire, Ecole Polytechnique Optimal design of structures

 11

✞ ☎
Upwind scheme for Hamilton-Jacobi
✝ ✆
∂ψ
To solve the eikonal transport equation + c|∇ψ| = 0 in D we must use an
∂t
upwind scheme to make a difference between sharp corners and rounding
corners.
∂ψ
1-d analogy: define u = ∂x and differentiate the H-J equation

∂u ∂f (u)
+ =0 with f (u) = c |u| .
∂t ∂x
If c > 0, then f (u) is convex. The classical theory of shock waves tells us that
the solution
 of the Riemann problem with  initial data
 u x < 0,  shock if uL > uR ,
L
u(0, x) = is u(t, x) =
 uR x > 0.  rarefaction if uL < uR .

G. Allaire, Ecole Polytechnique Optimal design of structures

 12

✄
✂Osher-Sethian numerical scheme ✁
We solve
∂ψ
− j|∇x ψ| = 0 in D
∂t
by an explicit upwind 1st order scheme
ψin+1 − ψin
− max(jin , 0) g + (Dx+ ψin , Dx− ψin ) − min(jin , 0) g − (Dx+ ψin , Dx− ψin ) = 0
∆t
n
ψi+1 −ψin n
ψin −ψi−1
with Dx+ ψin = ∆x , Dx− ψin = ∆x , et
p
g − (d+ , d− ) = min(d+ , 0)2 + max(d− , 0)2 ,
+ +
p−
g (d , d ) = max(d+ , 0)2 + min(d− , 0)2 .
☞ We rather use a 2nd order extension (with min-mod limiters).
☞ This is the Osher scheme for conservation laws ”translated” to H-J
equations, with a slight modification due to Rouy-Tourin.
☞ One can add a parabolic part for perimeter penalization.

G. Allaire, Ecole Polytechnique Optimal design of structures

 13

✞ ☎
Another numerical scheme (adapted to Freefem)
✝ ✆
Idea of J. Strain (JCP 99): Semi-Lagrangiam Methods for Level Set
Equations.
For ”small” time, we linearize the H-J equation as

∂ψ

 − jn0 · ∇x ψ = 0 in D × (0, T ),
∂t

∇x ψ0
ψ(0, x) = ψ (x) in D and n (x) = .

0 0

|∇x ψ0 |


Then, we use a method of characteristics to solve this linearization.

Solve the O.D.E.

 dX = −j(X)n0 (X)
 for 0 < t < T,
dt
 X(0, x) = x.


Then ψ (t, X(t)) = ψ0 (x). In Freefem, use the convect operator.

G. Allaire, Ecole Polytechnique Optimal design of structures

 14

✞ ☎
Application to shape optimization
✝ ✆

Shape derivative Z
J ′ (Ω0 )(θ) = j(u, p) θ · n ds.
Γ0

Gradient algorithm: choose θ such that J ′ (Ω0 )(θ) < 0 and move the shape
 
Ω = Id + θ Ω0 with θ = −t j(u, p) n

for some descent step t > 0.

➫ The normal n is extended and defined everywhere in D.
➫ The shape moves with a normal advection velocity V = −j.
➫ For the “pseudo-time” t (descent step), we solve the Hamilton-Jacobi
equation
∂ψ
− j|∇x ψ| = 0 in D
∂t

G. Allaire, Ecole Polytechnique Optimal design of structures

 15

NUMERICAL ALGORITHM

1. Initialization of the level set function ψ0 (including holes).

2. Iteration until convergence for k ≥ 1:
(a) Computation of uk and pk by solving linearized elasticity problem with
the shape ψk . Evaluation of the shape gradient = normal velocity Vk
(b) Transport of the shape by Vk (Hamilton Jacobi equation) to obtain a
new shape ψk+1 .
(c) (Occasionally, re-initialization of the level set function ψk+1 as the
signed distance to the interface).

G. Allaire, Ecole Polytechnique Optimal design of structures

 16

✞ ☎
Algorithmic issues
✝ ✆
✗ Quadrangular mesh.
✗ Upwind finite difference scheme of order 2 for the Hamilton Jacobi
equation.
✗ Q1 finite elements for the elasticity problems in the box D

∗


 − div (A e(u)) = 0 in D

 u=0

on ΓD
∗




 A e(u) n = g on ΓN

 A∗ e(u)
n = 0

on ∂D \ (ΓN ∪ ΓD ).

✗ Elasticity tensor A∗ defined as a “mixture” of A and a weak ersatz

material mimicking holes: A∗ = θA with 10−3 ≤ θ ≤ 1 and θ = volume of
the shape ψ < 0 in each cell.
✗ At each elasticity analysis, we perform many time steps of transport (its
number is controlled by the decrease of the objective function).

G. Allaire, Ecole Polytechnique Optimal design of structures

 17

✄
✂Re-initialization ✁

In order to regularize the level set function (which may become too flat or too
steep), we reinitialize it periodically by solving
∂ψ  
+ sign(ψ) |∇x ψ| − 1 = 0 in D,
∂t
which admits as a stationary solution the signed distance to the initial
interface {ψ(t = 0, x) = 0}.

G. Allaire, Ecole Polytechnique Optimal design of structures

 18

✄
✂Influence of reinitialization ✁

G. Allaire, Ecole Polytechnique Optimal design of structures

 19

✞ ☎
Short cantilever (compliance minimization)
✝ ✆

G. Allaire, Ecole Polytechnique Optimal design of structures

 20

✞ ☎
Long cantilever (compliance minimization)
✝ ✆

G. Allaire, Ecole Polytechnique Optimal design of structures

 21

✄
✂NUMERICAL EXAMPLES ✁

See the web page

[Link] [Link]

A Scilab code for the level-set method can be downloaded at

[Link] [Link]

G. Allaire, Ecole Polytechnique Optimal design of structures

 22

✞ ☎
Various objective functions
✝ ✆

1. Compliance
2. Design dependent load
3. Multiple loads (sum of compliances)
4. Eigenfrequency maximization
5. Least square criteria
6. Minimization of a stress norm
7. Robust compliance (worst case design)

G. Allaire, Ecole Polytechnique Optimal design of structures

 23

✄
✂Stress minimization ✁
11111
00000
00000
11111
00000
11111

Boundary conditions Compliance minimization

G. Allaire, Ecole Polytechnique Optimal design of structures

 24

✞ ☎
Stress minimization (continued)
✝ ✆

|σ|α with α = 2 (left), 5 (middle) and 10 (right).

R
L-beam problem: min

G. Allaire, Ecole Polytechnique Optimal design of structures

 25

|σ|2 (right)
R
Optimal 3-d masts for the compliance (left), and

G. Allaire, Ecole Polytechnique Optimal design of structures

 26

✄
✂References ✁

☞ G. Allaire, F. Jouve, A.-M. Toader, A level-set method for shape

optimization, C. R. Acad. Sci. Paris, Série I, 334, pp.1125-1130 (2002).

☞ G. Allaire, F. Jouve, A.-M. Toader, Structural optimization using sensitivity

analysis and a level-set method, J. Comp. Phys. Vol 194/1, pp.363-393
(2004).
☞ G. Allaire, F. de Gournay, F. Jouve, A.-M. Toader, Structural optimization
using topological and shape sensitivity via a level set method, Control and
Cybernetics 34, pp.59-80 (2005).
☞ G. Allaire, F. Jouve, A level-set method for vibration and multiple loads
structural optimization, Comput. Methods Appl. Mech. Engrg. 194,
pp.3269-3290 (2005).
☞ F. de Gournay, G. Allaire, F. Jouve, Shape and topology optimization of the
robust compliance via the level set method, COCV 14, pp.43-70 (2008).

G. Allaire, Ecole Polytechnique Optimal design of structures

 27

✞ ☎
References (Ctd.)
✝ ✆

☞ G. Allaire, F. Jouve, Minimum stress optimal design with the level set
method, Engineering Analysis with Boundary Elements 32, pp.909-918
(2008).
☞ G. Allaire, Ch. Dapogny, G. Delgado, G. Michailidis, Multi-phase
structural optimization via a level set method, COCV 20, pp.576-611
(2014).
☞ G. Allaire, F. Jouve, G. Michailidis, Thickness control in structural
optimization via a level set method, to appear in SMO.
☞ G. Allaire, Ch. Dapogny, P. Frey, Shape optimization with a level set
based mesh evolution method, CMAME 282, 22-53 (2014).

G. Allaire, Ecole Polytechnique Optimal design of structures