Abstract
We give explicit polynomial-sized (in \(n\) and \(k\)) semidefinite representations of the hyperbolicity cones associated with the elementary symmetric polynomials of degree \(k\) in \(n\) variables. These convex cones form a family of non-polyhedral outer approximations of the non-negative orthant that preserve low-dimensional faces while successively discarding high-dimensional faces. More generally we construct explicit semidefinite representations (polynomial-sized in \(k,m\), and \(n\)) of the hyperbolicity cones associated with \(k\)th directional derivatives of polynomials of the form \(p(x)=\det (\sum _{i=1}^{n}A_i x_i)\) where the \(A_i\) are \(m\times m\) symmetric matrices. These convex cones form an analogous family of outer approximations to any spectrahedral cone. Our representations allow us to use semidefinite programming to solve the linear cone programs associated with these convex cones as well as their (less well understood) dual cones.
Similar content being viewed by others
References
Blekherman, G., Parrilo, P.A., Thomas, R.R. (eds.): Semidefinite Optimization and Convex Algebraic Geometry. MOS-SIAM Series on Optimization. SIAM, Philadelphia (2013)
Brändén, P.: Hyperbolicity cones of elementary symmetric polynomials are spectrahedral (2012). Optim. Lett. 8(5), 1773–1782 (2014)
Choe, Y.B., Oxley, J.G., Sokal, A.D., Wagner, D.G.: Homogeneous multivariate polynomials with the half-plane property. Adv. Appl. Math. 32(1–2), 88–187 (2004)
Gouveia, J., Netzer, T.: Positive polynomials and projections of spectrahedra. SIAM J. Optim. 21(3), 960 (2011)
Gouveia, J., Parrilo, P.A., Thomas, R.R.: Lifts of convex sets and cone factorizations. Math. Oper. Res. 38(2), 248–264 (2013)
Gårding, L.: An inequality for hyperbolic polynomials. J. Math. Mech. 8(6), 957–965 (1959)
Güler, O.: Hyperbolic polynomials and interior point methods for convex programming. Math. Oper. Res. 22(2), 350–377 (1997)
Helton, J.W., Vinnikov, V.: Linear matrix inequality representation of sets. Commun. Pure Appl. Math. 60(5), 654–674 (2007)
Kaibel, V., Pashkovich, K., Theis, D.: Symmetry matters for the sizes of extended formulations. In: Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 6080, pp. 135–148. Springer, Berlin (2010)
Lewis, A.S., Parrilo, P.A., Ramana, M.V.: The Lax conjecture is true. Proc. Am. Math. Soc. 133(9), 2495–2500 (2005)
Löfberg, J.: YALMIP: a toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference. Taipei, Taiwan (2004). http://users.isy.liu.se/johanl/yalmip
Miranda, H.F., Thompson, R.C.: Group majorization, the convex hulls of sets of matrices, and the diagonal element-singular value inequalities. Linear Algebr. Appl. 199, 131–141 (1994)
Nemirovski, A.: Advances in convex optimization: conic programming. In: Proceedings of the International Congress of Mathematicians: Madrid, August 22–30, 2006: invited lectures, pp. 413–444 (2006)
Nemirovski, A., Ben-Tal, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications. MOS-SIAM Series on Optimization. SIAM, Philadelphia (2001)
Nesterov, Y., Nemirovskii, A.: Interior Point Polynomial Algorithms in Convex Programming, SIAM Studies in Applied Mathematics, vol. 13. SIAM, Philadelphia (1993)
Nie, J., Parrilo, P.A., Sturmfels, B.: Semidefinite representation of the \(k\)-ellipse. In: Algorithms in Algebraic Geometry, The IMA Volumes in Mathematics and its Applications, vol. 146, pp. 117–132. Springer, New York (2008)
Ramana, M., Goldman, A.J.: Some geometric results in semidefinite programming. J. Glob. Optim. 7(1), 33–50 (1995)
Renegar, J.: Hyperbolic programs, and their derivative relaxations. Found. Comput. Math. 6, 59–79 (2006)
Rockafellar, R.T.: Convex Analysis, vol. 28. Princeton university press, Princeton (1997)
Sanyal, R.: On the derivative cones of polyhedral cones. Adv. Geom. 13(2), 315–321 (2013)
Sanyal, R., Sottile, F., Sturmfels, B.: Orbitopes. Mathematika 57(02), 275–314 (2011)
Toh, K.C., Todd, M.J., Tütüncü, R.H.: SDPT3—a MATLAB software package for semidefinite programming, version 1.3. Optim. Methods Softw. 11(1–4), 545–581 (1999)
Zinchenko, Y.: On hyperbolicity cones associated with elementary symmetric polynomials. Optim. Lett. 2(3), 389–402 (2008)
Acknowledgments
The authors would like to thank the anonymous referees for many helpful suggestions that led to substantial improvements in the presentation of the paper. This research was funded by the Air Force Office of Scientific Research under Grants FA9550-11-1-0305 and FA9550-12-1-0287.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Saunderson, J., Parrilo, P.A. Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones. Math. Program. 153, 309–331 (2015). https://doi.org/10.1007/s10107-014-0804-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-014-0804-y