Using the conjugate gradient method in interior-points methods for semidefinite programs

In recent years, Semidefinite Programming (SDP) has been intensively studied from both theoretical and practical aspects in various fields including interior-point methods, combinatorial optimization, and the control and systems theory. Besides the SDPA (Semidefinite Programming Algorithm) which the authors' group developed to solve SDPs using the primal–dual interior-point method, many computer programs for SDPs are now available through the Internet. Most of those programs utilize direct methods such as the Cholesky factorization or the LU factorization to solve a system of linear equations which arises at each iteration to generate a search direction. The system of equations to be solved at each iteration is full dense in general. Hence, as the size of the system of linear equations gets larger, the use of such direct methods becomes more difficult; even storing its coefficient matrix in the computer memory becomes impossible. To overcome this difficulty, we incorporate the conjugate graduate method, which is a popular iterative method for solving systems of linear equations, and various improvements into the SDPA. In particular, the resultant modified method, which we call the SDPA-CG, does not store the coefficient matrix of the system of equations to be solved at each iteration. This feature of the SDPA-CG makes it possible to handle much larger size of SDPs compared with the SDPA. Some numerical experiments show that when the SDPA-CG is applied to sparse problems having a large number of inequality constraints, the conjugate gradient method works very efficiently in earlier stages of the SDPA-CG until the SDPA-CG generates an approximate solution with a low accuracy. In particular, the SDPA-CG solves an SDP relaxation of the maximum clique problem which has 500 × 500 variable matrices and more than 110,000 inequality constraints.