Plea for a semidefinite optimization solver in complex numbers

Numerical optimization in complex numbers has drawn much less attention than in real numbers. A widespread opinion is that, since a complex number is a pair of real numbers, the best strategy to solve a complex optimization problem is to transform it into real numbers and to solve the latter by a real number solver. This paper defends another point of view and presents four arguments to convince the reader that skipping the transformation phase and using a complex number algorithm, if any, can sometimes have significant benefits. This is demonstrated for the particular case of a semidefinite optimization problem solved by a feasible corrector-predictor primal-dual interior-point method. In that case, the complex number formulation has the advantage (i) of having a smaller memory storage, (ii) of having a faster iteration, (iii) of requiring less iterations, and (iv) of having “smaller” feasible and solution sets. The computing time saving is rooted in the fact that some operations (like the matrix-matrix product) are much faster for complex operands than for their double size real counterparts, so that the conclusions of this paper could be valid for other problems in which these operations count a great deal in the computing time. The iteration number saving has its origin in the smaller (though complex) dimension of the problem in complex numbers. Numerical experiments show that all together these properties result in a code that can run up to four times faster. Finally, the feasible and solution sets are smaller since they are isometric to only a part of the feasible and solution sets of the problem in real numbers, which increases the chance of having a unique solution to the problem.

Article

Download

View PDF