Abstract
We present a first-order approach for solving semidefinite programs. The goal of this approach is to compute a solution of the semidefinite program (SDP) up to a high accuracy in spite of using only partial second-order information. We propose a hybrid approach that uses an accelerated projection method to generate an approximate solution and then switches to the quasiminimal residual algorithm (QMR) algorithm applied to a symmetrized version of the Alizadeh-Haeberly-Overton (AHO) system to improve this approximation. Some numerical experiments based on a number of random test examples illustrate the potential of this approach.
Acknowledgements
The authors thank two anonymous referees for their helpful comments that helped to improve the presentation of this paper. This work was supported by the DFG via grant JA 492/9-1.
Notes
When X
opt has k positive eigenvalues, the associated k×k-block of X
opt can be changed by arbitrary but sufficiently small perturbations without changing positive semidefiniteness or complementarity to S
opt. Uniqueness of this k×k-block implies . Using the same implication for S
opt leads to
.