A general quadratic programming problem consists in minimizing a quadratic function of the form:
where the vector is subject to inequality and equality constraints:
The matrix is symmetric, while and 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:
where is the diagonal matrix element of the one-body component of the Hamiltonian, while and are Coulomb and exchange integrals, respectively. All the sums run over the occupied orbitals of the Slater determinant.
If we introduce the occupation vector , with elements , then the energy of a Slater determinant may be written as a quadratic function:
with the matrix is defined as . Now let’s ask the question: given a set of molecular orbitals , what is the occupation vector that minimizes the energy of a Slater determinant with a given number of alpha and beta electrons () ? 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 . 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 must satisfy . 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 (). If 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 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 will either be 0 or 1, and the uncorrelated state will be a Slater determinant.