Semidefinite programming algorithms

M. Nakata, H. Nakatsuji, M. Ehara, M. Fukuda, K. Nakata, and K. Fujisawa, Variational calculations of fermion second-order reduced density matrices by semidefinite programming algorithm. J. Chem. Phys. 114, 8282 (2001). 

S. Burer and R. D. C. Monteiro, A nonhnear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Programming Ser. B 95, 329 (2003). 

Here we briefly sketch two directions in research on algorithms for semidefinite programming. A more complete discussion can be found in M. Todd s Semidefinite Optimization [18], or in the Handbook of Semidefinite Programming edited by WoUcowicz et al. [19]. 

It is fair to say that neither of these two approaches works especially well N-representability conditions in the spatial representation are virtually unknown and the orbital-resolved computational methods are promising, but untested. It is interesting to note that one of the most common computational algorithms (cf. Eq. (96)) can be viewed as a density-matrix optimization, although most authors consider only a weak A -representability constraint on the occupation numbers of the g-matrix [1, 4, 69]. Additional A-representability constraints could, of course, be added, but it seems unlikely that the resulting g-density functional theory approach would be more efficient than direct methods based on semidefinite programming [33, 35-37]. 

The constraint matrices A,- in Eq. (19) contain the mappings among D, Q, and G, the contractions to D and g, and the fixed-trace condition. Semidefinite programs for quantum chemical Hamiltonians have been solved with a variety of algorithms [27, 33, 37, 54, 60]. In this work, we utilize the boundary-point method [26, 37], a type of quadratic regularization method. The floating-point... 

As described above, the original MVU algorithm can be very computationally expensive as performing semidefinite programming on an n x n matrix leads to a complexity of 0 nk) ). Therefore, a landmark approach to MVU has been presented that seeks to decrease the complexity of MVU and thus enable it to be used for a broader class of problems [26]. So called Landmark MVU (L-MVU) seeks to work on a random subset of m landmarks so that the feature matrix F can be reformed as... 

---