Avoiding numerical cancellation in the interior point method for solving semidefinite programs

The matrix variables in a primal-dual pair of semidefinite programs are getting increasingly ill-conditioned as they approach a complementary solution. Multiplying the primal matrix variable with a vector from the eigenspace of the non-basic part will therefore result in heavy numerical cancellation. This effect is amplified by the scaling operation in interior point methods. In order to avoid numerical problems in interior point methods, we therefore propose to maintain the matrix variables in a product form. We discuss how the factors of this product form can be updated after a main iteration of the interior point method with Nesterov-Todd scaling.

Citation

CentER Report 2001-27, Tilburg University, Tilburg, the Netherlands, March 2001.

Article

Download

View Avoiding numerical cancellation in the interior point method for solving semidefinite programs