Repository logo
 

On representing the positive semidefinite cone using the second-order cone

Accepted version
Peer-reviewed

Change log

Authors

Abstract

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.

Description

Keywords

math.OC, math.OC

Journal Title

Mathematical Programming

Conference Name

Journal ISSN

0025-5610
1436-4646

Volume Title

Publisher

Springer
Sponsorship
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