The Simplest Semidefinite Programs are Trivial

We consider optimization problems of the following type:

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: 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.