×

Global optimization of truss topology with discrete bar areas. I: Theory of relaxed problems. (English) Zbl 1181.90202

Summary: This two part paper considers the classical problem of finding a truss design with minimal compliance subject to a given external force and a volume bound. The design variables describe the cross-section areas of the bars. While this problem is well-studied for continuous bar areas, we treat here the case of discrete areas. This problem is of major practical relevance if the truss must be built from pre-produced bars with given areas. As a special case, we consider the design problem for a single bar area, i.e., a 0/1-problem. In contrast to heuristic methods considered in other approaches, Part I of the paper together with Part II present an algorithmic framework for the calculation of a global optimizer of the underlying large-scaled mixed integer design problem. This framework is given by a convergent branch-and-bound algorithm which is based on solving a sequence of nonconvex continuous relaxations. The main issue of the paper and of the approach lies in the fact that the relaxed nonlinear optimization problem can be formulated as a quadratic program (QP). Here the paper generalizes and extends the available theory from the literature. Although the Hessian of this QP is indefinite, it is possible to circumvent the non-convexity and to calculate global optimizers. Moreover, the QPs to be treated in the branch-and-bound search tree differ from each other just in the objective function. In Part I we give an introduction to the problem and collect all theory and related proofs for the treatment of the original problem formulation and the continuous relaxed problems. The implementation details and convergence proof of the branch-and-bound methodology and the large-scale numerical examples are presented in Part II [Comput. Optim. Appl. 44, No. 2, 315–341 (2009; Zbl 1184.90110)].

MSC:

90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
74P10 Optimization of other properties in solid mechanics

Citations:

Zbl 1184.90110

Software:

