Performance of convex underestimators in a branch-and-bound framework

详细信息    查看全文

• 作者：Yannis A. Guzman ; M. M. Faruque Hasan ; Christodoulos A. Floudas
• 关键词：Global optimization ; Convex underestimators ; Branch ; and ; bound
• 刊名：Optimization Letters
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：10
• 期：2
• 页码：283-308
• 全文大小：495 KB
• 参考文献：1.IBM: IBM ILOG CPLEX Optimization Studio (2013). http://​www.​cplex.​com
  2.Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: A global optimization method, \(\alpha \) BB, for general twice-differentiable constrained NLPs-II. Implementation and computational results. Comput. Chem. Eng. 22(9), 1159–1179 (1998b)
  3.Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A global optimization method, \(\alpha \) BB, for general twice-differentiable constrained NLPs-I. Theoretical advances. Comput. Chem. Eng. 22(9), 1137–1158 (1998a)
  4.Adjiman, C.S., Floudas, C.A.: Rigorous convex underestimators for general twice-differentiable problems. J. Global Optim. 9(1), 23–40 (1996)CrossRef MathSciNet MATH
  5.Akrotirianakis, I.G., Floudas, C.A.: A new class of improved convex underestimators for twice continuously differentiable constrained NLPs. J. Global Optim. 30(4), 367–390 (2004a)
  6.Akrotirianakis, I.G., Floudas, C.A.: Computational experience with a new class of convex underestimators: Box-constrained NLP problems. J. Global Optim. 29(3), 249–264 (2004b)
  7.Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273–286 (1983)CrossRef MathSciNet MATH
  8.Androulakis, I.P., Maranas, C.D., Floudas, C.A.: \(\alpha \) BB: a global optimization method for general constrained nonconvex problems. J. Global Optim. 7(4), 337–363 (1995)CrossRef MathSciNet MATH
  9.Bendtsen, C., Stauning, O.: Fadbad, a flexible C++ package for automatic differentiation. Department of Mathematical Modelling, Technical University of Denmark (1996)
  10.Brauer, A.: Limits for the characteristic roots of a matrix. II. Duke Math. J. 14(1), 21–26 (1947)CrossRef MathSciNet MATH
  11.Floudas, C.A.: Deterministic Global Optimization: Theory, Methods and Applications, vol. 37. Springer, Berlin (2000)
  12.Floudas, C.A., Pardalos, P.M., Adjiman, C.S., Esposito, W.R., Gumus, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems in Local and Global Optimization, vol. 33. Kluwer Academic Publishers, Dordrecht (1999)
  13.Gershgorin, S.A.: Über die abgrenzung der eigenwerte einer matrix. Izv. Akad. Nauk SSSR, Ser. Fiz.-Mat. 6, 749–754 (1931)
  14.Gill, P.E., Murray, W., Saunders, M.A.: User’s guide for SNOPT 5.3: a Fortran package for large-scale nonlinear programming. Technical Report (1999)
  15.Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: User’s guide for NPSOL (Version 4.0): a Fortran package for nonlinear programming. Technical Report, DTIC Document (1986)
  16.Gounaris, C.E., Floudas, C.A.: Tight convex underestimators for \({\cal {C}}^2\) -continuous problems: II. Multivariate functions. J. Global Optim. 42(1), 69–89 (2008)CrossRef MathSciNet MATH
  17.Hansen, E.R.: Sharpness in interval computations. Reliab. Comput. 3(1), 17–29 (1997)CrossRef MathSciNet MATH
  18.Hladík, M.: The effect of hessian evaluations in the global optimization \(\alpha \) BB method, Preprint (2013). http://​arxiv.​org/​abs/​1307.​2791
  19.Kvasov, D.E., Sergeyev, Y.D.: Lipschitz gradients for global optimization in a one-point-based partitioning scheme. J. Comput. Appl. Math. 236(16), 4042–4054 (2012)CrossRef MathSciNet MATH
  20.Lasserre, J., Thanh, T.: Convex underestimators of polynomials. J. Global Optim. 56(1), 1–25 (2013)CrossRef MathSciNet MATH
  21.Lera, D., Sergeyev, Y.D.: Acceleration of univariate global optimization algorithms working with lipschitz functions and lipschitz first derivatives. SIAM J. Optim. 23(1), 508–529 (2013)CrossRef MathSciNet MATH
  22.Maranas, C.D., Floudas, C.A.: A global optimization approach for Lennard–Jones microclusters. J. Chem. Phys. 97(10), 7667–7678 (1992)CrossRef
  23.Maranas, C.D., Floudas, C.A.: A deterministic global optimization approach for molecular structure determination. J. Chem. Phys. 100(2), 1247–1261 (1994a)CrossRef MathSciNet
  24.Maranas, C.D., Floudas, C.A.: Global minimum potential energy conformations of small molecules. J. Global Optim. 4(2), 135–170 (1994)CrossRef MathSciNet MATH
  25.Maranas, C.D., Floudas, C.A.: Finding all solutions of nonlinearly constrained systems of equations. J. Global Optim. 7(2), 143–182 (1995)CrossRef MathSciNet MATH
  26.McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part I—convex underestimating problems. Math. Program. 10(1), 147–175 (1976)CrossRef MathSciNet MATH
  27.Meyer, C.A., Floudas, C.A.: Trilinear monomials with positive or negative domains: facets of the convex and concave envelopes. Nonconvex Optim. Appl. 74, 327–352 (2003)CrossRef MathSciNet
  28.Meyer, C.A., Floudas, C.A.: Trilinear monomials with mixed sign domains: facets of the convex and concave envelopes. J. Global Optim. 29(2), 125–155 (2004)CrossRef MathSciNet MATH
  29.Meyer, C.A., Floudas, C.A.: Convex underestimation of twice continuously differentiable functions by piecewise quadratic perturbation: spline \(\alpha \) BB underestimators. J. Global Optim. 32(2), 221–258 (2005)CrossRef MathSciNet MATH
  30.Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3), 969–984 (1993)CrossRef MathSciNet MATH
  31.Rohn, J.: Bounds on eigenvalues of interval matrices. Zeitschrift fr Angewandte Mathematik und Mechanik 78(S3), 1049–1050 (1998)CrossRef MathSciNet
  32.Sergeyev, Y.D., Strongin, R.G., Lera, D.: Introduction to Global Optimization Exploiting Space-Filling Curves. Springer, Berlin (2013)CrossRef MATH
  33.Skjäl, A., Westerlund, T.: New methods for calculating \(\alpha \) BB-type underestimators. J. Global Optim. 58(3), 411–427 (2014)CrossRef MathSciNet MATH
  34.Skjäl, A., Westerlund, T., Misener, R., Floudas, C.: A generalization of the classical \(\alpha \) BB convex underestimation via diagonal and nondiagonal quadratic terms. J. Optim. Theory Appl. 154(2), 462–490 (2012)CrossRef MathSciNet MATH
  35.Surjanovic, S., Bingham, D.: Virtual library of simulation experiments: test functions and datasets (2013). http://​www.​sfu.​ca/​~ssurjano/​optimization.​html
  36.Tawarmalani, M., Sahinidis, N.V.: Semidefinite relaxations of fractional programs via novel convexification techniques. J. Global Optim. 20(2), 133–154 (2001)CrossRef MathSciNet
  37.Tawarmalani, M., Sahinidis, N.V.: Convex extensions and envelopes of lower semi-continuous functions. Math. Program. 93(2), 247–263 (2002)CrossRef MathSciNet MATH
  38.Whaley, R.C., Petitet, A.: Minimizing development and maintenance costs in supporting persistently optimized BLAS. Softw. Pract. Experience 35(2), 101–121 (2005)CrossRef
  39.Yamashita, M., Fujisawa, K., Nakata, K., Nakata, M., Fukuda, M., Kobayashi, K., Goto, K.: A high-performance software package for semidefinite programs: SDPA 7. Technical Report B-460, Department of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo, Japan (2010)
  
