(422i) Reformulation Linearization Techniques: An Application to Hartree-Fock Calculations

Authors: 
Zorn, Jr., K., Carnegie Mellon University


Hartree-Fock (HF) theory is a set of assumptions and approximations in ab-initio quantum chemistry. Under HF, independent electronic motion results from mean fields involving electron-nucleus attraction, electron-electron repulsion, and electron-electron exchange energy. HF also invokes the variational theorem which states that approximations to the true electronic wavefunction yield energies that are higher than the energy of the real system. A set of coupled, nonlinear differential equations results and the most accurate wavefunction is determined as that which produces the lowest ground-state energy.

In closed-shell atomic systems, the Hartree-Fock and linear combination of atomic orbitals (LCAO) approximations yield an explicit definition of total energy. For these systems, the resulting energy equation is a polynomial expression in terms of LCAO coefficients. Hartree-Fock systems are typically solved by self-consistent field (SCF) iteration, but combining the polynomial energy equation with constraints that ensure basis set orthogonality produces a continuous nonlinear minimization problem [1].

One of the main challenges associated with the solution of the above models is their multimodal nature due to the highly nonlinear, nonconvex constraints involved. Key in the solution of such models with a branch-and-bound algorithm [2] is the development of a tight convex relaxation. It is now understood that successful application of these techniques demands tight relaxations, which, in turn, often require unconventional mathematical reformulations of the problem constraints. We utilize reformulation linearization techniques (RLT) due to Sherali and co-workers that were originally developed for combinatorial optimization problems [3, 4] and have been recently extended to continuous polynomial nonlinear optimization problems [5]. The quantum chemical application is used to gain insights to the problem of identifying strong RLT subsets with the aim of producing tight, lower-dimensional problem formulations. Computational results are presented involving atomic helium and beryllium with contracted minimal Gaussian basis sets.

[1] L. Liberti, C. Lavor, N. Maculan, and M.A.C Nascimento. ?Reformulation in Mathematical Programming: An Application to Quantum Chemistry.? Discrete Applied Mathematics, 157(6) (2009): 1309-1318.

[2] M. Tawarmalani and N. V. Sahinidis. "Global optimization of mixed-integer nonlinear programs: A theoretical and computational study." Mathematical Programming, 99(3) (2004): 563-591.

[3] W.P. Adams and H.D. Sherali. ?Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems.? Operations Research, 38(2) (1990): 217-226.

[4] H.D. Sherali and W.P. Adams. ?A Hierarchy of Relaxations and Convex Hull Characterizations for Mixed-Integer Zero-One Programming Problems.? Discrete Applied Mathematics, 52 (1994): 83-106.

[5] H.D. Sherali and C.H. Tuncbilek. ?New Reformulation Linearization/Convexification Relaxations for Univariate and Multivariate Polynomial Programming Problems.? Operations Research Letters, 21 (1997): 1-9.