Abstract
We investigate the relation between the cone \({\mathcal{C}^{n}}\) of n × n copositive matrices and the approximating cone \({\mathcal{K}_{n}^{1}}\) introduced by Parrilo. While these cones are known to be equal for n ≤ 4, we show that for n ≥ 5 they are not equal. This result is based on the fact that \({\mathcal{K}_{n}^{1}}\) is not invariant under diagonal scaling. We show that for any copositive matrix which is not the sum of a nonnegative and a positive semidefinite matrix we can find a scaling which is not in \({\mathcal{K}_{n}^{1}}\). In fact, we show that if all scaled versions of a matrix are contained in \({\mathcal{K}_{n}^{r}}\) for some fixed r, then the matrix must be in \({\mathcal{K}_{n}^{0}}\). For the 5 × 5 case, we show the more surprising result that we can scale any copositive matrix X into \({\mathcal{K}_{5}^{1}}\) and in fact that any scaling D such that \({(DXD)_{ii} \in \{0,1\}}\) for all i yields \({DXD \in \mathcal{K}_{5}^{1}}\). From this we are able to use the cone \({\mathcal{K}_{5}^{1}}\) to check if any order 5 matrix is copositive. Another consequence of this is a complete characterisation of \({\mathcal{C}^{5}}\) in terms of \({\mathcal{K}_{5}^{1}}\). We end the paper by formulating several conjectures.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bomze I.M., de Klerk E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Glob. Optim. 24(2), 163–185 (2002)
de Klerk E., Pasechnik D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875–892 (2002)
Dickinson, P.J.C., Dür, M., Gijben, L., Hildebrand, R.: Irreducible elements of the copositive cone (preprint, 2012). http://www.optimization-online.org/DB_HTML/2012/03/3383.html.
Hall M. Jr., Newman M.: Copositive and completely positive quadratic forms. Proc. Camb. Phil. Soc 59, 329–339 (1963)
Haynsworth E., Hoffman A.J.: Two remarks on copositive matrices. Linear Algebra Appl. 2, 387–392 (1969)
Hildebrand, R.: The extreme rays of the 5 × 5 copositive cone. Linear Algebra Appl (in print). http://dx.doi.org/10.1016/j.laa.2012.04.017
Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry. IMA Volumes in Mathematics and its Applications, vol. 149, pp. 157–270. Springer, New York (2009)
Maxfield, J.E., Minc, H.: On the matrix equation X′ X = A. Proc. Edinb. Math. Soc 13(2), 125–129 (1962/1963)
Murty K.G., Kabadi S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117–129 (1987)
Parrilo, PA.: Parrilo Structured semidefinite programs and semi-algebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology (2000). http://thesis.library.caltech.edu/1647/.
Peña J., Vera J., Zuluaga L.F.: Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18(1), 87–105 (2007)
Robinson, R.M.: Some definite polynomials which are not sums of squares of real polynomials. In: Selected Questions of Algebra and Logic (collection dedicated to the memory of A. I. Mal’cev) (Russian), pp. 264–282 (1973) (Izdat. “Nauka” Sibirsk. Otdel., Novosibirsk)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Dickinson, P.J.C., Dür, M., Gijben, L. et al. Scaling relationship between the copositive cone and Parrilo’s first level approximation. Optim Lett 7, 1669–1679 (2013). https://doi.org/10.1007/s11590-012-0523-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-012-0523-3