• 作者单位：Yannis A. Guzman (1)
  M. M. Faruque Hasan (1) (2)
  Christodoulos A. Floudas (1)
  
  1. Department of Chemical and Biological Engineering, Princeton University, Princeton, NJ, 08544, USA
  2. Artie McFerrin Department of Chemical Engineering, Texas A&M University, College Station, Texas, 77843, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480

文摘

The efficient determination of tight lower bounds in a branch-and-bound algorithm is crucial for the global optimization of models spanning numerous applications and fields. The global optimization method \(\alpha \)-branch-and-bound (\(\alpha \)BB, Adjiman et al. in Comput Chem Eng 22(9):1159–1179, 1998b, Comput Chem Eng 22(9):1137–1158, 1998a; Adjiman and Floudas in J Global Optim 9(1):23–40, 1996; Androulakis et al. J Global Optim 7(4):337–363, 1995; Floudas in Deterministic Global Optimization: Theory, Methods and Applications, vol. 37. Springer, Berlin, 2000; Maranas and Floudas in J Chem Phys 97(10):7667–7678, 1992, J Chem Phys 100(2):1247–1261, 1994a, J Global Optim 4(2):135–170, 1994), guarantees a global optimum with \(\epsilon \)-convergence for any \(\mathcal {C}^2\)-continuous function within a finite number of iterations via fathoming nodes of a branch-and-bound tree. We explored the performance of the \(\alpha \)BB method and a number of competing methods designed to provide tight, convex underestimators, including the piecewise (Meyer and Floudas in J Global Optim 32(2):221–258, 2005), generalized (Akrotirianakis and Floudas in J Global Optim 30(4):367–390, 2004a, J Global Optim 29(3):249–264, 2004b), and nondiagonal (Skjäl et al. in J Optim Theory Appl 154(2):462–490, 2012) \(\alpha \)BB methods, the Brauer and Rohn+E (Skjäl et al. in J Global Optim 58(3):411–427, 2014) \(\alpha \)BB methods, and the moment method (Lasserre and Thanh in J Global Optim 56(1):1–25, 2013). Using a test suite of 40 multivariate, box-constrained, nonconvex functions, the methods were compared based on the tightness of generated underestimators and the efficiency of convergence of a branch-and-bound global optimization algorithm. Keywords Global optimization Convex underestimators Branch-and-bound