Reformulation in mathematical programming: An application to quantum chemistry. (English) Zbl 1173.90494

Summary: This paper concerns the application of reformulation techniques in mathematical programming to a specific problem arising in quantum chemistry, namely the solution of Hartree-Fock systems of equations, which describe atomic and molecular electronic wave functions based on the minimization of a functional of the energy. Their traditional solution method does not provide a guarantee of global optimality and its output depends on a provided initial starting point. We formulate this problem as a multi-extremal nonconvex polynomial programming problem, and solve it with a spatial Branch-and-Bound algorithm for global optimization. The lower bounds at each node are provided by reformulating the problem in such a way that its convex relaxation is tight. The validity of the proposed approach was established by successfully computing the ground-state of the helium and beryllium atoms.


90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
90C11 Mixed integer programming


Full Text: DOI


[1] 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 (1998)
[2] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., Data Structures and Algorithms (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0307.68053
[3] Al-Khayyal, F. A.; Falk, J. E., Jointly constrained biconvex programming, Math. Oper. Res., 8, 2, 273-286 (1983) · Zbl 0521.90087
[4] Feller, D.; Davidson, E. R., Basis sets for ab initio molecular orbital calculations and intermolecular forces, (Lipkowitz, K. B.; Boyd, D. B., Reviews of Computational Chemistry, vol. 1 (1990), VCH Publishers Inc.: VCH Publishers Inc. New York), 1-43
[7] Kucherenko, S.; Sytsko, Yu., Application of deterministic low-discrepancy sequences in global optimization, Comput. Optimization Appl., 30, 3, 297-318 (2004) · Zbl 1078.90052
[8] Lavor, C.; Liberti, L.; Maculan, N.; Chaer Nascimento, M. A., Solving Hartree-Fock systems with global optimization methods, Europhys. Lett., 5, 77 (2007), 50006p1-50006p5
[9] Levine, I. N., Quantum Chemistry (2000), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ
[11] Liberti, L., Reduction constraints for the global optimization of NLPs, Internat. Trans. Oper. Res., 11, 1, 34-41 (2004) · Zbl 1057.90043
[12] Liberti, L., Linearity embedded in nonconvex programs, J. Global Optimization, 33, 2, 157-196 (2005) · Zbl 1124.90026
[13] Liberti, L., Writing global optimization software, (Liberti, L.; Maculan, N., Global Optimization: From Theory to Implementation (2006), Springer: Springer Berlin), 211-262 · Zbl 1100.90004
[15] Liberti, L.; Pantelides, C. C., An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms, J. Global Optimization, 36, 161-189 (2006) · Zbl 1131.90045
[17] McCormick, G. P., Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems, Math. Programming, 10, 146-175 (1976) · Zbl 0349.90100
[18] Mladenović, N.; Petrović, J.; Kovačević-Vujčić, V.; Čangalović, M., Solving a spread-spectrum radar polyphase code design problem by tabu search and variable neighbourhood search, European J. Oper. Res., 151, 389-399 (2003) · Zbl 1053.90055
[19] Sherali, H. D.; Adams, W. P., A Reformulation-Linearization Technique for solving Discrete and Continuous Nonconvex Problems (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dodrecht · Zbl 0926.90078
[20] Sherali, H. D.; Alameddine, A., A new reformulation-linearization technique for bilinear programming problems, J. Global Optimization, 2, 379-410 (1992) · Zbl 0791.90056
[21] 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, 457-478 (1999)
[22] Törn, A.; Z˘ilinskas, A., Global Optimization (1989), Springer: Springer Berlin · Zbl 0752.90075
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.