Global optimization of nonconvex problems with convex-transformable intermediates. (English) Zbl 1417.90121
Summary: This paper addresses the global optimization of problems which contain convex-transformable functions. We present algorithms for identification of convex-transformable functions in general nonconvex problems, and introduce a new class of cutting planes based on recently developed relaxations for convex-transformable functions. These cutting planes correspond to the supporting hyperplanes of these convex relaxations. We integrate our recognition and cutting plane generation algorithms into the global solver BARON, and test our implementation by conducting numerical experiments on a large collection of nonconvex problems. Results demonstrate that the proposed implementation accelerates the convergence speed of the branch-and-bound algorithm, by significantly reducing computational time, number of nodes in the search tree, and required memory.
MSC:
| 90C26 | Nonconvex programming, global optimization |
References:
| [1] | Al-Khayyal, FA; Falk, JE, Jointly constrained biconvex programming, Math. Oper. Res., 8, 273-286, (1983) · Zbl 0521.90087 · doi:10.1287/moor.8.2.273 |
| [2] | Avriel, M., Diewert, W.E., Schaible, S., Zang, I.: Generalized Concavity. Plenum Press, New York (1988) · Zbl 0679.90029 · doi:10.1007/978-1-4684-7600-2 |
| [3] | Ayotte-Sauv, E.: NRC Library, Personal Communication (2016) |
| [4] | Bao, X.; Khajavirad, A.; Sahinidis, NV; Tawarmalani, M., Global optimization of nonconvex problems with multilinear intermediates, Math. Program. Comput., 7, 1-37, (2015) · Zbl 1317.90243 · doi:10.1007/s12532-014-0073-z |
| [5] | Bao, X.; Sahinidis, NV; Tawarmalani, M., Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs, Optim. Methods Softw., 24, 485-504, (2009) · Zbl 1179.90252 · doi:10.1080/10556780902883184 |
| [6] | Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237 · doi:10.1080/10556780903087124 |
| [7] | Berthold, T., Gamrath, G., Hendel, G., Heinz, S., Koch, T., Pfetsch, M., Vigerske, S., Waniek, R., Winkler, M., Wolter, K.: SCIP 3.2, User’s Manual (2016) |
| [8] | Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049 · doi:10.1017/CBO9780511804441 |
| [9] | Bussieck, MR; Drud, AS; Meeraus, A., MINLPLib—a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 114-119, (2003) · Zbl 1238.90104 · doi:10.1287/ijoc.15.1.114.15159 |
| [10] | Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263 |
| [11] | GLOBAL Library. http://www.gamsworld.org/global/globallib.htm. Accessed 20 June 2017 |
| [12] | Grossmann, IE, Mixed-integer programming approach for the synthesis of integrated process flowsheets, Comput. Chem. Eng., 9, 463-482, (1985) · doi:10.1016/0098-1354(85)80023-5 |
| [13] | Hunting, M.: AIMMS Library, Personal Communication (2016) |
| [14] | Jach, M.; Michaels, D.; Weismantel, R., The convex envelope of \((n-1)\)-convex functions, SIAM J. Optim., 19, 1451-1466, (2008) · Zbl 1176.90467 · doi:10.1137/07069359X |
| [15] | Khajavirad, A.; Michalek, JJ, A deterministic Lagrangian-based global optimization approach for quasiseparable nonconvex mixed-integer nonlinear programs, J. Mech. Des., 131, 051009, (2009) · doi:10.1115/1.3087559 |
| [16] | Khajavirad, A.; Michalek, JJ; Sahinidis, NV, Relaxations of factorable functions with convex-transformable intermediates, Math. Program., 144, 107-140, (2014) · Zbl 1301.65047 · doi:10.1007/s10107-012-0618-8 |
| [17] | Khajavirad, A.; Sahinidis, NV, Convex envelopes of products of convex and component-wise concave functions, J. Glob. Optim., 52, 391-409, (2011) · Zbl 1268.90052 · doi:10.1007/s10898-011-9747-5 |
| [18] | Khajavirad, A.; Sahinidis, NV, Convex envelopes generated from finitely many compact convex sets, Math. Program., 137, 371-408, (2013) · Zbl 1284.90055 · doi:10.1007/s10107-011-0496-5 |
| [19] | Khajavirad, A., Sahinidis, N.V.: A hybrid LP/NLP paradigm for global optimization relaxations. Mathematical Programming Computation, Under review after minor revision (2017) · Zbl 1400.90227 |
| [20] | Li, H.; Tsai, J.; Floudas, CA, Convex underestimation for posynomial functions of positive variables, Optim. Lett., 2, 333-340, (2008) · Zbl 1152.90610 · doi:10.1007/s11590-007-0061-6 |
| [21] | Lin, Y.; Schrage, L., The global solver in the LINDO API, Optim. Methods Softw., 24, 657-668, (2009) · Zbl 1177.90325 · doi:10.1080/10556780902753221 |
| [22] | Lu, H.; Li, H.; Gounaris, CE; Floudas, CA, Convex relaxation for solving posynomial programs, J. Glob. Optim., 46, 147-154, (2010) · Zbl 1181.90225 · doi:10.1007/s10898-009-9414-2 |
| [23] | Lundell, A.; Westerlund, J.; Westerlund, T., Some transformation techniques with applications in global optimization, J. Glob. Optim., 43, 391-405, (2009) · Zbl 1169.90453 · doi:10.1007/s10898-007-9223-4 |
| [24] | Lundell, A.; Westerlund, T., Convex underestimation strategies for signomial functions, Optim. Methods Softw., 24, 505-522, (2009) · Zbl 1178.90278 · doi:10.1080/10556780802702278 |
| [25] | McCormick, GP, Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665 |
| [26] | Meyer, CA; Floudas, CA, Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes, J. Glob. Optim., 29, 125-155, (2004) · Zbl 1085.90047 · doi:10.1023/B:JOGO.0000042112.72379.e6 |
| [27] | Meyer, CA; Floudas, CA, Convex envelopes for edge-concave functions, Math. Program., 103, 207-224, (2005) · Zbl 1099.90045 · doi:10.1007/s10107-005-0580-9 |
| [28] | Misener, R.; Floudas, ChA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526, (2014) · Zbl 1301.90063 · doi:10.1007/s10898-014-0166-2 |
| [29] | Misener, R.; Gounaris, CE; Floudas, CA, Mathematical modeling and global optimization of large-scale extended pooling problems with the (EPA) complex emissions constraints, Comput. Chem. Eng., 34, 1432-1456, (2010) · doi:10.1016/j.compchemeng.2010.02.014 |
| [30] | Polisetty, PK; Gatzke, EP; Voit, EO, Yield optimization of regulated metabolic systems using deterministic branch-and-reduce methods, Biotechnol. Bioeng., 99, 1154-1169, (2008) · doi:10.1002/bit.21679 |
| [31] | Princeton Library. http://www.gamsworld.org/performance/princetonlib/princetonlib.htm. Accessed 20 June 2017 |
| [32] | Rikun, AD, A convex envelope formula for multilinear functions, J. Glob. Optim., 10, 425-437, (1997) · Zbl 0881.90099 · doi:10.1023/A:1008217604285 |
| [33] | Sahinidis, NV, BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 201-205, (1996) · Zbl 0856.90104 · doi:10.1007/BF00138693 |
| [34] | Sahinidis, N.V.: BARON 15.9.22: global optimization of mixed-integer nonlinear programs, User’s Manual (2015) |
| [35] | Sahinidis, NV; Tawarmalani, M.; Yu, M., Design of alternative refrigerants via global optimization, AIChE J., 49, 1761-1775, (2003) · doi:10.1002/aic.690490714 |
| [36] | Sherali, HD, Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets, Acta Math. Vietnam., 22, 245-270, (1997) · Zbl 0914.90205 |
| [37] | Sherali, HD; Wang, H., Global optimization of nonconvex factorable programming problems, Math. Program., 89, 459-478, (2001) · Zbl 0985.90073 · doi:10.1007/PL00011409 |
| [38] | Tawarmalani, M.; Richard, J-P; Xiong, C., Explicit convex and concave envelopes through polyhedral subdivisions, Math. Program., (2012) · Zbl 1273.90165 · doi:10.1007/s10107-012-0581-4 |
| [39] | Tawarmalani, M.; Sahinidis, NV, Semidefinite relaxations of fractional programs via novel techniques for constructing convex envelopes of nonlinear functions, J. Glob. Optim., 20, 137-158, (2001) · Zbl 1001.90064 · doi:10.1023/A:1011233805045 |
| [40] | Tawarmalani, M.; Sahinidis, NV, Convex extensions and convex envelopes of l.s.c. functions, Math. Program., 93, 247-263, (2002) · Zbl 1065.90062 · doi:10.1007/s10107-002-0308-z |
| [41] | Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 1031.90022 · doi:10.1007/978-1-4757-3532-1 |
| [42] | Tawarmalani, M.; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program., 99, 563-591, (2004) · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6 |
| [43] | Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8 |
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.
