1 Introduction
The level-set method was originally developed as a mathematical tool for tracking the motion of interfaces in two or three dimensions (Osher and Sethian
1988; Sethian
1999; Osher and Fedkiw
2003). The key idea is to represent interfaces using a discretized implicit function, which is then evolved under a velocity field to track interface motion. This approach naturally allows for complicated phenomena to occur, such as interface merging or splitting. Sethian and Wiegmann (
2000) were first to utilise the level-set method for structural optimization, noting its natural handling of topological changes, coupled with a clear and smooth interface representation. This attractive combination has seen significant interest in level-set based structural optimization methods in recent years and they have become a viable alternative to traditional topology optimization methods based on element-wise design variables, such as the Solid Isotropic Material with Penalisation (SIMP) method (Bendsøe and Sigmund
2003) and Evolutionary Structural Optimization (ESO) methods (Huang and Xie
2010).
This introduction intends to provide a general overview of the range of approaches to level-set based optimization. For more comprehensive reviews see: van Dijk et al. (
2013), Sigmund and Maute (
2013), Deaton and Grandhi (
2014) and the critical comparison of several level-set methods by Gain and Paulino (
2013). The key common feature of all level-set methods is the representation of the boundary as the zero level-set of an implicit function. In level-set based optimization, sensitivities are then used to update the implicit function and hence optimize the position of the boundaries. The implicit boundary representation allows natural handling of topological changes, such as merging or insertion of holes. This allows for some degree of topology optimization, although special techniques are often required to create new holes during optimization (Allaire et al.
2005; Park and Youn
2008; Dunning and Kim
2013). The initial approaches to level-set based optimization used shape derivatives coupled with the original level-set method for front tracking. In this approach the implicit function is frequently re-initialized to become a signed distance function and it is updated by solving a Hamilton-Jacobi (H-J) type equation using an explicit upwind scheme (Allaire et al.
2004; Wang et al.
2003). This is sometimes called the conventional approach (Deaton and Grandhi
2014). Variations on the conventional approach include solving the H-J equation using semi-implicit additive operator splitting (Luo et al.
2008) or a semi-Lagrange approach (Xia et al.
2006). These methods can overcome the Courant–Friedrichs–Lewy (CFL) stability condition that limit the efficiency of the conventional approach. Alternative implicit functions have also been employed in level-set based optimization. Radial basis functions can be used to convert the Hamilton-Jacobi PDE into an ODE (Wang and Wang
2006a) or a simple set of algebraic equations (Luo et al.
2007). The spectral level set method represents the implicit function as coefficients of a Fourier series and the design variables are the coefficients of the basis functions (Gomes and Suleman
2006). There are also methods based on phase fields (Takezawa et al.
2010; Blank et al.
2010) where the implicit function is used to define the material phase of a point and the update is performed by solving a reaction–diffusion equation.
Practical engineering problems often involve several constraints and various approaches have been employed to handle constraints in level-set based optimization. Some approaches are limited to problems with a single constraint, such as the maximum material volume. This constraint can be added to the objective using a fixed Lagrange multiplier (Allaire et al.
2004; Wang and Wang
2006a). This is effectively a penalty method, which cannot guarantee the constraint is satisfied. An alternative is to obtain the Lagrange multiplier under the assumption that the volume remains constant during the level-set update (Wang et al.
2003). However, conserving volume or mass with the level-set method can be difficult. This method can be improved by adjusting the Lagrange multiplier to account for the current feasibility of the constraint (Wang and Wang
2006b) or by using Newton’s method to correct the Lagrange multiplier if the constraint becomes infeasible (Osher and Santosa
2001). A further approach is to explicitly compute the Lagrange multiplier each iteration, using a one-dimensional optimization technique, to ensure constraint feasibility (Wang et al.
2007; Zhu et al.
2010; Dunning and Kim
2013).
The methods discussed so far have been applied to only single constraint problems where the constraint is usually an upper limit on material volume. To handle multiple constraints, a gradient projection method has been used, where the decent direction of the objective function is projected onto the tangential space of the active constraints (Wang and Wang
2004). However, a return mapping algorithm is required to handle non-linear constraints and infeasible initial designs (Yulin and Xiaoming
2004). This algorithm modifies the velocity function by adding a linear combination of the violated constraint gradients, so that they become feasible over one or more iterations. The gradient projection method has been demonstrated for multiple volume constraints for multiple materials (Wang and Wang
2004; Yulin and Xiaoming
2004) and for a volume and input displacement constraint for compliant mechanism design (Yulin and Xiaoming
2004). Another approach to handle multiple constraints is to use the augmented Lagrange multiplier method (Luo et al.
2008,
2009). However, the choice of penalty parameters can affect the convergence and efficiency of the level-set method (Zhu et al.
2010) and it can be difficult to satisfy the constraint unless the parameter is very large (van Dijk et al.
2012).
All the constraint handling methods discussed so far are applicable to conventional level-set optimization methods. Some alternative level-set methods are formulated such that traditional optimization techniques can be applied. This is often the case when using parameterizations other than the signed distance function. For example, the Method of Moving Asymptotes (MMA) can be used when the implicit function is parameterized using compactly supported radial basis functions, which converts the H-J PDE into a set of algebraic equations (Luo et al.
2007). The level-set optimization method proposed by van Dijk et al. (
2012) links implicit function values at the nodes to density values within elements using an exact Heaviside function. Gradients are first obtained at the element level and then linked to the level-set design variables using the chain rule, thus allowing multiple constraints to be handled without using penalty parameters. However, the relationship between the nodal implicit function values and element densities is non-linear, which can lead to an ill-conditioned optimization problem. The method was used to solve problems with multiple compliance constraints, although further regularization was required to remove numerical artifacts from the solutions, such as material islands. Another limitation of this approach is that it is linked to the density based material model for sensitivity analysis and is not easily applicable to other material models, such as the eXtended Finite Element Method (X-FEM) (Wei et al.
2010), superimposed moving mesh (Wang and Wang
2006b) or an adaptive moving mesh (Liu and Korvink
2008).
This paper presents a new approach for handling multiple constraints in the conventional level-set topology optimization method. The key features of the new method are discretized boundary integrals to estimate function changes and the formulation of an optimization sub-problem to attain the velocity function. This approach does not require penalty parameters to handle constraints and has the additional benefit of being able to simultaneously optimize non-level-set design variables. The simultaneous optimization of the level-set implicit function and additional design variables has received little attention in the literature. However, level-set methods that use a parameterization that allows the use of mathematical programming could potentially be extended to include other design variables (Luo et al.
2007; van Dijk et al.
2012), although this is not discussed by the authors.
The paper is organized as follows: first we review the conventional level-set method, then an approach is developed where the velocity function sub-problem is formulated as a linear program (LP), called the LP level-set method. This is further developed where the sub-problem is solved using Sequential LP, called the SLP level-set method. This is followed by numerical implementation details and a range of numerical examples is used to demonstrate the new method.
2 Level-set based optimization
This section reviews the conventional level-set method for optimization. First, the boundary of the structure is defined as the zero level set of an implicit function:
$$ \left\{\begin{array}{c}\hfill \phi (x)\ge 0,x\in \varOmega \hfill \\ {}\hfill \phi (x)=0,x\in \varGamma \hfill \\ {}\hfill \phi (x)<0,x\notin \varOmega \hfill \end{array}\right. $$
(1)
where Ω is the domain for the structure, Γ is the boundary of the structure,
ϕ(
x) is the implicit function and
x ∈ Ω
d
, where Ω
d
is the design domain containing the structure, Ω ⊂ Ω
d
. This implicit description allows the boundary to break and merge naturally, allowing topological changes to occur during optimization. In the conventional approach, the implicit function is initialized as a signed distance function, where the magnitude is the distance to the boundary and the sign is defined by (
1). The signed distance property promotes stability in the level-set method and it is desirable to maintain this property throughout the optimization (Allaire et al.
2004; Yulin and Xiaoming
2004).
The position, shape and topology of the structure boundary is optimized by iteratively solving the following advection equation:
$$ \frac{\partial \phi (x)}{\partial t}+\nabla \phi \left(x,t\right)\frac{dx}{dt}=0 $$
(2)
where
t is a fictitious time domain. The advection equation (
2) becomes a Hamilton-Jacobi type equation by considering advection velocities of the type:
dx /
dt =
V ⋅ ∇
ϕ (
x) (Sethian
1999; Osher and Fedkiw
2003). The equation is then discretized and solved using an explicit forward Euler scheme, producing the following update rule for the discrete implicit function values:
$$ {\phi}_i^{k+1}={\phi}_i^k-\Delta t\left|\nabla {\phi}_i^k\right|{V}_i $$
(3)
where
k is the iteration number,
i is a discrete point in the design domain, Δ
t is the time step and
V
i
is the velocity value at the point
i. In the conventional approach to level-set based optimization, the velocity function is obtained from a shape derivative.
There are two common methods for obtaining the velocity values at the discrete points. If the design is analysed using the ersatz material method, where weak material is used to model the void, then derivative and velocity values can be computed directly at all points in the domain. This is known as the natural velocity extension method (Osher and Santosa
2001; van Dijk et al.
2013). The disadvantage of this method is that the implicit function requires frequent re-initialization to maintain the signed distance property of the implicit function, which is important for the stability of the conventional level-set method. The second approach is to compute sensitivity and velocity values only at the structural boundary and then extend velocities to discrete points in such a way that the signed distance function is preserved after solving (
2) (Liu and Korvink
2008; Dunning et al.
2011). The second velocity extension approach is used during the development of the SLP level-set method, which is introduced in the next section.