Jun 232013

A general quadratic programming problem consists in minimizing a quadratic function of the form: 

    \[f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^{T} \mathbf{Q} \mathbf{x} + \mathbf{c}^{T} \mathbf{x},\]

where the vector \mathbf{x} \in \mathbb{R}^n is subject to inequality and equality constraints:

    \[\mathbf{A} \mathbf{x} \leq \mathbf{b},\]

    \[\mathbf{E} \mathbf{x} = \mathbf{d}.\]

The n \times n matrix \mathbf{Q} is symmetric, while \mathbf{A} and \mathbf{E} are general matrices that enforce the constraints.

It turns out that there are a few interesting problems in electronic structure theory that can be formulated as quadratic programming problems.  For example, the energy of a Slater determinant is: 

    \[E = \sum_{i}^{\rm occ} h_{ii} + \frac{1}{2} \sum_{ij}^{\rm occ} (J_{ij} - K_{ij}),\]

where h_{ii} is the diagonal matrix element of the one-body component of the Hamiltonian, while J_{ij} and K_{ij} are Coulomb and exchange integrals, respectively.  All the sums run over the occupied orbitals of the Slater determinant.

If we introduce the occupation vector \mathbf{n}, with elements n_i = 0,1, then the energy of a Slater determinant may be written as a quadratic function: 

    \[E(\mathbf{n}) = \mathbf{h}^T \mathbf{n} + \frac{1}{2} \mathbf{n}^{T} \mathbf{V} \mathbf{n},\]

 with the matrix \mathbf{V} is defined as V_{ij} = J_{ij}-K_{ij}.  Now let’s ask the question: given a set of molecular orbitals \phi_p, what is the occupation vector that minimizes the energy of a Slater determinant with a given number of alpha and beta electrons (N_\alpha, N_\beta?  This is a binary quadratic programming problem, because the set of conditions given by the general quadratic programming problem are augmented with the requirement that n_i = 0 \text{ or } 1.  Binary quadratic problems are NP-hard, but in the case of the electronic structure counterpart, a good dose of heuristics (physics) can be used to find a solution.

For a wave function whose two- and higher-body cumulants are zero, in the natural orbital basis the energy expression is identical to the  one for a single Slater determinant, with the difference that the natural occupation numbers n_i must satisfy 0 \leq n_i \leq 1.  Thus, finding the optimal uncorrelated state is equivalent to a standard quadratic programming problem.  Interestingly, the computational complexity of this problem appears to depend on the properties of the matrix \mathbf{V} (\mathbf{Q}).  If \mathbf{V} is positive definite this problem can be solved in polynomial time, otherwise it is NP-hard (according to the wikipedia article on quadratic programming).  I do not know whether the \mathbf{V} that arises in electronic structure problems is always positive definite, but I suspect it is.  It would be interesting to check this property numerically.  In addition, if the orbitals are variationally optimal, then n_i will either be 0 or 1, and the uncorrelated state will be a Slater determinant.

 June 23, 2013  Uncategorized

Sorry, the comment form is closed at this time.