×

A reformulation framework for global optimization. (English) Zbl 1277.90102

Summary: We present a global optimization method for solving nonconvex mixed integer nonlinear programming (MINLP) problems. A convex overestimation of the feasible region is obtained by replacing the nonconvex constraint functions with convex underestimators. For signomial functions single-variable power and exponential transformations are used to obtain the convex underestimators. For more general nonconvex functions, two versions of the so-called \(\alpha\)BB-underestimator, valid for twice-differentiable functions, are integrated in the actual reformulation framework. However, in contrast to what is done in branch-and-bound type algorithms, no direct branching is performed in the actual algorithm. Instead a piecewise convex reformulation is used to convexify the entire problem in an extended variable-space, and the reformulated problem is then solved by a convex MINLP solver. As the piecewise linear approximations are made finer, the solution to the convexified and overestimated problem forms a converging sequence towards a global optimal solution. The result is an easily-implementable algorithm for solving a very general class of optimization problems.

MSC:

90C26 Nonconvex programming, global optimization
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adjiman C.S., Androulakis I.P., Floudas C.A.: Global optimization of mixed-integer nonlinear problems. AIChE J. 46(9), 1769-1797 (2000) · doi:10.1002/aic.690460908
[2] Adjiman C.S., Dallwig S., Floudas C.A., Neumaier A.: A global optimization method, αBB, for general twice-differentiable constrained NLPs—I. Theoretical advances. Comput. Chem. Eng. 22(9), 1137-1158 (1998) · doi:10.1016/S0098-1354(98)00027-1
[3] Adjiman C.S., Dallwig S., Floudas C.A., Neumaier A.: A global optimization method, αBB, for general twice differentiable NLPs—II. Implementation and computional results. Comput. Chem. Eng. 22, 1159-1179 (1998) · doi:10.1016/S0098-1354(98)00218-X
[4] Adjiman C.S., Androulakis I.P., Floudas C.A.: Global optimization of MINLP problems in process synthesis and design. Comput. Chem. Eng. 21, 445-450 (1997) · doi:10.1016/S0097-8485(97)00020-X
[5] Akrotirianakis I.G., Floudas C.A.: Computational experience with a new class of convex underestimators: box-constrained NLP problems. J. Glob. Optim. 29(3), 249-264 (2004) · Zbl 1133.90420 · doi:10.1023/B:JOGO.0000044768.75992.10
[6] Akrotirianakis I.G., Floudas C.A.: A new class of improved convex underestimators for twice continuously differentiable constrained NLPs. J. Glob. Optim. 30(4), 367-390 (2004) · Zbl 1082.90090 · doi:10.1007/s10898-004-6455-4
[7] Androulakis I.P., Maranas C.D., Floudas C.A.: αBB: a global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7, 337-363 (1995) · Zbl 0846.90087 · doi:10.1007/BF01099647
[8] Björk, K.-M.: A global optimization method with some heat exchanger network applications. Ph.D. thesis, Åbo Akademi University (2002) · Zbl 0369.90112
[9] Brönnimann H., Melquiond G., Pion S.: The design of the Boost interval arithmetic library. Theor. Comput. Sci. 351, 111-118 (2006) · Zbl 1086.65046 · doi:10.1016/j.tcs.2005.09.062
[10] Dembo R.S.: Current state of the art of algorithms and computer software for geometric programming. J. Optim. Theory Appl. 26(2), 149-183 (1978) · Zbl 0369.90121 · doi:10.1007/BF00933402
[11] Floudas, C.A.: Deterministic global optimization. Theory, methods and applications. Number 37 in Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht (2000) · Zbl 1173.90483
[12] Floudas C.A., Kreinovich V.: On the functional form of convex underestimators for twice continuously differentiable functions. Optim. Lett. 1, 187-192 (2007) · Zbl 1133.49030 · doi:10.1007/s11590-006-0003-8
[13] Floudas, C. A.; Kreinovich, V.; Törn, A. (ed.); Zilinskas, J. (ed.), Towards optimal techniques for solving global optimization problems: symmetry-based approach, 21-42 (2007), Boston, MA · Zbl 1267.90105 · doi:10.1007/978-0-387-36721-7_2
[14] Horst, R., Pardalos, P.M., Romeijn, H.E.: Handbook of global optimization. Number 2 in Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht (2002)
[15] Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Nonconvex Optimization and its Applications. Kluwer Academic Publishers, Dordrecht (2000) · Zbl 0966.90073
[16] Jeroslow, R.G., Lowe, J.K.: Modelling with integer variables. In: Mathematical Programming at Oberwolfach II, vol. 22 of Mathematical Programming Studies, pp. 167-184. Springer, Berlin (1984) · Zbl 0554.90081
[17] Li H.-L., Tsai J.F., Floudas C.A.: Convex underestimation for posynomial functions of positive variables. Optim. Lett. 2(3), 333-340 (2008) · Zbl 1152.90610 · doi:10.1007/s11590-007-0061-6
[18] Liberti, L.; Cafieri, S.; Tarissan, F.; Abraham, A. (ed.); Hassanien, A.-E. (ed.); Siarry, P. (ed.); Engelbrecht, A. (ed.), Reformulations in mathematical programming: a computational approach, 153-234 (2009), Berlin · doi:10.1007/978-3-642-01085-9_7
[19] Lin M.-H., Tsai J.-F.: Range reduction techniques for improving computational efficiency in global optimization of signomial geometric programming problems. Eur. J. Oper. Res. 216(1), 17-25 (2012) · Zbl 1242.90177 · doi:10.1016/j.ejor.2011.06.046
[20] Liu W.B., Floudas C.A.: A remark on the GOP algorithm for global optimization. J. Glob. Optim. 3, 519-521 (1993) · Zbl 0785.90089 · doi:10.1007/BF01096418
[21] Lundell, A.: Transformation techniques for signomial functions in global optimization. Ph.D. thesis, Åbo Akademi University (2009) · Zbl 1242.90137
[22] Lundell A., Westerlund J., Westerlund T.: Some transformation techniques with applications in global optimization. J. Glob. Optim. 43(2), 391-405 (2009) · Zbl 1169.90453 · doi:10.1007/s10898-007-9223-4
[23] Lundell A., Westerlund T.: Optimization of power transformations in global optimization. Chem. Eng. Trans. 11, 95-100 (2007)
[24] Lundell, A., Westerlund, T.: Exponential and power transformations for convexifying signomial terms in MINLP problems. In: Bruzzone, L. (ed.) Proceedings of the 27th IASTED International Conference on Modelling, Identification and Control, pp. 154-159. ACTA Press, Anaheim · Zbl 1169.90453
[25] Lundell A., Westerlund T.: Convex underestimation strategies for signomial functions. Optim. Methods Softw. 24, 505-522 (2009) · Zbl 1178.90278 · doi:10.1080/10556780802702278
[26] Lundell, A., Westerlund, T.: Implementation of a convexification technique for signomial functions. In: Jezowski, J., Thullie, J. (eds.) Proceedings of the 19th European Symposium on Computer Aided Process Engineering, vol. 26 of Computer Aided Chemical Engineering, pp. 579-583. Elsevier, Amsterdam (2009) · Zbl 1243.90181
[27] Lundell A., Westerlund T.: On the relationship between power and exponential transformations for positive signomial functions. Chem. Eng. Trans. 17, 1287-1292 (2009)
[28] Lundell, A., Westerlund, T.: Optimization of transformations for convex relaxations of MINLP problems containing signomial functions. In: de Brito Alves, R.M., do Nascimento, C.A.O., Biscaia, E.C. (eds.) Proceedings of the 10th International Symposium on Process Systems Engineering: Part A, vol. 27 of Computer Aided Chemical Engineering, pp. 231-236. Elsevier, Amsterdam (2009)
[29] Lundell, A.; Westerlund, T.; Lee, J. (ed.); Leyffer, S. (ed.), Global optimization of mixed-integer signomial programming problems, 349-369 (2012), New York, NY · Zbl 1242.90137 · doi:10.1007/978-1-4614-1927-3_12
[30] Maranas C.D., Floudas C.A.: Finding all solutions of nonlinearly constrained systems of equations. J. Glob. Optim. 7, 143-182 (1995) · Zbl 0841.90115 · doi:10.1007/BF01097059
[31] Maranas C.D., Floudas C.A.: Global optimization in generalized geometric programming. Comput. Chem. Eng. 21(4), 351-369 (1997) · doi:10.1016/S0098-1354(96)00282-7
[32] Meyer C.A., Floudas C.A.: Convex underestimation of twice continuously differentiable functions by piecewise quadratic perturbation: Spline αBB underestimators. J. Glob. Optim. 32(2), 221-258 (2005) · Zbl 1080.90059 · doi:10.1007/s10898-004-2704-9
[33] Pardalos P.M., Romeijn H.E., Tuy H.: Recent developments and trends in global optimization. J. Comput. Appl. Math. 124(1-2), 209-228 (2000) · Zbl 0969.90067 · doi:10.1016/S0377-0427(00)00425-8
[34] Pardalos, P.M., Rosen, J.B.: Constrained Global Optimization: Algorithms and Applications, vol. 268 of Lecture notes in Computer Science. Springer, Berlin (1987) · Zbl 0638.90064
[35] Peterson E.L.: The origins of geometric programming. Ann. Oper. Res. 105, 15-19 (2001) · Zbl 1024.90002 · doi:10.1023/A:1013320729170
[36] Pörn R., Björk K.-M., Westerlund T.: Global solution of optimization problems with signomial parts. Discret. Optim. 5, 108-120 (2008) · Zbl 1134.90041 · doi:10.1016/j.disopt.2007.11.005
[37] Pörn R., Harjunkoski I., Westerlund T.: Convexification of different classes of non-convex MINLP problems. Comput. Chem. Eng. 23, 439-448 (1999) · doi:10.1016/S0098-1354(98)00305-6
[38] Rijckaert M.J., Martens X.M.: Comparison of generalized geometric programming algorithms. J. Optim. Theory Appl. 26(2), 205-242 (1978) · Zbl 0369.90112 · doi:10.1007/BF00933404
[39] Rosenthal R.E.: GAMS—A User’s Guide. GAMS Development Corporation, Washington, DC (2008)
[40] Skjäl A., Lundell A., Westerlund T.: Global optimization with C2 constraints by convex reformulations. Chem. Eng. Trans. 24, 373-378 (2011)
[41] Tsai J.F., Lin M.-H.: Global optimization of signomial mixed-integer nonlinear programming problems with free variables. J. Glob. Optim. 42(1), 39-49 (2008) · Zbl 1173.90483 · doi:10.1007/s10898-007-9211-8
[42] Tsai J.F., Lin M.-H.: An efficient global approach for posynomial geometric programming problems. INFORMS J. Comput. 23, 483-492 (2011) · Zbl 1243.90181 · doi:10.1287/ijoc.1100.0403
[43] Westerlund, T.; Liberti, L. (ed.); Maculan, N. (ed.), Some transformation techniques in global optimization, 47-74 (2005), Berlin
[44] Westerlund T., Lundell A., Westerlund J.: On convex relaxations in nonconvex optimization. Chem. Eng. Trans. 24, 331-336 (2011)
[45] Westerlund T., Westerlund J.: GGPECP—An algorithm for solving non-convex MINLP problems by cutting plane and transformation techniques. Chem. Eng. Trans. 3, 1045-1050 (2003)
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.