Alternating direction method of multipliers for truss topology optimization with limited number of nodes: a cardinality-constrained second-order cone programming approach. (English) Zbl 1397.74163
Summary: 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.
MSC:
| 74P15 | Topological methods for optimization problems in solid mechanics |
| 90C90 | Applications of mathematical programming |
| 90C22 | Semidefinite programming |
Keywords:
topology optimization; truss optimization; manufacturability; alternating direction method of multipliers; cardinality-constrained second-order cone programming; mixed-integer second-order cone programmingReferences:
| [1] | Anjos MF, Lasserre JB (eds) (2012) Handbook on semidefinite, conic and polynomial optimization. Springer, New York · Zbl 1235.90002 |
| [2] | Achtziger, W, Local stability of trusses in the context of topology optimization part I: exact modelling, Struct Optim, 17, 235-246, (1999) |
| [3] | Andersen, ED; Roos, C; Terlaky, T, On implementing a primal-dual interior-point method for conic quadratic optimization, Math Program, 95, 249-277, (2003) · Zbl 1030.90137 · doi:10.1007/s10107-002-0349-3 |
| [4] | Arastoo, R; Bahavarnia, M; Kothare, MV; Motee, N, Output feedback controller sparsification via \(\cal{H}_{2}\)-approximation, IFAC-PapersOnLine, 48, 112-117, (2015) · doi:10.1016/j.ifacol.2015.10.316 |
| [5] | Asadpoure, A; Guest, JK; Valdevit, L, Incorporating fabrication cost into topology optimization of discrete structures and lattices, Struct Multidiscip Optim, 51, 385-396, (2015) · doi:10.1007/s00158-014-1133-8 |
| [6] | Bendsøe, MP; Ben-Tal, A; Zowe, J, Optimization methods for truss geometry and topology design, Struct Optim, 7, 141-159, (1994) · doi:10.1007/BF01742459 |
| [7] | Ben-Tal, A; Nemirovski, A, Robust truss topology optimization via semidefinite programming, SIAM J Optim, 7, 991-1016, (1997) · Zbl 0899.90133 · doi:10.1137/S1052623495291951 |
| [8] | Ben-Tal A, Nemirovski A (2001) Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, Philadelphia · Zbl 0986.90032 · doi:10.1137/1.9780898718829 |
| [9] | Bertsimas, D; Shioda, R, Algorithm for cardinality-constrained quadratic optimization, Comput Optim Appl, 43, 1-22, (2009) · Zbl 1178.90262 · doi:10.1007/s10589-007-9126-9 |
| [10] | Boyd, S; Parikh, N; Chu, E; Peleato, B; Eckstein, J, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found Trends Mach Learn, 3, 1-122, (2010) · Zbl 1229.90122 · doi:10.1561/2200000016 |
| [11] | Bruckstein, AM; Donoho, DL; Elad, M, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev, 51, 34-81, (2009) · Zbl 1178.68619 · doi:10.1137/060657704 |
| [12] | Burdakov, OP; Kanzow, C; Schwartz, A, Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method, SIAM J Optim, 26, 397-425, (2016) · Zbl 1332.90220 · doi:10.1137/140978077 |
| [13] | Candès, EJ; Wakin, MB; Boyd, SP, Enhancing sparsity by reweighted \(ℓ _{1}\) minimization, J Fourier Anal Appl, 14, 877-905, (2008) · Zbl 1176.94014 · doi:10.1007/s00041-008-9045-x |
| [14] | Chartrand, R, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process Lett, 14, 707-710, (2007) · doi:10.1109/LSP.2007.898300 |
| [15] | Chartrand, R, Nonconvex splitting for regularized low-rank \(+\) sparse decomposition, IEEE Trans Signal Process, 60, 5810-5819, (2012) · Zbl 1393.94190 · doi:10.1109/TSP.2012.2208955 |
| [16] | 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) |
| [17] | Cui, XT; Zheng, XJ; Zhu, SS; Sun, XL, Convex relaxations and MIQCQP reformulations for a class of cardinality-constrained portfolio selection problems, J Glob Optim, 56, 1409-1423, (2013) · Zbl 1275.90044 · doi:10.1007/s10898-012-9842-2 |
| [18] | Diamond, S; Takapoui, R; Boyd, S, A general system for heuristic minimization of convex functions over non-convex sets, Optim Methods Softw, 33, 165-193, (2018) · Zbl 1386.90182 · doi:10.1080/10556788.2017.1304548 |
| [19] | 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 · Zbl 06869181 |
| [20] | Grant, M; Boyd, S; Blondel, V (ed.); Boyd, S (ed.); Kimura, H (ed.), Graph implementations for nonsmooth convex programs, 95-110, (2008), Berlin · Zbl 1205.90223 · doi:10.1007/978-1-84800-155-8_7 |
| [21] | Grant M, Boyd S (2017) CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx/. Accessed Jan 2017 |
| [22] | Guo, X; Cheng, GD; Olhoff, N, Optimum design of truss topology under buckling constraints, Struct Multidiscip Optim, 30, 169-180, (2005) · doi:10.1007/s00158-004-0511-z |
| [23] | Gurobi Optimization, Inc.: Gurobi optimizer reference manual. http://www.gurobi.com/. Accessed Sept 2016 |
| [24] | He, L; Gilbert, M, Rationalization of trusses generated via layout optimization, Struct Multidiscip Optim, 52, 677-694, (2015) · doi:10.1007/s00158-015-1260-x |
| [25] | Hegemier, GA; Prager, W, On michell trusses, Int J Mech Sci, 11, 209-215, (1969) · Zbl 0164.26302 · doi:10.1016/0020-7403(69)90006-X |
| [26] | Kanamori, T; Takeda, A, Numerical study of learning algorithms on Stiefel manifold, CMS, 11, 319-340, (2014) · Zbl 1331.68184 · doi:10.1007/s10287-013-0181-7 |
| [27] | Kanno, Y, 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, (2013) · doi:10.1002/eqe.2292 |
| [28] | Kanno, Y, 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, (2016) · Zbl 1343.90070 · doi:10.1007/s10589-015-9766-0 |
| [29] | Kanno, Y, Mixed-integer second-order cone programming for global optimization of compliance of frame structure with discrete design variables, Struct Multidiscip Optim, 54, 301-316, (2016) · doi:10.1007/s00158-016-1406-5 |
| [30] | Kanno, Y; Yamada, H, A note on truss topology optimization under self-weight load: mixed-integer second-order cone programming approach, Struct Multidiscip Optim, 56, 221-226, (2017) · doi:10.1007/s00158-017-1657-9 |
| [31] | Kirsch, U, Optimal topologies of structures, Appl Mech Rev, 42, 223-239, (1989) · Zbl 0675.73058 · doi:10.1115/1.3152429 |
| [32] | Kočvara, M; Terlaky, T (ed.); Anjos, MF (ed.); Ahmed, S (ed.), Truss topology design by linear conic optimization, (2017), Philadelphia |
| [33] | Le Thi, HA; Dinh, TP; Le, HM; Vo, XT, DC approximation approaches for sparse optimization, Eur J Oper Res, 244, 26-46, (2015) · Zbl 1346.90819 · doi:10.1016/j.ejor.2014.11.031 |
| [34] | Lin, F; Fardad, M; Jovanović, MR, Design of optimal sparse feedback gains via the alternating direction method of multipliers, IEEE Trans Autom Control, 58, 2426-2431, (2013) · Zbl 1369.93215 · doi:10.1109/TAC.2013.2257618 |
| [35] | 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) |
| [36] | Magnússon, S; Rabbat, MG; Fischione, C, On the convergence of alternating direction Lagrangian methods for nonconvex structured optimization problems, IEEE Trans Control Netw Syst, 3, 296-309, (2016) · Zbl 1370.90196 · doi:10.1109/TCNS.2015.2476198 |
| [37] | Masazade, E; Fardad, M; Varshney, PK, Sparsity-promoting extended Kalman filtering for target tracking in wireless sensor networks, IEEE Signal Process Lett, 19, 845-848, (2012) · doi:10.1109/LSP.2012.2220350 |
| [38] | Mazurek, A, Geometrical aspects of optimum truss like structures for three-force problem, Struct Multidiscip Optim, 45, 21-32, (2012) · Zbl 1274.74236 · doi:10.1007/s00158-011-0679-y |
| [39] | Mazurek, A; Baker, WF; Tort, C, Geometrical aspects of optimum truss like structures, Struct Multidiscip Optim, 43, 231-242, (2011) · doi:10.1007/s00158-010-0559-x |
| [40] | Mela, K, Resolving issues with member buckling in truss topology optimization using a mixed variable approach, Struct Multidiscip Optim, 50, 1037-1049, (2014) · doi:10.1007/s00158-014-1095-x |
| [41] | Michell, AGA, The limits of economy of material in frame-structures, Lond Edinb Dublin Philos Mag J Sci, 8, 589-597, (1904) · JFM 35.0828.01 · doi:10.1080/14786440409463229 |
| [42] | Miyashiro, R; Takano, Y, Mixed integer second-order cone programming formulations for variable selection in linear regression, Eur J Oper Res, 247, 721-731, (2015) · Zbl 1346.90616 · doi:10.1016/j.ejor.2015.06.081 |
| [43] | Natarajan, BK, Sparse approximate solutions to linear systems, SIAM J Comput, 24, 227-234, (1995) · Zbl 0827.68054 · doi:10.1137/S0097539792240406 |
| [44] | Ohsaki M (2011) Optimization of finite dimensional structures. CRC Press, Boca Raton · Zbl 1223.74002 |
| [45] | Ohsaki, M; Kanno, Y; Tsuda, S, Linear programming approach to design of spatial link mechanism with partially rigid joints, Struct Multidiscip Optim, 50, 945-956, (2014) · doi:10.1007/s00158-014-1094-y |
| [46] | Parkes, EW, Joints in optimum frameworks, Int J Solids Struct, 11, 1017-1022, (1975) · Zbl 0311.73038 · doi:10.1016/0020-7683(75)90044-X |
| [47] | 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/ |
| [48] | Prager, W, Optimal layout of cantilever trusses, J Optim Theory Appl, 23, 111-117, (1977) · Zbl 0342.73053 · doi:10.1007/BF00932301 |
| [49] | Prager, W, Optimal layout of trusses with finite numbers of joints, J Mech Phys Solids, 26, 241-250, (1978) · doi:10.1016/0022-5096(78)90019-4 |
| [50] | Rozvany, GIN, Difficulties in truss topology optimization with stress, local buckling and system stability constraints, Struct Optim, 11, 213-217, (1996) · doi:10.1007/BF01197036 |
| [51] | Sagnol G (2012) PICOS: a python interface for conic optimization solvers. http://picos.zib.de/. Accessed Feb 2017 |
| [52] | Sturm, JF, Using sedumi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim Methods Softw, 11, 625-653, (1999) · Zbl 0973.90526 · doi:10.1080/10556789908805766 |
| [53] | 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 · Zbl 1434.90117 |
| [54] | Topping, BHV, Shape optimization of skeletal structures: a review, J Struct Eng, 109, 1933-1951, (1983) · doi:10.1061/(ASCE)0733-9445(1983)109:8(1933) |
| [55] | Torii, AJ; Lopez, RH; Miguel, LFF, Design complexity control in truss optimization, Struct Multidiscip Optim, 54, 289-299, (2016) · doi:10.1007/s00158-016-1403-8 |
| [56] | Tütüncü, RH; Toh, KC; Todd, MJ, Solving semidefinite-quadratic-linear programs using SDPT3, Math Program, B95, 189-217, (2003) · Zbl 1030.90082 · doi:10.1007/s10107-002-0347-5 |
| [57] | Zheng, X; Sun, X; Li, D; Sun, J, Successive convex approximations to cardinality-constrained convex programs: a piecewise-linear DC approach, Comput Optim Appl, 59, 379-397, (2014) · Zbl 1302.90157 · doi:10.1007/s10589-013-9582-3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
