×

zbMATH — the first resource for mathematics

Range reduction techniques for improving computational efficiency in global optimization of signomial geometric programming problems. (English) Zbl 1242.90177
Summary: Many global optimization approaches for solving signomial geometric programming problems are based on transformation techniques and piecewise linear approximations of the inverse transformations. Since using numerous break points in the linearization process leads to a significant increase in the computational burden for solving the reformulated problem, this study integrates the range reduction techniques in a global optimization algorithm for signomial geometric programming to improve computational efficiency. In the proposed algorithm, the non-convex geometric programming problem is first converted into a convex mixed-integer nonlinear programming problem by convexification and piecewise linearization techniques. Then, an optimization-based approach is used to reduce the range of each variable. Tightening variable bounds iteratively allows the proposed method to reach an approximate solution within an acceptable error by using fewer break points in the linearization process, therefore decreasing the required CPU time. Several numerical experiments are presented to demonstrate the advantages of the proposed method in terms of both computational efficiency and solution quality.

MSC:
90C26 Nonconvex programming, global optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
LINDO; LINGO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adjiman, C.S.; Androulakis, I.P.; Floudas, C.A., A global optimization method, αBB, for general twice – differentiable NLPs-II. implementation and computational results, Computers and chemical engineering, 22, 9, 1159-1179, (1998)
[2] Adjiman, C.S.; Androulakis, I.P.; Floudas, C.A., Global optimization of mixed-integer nonlinear problems, Aiche journal, 46, 9, 1769-1797, (2000)
[3] Audet, C.; Hansen, P.; Jaumard, B.; Savard, G., A branch and cut algorithm for nonconvex quadratically constrained quadratic programming, Mathematical programming, 87, 1, Ser. A, 131-152, (2000) · Zbl 0966.90057
[4] Audet, C.; Hansen, P.; Karam, A.; Ng, C.T.; Perron, S., Exact L2-norm plane separation, Optimization letters, 2, 4, 483-495, (2008) · Zbl 1159.90514
[5] Avriel, M.; Williams, A.C., Complementary geometric programming, SIAM journal on applied mathematics, 19, 1, 125-141, (1970) · Zbl 0319.90035
[6] Avriel, M.; Williams, A.C., An extension of geometric programming with applications in engineering optimization, Journal of engineering mathematics, 5, 3, 187-194, (1971)
[7] Biegler, L.T.; Grossmann, I.E., Retrospective on optimization, Computers and chemical engineering, 28, 8, 1169-1192, (2004)
[8] Dembo, R.S., A set of geometric programming test problems and their solutions, Mathematical programming, 10, 192-213, (1976) · Zbl 0349.90066
[9] Floudas, C.A., Deterministic global optimization: theory, methods and application, (2000), Kluwer Academic Publishers Boston
[10] Floudas, C.A.; Gounaris, C.E., A review of recent advances in global optimization, Journal of global optimization, 45, 1, 3-38, (2009) · Zbl 1180.90245
[11] Floudas, C.A.; Pardalos, P.M., A collection of test problems for constrained global optimization algorithms, Lecture notes in computer science, 455, (1990), Springer Berlin · Zbl 0718.90054
[12] Floudas, C.A.; Pardalos, P.M.; Adjiman, C.S.; Esposito, W.R.; Gümüs, Z.H.; Harding, S.T.; Klepeis, J.L.; Meyer, C.A.; Schweiger, C.A., Handbook of test problems in local and global optimization, (1999), Kluwer Academic Publishers Boston · Zbl 0943.90001
[13] Gounaris, C.E.; Floudas, C.A., Convexity of products of univariate functions and convexification transformations for geometric programming, Journal of optimization theory and its applications, 138, 3, 407-427, (2008) · Zbl 1163.90017
[14] Kortanek, K.; Xu, X.; Ye, Y., An infeasible interior-point algorithm for solving primal and dual geometric programs, Mathematical programming, 76, 155-181, (1997) · Zbl 0881.90106
[15] Li, H.L.; Lu, H.C., Global optimization for generalized geometric programs with mixed free-sign variables, Operations research, 57, 3, 701-713, (2009) · Zbl 1226.90078
[16] Li, H.L.; Lu, H.C.; Huang, C.H.; Hu, N.Z., A superior representation method for piecewise linear functions, INFORMS journal on computing, 21, 314-321, (2009) · Zbl 1243.90128
[17] Lindo, 2008. LINGO, Release 11. Lindo System Inc., Chicago.
[18] Lu, H.C.; Li, H.L.; Gounaris, C.E.; Floudas, C.A., Convex relaxation for solving posynomial programs, Journal of global optimization, 46, 1, 147-154, (2010) · Zbl 1181.90225
[19] Lundell, A.; Westerlund, T., On the relationship between power and exponential transformations for positive signomial functions, Chemical engineering transactions, 17, 1287-1292, (2009)
[20] Lundell, A.; Westerlund, T., Convex underestimation strategies for signomial functions, Optimization methods and software, 24, 505-522, (2009) · Zbl 1178.90278
[21] Lundell, A.; Westerlund, J.; Westerlund, T., Some transformation techniques with applications in global optimization, Journal of global optimization, 43, 2-3, 391-405, (2009) · Zbl 1169.90453
[22] Maranas, C.D.; Floudas, C.A., Finding all solutions of nonlinearly constrained systems of equations, Journal of global optimization, 7, 143-182, (1995) · Zbl 0841.90115
[23] Maranas, C.D.; Floudas, C.A., Global optimization in generalized geometric programming, Computers and chemical engineering, 21, 4, 351-370, (1997) · Zbl 0891.90165
[24] Passy, U., Generalized weighted Mean programming, SIAM journal on applied mathematics, 20, 4, 763-778, (1971) · Zbl 0233.90021
[25] Passy, U.; Wilde, D.J., Generalized polynomial optimization, SIAM journal on applied mathematics, 15, 5, 1344-1356, (1967) · Zbl 0171.18002
[26] Perron, S., 2004. Applications jointes de l’optimisation combinatoire et globale. Ph.D. thesis, École Polytechnique de Montréal.
[27] Pörn, R.; Bjork, K.M.; Westerlund, T., Global solution of optimization problems with signomial parts, Discrete optimization, 5, 108-120, (2008) · Zbl 1134.90041
[28] Quesada, I.; Grossmann, I., A global optimization algorithm for linear fractional and bilinear programs, Journal of global optimization, 6, 39-76, (1995) · Zbl 0835.90074
[29] Rijckaert, M.J.; Martens, X.M., Comparison of generalized geometric programming algorithms, Journal of optimization theory and applications, 26, 205-242, (1978) · Zbl 0369.90112
[30] Ryoo, H.S.; Sahinidis, N.V., Global optimization of nonconvex NLPs and MINLPs with applications in process design, Computers and chemical engineering, 19, 5, 551-566, (1995)
[31] Shen, P., Linearization method of global optimization for generalized geometric programming, Applied mathematics and computation, 162, 353-370, (2005) · Zbl 1071.65089
[32] Smith, E.M.B.; Pantelides, C.C., A symbolic reformulation/spatial branch and bound algorithm for the global solution of nonconvex minlps, Computers and chemical engineering, 23, 457-478, (1999)
[33] Tsai, J.F.; Lin, M.H., Global optimization of signomial mixed-integer nonlinear programming problems with free variables, Journal of global optimization, 42, 39-49, (2008) · Zbl 1173.90483
[34] Tsai, J.F., Lin, M.H., in press. An efficient global approach for posynomial geometric programming problems. INFORMS Journal on Computing. doi:10.1287/ijoc.1100.0403. · Zbl 1243.90181
[35] Tsai, J.F.; Lin, M.H.; Hu, Y.C., On generalized geometric programming problems with non-positive variables, European journal of operational research, 178, 1, 10-19, (2007) · Zbl 1109.90050
[36] Vielma, J.P.; Nemhauser, G., Modeling disjunctive constraints with a logarithmic number of binary variables and constraints, Mathematical programming, 128, 49-72, (2011) · Zbl 1218.90137
[37] Wang, Y.J.; Liang, Z., A deterministic global optimization algorithm for generalized geometric programming, Applied mathematics and computation, 168, 722-737, (2005) · Zbl 1105.65335
[38] Westerlund, T., Some transformation techniques in global optimization, (), 45-74 · Zbl 1100.90037
[39] Westerlund, T.; Westerlund, J., GGPECP-an algorithm for solving nonconvex MINLP problems by cutting plane and transformation techniques, Chemical engineering transactions, 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.