UCLA

In recent years, semidefinite programming has been an important topic in the area of convex optimization, and several methods for exploiting the sparse structure in semidefinite programming problems have been developed. Some methods have been proposed to transform the standard semidefinite program into a conic optimization problem with respect to the cone of positive semidefinite completable matrices, and to take advantage of the sparsity pattern of the completable matrices. However, the problem arises of how to recover an optimal solution for the original semidefinite program, \ie, how to find a positive semidefinite completion for the positive semidefinite completable solution. In particular, a low-rank completion is of great interest in many applications. In general, it is difficult to determine the minimum rank among all positive semidefinite completions. However, if the sparsity pattern is chordal, efficient algorithms are known for constructing a positive semidefinite matrix completion with minimum rank.

In the thesis, we investigate this completion approach as an inexpensive post-processing technique for semidefinite relaxations of nonconvex quadratic problems. We test the method on semidefinite relaxations of the optimal power flow problem. By numerical experiments, we show that the completion results substantially reduce the rank of the solution for the semidefinite relaxation.