Title: Semidefinite Programming: Implementation and Applications

The semidefinite program (SDP) is convex optimization problem which consists in minimizing a linear function over the intersection of a linear affine space and the cone of positive semidefinite matrices. SDPs have been studied since the early 90's and most of their theoretical solvability (in polynomial time) were already established by interior-point methods. Some other alternatives to solve SDP are the the so-called first- order methods. Several software like CSDP, PENNON, SBmethod, SDPA, SDPT3, SeDuMi, etc are public available. After introducing the topic, some specific techniques to explore the sparsity of large-scale SDPs will be focused, specially the ones concerning matrix completions [1,2] and Lagrangian duals [3] when solving by interior-point methods. Finally, we will present a specific application from quantum chemistry where we want to determine the electronic structure of a fermion system [4]. It turns out that these problems are huge-scale SDPs and very challenging in practice, requiring parallel computation and large amount of memory.
References
[1] M. Fukuda, M. Kojima, K. Murota, and K. Nakata, "Exploiting sparsity in semidefinite programming via matrix completion I: General framework", SIAM Journal on Optimization, 11 (2000), pp. 647-674.
[2] M. Fukuda, M. Kojima, and M. Shida, "Lagrangian dual interior-point methods for semidefinite programs", SIAM Journal on Optimization, 12 (2002), pp. 1007--1031.
[3] K. Nakata, K. Fujisawa, M. Fukuda, M. Kojima, and K. Murota, "Exploiting sparsity in semidefinite programming via matrix completion II: Implementation and numerical results", Mathematical Programming, Series B 95 (2003), pp. 303-327.
[4] Z. Zhao, B. J. Braams, M. Fukuda, M. L. Overton, and J. K. Percus, "The reduced density matrix method for electronic structure and the role of three-index representability", to appear in The Journal of Chemical Physics.