A New Primal-Dual Interior-Point Method for Semidefinite Programming

Farid Alizadeh, J.-P. Haeberly, Michael L. Overton

1994 · 31 citations · 0 references

Concepts

Abstract

Semidefinite programming (SDP) is a convex optimization problem in the space of symmetric matrices. Primal-dual interior-point methods for SDP are discussed. These generate primal and dual matrices X and Z which commute only in the limit. A new method is proposed which iterates in the space of commuting matrices. Let S! n\\Thetan denote the set of real symmetric n \\Theta n matrices. The standard inner product on this space is A ffl B = tr AB = P i;j a ij b ij : By X 0, where X 2 S! n\\Thetan , we mean that X is positive semidefinite. Consider the semidefinite programming problem (SDP) min C ffl X (1) s:t: A i ffl X = b i i = 1; . . . ; m; X 0: (2) Here C and A i , i = 1; . . . ; m, are all fixed matrices in S! n\\Thetan , and the unknown variable X also lies in S! n\\Thetan . The semidefinite constraint on X is said to be nonsmooth, since it is equivalent to a bound constraint on the least eigenvalue of X , which is not a differentiable function of X . The constraint is, how...