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

Liberti, Leo; Lavor, Carlile; Maculan, Nelson; Nascimento, Marco Antonio Chaer

Discrete Appl. Math. 157, No. 6, 1309-1318 (2009).

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.

MSC:

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

Keywords:

Hartree-Fock; global optimization; branch-and-bound

Software:

CPLEX; SNOPT

References:

[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