Adaptive solution of truss layout optimization problems with global stability constraints

Optimization of the layout of truss structures is a class of problem that has been studied for many decades, starting with the seminal paper of Michell (1904). When solved computationally, truss layout optimization problems are usually formulated based on the ground structure approach (Dorn et al. 1964), in which a set of nodes are distributed across the design space, then interlinked by potential connecting bars. The main design (as forces are also design variables) in most cases are the cross-sectional areas of these bars, but may also include the coordinates of the nodes when geometry optimization is used (Svanberg 1981).

The most common objectives of the optimization are to minimize the volume of the truss or to minimize its compliance, for which several formulations exist, ranging from linear programming, for example for the plastic design formulation, to nonlinear programming when kinematic compatibility constraints are involved (Hemp 1973; Achtziger et al. 1992; Ben-Tal and Bendsøe 1993; Bendsøe and Sigmund 2003; Stolpe and Svanberg 2004; Rozvany et al. 2014).

Even though the solutions obtained using the aforementioned classical formulations can give useful insights into potential layouts of truss bars in a structure for use in the early stage of the design process, the designs generated may fail to satisfy many practical requirements, and therefore may require extensive modification in the later stages of the design process. Hence, in order to improve the practicality of the designs generated by layout optimization, researchers have sought to introduce many practical engineering issues in the formulation, such as constraints on stresses (Kirsch 1990; Guo et al. 2001; Stolpe and Svanberg 2001, 2003), constraints on local buckling based on the Euler formula involving continuous (Zhou 1996; Achtziger 1999; Rozvany 1996; Guo et al. 2001, 2005) or discrete (Mela 2014) variables, addressing global stability (Khot et al. 1976; Szyszkwoski et al. 1989), and in particular, via the use of nominal forces (Tyas et al. 2006; Descamps and Coelho 2014) or via introduction of global stability constraints (Ben-Tal et al. 2000; Levy et al. 2004; Stingl 2006; Evgrafov 2005; Tugilimana et al. 2018), to mention a few. In recent years, several articles have considered optimization of beam/frame structures with buckling constraints (Torii et al. 2015; Madah and Amir 2017; Mitjana et al. 2019).

The aforementioned contributions which include Euler buckling constraints are intended to avoid slender bars in compression being included in the solution while including nominal forces are designed to ensure nodes connecting bars in compression are adequately braced. Formulations which directly include global stability constraints are concerned with ensuring the stability of the whole structure. This is of interest because, even if a structure is well-braced, it may fail as a result of insufficient overall elastic stiffness. Note that global stability problem formulations implicitly address the nodal instability problem, though do not take into account local instabilities of the sort dealt with by the Euler formula (e.g. Levy et al. 2004).

The focus of this paper is on problems with global stability constraints. These problems are in general formulated as nonlinear and nonconvex semidefinite programs (Ben-Tal et al. 2000; Levy et al. 2004; Stingl 2006; Evgrafov 2005). Such problems are computationally challenging and for large-scale structures are usually considered numerically intractable, though software capable of solving small problems is available (Fiala et al. 2013; Kočvara and Stingl 2003). For this reason, some studies formulate the nonlinear semidefinite programming problem as an equivalent nonlinear programming problem (Tugilimana et al. 2018). Nevertheless, in all approaches, the size of problems that have been solved thus far in the literature has either been small or otherwise limited, e.g. by only specifying minimum connectivity between the nodes in the design space. This is in stark contrast to the plastic design formulation, solvable via linear programming, when full nodal connectivity problems can be solved even for high nodal densities.

