×

A generalization of the classical \(\alpha \)BB convex underestimation via diagonal and nondiagonal quadratic terms. (English) Zbl 1256.90038

Summary: The classical \(\alpha \)BB method determines univariate quadratic perturbations that convexify twice continuously differentiable functions. This paper generalizes \(\alpha \)BB to additionally consider nondiagonal elements in the perturbation Hessian matrix. These correspond to bilinear terms in the underestimators, where previously all nonlinear terms were separable quadratic terms. An interval extension of Gerschgorin’s circle theorem guarantees convexity of the underestimator. It is shown that underestimation parameters which are optimal, in the sense that the maximal underestimation error is minimized, can be obtained by solving a linear optimization model.
Theoretical results are presented regarding the instantiation of the nondiagonal underestimator that minimizes the maximum error. Two special cases are analyzed to convey an intuitive understanding of that optimally-selected convexifier. Illustrative examples that convey the practical advantage of these new \(\alpha \)BB underestimators are presented.

MSC:

90C26 Nonconvex programming, global optimization

Software:

ROSE; RealPaver; libMC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: A global optimization method, {\(\alpha\)}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
[2] Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A global optimization method, {\(\alpha\)}BB, for general twice differentiable NLPs-I. Theoretical advances. Comput. Chem. Eng. 22, 1137–1158 (1998) · doi:10.1016/S0098-1354(98)00027-1
[3] 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
[4] Floudas, C.A.: Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, New York (1995) · Zbl 0886.90106
[5] Floudas, C.A.: Deterministic Global Optimization: Theory, Methods and Applications. Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht (2000)
[6] Floudas, C.A., Gounaris, C.E.: A review of recent advances in global optimization. J. Glob. Optim. 45, 3–38 (2009) · Zbl 1180.90245 · doi:10.1007/s10898-008-9332-8
[7] Floudas, C.A., Pardalos, P.M.: State-of-the-art in global optimization–computational methods and applications–preface. J. Glob. Optim. 7, 113 (1995) · Zbl 0843.00057 · doi:10.1007/BF01097056
[8] Floudas, C.A., Akrotirianakis, I.G., Caratzoulas, S., Meyer, C.A., Kallrath, J.: Global optimization in the 21st century: advances and challenges. Comput. Chem. Eng. 29, 1185–1202 (2005) · doi:10.1016/j.compchemeng.2005.02.006
[9] Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht (1999) · Zbl 0926.90078
[10] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Norwell (2002) · Zbl 1031.90022
[11] 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) · Zbl 1133.90420 · doi:10.1023/B:JOGO.0000044768.75992.10
[12] 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) · Zbl 1082.90090 · doi:10.1007/s10898-004-6455-4
[13] Akrotirianakis, I.G., Meyer, C.A., Floudas, C.A.: The role of the off-diagonal elements of the Hessian matrix in the construction of tight convex underestimators for nonconvex functions. In: Discovery Through Product and Process Design. Foundations of Computer-Aided Process Design, pp. 501–504 (2004)
[14] 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
[15] 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
[16] Liberti, L.: Reformulations in mathematical programming: automatic symmetry detection and exploitation. Math. Program. (2010). doi: 10.1007/s10107-010-0351-0 · Zbl 1235.90103
[17] Liberti, L., Cafieri, S., Tarissan, F.: Reformulations in mathematical programming: A computational approach. In: Abraham, A., Hassanien, A.E., Siarry, P. (eds.) Foundations of Computational Intelligence, vol. 3, pp. 153–234. Springer, New York (2009)
[18] Smith, E.M.B., Pantelides, C.C.: A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23(4–5), 457–478 (1999) · doi:10.1016/S0098-1354(98)00286-5
[19] Tawarmalani, M., Sahinidis, N.V.: 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
[20] McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part 1–convex underestimating problems. Math. Program. 10, 147–175 (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665
[21] Mitsos, A., Chachuat, B., Barton, P.I.: McCormick-based relaxations of algorithms. SIAM J. Optim. 20, 573–601 (2009) · Zbl 1192.65083 · doi:10.1137/080717341
[22] Scott, J.K., Stuber, M.D., Barton, P.I.: Generalized McCormick relaxations. J. Glob. Optim. 51, 569–606 (2011) · Zbl 1232.49033 · doi:10.1007/s10898-011-9664-7
[23] Bompadre, A., Mitsos, A.: Convergence rate of McCormick relaxations. J. Glob. Optim. 52, 1–28 (2011) · Zbl 1257.90077 · doi:10.1007/s10898-011-9685-2
[24] Gatzke, E.P., Tolsma, J.E., Barton, P.I.: Construction of convex relaxations using automated code generation techniques. Optim. Eng. 3, 305–326 (2002) · Zbl 1035.90063 · doi:10.1023/A:1021095211251
[25] Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: Global optimization of MINLP problems in process synthesis and design. Comput. Chem. Eng. 21(Suppl. S), S445–S450 (1997)
[26] Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: Global optimization of mixed-integer nonlinear problems. AIChE J. 46, 1769–1797 (2000) · doi:10.1002/aic.690460908
[27] Maranas, C.D., Floudas, C.A.: A global optimization approach for Lennard-Jones microclusters. J. Chem. Phys. 97, 7667–7678 (1992) · doi:10.1063/1.463486
[28] Zlobec, S.: On the Liu-Floudas convexification of smooth programs. J. Glob. Optim. 32, 401–407 (2005) · Zbl 1149.90409 · doi:10.1007/s10898-004-3134-4
[29] Zlobec, S.: Characterization of convexifiable functions. Optimization 55, 251–261 (2006) · Zbl 1124.90038 · doi:10.1080/02331930600711968
[30] Zlobec, S.: Saddle-point optimality: A look beyond convexity. J. Glob. Optim. 29, 97–112 (2004) · Zbl 1073.90031 · doi:10.1023/B:JOGO.0000035004.66019.3b
[31] Zlobec, S.: On two simple decompositions of Lipschitz functions. Optimization 57, 249–261 (2008) · Zbl 1134.90503 · doi:10.1080/02331930701779880
[32] Androulakis, I.P., Maranas, C.D., Floudas, C.A.: {\(\alpha\)}BB: A global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7, 337–363 (1995) · Zbl 0846.90087 · doi:10.1007/BF01099647
[33] Adjiman, C.S., Floudas, C.A.: Rigorous convex underestimators for general twice-differentiable problems. J. Glob. Optim. 9, 23–40 (1996) · Zbl 0862.90114 · doi:10.1007/BF00121749
[34] Chang, M.H., Park, Y.C., Lee, T.Y.: A new global optimization method for univariate constrained twice-differentiable NLP problems. J. Glob. Optim. 39, 79–100 (2007) · Zbl 1156.65057 · doi:10.1007/s10898-006-9121-1
[35] Birgin, E., Floudas, C.A., Martínez, J.: Global minimization using an augmented Lagrangian method with variable lower-level constraints. Math. Program. 125, 139–162 (2010) · Zbl 1198.90322 · doi:10.1007/s10107-009-0264-y
[36] Bravo, J.M., Alamo, A.T., Redondo, M.J., Camacho, E.F.: An algorithm for bounded-error identification of nonlinear systems based on DC functions. Automatica 44, 437–444 (2008) · Zbl 1283.93086 · doi:10.1016/j.automatica.2007.05.026
[37] 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. 37, 1841–1858 (1998) · doi:10.1021/ie970852g
[38] Esposito, W.R., Floudas, C.A.: Deterministic global optimization in nonlinear optimal control problems. J. Glob. Optim. 17, 97–126 (2000) · Zbl 0980.49027 · doi:10.1023/A:1026578104213
[39] Esposito, W.R., Floudas, C.A.: Global optimization for the parameter estimation of differential-algebraic systems. Ind. Eng. Chem. Res. 39, 1291–1310 (2000) · doi:10.1021/ie990486w
[40] Esposito, W.R., Floudas, C.A.: Deterministic global optimization in isothermal reactor network synthesis. J. Glob. Optim. 22, 59–95 (2002) · Zbl 1045.90094 · doi:10.1023/A:1013842726210
[41] Floudas, C.A., Stein, O.: The adaptive convexification algorithm: a feasible point method for semi-infinite programming. SIAM J. Optim. 18, 1187–1208 (2007) · Zbl 1216.90094 · doi:10.1137/060657741
[42] Floudas, C.A., Gümüs, Z.H., Ierapetritou, M.G.: Global optimization in design under uncertainty: feasibility test and flexibility index problems. Ind. Eng. Chem. Res. 40, 4267–4282 (2001) · doi:10.1021/ie001014g
[43] Gümüs, Z.H., Floudas, C.A.: Global optimization of nonlinear bilevel programming problems. J. Glob. Optim. 20, 1–31 (2001) · Zbl 1049.90092 · doi:10.1023/A:1011268113791
[44] Klepeis, J.L., Floudas, C.A.: A comparative study of global minimum energy conformations of hydrated peptides. J. Comput. Chem. 20, 636–654 (1999) · doi:10.1002/(SICI)1096-987X(19990430)20:6<636::AID-JCC10>3.0.CO;2-D
[45] Klepeis, J.L., Floudas, C.A.: Free energy calculations for peptides via deterministic global optimization. J. Chem. Phys. 110, 7491–7512 (1999) · doi:10.1063/1.478652
[46] Klepeis, J.L., Floudas, C.A.: Deterministic global optimization and torsion angle dynamics for molecular structure prediction. Comput. Chem. Eng. 24, 1761–1766 (2000) · doi:10.1016/S0098-1354(00)00461-0
[47] Klepeis, J.L., Floudas, C.A.: Ab initio tertiary structure prediction of proteins. J. Glob. Optim. 25, 113–140 (2003) · Zbl 1045.92018 · doi:10.1023/A:1021331514642
[48] Klepeis, J.L., Floudas, C.A.: ASTRO-FOLD: a combinatorial and global optimization framework for ab initio prediction of three-dimensional structures of proteins from the amino acid sequence. Biophys. J. 85, 2119–2146 (2003) · doi:10.1016/S0006-3495(03)74640-2
[49] Klepeis, J.L., Floudas, C.A., Morikis, D., Lambris, J.D.: Predicting peptide structures using NMR data and deterministic global optimization. J. Comput. Chem. 20, 1354–1370 (1999) · doi:10.1002/(SICI)1096-987X(199910)20:13<1354::AID-JCC3>3.0.CO;2-N
[50] Klepeis, J.L., Pieja, M., Floudas, C.A.: A new class of hybrid global optimization algorithms for peptide structure prediction: integrated hybrids. Comput. Phys. Commun. 151, 121–140 (2003) · Zbl 1196.90134 · doi:10.1016/S0010-4655(02)00735-X
[51] Maranas, C.D., Floudas, C.A.: A deterministic global optimization approach for molecular-structure determination. J. Chem. Phys. 100, 1247–1261 (1994) · doi:10.1063/1.467236
[52] McDonald, C.M., Floudas, C.A.: Decomposition based and branch and bound global optimization approaches for the phase equilibrium problem. J. Glob. Optim. 5, 205–251 (1994) · Zbl 0820.90100 · doi:10.1007/BF01096454
[53] McDonald, C.M., Floudas, C.A.: Global optimization for the phase and chemical equilibrium problem: application to the NRTL equation. Comput. Chem. Eng. 19, 1111–1141 (1995) · doi:10.1016/0098-1354(94)00106-5
[54] McDonald, C.M., Floudas, C.A.: Global optimization for the phase stability problem. AIChE J. 41, 1798–1814 (1995) · doi:10.1002/aic.690410715
[55] McDonald, C.M., Floudas, C.A.: Global optimization and analysis for the Gibbs free energy function for the UNIFAC, Wilson, and ASOG equations. Ind. Eng. Chem. Res. 34, 1674–1687 (1995) · doi:10.1021/ie00044a020
[56] Mitsos, A., Lemonidis, P., Lee, C.K., Barton, P.I.: Relaxation-based bounds for semi-infinite programs. SIAM J. Optim. 19, 77–113 (2008) · Zbl 1163.90035 · doi:10.1137/060674685
[57] Papamichail, I., Adjiman, C.S.: A rigorous global optimization algorithm for problems with ordinary differential equations. J. Glob. Optim. 24, 1–33 (2002) · Zbl 1026.90071 · doi:10.1023/A:1016259507911
[58] Papamichail, I., Adjiman, C.S.: Proof of convergence for a global optimization algorithm for problems with ordinary differential equations. J. Glob. Optim. 33, 83–107 (2005) · Zbl 1093.90060 · doi:10.1007/s10898-004-6100-2
[59] Zhu, Y.S., Inoue, K.: Calculation of chemical and phase equilibrium based on stability analysis by QBB algorithm: application to NRTL equation. Chem. Eng. Sci. 56, 6915–6931 (2001) · doi:10.1016/S0009-2509(01)00336-0
[60] 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
[61] Floudas, C.A., Kreinovich, V.: Towards optimal techniques for solving global optimization problems: Symmetry-based approach. In: Törn, A., Zilinskas, J. (eds.) Models and Algorithms for Global Optimization, pp. 21–42. Springer, New York (2007) · Zbl 1267.90105
[62] Meyer, C.A., Floudas, C.A.: Convex underestimation of twice continuously differentiable functions by piecewise quadratic perturbation: spline {\(\alpha\)}BB underestimators. J. Glob. Optim. 32, 221–258 (2005) · Zbl 1080.90059 · doi:10.1007/s10898-004-2704-9
[63] Gounaris, C.E., Floudas, C.A.: Tight convex underestimators for $\(\backslash\)mathcal {C}\^{2}$ -continuous problems: I. Univariate functions. J. Glob. Optim. 42, 51–67 (2008) · Zbl 1173.90503 · doi:10.1007/s10898-008-9287-9
[64] Gounaris, C.E., Floudas, C.A.: Tight convex underestimators for $\(\backslash\)mathcal {C}\^{2}$ -continuous problems: II. Multivariate functions. J. Glob. Optim. 42, 69–89 (2008) · Zbl 1170.90459 · doi:10.1007/s10898-008-9288-8
[65] Neumaier, A.: Interval Methods for Systems of Equations. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (1990) · Zbl 0715.65030
[66] Wolfe, M.A.: Interval mathematics, algebraic equations and optimization. J. Comput. Appl. Math. 124, 263–280 (2000) · Zbl 0994.65052 · doi:10.1016/S0377-0427(00)00421-0
[67] Domes, F., Neumaier, A.: Constraint propagation on quadratic constraints. Constraints 15, 404–429 (2010) · Zbl 1208.68200 · doi:10.1007/s10601-009-9076-1
[68] Granvilliers, L., Benhamou, F.: Algorithm 852: RealPaver: an interval solver using constraint satisfaction techniques. ACM Trans. Math. Softw. 32, 138–156 (2006) · Zbl 1346.65020 · doi:10.1145/1132973.1132980
[69] Gerschgorin, S.: Über die abgrenzung der eigenwerte einer matrix. Izv. Akad. Nauk SSSR, Ser. Fiz. Mat. 6, 749–754 (1931) · Zbl 0003.00102
[70] Tardella, F.: On a class of functions attaining their maximum at the vertices of a polyhedron. Discrete Appl. Math. 22, 191–195 (1988/89) · Zbl 0663.90068 · doi:10.1016/0166-218X(88)90093-5
[71] Tardella, F.: Existence and sum decomposition of vertex polyhedral convex envelopes. Optim. Lett. 2, 363–375 (2008) · Zbl 1152.90614 · doi:10.1007/s11590-007-0065-2
[72] Vanderbei, R.J.: Linear Programming: Foundations and Extensions. International Series in Operations Research &amp; Management Science. Springer, Berlin (2008). ISBN 9780387743875
[73] Hertz, D., Adjiman, C.S., Floudas, C.A.: Two results on bounding the roots of interval polynomials. Comput. Chem. Eng. 23, 1333–1339 (1999) · doi:10.1016/S0098-1354(99)00292-6
[74] 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. Kluwer Academic Publishers, Dordrecht (1999) · Zbl 0943.90001
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.