On representing the positive semidefinite cone using the second-order cone
MetadataShow full item record
Fawzi, H. (2018). On representing the positive semidefinite cone using the second-order cone. Mathematical Programming, 1-10. https://doi.org/10.1007/s10107-018-1233-0
The second-order cone plays an important role in convex optimization and has strong expressive abilities despite its apparent simplicity. Second-order cone formulations can also be solved more efficiently than semidefinite programming problems in general. We consider the following question, posed by Lewis and Glineur, Parrilo, Saunderson: is it possible to express the general positive semidefinite cone using second-order cones? We provide a negative answer to this question and show that the (Formula presented.) positive semidefinite cone does not admit any second-order cone representation. In fact we show that the slice consisting of (Formula presented.) positive semidefinite Hankel matrices does not admit a second-order cone representation. Our proof relies on exhibiting a sequence of submatrices of the slack matrix of the (Formula presented.) positive semidefinite cone whose “second-order cone rank” grows to infinity.
Part of this work was done while the author was at Massachusetts Institute of Technology where he was supported by Grant AFOSR FA9550-11-1-0305
External DOI: https://doi.org/10.1007/s10107-018-1233-0
This record's URL: https://www.repository.cam.ac.uk/handle/1810/270667