In this article, we propose a relaxation of the nonlinear and nonconvex semidefinite programming formulation, for which we develop an efficient optimization algorithm based on interior point methods. The method is coupled with other novel techniques to make it capable of solving large-scale problems and with full nodal connectivity. The relaxed problem is still a semidefinite program but ignores the kinematic compatibility constraints present in standard elastic formulations. We observe huge computational gains by solving the relaxed formulation and provide lower bounds for the associated general nonlinear problems. Moreover, we report an estimation of the violation of the removed kinematics compatibility equations by solving an associated least-squares problem. For some small-scale benchmark problems, we additionally make comparisons between solutions of the relaxed and original nonlinear problems. In general, the error due to ignoring the kinematic compatibility equations are observed to be very small for reasonable values of the stability load factor, suggesting that solutions to the relaxed problems are acceptable. However, as we increase the value of the stability load factor beyond practically realistic values, we observe a high degree of violation in the compatibility equations and significant differences in the optimal designs. For some of the examples presented in this article, we also calculate the violation of the elastic stress constraints for the solution of the relaxed semidefinite program. The numerical results once again confirm the usefulness of the solutions obtained, when stability load factors of practical interest are used. Next, we describe the techniques that contribute to the efficiency of the proposed solution algorithm.

Firstly, we employ the adaptive ‘member adding’ approach, previously used to solve plastic truss layout optimization problems (Gilbert and Tyas 2003; Sokół and Rozvany 2013; Weldeyesus and Gondzio 2018) via linear programming, though now solving the problems of interest here via semidefinite programming. It is a procedure in which we approximate the large-scale original problem by a sequence of smaller subproblems, the solutions of which ultimately converge to that of the original problem. In the context of truss optimization, this is done by first solving the problem with minimum nodal connectivity, followed by generating and adding more members/bars based on degree of violation of constraints in the dual problem. The procedure continues until the solution to the original problems is obtained. This procedure greatly reduces the memory required to solve a given problem and, even using a standard desktop computer, we have managed to solve problems that otherwise would require hundreds of GB memory. Detailed statistics are presented in Section 6; see in particular the large-scale bridge example problem described in Section 6.3.1.

Secondly, similar to Ben-Tal and Nemirovski (1997), we explicitly utilize the structures of the problems, i.e. the high degree of sparsity and low-rank property of the element stiffness matrices (Bendsøe et al. 1994; Ben-Tal 1993b; Achtziger et al. 1992; Bendsøe and Sigmund 2003), to address the computational bottle-neck associated with using the interior point method to solve semidefinite programming problems. This determines the coefficient matrix of the linear system originating in the algorithm. Roughly speaking, instead of performing \(\mathcal {O}(mn^{3}+m^{2}n^{2})\) arithmetic operations (Fujisawa et al. 2000), by using standard and straightforward expressions to determine the matrices involved in the linear systems, we perform \(\mathcal {O}(m^{2}n)\) arithmetic operations, where m is the number of bars and n is number of nodal degrees of freedom. Note that the sparsity of the element matrices is also effectively used in performing matrix inner products in the adaptive member adding procedure, as described in Remark 6.

Finally, as when solving the plastic truss layout optimization using the interior point method (Weldeyesus and Gondzio 2018), we apply a warm-start strategy to solve some of the subsequent problems, determining an initial point that reduces the number of interior point iterations and overall improves the convergence characteristics of the optimization process. The technique relies on an observation that the number of newly added bars decreases towards the end of the adaptive member adding procedure and therefore the degree of similarity between successive subproblems increases at this stage.

The paper is organized as follows. In Section 2, we present the general nonlinear and nonconvex semidefinite programming model of the truss layout optimization problem with global stability constraints, its relaxation, and the least-squares problem used to estimate violation of the kinematic compatibility constraints. We describe the general framework of the primal-dual interior point method and exploitation of the structure of the matrices in Section 3 and the adaptive member adding procedure in Section 4. The warm-start strategy and related mathematical analysis are presented in Section 5 and numerical experiments are described in Section 6. Finally, conclusions and possible future research directions are presented in Section 7.

