Abstract
We present a new relaxation method for the deterministic global optimization of general nonconvex and \({\mathscr {C}}^2\)-continuous problems. Instead of using a convex underestimator, the method uses an edge-concave (componentwise concave) underestimator to relax a nonconvex function. The underestimator is constructed by subtracting a positive quadratic expression such that all nonedge-concavities in the original function is overpowered by the added expression. While the edge-concave underestimator is nonlinear, the linear facets of its vertex polyhedral convex envelope leads to a linear programming (LP)-based relaxation of the original nonconvex problem. We present some theoretical results on this new class of underestimators and compare the performance of the LP relaxation with relaxations obtained by convex underestimators such as \(\alpha \hbox {BB}\) and its variants for several test problems. We also discuss the potential of a hybrid relaxation, relying on the dynamic selection of convex and edge-concave underestimators using criteria such as maximum separation distance.
Similar content being viewed by others
References
Floudas, C.A., Pardalos, P.M.: State-of-the-art in global optimization—computational methods and applications—preface. J. Glob. Optim. 7(2), 113 (1995)
Sherali, H.D., Adams, W.P.: Reformulation-Linearization Techniques in Discrete, Continuous Optimization. Kluwer Academic Publishers, Dordrecht (2002)
Floudas, C.A., Pardalos, P.M., Adjiman, C.S., Esposito, W.R., Gms, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems in Local, Global Optimization. Kluwer Academic Publishers, Dordrecht (1999)
Floudas, C.A.: Deterministic Global Optimization: Theory, Methods, Applications. Kluwer Academic Publishers, Dordrecht (2000)
Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization, Second edn. Kluwer Academic Publishers, Dordrecht (2000)
Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Applications, Software, and Applications. Kluwer Academic Publishers, Norwell (2002)
Floudas, C.A., Pardalos, P.M.: Frontiers in Global Optimization. Kluwer Academic Publishers, Dordrecht (2003)
Floudas, C.A.: Research challenges opportunities, synergism in systems engineering, computational biology. AIChE J. 51, 1872–1884 (2005)
Floudas, C.A., Akrotirianakis, I.G., Caratzoulas, S., Meyer, C.A., Kallrath, J.: Global optimization in the 21st century: advances, challenges. Comput. Chem. Eng. 29, 1185–1202 (2005)
Floudas, C.A., Gounaris, C.E.: A review of recent advances in global optimization. J. Glob. Optim. 45(1), 3–38 (2009)
McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part 1-convex underestimating problems. Math. Program. 10(1), 147–175 (1976)
Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273–286 (1983)
Meyer, C.A., Floudas, C.A.: Trilinear monomials with positive or negative domains: facets of the convex, concave envelopes. In: Floudas, C.A., Pardalos, P.M. (eds.) Frontiers in Global Optimization, pp. 327–352. Kluwer Academic Publishers, Dordrecht (2003)
Meyer, C.A., Floudas, C.A.: Trilinear monomials with mixed sign domains: facets of the convex, concave envelopes. J. Glob. Optim. 29(2), 125–155 (2004)
Ryoo, H.S., Sahinidis, N.V.: Analysis of bounds for multilinear functions. J. Glob. Optim. 19, 403–424 (2001)
Maranas, C.D., Floudas, C.A.: Finding all solutions of nonlinearly constrained systems of equations. J. Glob. Optim. 7(2), 143–182 (1995)
Tawarmalani, M., Sahinidis, N.V.: Semidefinite relaxations of fractional programs via novel convexification techniques. J. Glob. Optim. 20(2), 133–154 (2001)
Tawarmalani, M., Sahinidis, N.V.: Convex extensions, envelopes of lower semi-continuous functions. Math. Program. 247–263, 93 (2002)
Liberti, L., Pantelides, C.C.: Convex envelopes of monomials of odd degree. J. Glob. Optim. 25(2), 157–168 (2003)
Meyer, C.A., Floudas, C.A.: Convex envelopes for edge-concave functions. Math. Program. 103(2), 207–224 (2005)
Tardella, F.: On a class of functions attaining their maximum at the vertices of a polyhedron. Discrete Appl. Math. 22, 191–195 (1988)
Tardella, F.: On the existence of polyhedral convex envelopes. In: Floudas, C.A., Pardalos, P.M. (eds.) Frontiers in Global Optimization, pp. 563–573. Kluwer Academic Publishers, Dordrecht (2003)
Tardella, F.: Existence, sum decomposition of vertex polyhedral convex envelopes. Optim. Lett. 2, 363–375 (2008)
Caratzoulas, S., Floudas, C.A.: Trigonometric convex underestimator for the base functions in Fourier space. J. Optim. Theory Appl. 124, 339–362 (2005)
Maranas, C.D., Floudas, C.A.: Global minimum potential energy conformations of small molecules. J. Glob. Optim. 4, 135–170 (1994)
Androulakis, I.P., Maranas, C.D., Floudas, C.A.: \(\alpha \text{ BB }\): a global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7, 337–363 (1995)
Adjiman, C.S., Floudas, C.A.: Rigorous convex underestimators for general twice-differentiable problems. J. Glob. Optim. 9, 23–40 (1996)
Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A Global Optimization method, \(\alpha \text{ BB }\), for general twice differentiable NLPs-I. Theoretical advances. Comput. Chem. Eng. 22, 1137–1158 (1998)
Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: A global optimization method, \(\alpha \text{ BB }\), for general twice differentiable NLPs-II. Implementation, computional results. Comput. Chem. Eng. 22, 1159–1179 (1998)
Akrotirianakis, I.G., Floudas, C.A.: A new class of improved convex underestimators for twice continuously differentiable constrained NLPs. J. Glob. Optim. 30, 367–390 (2004)
Akrotirianakis, I.G., Floudas, C.A.: Computational experience with a new class of convex underestimators: box-constrained NLP problems. J. Glob. Optim. 29, 249–264 (2004)
Floudas, C.A., Kreinovich, V.: Towards optimal techniques for solving global optimization problems: symmetry-based approach. In: Torn, A., Zilinskas, J. (eds.) Models, Algorithms for Global Optimization, pp. 21–42. Springer, Berlin (2006)
Floudas, C.A., Kreinovich, V.: On the functional form of convex underestimators for twice continuously differentiable functions. Optim. Lett. 1(2), 187–192 (2007)
Meyer, C.A., Floudas, C.A.: Convex underestimation of twice continuously differentiable functions by piecewise quadratic perturbation: spline \(\alpha \text{ BB }\) underestimators. J. Glob. Optim. 32, 221–258 (2005)
Gounaris, C.E., Floudas, C.A.: Tight convex underestimators for \(C^2\)-continuous problems: I. Univariate functions. J. Glob. Optim. 42(1), 51–67 (2008)
Gounaris, C.E., Floudas, C.A.: Tight convex underestimators for \(C^2\)-continuous problems: II. Multivariate functions. J. Glob. Optim. 42(1), 69–89 (2008)
Misener, R., Gounaris, C.E., Floudas, C.A.: Mathematical modeling and global optimization of large-scale extended pooling problems with the (EPA) complex emissions constraints. Comput. Chem. Eng. 34(9), 1432–1456 (2010)
Misener, R., Floudas, C.A.: Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear, edge-concave relaxations. Math. Program. 136(1), 155–182 (2012)
Misener, R., Floudas, C.A.: GloMIQO: global mixed-integer quadratic optimizer. J. Glob. Optim. 57(1), 3–50 (2013)
Misener, R., Floudas, C.A.: ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations. J. Glob. Optim. 59(2–3), 503–526 (2014)
Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225–249 (2005)
Hertz, D., Adjiman, C.S., Floudas, C.A.: Two results on bounding the roots of interval polynomials. Comput. Chem. Eng. 23, 1333–1339 (1999)
Skjäl, A., Westerlund, T., Misener, R., Floudas, C.A.: A generalization of the classical \(\alpha \text{ BB }\) convex underestimation via diagonal and nondiagonal quadratic terms. J. Optim. Theory Appl. 154(2), 462–490 (2012)
Skjäl, A., Westerlund, T.: New methods for calculating \(\alpha \text{ BB }\)-type underestimators. J. Glob. Optim. 58(3), 411–427 (2014)
Guzman, Y.A., Hasan, M.M.F., Floudas, C.A.: Performance of convex underestimators in a branch-and-bound global optimization framework. Optim. Lett. 10(2), 283–308 (2016)
Berna, T., Locke, M., Westerberg, A.W.: A new approach to optimization of chemical processes. AIChE J. 26(1), 37–43 (1980)
Acknowledgements
Financial support from the U.S. National Science Foundation (Award Number CBET-1606027) is gratefully acknowledged. M.M.F.H. likes to thank Dr. Yannis Guzman and Dr. Eric First for their help in comparing results with previous methods.
Author information
Authors and Affiliations
Corresponding author
Additional information
This article is dedicated to the memory of our dear mentor Professor Christodoulos A. Floudas, who died on 14 August 2016.
Rights and permissions
About this article
Cite this article
Hasan, M.M.F. An edge-concave underestimator for the global optimization of twice-differentiable nonconvex problems. J Glob Optim 71, 735–752 (2018). https://doi.org/10.1007/s10898-018-0646-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-018-0646-x