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. A complete example illustrates these numerical issues. In order to avoid numerical problems in interior point methods, we propose to maintain the matrix variables in a Cholesky form. We discuss how the factors of the v-space Cholesky form can be updated after a main iteration of the interior point method with Nesterov-Todd scaling. An analogue for second order cone programming is also developed. Numerical results demonstrate the success of this approach.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received: June 16, 2001 / Accepted: April 5, 2002 Published online: October 9, 2002
Key Words. semidefinite programming – second order cone programming
Mathematics Subject Classification (2000): 90C22, 90C20
Rights and permissions
About this article
Cite this article
Sturm, J. Avoiding numerical cancellation in the interior point method for solving semidefinite programs. Math. Program., Ser. B 95, 219–247 (2003). https://doi.org/10.1007/s10107-002-0348-4
Issue Date:
DOI: https://doi.org/10.1007/s10107-002-0348-4