In this section, we describe the formulation for the layout optimization of trusses with global stability constraints problem. We use the ‘ground structure’ approach (Dorn et al. 1964) to formulate all problems. This is done by distributing a finite set of nodes, say d, across the design space and connecting these nodes by all possible potential bars, including overlapping ones. Hence, we have m = d(d − 1)/2 bars, where clearly m ≫ d. We denote the cross-sectional areas of the bars by a_i, i = 1,...,m. Let \(f_{\ell }\in \mathbb {R}^{n},\ell =1,\dots ,n_{L} \) be a set of external forces applied to the structure where n (≈ Nd, N is the dimension of the design space, i.e. 2 or 3) is the number of the non-fixed degrees of freedom. Then, the associated (nodal) displacements \(u_{\ell }\in \mathbb {R}^{n}\), ℓ = 1,…,n_L satisfy the elastic stiffness equation

where the stiffness matrix K(a) is computed as

and the element stiffness matrices K_i’s are given by

with \({\gamma }_{i} \in \mathbb {R}^{n}\) being the vector of direction cosines for the i th bar.

Introducing the axial forces q_ℓ in member i which are given by

allows us to rewrite (1) as

where \(B=(\gamma _{1},\cdots ,\gamma _{m})\in \mathbb {R}^{n\times m}\).

Next, we define the geometric stiffness matrix G(q_ℓ) as given by

where

in which the vectors δ_i,η_i are determined so that γ_i, δ_i, η_i are mutually orthogonal (see Kočvara (2002) for details). The vectors δ_i and η_i are not necessarily unique. These are chosen in Kočvara (2002) as the orthogonal basis of the null space of \({\gamma _{i}^{T}}\) and we follow similar approach in our implementation.

Now, the multiple load case minimum weight (or, strictly speaking, minimum volume) truss layout optimization problem with global stability constraints can be formulated as

where \(l\in \mathbb {R}^{m}\) is a vector of lengths of the bars, and σ⁺ > 0 and σ⁻ > 0 are the material yield stresses in tension and compression, respectively. Note that we can find a similar formulation to problem (8) in Tugilimana et al. (2018) with additional constraints enforcing local (Euler) buckling. The parameter τ_ℓ can be interpreted as a stability load factor and must be set to \( \bar {\tau }_{\ell }\geq 1, \forall \ell \) to indicate that the resulting optimal structure is stable for the loads f_ℓ,ℓ ∈{1,…,n_L}.

It is worth mentioning that problem formulation (8) does not address local buckling, as addressed, e.g. by the Euler buckling equation. Therefore, we can expect that the optimal design obtained by solving problem (8) could potentially include slender bars (Levy et al. 2004).

Due to the inclusion of the nonlinear kinematic compatibility equations (4), problem (8) is a nonlinear and nonconvex semidefinite programming problem. Such problems are in general very difficult to solve. In Fiala et al. (2013) and Stingl (2006), methods for treating nonlinear semidefinite programming problems are described in which a variant of formulation (8) is solved. These formulations are very attractive, but the challenge of solving large-scale problems still remains. In Tugilimana et al. (2018), problem (8) is transformed from a semidefinite programming problem to a standard nonlinear programming problem.

In this paper, we relax problem (8) by ignoring the kinematic compatibility constraint (4), and solve a semidefinite programming problem of very large dimension because we allow full nodal connectivity. Namely, we consider

which is a (linear) semidefinite program and can be interpreted as the plastic design formulation with global stability constraints. In our numerical experiments described in Section 6, we additionally report the maximum violation of the kinematic compatibility constraints for the optimal designs obtained by solving the relaxed problem (9). This violation is estimated by solving the least-squares problem

where a^∗ and \(q^{*}_{\ell }\) are the solutions of the relaxed problem (9).

Note that the special case τ_ℓ = 0,∀ℓ, or in other words, excluding the matrix inequality constraints, reduces problem (9) to the plastic layout optimization problem, which is a linear program that can be solved efficiently by an interior point method (Weldeyesus and Gondzio 2018).

We adopt the Mehrotra-type primal-dual predictor-corrector interior point method (Fujisawa et al. 2000) for semidefinite programming.

Introducing the slack variables \(s^{-}_{\ell }\), \(s^{+}_{\ell }\in \mathbb {R}_{+}^{m}\), and \(S_{\ell }\in \mathbb {S}_{+}^{n}\), we rewrite (8) as

