1994 · 31 citations · 0 references
Natural SciencesComputer ScienceComputational GeometryDesign OptimizationOptimizationConstrained OptimizationConvex OptimizationLinear ProgrammingMatrix ComputationNonlinear ProgrammingOptimization TheoryDuality TheoryMatrix Equation SolversPrimal-dual AlgorithmsSemidefinite Programming
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...