Abstract
In Part I (Gounaris, C.E., Floudas, C.A.: Tight convex understimators for \({\mathcal {C}^{2}}\)-continuous functions: I: Univariate functions. J. Global Optim. (2008). doi: 10.007/s10898-008-9287-9), we introduced a novel approach for the underestimation of univariate functions which was based on a piecewise application of the well-known αBB underestimator. The resulting underestimators were shown to be very tight and, in fact, can be driven to coincide with the convex envelopes themselves. An approximation by valid linear supports, resulting in piecewise linear underestimators was also presented. In this paper, we demonstrate how one can make use of the high quality results of the approach in the univariate case so as to extend its applicability to functions with a higher number of variables. This is achieved by proper projections of the multivariate αBB underestimators into select two-dimensional planes. Furthermore, since our method utilizes projections into lower-dimensional spaces, we explore ways to recover some of the information lost in this process. In particular, we apply our method after having transformed the original problem in an orthonormal fashion. This leads to the construction of even tighter underestimators, through the accumulation of additional valid linear cuts in the relaxation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Achenie, L.K.E., Biegler, L.T.: A superstructure based approach to chemical reactor network synthesis. Comput. Chem. Eng. 14, 23–40 (1990)
Adjiman, C.S., Floudas, C.A.: Rigorous convex underestimators for general twice-differentiable problems. J. Global Optim. 9, 23–40 (1996)
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, 1137–1158 (1998a)
Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: A global optimization method, αBB, for general twice-differentiable constrained NLPs II. Implementation and computational results. Comput. Chem. Eng. 22, 1159–1179 (1998b)
Aggarwal, A., Floudas, C.A.: Synthesis of general separation sequences—nonsharp separations. Comput. Chem. Eng. 14, 631–653 (1990)
Akrotirianakis, I.G., Floudas, C.A.: A new class of improved convex underestimators for twice continuously differentiable constrained NLPs. J. Global Optim. 30, 367–390 (2004a)
Akrotirianakis, I.G., Floudas, C.A.: Computational experience with an new class of convex underestimators: box-constrained NLP problems. J. Global Optim. 29, 249–264 (2004b)
Ali, M.M., Khompatraporn, C., Zabinsky, Z.B.: A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems. J. Global Optim. 31, 635–672 (2005)
Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8, 273–286 (1983)
Androulakis, I.P., Maranas, C.D., Floudas, C.A.: αBB: A global optimization method for general constrained nonconvex problems. J. Global Optim. 7, 337–363 (1995)
Caratzoulas, S., Floudas, C.A.: Trigonometric convex underestimator for the base functions in fourier space. J. Optim. Theory Appli. 124, 339–362 (2005)
Ciric, A.R., Floudas, C.A.: A retrofit approach of heat exchanger networks. Comp. Chem. Eng. 13, 703–715 (1989)
Esposito, W.R., Floudas, C.A.: Global optimization in parameter estimation of nonlinear algebraic models via the error-in-variables approach. Ind. Eng. Chem. Res. 35, 1841–1858 (1998)
Floudas, C.A.: Deterministic global optimization: Theory, Algorithms and Applications. Kluwer Academic Publishers (2000)
Floudas, C.A., Pardalos, P.M.: Preface. J. Glob Optim. 7, 113 (1995)
Floudas, C.A., Pardalos P.M.: Frontiers in global optimization. Kluwer Academic Publishers (2003)
Floudas, C.A.: Research challenges, opportunities and synergism in systems engineering and 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 and challenges. Comp. Chem. Eng. 29, 1185–1202 (2005)
Floudas, C.A., Fung, H.K., McAllister, S.R., Monnigmann, M., Rajgaria, R.: Advances in protein structure prediction and de novo protein design: a review. Chem. Eng. Sci. 61, 966–988 (2006)
Floudas, C.A., Kreinovich, V.: Towards optimal techniques for solving global optimization problems: symmetry-based approach. In: Torn, A., Zilinskas, J. (ed.) Models and Algorithms for Global Optimization, pp. 21–42. Springer (2007a)
Floudas, C.A., Kreinovich, V.: On the functional form of convex understimators for twice continuously differentiable functions. Optim. Lett. 1, 187–192 (2007b)
Ge, R.P., Qin, Y.F.: Globally convexized functions. Appl. Math Comput. 35, 131–158 (1990)
Gill, P.E., Murray, W., Saunders M.A., Wright, M.H.: User’s guide for NPSOL 5.0: a fortran package for nonlinear programming. Technical Report SOL 86–1 (1998)
Gounaris, C.E., Floudas, C.A.: Tight convex underestimators for \({\mathcal{C}^2}\) -continuous functions: I. Univariate functions. J. Global Optim. (2008). doi:10.1007/s10898-008-9287-9
Gümüş, Z.H., Floudas, C.A.: Global optimization of nonlinear bilevel programming problems. J. Global Optim. 20, 1–31 (2001)
Harding, S.T., Maranas, C.D., McDonald, C.M., Floudas, C.A.: Locating all homogeneous azeotropes in multicomponent mixtures. Ind. Eng. Chem. Res. 36, 160–178 (1997)
Horst, R., Pardalos, P.M., Thoai N.V.: Introduction to Global Optimization (Second Edition). Kluwer Academic Publishers, (2000)
Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 3rd ed. Springer (2003)
Kokossis, A.C., Floudas, C.A.: Optimization of complex reactor networks: I-isothermal operation. Chem. Eng. Sci. 43, 595–614 (1990)
Kokossis, A.C., Floudas, C.A.: Optimization of complex reactor networks: II-nonisothermal operation. Chem. Eng. Sci. 49, 1037–1051 (1994)
Liberti, L., Pantelides, C.C.: Convex envelopes of monomials of odd degree. J. Global Optim. 25, 157–168 (2003)
Maranas, C.D., Floudas, C.A.: Global minimum potential energy conformations of small molecules. J. Global Optim. 4, 135–170 (1994)
Maranas, C.D., Floudas, C.A.: Finding all solutions of nonlinearly constrained systems of equations. J. Global Optim. 7, 143–182 (1995)
Maranas, C.D., McDonald, C.M., Harding, S.T., Floudas, C.A.: Locating all azeotropes in homogeneous azeotropic systems. Comp. Chem. Eng. 20, S413–S418 (1996)
McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I – convex underestimating problems. Mathem. Prog. 10, 147–175 (1976)
McDonald, C.M., Floudas, C.A.: Decomposition based and branch and bound global optimization approaches for the phase equilibrium problem. J. Gl. Optim. 5, 205–251 (1994)
McDonald, C.M., Floudas, C.A.: Global optimization for the phase and chemical equilibrium problem: application to the NRTL Equation. Comp. Chem. Eng. 19, 1111–1141 (1995)
McDonald, C.M., Floudas, C.A.: GLOPEQ: a new computational tool for the phase and chemical equilibrium problem. Comp. Chem. Eng. 21, 1–23 (1997)
Meyer, C.A., Floudas, C.A.: Trilinear monomials with positive or negative domains: facets of the convex and concave envelopes. In: Floudas, C.A., Pardalos, P.M., (eds.) Frontiers in Global Optimization. Kluwer Academic Publishers (2003)
Meyer, C.A., Floudas, C.A.: Trilinear monomials with mixed sign domains: facets of the convex and concave envelopes. J. Global Optim. 29, 125–155 (2004)
Meyer, C.A., Floudas, C.A.: Convex envelopes for edge-concave functions. Math Prog. 103, 207–224 (2005)
Moré, J.J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained optimization software. ACM Trans. Math Software 7, 17–41 (1981)
Ryoo, H.S., Sahinidis, N.V.: Analysis of bounds for multilinear functions. J. Global Optim. 19, 403–424 (2001)
Sherali, H.D., Adams, W.P.: Reformulation-linearization techniques in discrete and continuous optimization. Kluwer Academic Publishers, (2002)
Tardella, F.: On the existence of polyhedral convex envelopes. In: Floudas, C.A., Pardalos, P.M., (eds) Frontiers in Global Optimization. Kluwer Academic Publishers (2003)
Tawarmalani, M., Sahinidis, N.V.: Semidefinite relaxations of fractional programs via novel convexification techniques. J. Global Optim. 20, 137–158 (2001)
Tawarmalani, M., Sahinidis, N.V.: Convexification and global optimization in continuous and mixed-integer nonlinear programming. Kluwer Academic Publishers (2002a)
Tawarmalani, M., Sahinidis, N.V.: Convex extensions and envelopes of lower semi-continuous functions. Math. Prog. 93, 247–263 (2002b)
Yee, T.F., Grossmann, I.E.: Simultaneous-optimization models for heat integration. 2-heat exchanger network synthesis. Comp. Chem. Eng. 14, 1165–1184 (1990)
Yeomans, H., Grossmann, I.E.: A systematic modeling framework of superstructure optimization in process synthesis. Comp. Chem. Eng. 23, 709–731 (1999)
Zabinsky, Z.B.: Stochastic Adaptive Search for Global Optimization. Kluwer Academic Publishers (2003)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gounaris, C.E., Floudas, C.A. Tight convex underestimators for \({\mathcal{C}^2}\) -continuous problems: II. multivariate functions. J Glob Optim 42, 69–89 (2008). https://doi.org/10.1007/s10898-008-9288-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-008-9288-8