and write down the following dual:

where \(\lambda _{\ell }\in \mathbb {R}^{n}\) denotes the virtual nodal displacement, \(x^{+}_{\ell }\), \(x^{+}_{\ell }\in \mathbb {R}^{m}, \ell =1,\dots ,n_{L}\), \(x_{a}\in \mathbb {R}^{m}\), \(X_{\ell }\in \mathbb {S}_{+}^{n}\), and the notation \(U\bullet V={\sum }_{i}{\sum }_{j}U_{ij}V_{ij}\) for \(U,V\in \mathbb {R}^{n\times n}\).

where the notation u ⋅ v, for any \(v,u\in \mathbb {R}^{m}\) is a component-wise multiplication and e = (1,...,1) of appropriate size. We denote by \(\xi _{d} = (\xi _{d_{1}}\), \(\xi _{d_{2,\ell }})\) the negative of the dual infeasibilities (13a)–(13b), by \(\xi _{p} = (\xi _{p_{1,\ell }}\), \( \xi _{p_{2,\ell }},\xi _{p_{3,\ell }},\xi _{p_{4,\ell }})\) the negative of the primal infeasibilities (13c)–(13f), and by \(\xi _{c} = (\xi _{c_{1,\ell }}\), \( \xi _{c_{2,\ell }},\xi _{c_{3}},\xi _{c_{4,\ell }})\) the negative of the violation complementarity equations (13g)–(13j). Note that a direction obtained with the scaling corresponding to the last complementarity equation (13j) is called the HRVW/KSH/M direction (Helmberg et al. 1996; Kojima et al. 1997; Monteiro 1997).

Now, we solve system (3) for a sequence of μ_k → 0 to find the solution of the primal and dual problems (9) and (12). This is done by applying Newton’s method to the optimality conditions (3) and solving the (reduced) linear system.

where (borrowing MATLAB notation) \( \tilde {B}\! = \text {blkdiag}(B,\!...,B)\), \( \tilde {A}_{22}=\text {blkdiag}(A_{11},...,A_{\ell \ell })\), and \(\tilde {A}_{12}=(A_{11},...,A_{1\ell })^{T}\) with

and D_kl are diagonal matrices. The vector (ξ₁,ξ₂,ξ₃)^T is the resulting right-hand side. For a complete description of the interior point method, we refer the reader to Fujisawa et al. (2000). The rest of this section is dedicated to the computational difficulties associated with the interior point method for semidefinite programming and the techniques we use to resolve these.

There are several computational challenges associated with the linear system (14). Firstly, all block matrices A_kl,k,l = 1,...,n_L are dense and require a large amount of memory to store them (see Fig. 1a for the sparsity structure of the coefficient matrix for a two-load case problem). Secondly, the straightforward computation of the coefficient matrix requires \(\mathcal {O}(mn^{3}+m^{2}n^{2})\) operations (Fujisawa et al. 2000).

The second challenge can be easily resolved by exploiting the low-rank property and sparsity of the data matrices K_i,G_i,i = 1,...,m (Ben-Tal and Nemirovski 1997; Bendsøe et al. 1994; Ben-Tal 1993b; Achtziger et al. 1992; Bendsøe and Sigmund 2003). From (3) and (7), it can be seen that the rank of the element stiffness matrices K_i,i = 1,...,m is always 1 and the rank of the element geometric stiffness matrices G_i,i = 1,...,m is 1 for two-dimensional problems and 2 for three-dimensional problems. The direction cosine vectors γ_i, δ_i, and η_i are all very sparse with at most 4 or 6 nonzero entries for two- and three-dimensional problems, respectively. Therefore, we utilize this property to compute the coefficient matrix efficiently. For example, consider the block matrix A₁₁ (single-load case for notation simplicity). We have

which can be computed in \(\mathcal {O}(n)\) arithmetic operations and hence the computation of the coefficient matrix can be brought down to \(\mathcal {O}(m^{2}n)\).

