Abstract
We study the numerical solution of the problem , where
is a symmetric square matrix, and
is a linear operator, such that
is invertible. With
the desired fractional duality gap, and
the condition number of
, we prove
iteration complexity for a simple primal-dual interior point method directly based on those for linear programs with semi-definite constraints. We do not, however, require the numerically expensive scalings inherent in these methods to force fast convergence. For low-dimensional problems (
), our numerical experiments indicate excellent performance and only a very slowly growing dependence of the convergence rate on
. While our algorithm requires somewhat more iterations than existing interior point methods, the iterations are cheaper. This gives better computational times.
Acknowledgements
This research was financially supported by the SFB research programme F32 ‘Mathematical Optimization and Applications in Biomedical Sciences’ of the Austrian Science Fund (FWF), and by the King Abdullah University of Science and Technology (KAUST) Award No. KUK-I1-007-43.
Notes
This work was mostly done while the author was at the Institute for Mathematics and Scientific Computing, University of Graz, Austria.