Deterministic global optimization in ab-initio quantum chemistry. (English) Zbl 1275.90065

Summary: A large number of problems in ab-initio quantum chemistry involve finding the global minimum of the total system energy. These problems are traditionally solved by numerical approaches equivalent to local optimization. While these approaches are relatively efficient, they do not provide guarantees of global optimality unless a starting point sufficiently close to the global minimum is known a priori. Due to the enormous amount of computational effort required to solve these problems, more mathematically rigorous alternatives have so far received very little attention. Taking the above issue into consideration, this paper explores the use of deterministic global optimization in the context of the Hartree-Fock theory, an important mathematical model applied in many quantum chemistry methods. In particular, it presents a general purpose approach for generating linear relaxations for problems arising from the Hartree-Fock theory. This is then implemented as an extension to the COUENNE (convex over and under envelopes for nonlinear estimation) branch and bound mixed integer nonlinear programs solver. The proof of concept calculations that simultaneously optimise the orbital coefficients and the location of the nuclei in closed-shell Hartree-Fock calculations are presented and discussed.


90C26 Nonconvex programming, global optimization
90C90 Applications of mathematical programming
Full Text: DOI


[1] Adjiman C.S., Dallwig S., Floudas C.A., Neumaier A.: A global optimization method, αBB, for general twice-differentiable constrained NLPs - I. Theor Adv Comput Chem Eng 22, 1137-1158 (1998)
[2] Adjiman C.S., Androulakis I.P., Floudas C.A.: A global optimization method, αBB, for general twice-differentiable constrained NLPs - II. Implement Comput Resul Comput Chem Eng 22, 1159-1179 (1998)
[3] Belotti, P., Lee, J., Liberti, L., Margot, F., Waechter, A.: Branching and bounds tightening techniques for non-convex minlp. Technical report RC24620 (W0808-031), IBM, August 2008 · Zbl 1179.90237
[4] Bonami P., Biegler L.T., Conn A.R., Cornuéjols G., Grossmann I.E., Laird C.D., Lee J., Lodi A., Margot F., Sawaya N., Wächter A.: An algorithmic framework for convex mixed integer nonlinear programs. Discret. Opt. 5(2), 186-204 (2008) In Memory of George B. Dantzig · Zbl 1151.90028
[5] Bouferguene A., Fares M., Hoggan P.E.: STOP: a slater-type orbital package for molecular electronic structure determination. Int. J. Quantum Chem. 57(4), 801-810 (1996)
[6] Brook A., Kendrick D., Meeraus A.: GAMS, a user’s guide. SIGNUM Newsl. 23, 10-11 (1988)
[7] Cafieri S., Lee J., Liberti L.: On convex relaxations of quadrilinear terms. J. Glob. Optim. 47, 661-685 (2010) · Zbl 1202.90236
[8] Crainic T., Cun B., Roucairol C.: Parallel branch-and-bound algorithms, chapter 1. Wiley, New Yok (2006)
[9] Daven D.M., Tit N., Morris J.R., Ho K.M.: Structural optimization of Lennard-Jones clusters by a genetic algorithm. Chem. Phys. Lett. 256(1-2), 195-200 (1996)
[10] Doll K., Schön J.C., Jansen M.: Structure prediction based on ab initio simulated annealing for boron nitride. Phys. Rev. B 78, 144110 (2008)
[11] Falk J.E., Soland R.M.: An algorithm for separable nonconvex programming. Manag. Sci. 15, 550-569 (1969) · Zbl 0172.43802
[12] Floudas C.A., Gounaris C.E.: A review of recent advances in global optimization. J. Glob. Optim. 45, 3-38 (2009) · Zbl 1180.90245
[13] Floudas C.A.: Deterministic Global Optimization: Theory, Methods and Applications. Springer, Secaucus, NJ (2005)
[14] Foresman J.B., Frisch A.: Exploring Chemistry with Electronic Structure Methods. Gaussian, Inc, New Haven (1996)
[15] Forrest, J., Lougee-Heimer, R.: CBC user guide. IBM (2005). Accessed 7 Feb 2011
[16] Forrest, J., de la Nuez, D., Lougee-Heimer, R.: CLP user guide. IBM (2004). Accessed 7 Feb 2011
[17] Fourer, R., Gay, D.M., Kernighan, B. (1989) Algorithms and model formulations in mathematical programming. Chapter AMPL: A Mathematical Programming Language, pp. 150-151. Springer, New York
[18] Frisch M.J., Trucks G.W., Schlegel H.B., Scuseria G.E., Robb M.A., Cheeseman J.R., Montgomery J.A. Jr., Vreven T., Kudin K.N., Burant J.C., Millam J.M., Iyengar S.S., Tomasi J., Barone V., Mennucci B., Cossi M., Scalmani G., Rega N., Petersson G.A., Nakatsuji H., Hada M., Ehara M., Toyota K., Fukuda R., Hasegawa J., Ishida M., Nakajima T., Honda Y., Kitao O., Nakai H., Klene M., Li X., Knox J.E., Hratchian H.P., Cross J.B., Bakken V., Adamo C., Jaramillo J., Gomperts R., Stratmann R.E., Yazyev O., Austin A.J., Cammi R., Pomelli C., Ochterski J.W., Ayala P.Y., Morokuma K., Voth G.A., Salvador P., Dannenberg J.J., Zakrzewski V.G., Dapprich S., Daniels A.D., Strain M.C., Farkas O., Malick D.K., Rabuck A.D., Raghavachari K., Foresman J.B., Ortiz J.V., Cui Q., Baboul A.G., Clifford S., Cioslowski J., Stefanov B.B., Liu G., Liashenko A., Piskorz P., Komaromi I., Martin R.L., Fox D.J., Keith T., Al-Laham M.A., Peng C.Y., Nanayakkara A., Challacombe M., Gill P.M.W., Johnson B., Chen W., Wong M.W., Gonzalez C., Pople J.A.: Gaussian 03, Revision C.02. Gaussian, Inc, Wallingford (2004)
[19] GAMS Development Corp (2011) GAMS—the solver manuals. Technical report, Washington, July 2011
[20] Gattupalli R., Lucia A.: Molecular conformation of n-alkanes using terrain/funneling methods. J. Glob. Optim. 43, 429-444 (2009). doi:10.1007/s10898-007-9206-5 · Zbl 1279.90134
[21] Gill P.M.W.: Molecular integrals over gaussian basis functions. Adv. Quantum Chem. 25, 141-205 (1994)
[22] Gill P.M.W., Johnson B.G., Pople J.A.: Two-electron repulsion integrals over gaussian s functions. Int. J. Quantum Chem. 40, 745-752 (1991)
[23] Head-Gordon M., Pople J.A.: A method for two-electron gaussian integral and integral derivative evaluation using recurrence relations. J. Comput. Phys. 26, 218-231 (1978)
[24] Holland J.H.: Genetic algorithms and the optimal allocation of trials. SIAM J. Comput. 2(2), 88-105 (1973) · Zbl 0259.90031
[25] Horst R., Pardalos P.M.: Handbook of Global Optimization. Kluwer, Dordrecht (1995) · Zbl 0805.00009
[26] ILOG CPLEX 10.0 User’s Manual, January 2006
[27] Kearfott B.R.: Rigorous Global Search: Continuous Problems. Kluwer, Dordrecht (1996) · Zbl 0876.90082
[28] Kirkpatrick S., Gelatt C.D., Vecchi M.P.: Optimization by simulated annealing. Science 220(4598), 671-680 (1983) · Zbl 1225.90162
[29] Klepeis J.L., Floudas C.A.: Comparative study of global minimum energy conformations of hydrated peptides. J. Comput. Chem. 20(6), 636-654 (1999)
[30] 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(13), 1354-1370 (1999)
[31] Klepeis J.L., Androulakis I.P., Ierapetritou M.G., Floudas C.A.: Predicting solvated peptide conformations via global minimization of energetic atom-to-atom interactions. Comput. Chem. Eng 22(6), 765-788 (1998)
[32] Klepeis J.L., Pieja M.J., Floudas C.A.: A new class of hybrid global optimization algorithms for peptide structure prediction: integrated hybrids. Comput. Phys. Commun. 151(2), 121-140 (2003) · Zbl 1196.90134
[33] Klepeis, J.; Floudas, C.; Floudas, C. A. (ed.); Pardalos, P. M. (ed.), Multiple minima problem in protein folding: abb global optimization approach, 1644-1651 (2001), USA
[34] Land A.H., Doig A.G.: An automatic method of solving discrete programming problems. Econometrica 28(3), 497-520 (1960) · Zbl 0101.37004
[35] Lavor C.: A deterministic approach for global minimization of molecular potential energy functions. Int. J. Quantum Chem. 95(3), 336-343 (2003)
[36] Lavor, C.; Liberti, L.; Maculan, N.; Pintér, J. D. (ed.); Pardalos, P. (ed.), Computational experience with the molecular distance geometry problem, 213-225 (2006), USA · Zbl 1129.90389
[37] Lavor C.C., Cardozo T.M., ChaerNascimento M.A.: Using an interval branch-and-bound algorithm in the Hartree-Fock method. Int. J. Quantum Chem. 103(5), 500-504 (2005)
[38] Lavor C., Liberti L., Maculan N., Nascimento M.A.C.: Solving Hartree-Fock systems with global optimization methods. Europhys. Lett. 77(5), 50006 (2007)
[39] Liberti, L.: Ev3: a library for symbolic computation in c++ using n-ary trees lix,. Technical report, LIX, Ecole Polytechnique 91128 Palaiseau, France (2003) · Zbl 0841.90115
[40] Liberti, L.: Reformulation and convex relaxation techniques for global optimization. PhD thesis, Imperial College of Science, Technology and Medicine, University of London, March 2004 · Zbl 1136.90442
[41] Liberti L., Lavor C., Maculan N., Nascimento M.A.C.: Reformulation in mathematical programming: an application to quantum chemistry. Discret. Appl. Math. 157, 1309-1318 (2009) · Zbl 1173.90494
[42] Liberti L., Pantelides C.C.: Convex envelopes of monomials of odd degree. J. Glob. Optim. 25, 157-168 (2003). doi:10.1023/A:1021924706467 · Zbl 1030.90117
[43] Lin Y., Schrage L.: The global solver in the LINDO API. Optim. Methods Softw. 24, 657-668 (2009) · Zbl 1177.90325
[44] Lin Y., Stadtherr M.A.: Deterministic global optimization of molecular structures using interval analysis. J. Comput. Chem. 26(13), 1413-1420 (2005)
[45] Little J.D., Murty K.C., Sweeney D.W., Karel C.: An algorithm for the travelling salesman problem. Oper. Res. 11, 972-989 (1963) · Zbl 0161.39305
[46] Lougee-Heimer R.: The common optimization interface for operations research: Promoting open-source software in the operations research community. IBM J. Res. Dev. 47, 57-66 (2003)
[47] Makino, K.; Berz, M.; Berz, M. (ed.); Bischof, C. (ed.); Corliss, G. (ed.); Griewank, A. (ed.), Remainder differential algebras and their applications, 63-74 (1996), Philadelphia · Zbl 0867.68062
[48] Maranas C.D., Floudas C.A.: A global optimization approach for Lennard-Jones microclusters. J. Chem. Phys. 97(10), 7667-7678 (1992)
[49] Maranas C.D., Floudas C.A.: Finding all solutions of nonlinearly constrained systems of equations. J. Glob. Optim. 7, 143-182 (1995). doi:10.1007/BF01097059 · Zbl 0841.90115
[50] McCormick G.P.: Computability of global solutions to factorable nonconvex programs: part i—convex underestimating problems. Math. Program. 10, 147-175 (1976). doi:10.1007/BF01580665 · Zbl 0349.90100
[51] McCormick, G.P.: Converting general nonlinear programming problems to separable nonlinear programming problems. Technical report T-267, George Washington University, Washington, DC (1972) · Zbl 0172.43802
[52] McMurchie L.E., Davidson E.R.: One- and two-electron integrals over cartesian guassian functions. J. Chem. Phys. 89(9), 5777-5786 (1988) · Zbl 1370.78045
[53] Nakatsuji H.: Structure of the exact wave function. J. Chem. Phys. 113(8), 2949-2956 (2000) · Zbl 1014.80007
[54] Neumaier A., Shcherbina O., Huyer W., Vinkó T.: A comparison of complete global optimization solvers. Math. Program. 103, 335-356 (2005). doi:10.1007/s10107-005-0585-4 · Zbl 1099.90001
[55] Obara S., Saika A.: Efficient recursive computation of molecular integrals over cartesian gaussian functions. J. Chem. Phys. 84(7), 3963 (1986)
[56] Rinnooy K.A., Timmer G.: Stochastic global optimization methods part i: clustering methods. Math. Program. 39, 27-56 (1987). doi:10.1007/BF02592070 · Zbl 0634.90066
[57] Sahinidis N.V.: BARON Branch and Reduce Optimization Navigator User’s Manual Version 4.0. Univeristy of Illinois at Urbana-Champaign, Illinois (2000)
[58] Sahni S.: Computationally related problems. SIAM J. Comput. 3(4), 262-279 (1974) · Zbl 0272.68040
[59] Schuchardt K.L., Didier B.T., Elsethagen T., Sun L., Gurumoorthi V., Chase J., Li J., Windus T.L.: Basis set exchange:? a community database for computational sciences. J. Chem. Inf. Model. 47(3), 1045-1052 (2007)
[60] Smith, E.: On the optimal design of continuous processes. PhD thesis, Imperial College of Science Technology and Medicine University of London, October 1996
[61] Szabo A., Ostlund N.S.: Modern Quantum Chemistry: Introduction to Advanced Electronic Structure Theory. Dover Publications, New York (1996)
[62] Waechter A., Biegler L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106, 25-57 (2006) · Zbl 1134.90542
[63] Wales D.J., Doye J.P.K.: Global optimization by basin-hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 atoms. J. Phys. Chem. A 101(28), 5111-5116 (1997)
[64] Wales D.J., Scheraga H.A.: Global optimization of clusters, crystals, and biomolecules. Science 285(5432), 1368-1372 (1999)
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.