In the next section, we discuss the novel approach employed to deal with the first challenge, i.e. the large memory requirements.

In problem formulation (9) we consider fully connected ground structures. Hence, for a N-dimensional problem comprising d nodes, the coefficient matrix (KKT) of the reduced Newton system (14) has dimension where m = d(d − 1)/2 and n ≈ Nd. Moreover, all of the larger blocks of the coefficient matrix, each with dimension m × m, are full matrices. This indicates that it would be computationally prohibitive to store or factorize the matrix (see also the large-scale bridge example problem described in Section 6.3.1).

In order to overcome this we extend the adaptive ‘member adding’ approach initially proposed for linear plastic truss layout optimization problems by Gilbert and Tyas (2003) and later used in other studies, for example by Sokół and Rozvany (2013) and Weldeyesus and Gondzio (2018). It is a strategy whereby the original large problem is solved by successively solving a number of smaller subproblems, i.e. problem instances with fewer bars, say \(\bar {m}\). In practice, \(\bar {m}\ll m\), hence each of the m × m dense blocks in the KKT matrix in (14) reduces to smaller \(\bar {m}\times \bar {m}\) blocks. Moreover, as the problem size increases (i.e. when higher nodal densities are used), the fraction of the bars \(\bar {m}/m\) used in the SDPs corresponding to the final member adding iterations decreases (see Remark 10 in Section 6.2). An overview of the member adding strategy, which can only be applied to the relaxed linear SDP (9), is provided below.

First, we start with a structure constituting minimum connectivity, for example with the structure shown in Fig. 2a for two-dimensional problems and Fig. 2b for three-dimensional problems, and let m₀ be the number of bars in the the initial structure. We denote by K₀ ⊂{1,…,m} the set of indices of the bars for which the primal problem (11) and its dual (12) are currently solved. Next, we compute the dual violations using only variables λ_ℓ and X_ℓ in (12) which are described below.

For any member i to be dual feasible (see (12)), we need

Now, since \(x^{+}_{\ell }\geq 0\) and \(x^{-}_{\ell }\geq 0\), from (17a), we have

and from (17b), we have

Combining (18) and (19), we get

for a member i to be dual feasible. Any member that violates (20) is said to be dual infeasible.

Now, solving the problem for members with indices in K₀, we use (20) to generate the set K as

where

with \(\lambda _{\ell }^{*}\) and \(X_{\ell }^{*}\) being optimal values, and β > 0 some prescribed tolerance. Then, we identify the bars with indices in K, filter them, and then finally add then to form the next problem. The purpose of the filtering is to limit the number of bars to be added in order to prevent fast growth of the size of the problem (for details of heuristic filtering approaches, see Weldeyesus and Gondzio 2018). Note that use of a different filtering approach may affect the size of each problem to be solved as part of the adaptive member adding process, and the number of iterations required, but not the final solution. For the numerical experiments in Section 6, we use the member bar length approach described as filtering strategy AP3 in Weldeyesus and Gondzio (2018). The member adding procedure terminates when K = ∅.

After performing several member adding iterations, the subsequent subproblems start to become more and more similar. Therefore, we use a warm-start strategy and determine an initial point that can reduce the number of interior point iterations required to obtain a solution. This has been used for the basic truss layout optimization problem formulated as a linear program in Weldeyesus and Gondzio (2018) and is now applied to the semidefinite programming formulations presented in this paper. The discussion in this section and the mathematical analysis closely follow Section 6 of Weldeyesus and Gondzio (2018).

As described in Section 4, we generate the set K in (21) at every member adding iteration. If K≠∅, then we form the new problem in which the variables are

where the vectors with the super-bar, all in \(\mathbb {R}^{k}\), k = |K|, represent the new variables corresponding to the newly added bars. We assume that the old solution (the left-hand side in (22)) was feasible in the previous instance of the adaptive member adding scheme.

