The Simplest Semidefinite Programs are Trivial

Abstract

We consider optimization problems of the following type: $$\\min\\left\\{\\mbox{tr}CX\\COLON AX = B, X \\quad \\mbox{positive semidefinite}\\right\\}.$$ Here, tr· denotes the trace operator, C and X are symmetric n × n matrices, B is a symmetric m × m matrix and A· denotes a linear operator. Such problems are called semidefinite programs and have recently become the object of considerable interest due to important connections with max-min eigenvalue problems and with new bounds for integer programming. In the context of symmetric matrices, the simplest linear operators have the following form: $$AX = MXM^T,$$ where M is an arbitrary m × n matrix. In this paper, we show that for such linear operators the optimization problem is trivial in the sense that an explicit solution can be given.