SpringerLink
Log in

Alternating direction method of multipliers for truss topology optimization with limited number of nodes: a cardinality-constrained second-order cone programming approach

  • Published:
Optimization and Engineering Aims and scope Submit manuscript

Abstract

This paper addresses the compliance minimization of a truss, where the number of available nodes is limited. It is shown that this optimization problem can be recast as a second-order cone programming with a cardinality constraint. We propose a simple heuristic based on the alternative direction method of multipliers. The efficiency of the proposed method is compared with a global optimization approach based on mixed-integer second-order cone programming. Numerical experiments demonstrate that the proposed method often finds a solution having a good objective value with small computational cost.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

Notes

  1. See, for example, Fig. 6 in Sect. 6.

  2. Although this number is not a norm, it is common to call it the \(\ell _{0}\)-norm (Bruckstein et al. 2009; Burdakov et al. 2016; Candès et al. 2008; Chartrand 2007; Gotoh et al. 2018; Le Thi et al. 2015; Zheng et al. 2014).

  3. It can also be rewritten as

    $$\begin{aligned} t + 1 \ge \left\|\left[\begin{array}{c} t - 1 \\ 2(Z \varvec{x} - \varvec{z}^{k} + \varvec{v}^{k}) \\ \end{array} \right]\right\| , \end{aligned}$$

    which is a second-order cone constraint.

  4. Since G is nonconvex, the projection of a point onto G is not necessarily unique.

  5. Such non-redundancy of overlap** members is also known for truss topology optimization considering, e.g., the self-weight load (Bendsøe et al. 1994; Kanno and Yamada 2017) and the member buckling constraints (Mela 2014; Guo et al. 2005).

  6. Through our preliminary numerical experiments it was found that the computational cost required by MOSEK does not change drastically depending on the value of M.

  7. To obtain these solutions, we used the ground structures without overlap** members.

  8. It should be clear that no initial point was assigned for the MISOCP approach, although in Table 2, for convenience of presentation, the results of MISOCP are placed in the rows concerning the results of the ADMM with initial point (A).