The interior point method has been implemented in MATLAB (R2016a). All numerical experiments have been performed using a PC equipped with an IntelⓇ Core™i5-4590T CPU running at 2.00 GHz with 16 GB RAM. For the case of the cold-start runs, the initial points a⁰, \(s_{\ell }^{+0}\), \(s_{\ell }^{-0}\), \(x_{\ell }^{+0},x_{\ell }^{-0}\), \(x_{a}^{+}\) are set to unity, S_ℓ, X_ℓ to the identity matrix I, and \(q_{\ell }^{0}\), \(\lambda _{\ell }^{0}\) to zero. The interior point algorithm terminates when

where \(\tilde {f}=(f_{1},...,f_{n_{L}})^{T}\), matrix terms are vectorized, and the primal and dual residuals ξ_p and ξ_d are given by (3). Note that, for feasible primal and dual points, the duality gap can easily be written as by performing some elementary algebraic operations.

The primal and dual relative feasibility tolerances are set to 𝜖_p = 𝜖_d = 10^− 6.

For the optimality tolerance, we use loose tolerances in the first few member adding iterations since the first few subproblems should not have to be solved to optimality, and then tighter tolerances in the final iterations, i.e. 𝜖_opt = [10^− 2, 10^− 2, 10^− 3, 10^− 4] and then always 10^− 5. The reported CPU times correspond to the entire solution process, including the member adding computations.

In the original problems, we consider all the potential bars, including overlapping bars. At the start of the solution process, we begin with the structure shown in Fig. 2a for two-dimensional problems and Fig. 2b for three-dimensional problems, and use β = 0.001 to generate the set of members in K given in (21) that are dual infeasible. If the warm-start strategy is used, then it is activated at the fourth member adding iteration or else before this if (m_k − m_k− 1)/m_k ≤ 0.12, where m_k is the number of bars used in the k th member adding iteration. In applying this strategy, we use the solutions obtained with tolerance ε_opt = 0.1 in the preceding problem instance to determine the initial point of the subsequent problem.

For all examples, λ_min denotes the smallest positive eigenvalue of the generalized eigenvalue problem

Moreover, we set τ_ℓ = 0 in (8) and (9) for problems without stability constraints and τ_ℓ ≥ 1 for problems with stability constraints. Its specific values are mentioned in the examples below. Additionally, when reporting the solution of the SDP relaxation (9), we also provide an estimate of the violation of the compatibility equations by solving the least-squares problem (10).

Finally, we use Young’s modulus E = 210 GPa, and equal tensile and compressive strengths of 350 MPa. In the plots of the optimal designs, bars in tension are shown in red and bars in compression are shown in blue (except for sake of clarity in the case of Fig. 13). In all cases, the bars shown are those with cross-sectional area ≥ 0.001a_max and the dark dots are the active nodes connecting these bars.

We have solved the truss layout optimization problem with global stability constraints via linear semidefinite programming by relaxing the nonlinear kinematic compatibility constraint. A primal-dual interior point method has been used, tailored to solving these problems efficiently. The implementation utilizes the sparse structure and low-rank property of the element stiffness matrices to reduce computational complexity when determining the linear systems arising in the algorithm. Moreover, we have extended the range of application of the adaptive member adding and warm-start techniques previously applied to truss layout optimization problems formulated as linear programs, so these can now be applied to problems modelled as semidefinite programs. By doing so, we have been able to find solutions to large-scale problems that could not have been solved using previously available methods and standard desktop computers.

We have demonstrated the validity of the solutions obtained for the relaxed problem by comparing them with solutions obtained for the original nonlinear problem for values of the stability load factor that are of interest to engineering practitioners.

Finally, direct methods were used to solve the linear systems arising from the interior point algorithm. The computational effort might be further reduced by use of iterative methods.

The input and output data that are used for all of the examples described in Section 6 are explicitly provided there. The same material has been used in all examples and the material properties are reported directly before Section 6.1. Note that these values and the applied loads require appropriate scaling if one wishes to use standard SDP solvers.