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

Jos F. Sturm (j.f.sturmkub.nl)

Abstract: 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.

Keywords: Semidefinite Programming

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

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

Download: [Postscript][PDF]

Entry Submitted: 05/02/2001
Entry Accepted: 05/11/2001
Entry Last Modified: 08/05/2002

Modify/Update this entry