QPA; nag; NAG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achtziger, W.: Topology optimization of discrete structures: an introduction in view of computational and nonsmooth aspects. In: Rozvany, G.I.N. (ed.) Topology Optimization in Structural Mechanics, pp. 57–100. Springer, Vienna (1997) · Zbl 0885.73048
[2] Achtziger, W.: Multiple load truss topology and sizing optimization: some properties of minimax compliance. J. Optim. Theory Appl. 98, 255–280 (1998) · Zbl 0915.73036 · doi:10.1023/A:1022637216104
[3] Achtziger, W., Stolpe, M.: Global optimization of truss topology w.r.t. discrete bar areas–Part I: theory of relaxed problems. Technical Report 308, Department of Mathematics, University of Dortmund, Dortmund, Germany (2005) · Zbl 1181.90202
[4] Achtziger, W., Stolpe, M.: Global optimization of truss topology with discrete bar areas–Part II: implementation and numerical results. Comput. Optim. Appl. (2006, submitted manuscript) · Zbl 1184.90110
[5] Achtziger, W., Stolpe, M.: Truss topology optimization with discrete design variables–guaranteed global optimality and benchmark examples. Struct. Multidiscip. Optim. 34(1), 1–20 (2007) · Zbl 1273.74396 · doi:10.1007/s00158-006-0074-2
[6] Achtziger, W., Bendsøe, M.P., Ben-Tal, A., Zowe, J.: Equivalent displacement based formulations for maximum strength truss topology design. Impact Comput. Sci. Eng. 4, 315–345 (1992) · Zbl 0769.73054 · doi:10.1016/0899-8248(92)90005-S
[7] Ben-Tal, A., Bendsøe, M.P.: A new method for optimal truss topology design. SIAM J. Optim. 3(2), 322–358 (1993) · Zbl 0780.90076 · doi:10.1137/0803015
[8] Ben-Tal, A., Nemirovski, A.: Potential reduction polynomial time method for truss topology design. SIAM J. Optim. 4(3), 596–612 (1994) · Zbl 0821.90137 · doi:10.1137/0804033
[9] Ben-Tal, A., Nemirovski, A.: Optimal design of engineering structures. OPTIMA Math. Program. Soc. Newsl. 47 (1995)
[10] Ben-Tal, A., Nemirovski, A.: Robust truss topology design via semidefinite programming. SIAM J. Optim. 7(4), 991–1016 (1997) · Zbl 0899.90133 · doi:10.1137/S1052623495291951
[11] Ben-Tal, A., Nemirovski, A.: Structural design. In: Handbook of Semidefinite Programming, pp. 443–467. Kluwer Academic, Dordrecht (2000) · Zbl 0957.90529
[12] Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. Society for Industrial and Applied Mathematics, Philadelphia (2001) · Zbl 0986.90032
[13] Ben-Tal, A., Teboulle, M.: Hidden convexity in some nonconvex quadratically constrained quadratic programming. Math. Program. 72(1), 51–63 (1996) · Zbl 0851.90087
[14] Bendsøe, M.P., Sigmund, O.: Topology Optimization–Theory, Methods and Applications. Springer, Berlin (2003) · Zbl 1059.74001
[15] Blum, E., Oettli, W.: Direct proof of the existence theorem in quadratic programming. Oper. Res. 20, 165–167 (1972) · Zbl 0238.90055 · doi:10.1287/opre.20.1.165
[16] Dorn, W.S., Gomory, R.E., Greenberg, H.J.: Automatic design of optimal structures. J. Méc. 3, 25–52 (1964)
[17] Frank, M., Wolfe, P.: An algorithm for quadratic programming. Nav. Res. Logist. Q. 3, 95–110 (1956) · doi:10.1002/nav.3800030109
[18] Friedlander, M.P., Leyffer, S.: Gradient projection for general quadratic programs. Technical Report ANL/MCS-P1370-0906, Argonne National Laboratory, Mathematics and Computer Science Division, Argonne, IL, U.S.A. (Sept. 2006)
[19] Gill, P.E., Murray, W.: Numerically stable methods for quadratic programming. Math. Program. 14, 349–372 (1978) · Zbl 0374.90054 · doi:10.1007/BF01588976
[20] Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: Inertia-controlling methods for general quadratic programming. SIAM Rev. 33, 1–36 (1991) · Zbl 0734.90062 · doi:10.1137/1033001
[21] Gould, N., Toint, Ph.: An iterative working-set method for large-scale nonconvex quadratic programming. Appl. Numer. Math. 43(1-2), 109–128 (2002) · Zbl 1012.65054 · doi:10.1016/S0168-9274(02)00120-4
[22] Gould, N., Toint, Ph.: Numerical methods for large-scale non-convex quadratic programming. In: Siddiqi, A.H., Kočvara, M. (eds.) Trends in Industrial and Applied Mathematics, pp. 149–179. Kluwer Academic, Dordrecht (2002)
[23] Groenwold, A.A., Stander, N., Snyman, J.A.: A pseudo-discrete rounding method for structural optimization. Struct. Optim. 11, 218–227 (1996) · Zbl 0899.73321 · doi:10.1007/BF01197037
[24] Hajela, P., Lee, E.: Genetic algorithms in truss topology optimization. Int. J. Solids Struct. 32(22), 3341–3357 (1995) · Zbl 0919.73113 · doi:10.1016/0020-7683(94)00306-H
[25] Jarre, F., Kočvara, M., Zowe, J.: Optimal truss design by interior point methods. SIAM J. Optim. 8(4), 1084–1107 (1998) · Zbl 0912.90231 · doi:10.1137/S1052623496297097
[26] Kane, C., Schoenauer, M.: Topological optimum design using genetic algorithms. Control Cybern. 25(5), 1059–1087 (1996) · Zbl 0877.73044
[27] Luo, Z.-Q., Zhang, S.: On extensions of the Frank-Wolfe theorems. Comput. Optim. Appl. 13, 87–110 (1999) · Zbl 1040.90536 · doi:10.1023/A:1008652705980
[28] The Numerical Algorithms Group Limited, Oxford, U.K. NAG Fortran Library Manual, Mark 21 edn. (2006)
[29] Ringertz, U.: On methods for discrete structural optimization. Eng. Optim. 13, 44–64 (1988) · doi:10.1080/03052158808940946
[30] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[31] Rozvany, G.I.N., Bendsøe, M.P., Kirsch, U.: Layout optimization of structures. Appl. Mech. Rev. 48, 41–119 (1995) · doi:10.1115/1.3005097
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.