DIMACS TR: 2000-01

On Formulating Semidefinite Programming Problems as Smooth Convex Nonlinear Optimization Problems

Authors: Robert J. Vanderbei and Hande Yurttan Benson


Consider the diagonal entries d_j, j=1,2,...,n, of the matrix D in an LDL^T factorization of an n-by-n matrix X. As a function of X, each d_j is well-defined on the closed domain of positive semidefinite matrices. We show that these functions are twice continuously differentiable and concave throughout the interior of this domain. Using these facts, we show how to formulate semidefinite programming problems as standard convex optimization problems that can be solved using an interior-point method for nonlinear programming.

Note: This research has been facilitated by the Special Year on Large Scale Discrete Optimization, via a graduate fellowship and the Workshop on Semidefinite Programming and Its Applications to Large Scale Optimization.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-01.ps.gz
DIMACS Home Page