References

  • Anjos MF, Lasserre JB (eds) (2012) Handbook on semidefinite, conic and polynomial optimization. Springer, New York

    MATH  Google Scholar 

  • Achtziger W (1999) Local stability of trusses in the context of topology optimization part I: exact modelling. Struct Optim 17:235–246

    Google Scholar 

  • Andersen ED, Roos C, Terlaky T (2003) On implementing a primal-dual interior-point method for conic quadratic optimization. Math Program 95:249–277

    Article  MathSciNet  MATH  Google Scholar 

  • Arastoo R, Bahavarnia M, Kothare MV, Motee N (2015) Output feedback controller sparsification via \(\cal{H}_{2}\)-approximation. IFAC-PapersOnLine 48:112–117

    Article  Google Scholar 

  • Asadpoure A, Guest JK, Valdevit L (2015) Incorporating fabrication cost into topology optimization of discrete structures and lattices. Struct Multidiscip Optim 51:385–396

    Article  Google Scholar 

  • Bendsøe MP, Ben-Tal A, Zowe J (1994) Optimization methods for truss geometry and topology design. Struct Optim 7:141–159

    Article  Google Scholar 

  • Ben-Tal A, Nemirovski A (1997) Robust truss topology optimization via semidefinite programming. SIAM J Optim 7:991–1016

    Article  MathSciNet  MATH  Google Scholar 

  • Ben-Tal A, Nemirovski A (2001) Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, Philadelphia

    Book  MATH  Google Scholar 

  • Bertsimas D, Shioda R (2009) Algorithm for cardinality-constrained quadratic optimization. Comput Optim Appl 43:1–22

    Article  MathSciNet  MATH  Google Scholar 

  • Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2010) Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn 3:1–122

    Article  MATH  Google Scholar 

  • Bruckstein AM, Donoho DL, Elad M (2009) From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev 51:34–81

    Article  MathSciNet  MATH  Google Scholar 

  • Burdakov OP, Kanzow C, Schwartz A (2016) Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method. SIAM J Optim 26:397–425

    Article  MathSciNet  MATH  Google Scholar 

  • Candès EJ, Wakin MB, Boyd SP (2008) Enhancing sparsity by reweighted \(\ell _{1}\) minimization. J Fourier Anal Appl 14:877–905

    Article  MathSciNet  MATH  Google Scholar 

  • Chartrand R (2007) Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Process Lett 14:707–710

    Article  Google Scholar 

  • Chartrand R (2012) Nonconvex splitting for regularized low-rank \(+\) sparse decomposition. IEEE Trans Signal Process 60:5810–5819

    Article  MathSciNet  Google Scholar 

  • Chartrand R, Wohlberg B (2013) A nonconvex ADMM algorithm for group sparsity with sparse groups. In: 2013 IEEE international conference on acoustics, speech and signal processing, Vancouver, pp 6009–6013 (2013)

  • Cui XT, Zheng XJ, Zhu SS, Sun XL (2013) Convex relaxations and MIQCQP reformulations for a class of cardinality-constrained portfolio selection problems. J Glob Optim 56:1409–1423

    Article  MathSciNet  MATH  Google Scholar 

  • Diamond S, Takapoui R, Boyd S (2018) A general system for heuristic minimization of convex functions over non-convex sets. Optim Methods Softw 33:165–193

    Article  MathSciNet  MATH  Google Scholar 

  • Gotoh J, Takeda A, Tono K (2018) DC formulations and algorithms for sparse optimization problems. Math. Program., to appear. https://doi.org/10.1007/s10107-017-1181-0

  • Grant M, Boyd S (2008) Graph implementations for nonsmooth convex programs. In: Blondel V, Boyd S, Kimura H (eds) Recent advances in learning and control (a tribute to M. Vidyasagar). Springer, Berlin, pp 95–110

    Chapter  Google Scholar 

  • Grant M, Boyd S (2017) CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx/. Accessed Jan 2017

  • Guo X, Cheng GD, Olhoff N (2005) Optimum design of truss topology under buckling constraints. Struct Multidiscip Optim 30:169–180

    Article  Google Scholar 

  • Gurobi Optimization, Inc.: Gurobi optimizer reference manual. http://www.gurobi.com/. Accessed Sept 2016

  • He L, Gilbert M (2015) Rationalization of trusses generated via layout optimization. Struct Multidiscip Optim 52:677–694

    Article  MathSciNet  Google Scholar 

  • Hegemier GA, Prager W (1969) On Michell trusses. Int J Mech Sci 11:209–215

    Article  MATH  Google Scholar 

  • Kanamori T, Takeda A (2014) Numerical study of learning algorithms on Stiefel manifold. CMS 11:319–340

    Article  MathSciNet  MATH  Google Scholar 

  • Kanno Y (2013) Damper placement optimization in a shear building model with discrete design variables: a mixed-integer second-order cone programming approach. Earthq Eng Struct Dyn 42:1657–1676

    Article  Google Scholar 

  • Kanno Y (2016a) Global optimization of trusses with constraints on number of different cross-sections: a mixed-integer second-order cone programming approach. Comput Optim Appl 63:203–236

    Article  MathSciNet  MATH  Google Scholar 

  • Kanno Y (2016b) Mixed-integer second-order cone programming for global optimization of compliance of frame structure with discrete design variables. Struct Multidiscip Optim 54:301–316

    Article  MathSciNet  Google Scholar 

  • Kanno Y, Yamada H (2017) A note on truss topology optimization under self-weight load: mixed-integer second-order cone programming approach. Struct Multidiscip Optim 56:221–226

    Article  MathSciNet  Google Scholar 

  • Kirsch U (1989) Optimal topologies of structures. Appl Mech Rev 42:223–239

    Article  MATH  Google Scholar 

  • Kočvara M (2017) Truss topology design by linear conic optimization. In: Terlaky T, Anjos MF, Ahmed S (eds) Advances and trends in optimization with engineering applications. SIAM, Philadelphia

    Google Scholar 

  • Le Thi HA, Dinh TP, Le HM, Vo XT (2015) DC approximation approaches for sparse optimization. Eur J Oper Res 244:26–46

    Article  MathSciNet  MATH  Google Scholar 

  • Lin F, Fardad M, Jovanović MR (2013) Design of optimal sparse feedback gains via the alternating direction method of multipliers. IEEE Trans Autom Control 58:2426–2431

    Article  MathSciNet  MATH  Google Scholar 

  • Löfberg J (2004) YALMIP: a toolbox for modeling and optimization in MATLAB. In: 2004 IEEE international conference on computer aided control system design, Taipei, pp 284–289 (2004)

  • Magnússon S, Rabbat MG, Fischione C (2016) On the convergence of alternating direction Lagrangian methods for nonconvex structured optimization problems. IEEE Trans Control Netw Syst 3:296–309

    Article  MathSciNet  MATH  Google Scholar 

  • Masazade E, Fardad M, Varshney PK (2012) Sparsity-promoting extended Kalman filtering for target tracking in wireless sensor networks. IEEE Signal Process Lett 19:845–848

    Article  Google Scholar 

  • Mazurek A (2012) Geometrical aspects of optimum truss like structures for three-force problem. Struct Multidiscip Optim 45:21–32

    Article  MathSciNet  MATH  Google Scholar 

  • Mazurek A, Baker WF, Tort C (2011) Geometrical aspects of optimum truss like structures. Struct Multidiscip Optim 43:231–242

    Article  Google Scholar 

  • Mela K (2014) Resolving issues with member buckling in truss topology optimization using a mixed variable approach. Struct Multidiscip Optim 50:1037–1049

    Article  MathSciNet  Google Scholar 

  • Michell AGA (1904) The limits of economy of material in frame-structures. Lond Edinb Dublin Philos Mag J Sci 8:589–597

    Article  MATH  Google Scholar 

  • Miyashiro R, Takano Y (2015) Mixed integer second-order cone programming formulations for variable selection in linear regression. Eur J Oper Res 247:721–731

    Article  MathSciNet  MATH  Google Scholar 

  • Natarajan BK (1995) Sparse approximate solutions to linear systems. SIAM J Comput 24:227–234

    Article  MathSciNet  MATH  Google Scholar 

  • Ohsaki M (2011) Optimization of finite dimensional structures. CRC Press, Boca Raton

    MATH  Google Scholar 

  • Ohsaki M, Kanno Y, Tsuda S (2014) Linear programming approach to design of spatial link mechanism with partially rigid joints. Struct Multidiscip Optim 50:945–956

    Article  MathSciNet  Google Scholar 

  • Parkes EW (1975) Joints in optimum frameworks. Int J Solids Struct 11:1017–1022

    Article  MATH  Google Scholar 

  • Pólik I (2005) Addendum to the SeDuMi user guide: version 1.1. Technical Report, Advanced Optimization Laboratory, McMaster University, Hamilton (2005). http://sedumi.ie.lehigh.edu/

  • Prager W (1977) Optimal layout of cantilever trusses. J Optim Theory Appl 23:111–117

    Article  MathSciNet  MATH  Google Scholar 

  • Prager W (1978) Optimal layout of trusses with finite numbers of joints. J Mech Phys Solids 26:241–250

    Article  Google Scholar 

  • Rozvany GIN (1996) Difficulties in truss topology optimization with stress, local buckling and system stability constraints. Struct Optim 11:213–217

    Article  Google Scholar 

  • Sagnol G (2012) PICOS: a python interface for conic optimization solvers. http://picos.zib.de/. Accessed Feb 2017

  • Sturm JF (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim Methods Softw 11(12):625–653

    Article  MathSciNet  MATH  Google Scholar 

  • Takapoui R, Moehle N, Boyd S, Bemporad A (2018) A simple effective heuristic for embedded mixed-integer quadratic programming. Int J Control, to appear. https://doi.org/10.1080/00207179.2017.1316016

  • Top** BHV (1983) Shape optimization of skeletal structures: a review. J Struct Eng 109:1933–1951

    Article  Google Scholar 

  • Torii AJ, Lopez RH, Miguel LFF (2016) Design complexity control in truss optimization. Struct Multidiscip Optim 54:289–299

    Article  MathSciNet  Google Scholar 

  • Tütüncü RH, Toh KC, Todd MJ (2003) Solving semidefinite-quadratic-linear programs using SDPT3. Math Program B95:189–217

    Article  MathSciNet  MATH  Google Scholar 

  • Zheng X, Sun X, Li D, Sun J (2014) Successive convex approximations to cardinality-constrained convex programs: a piecewise-linear DC approach. Comput Optim Appl 59:379–397

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors thank the referees and the editors for providing us with the detailed comments and suggestions, which were helpful in revision. The work of the first author is partially supported by JSPS KAKENHI 15KT0109 and 17K06633.

Author information

Authors and Affiliations

  1. Mathematics and Informatics Center, The University of Tokyo, Hongo 7-3-1, Tokyo, 113-8656, Japan

    Yoshihiro Kanno

  2. Laboratory for Future Interdisciplinary Research of Science and Technology, Institute of Innovative Research, Tokyo Institute of Technology, Nagatsuta 4259, Yokohama, 226-8503, Japan

    Shinnosuke Fujita

Authors
  1. Yoshihiro Kanno
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shinnosuke Fujita
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yoshihiro Kanno.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kanno, Y., Fujita, S. Alternating direction method of multipliers for truss topology optimization with limited number of nodes: a cardinality-constrained second-order cone programming approach. Optim Eng 19, 327–358 (2018). https://doi.org/10.1007/s11081-017-9372-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11081-017-9372-3

Keywords

Search

Navigation