Abstract
Copositivity plays a role in combinatorial and nonconvex quadratic optimization. However, testing copositivity of a given matrix is a co-NP-complete problem. We improve a previously given branch-and-bound type algorithm for testing copositivity and discuss its behavior in particular for the maximum clique problem. Numerical experiments indicate that the speedup is considerable.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bomze, I.M.: Copositive optimization – recent developments and applications. Eur. J. Oper. Res. forthcoming (2011)
Bomze I.M.: On standard quadratic optimization problems. J. Glob. Optim. 13, 369–387 (1998)
Bomze I.M.: Evolution towards the maximum clique. J. Glob. Optim. 10, 143–164 (1997)
Bomze I.M., Budinich M., Pelillo M., Rossi C.: Annealed replication: a new heuristic for the maximum clique problem. Discrete Appl. Math. 121, 27–49 (2002)
Bomze I.M., de Klerk E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Glob. Optim. 24, 163–185 (2002)
Bomze I.M., Dür M., de Klerk E., Roos C., Quist A.J., Terlaky T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18, 301–320 (2000)
Bomze, I.M., Eichfelder, G.: Copositivity detection by difference-of-convex decomposition and ω-subdivision. Preprint (2010), available online at http://www.optimization-online.org/DB_HTML/2010/01/2523.html
Bomze I.M., Locatelli M., Tardella F.: New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. Math. Program. 115, 31–64 (2008)
Bundfuss, S.: Copositive matrices, copositive programming, and applications. Ph.D. Dissertation, TU Darmstadt (2009). Online at http://www3.mathematik.tu-darmstadt.de/index.php?id=483
Bundfuss S., Dür M.: An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim. 20, 30–53 (2009)
Bundfuss S., Dür M.: Algorithmic copositivity detection by simplicial partition. Linear Algebra Appl. 428, 1511–1523 (2008)
Burer S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479–495 (2009)
de Klerk E., Pasechnik D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875–892 (2002)
Diananda P.: On non-negative forms in real variables some or all of which are non-negative. Proc. Camb. Philol. Soc. 58, 17–25 (1962)
Dür M.: Copositive programming – a survey. In: Diehl, M., Glineur, F., Jarlebring, E., Michiels, W. (eds.) Recent Advances in Optimization and its Applications in Engineering, pp. 3–20. Springer, Berlin (2010)
Fiedler M., Pták V.: On matrices with non-positive off-diagonal elements and positive principal minors. Czechoslovak Math. J. 12, 382–400 (1962)
Hall M. Jr, Newman M.: Copositive and completely positive quadratic forms. Proc. Camb. Philol. Soc. 59, 329–339 (1963)
Horst R.: On generalized bisection of n-simplices. Math. Comput. 218, 691–698 (1997)
Hiriart-Urruty J.-B., Seeger A.: A variational approach to copositive matrices. SIAM Rev. 52, 593–629 (2010)
Ikramov K.D., Savel’eva N.: Conditionally definite matrices. J. Math. Sci. 99, 1–50 (2000)
Löfberg, J.: YALMIP: A toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004)
Motzkin T.S., Straus E.G.: Maxima for graphs and a new proof of a theorem of Turan. Canadian J. Math. 17, 533–540 (1965)
Murty K.G., Kabadi S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39, 117–129 (1987)
Peña J., Vera J., Zuluaga L.: Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18, 87–105 (2007)
Sturm J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11/12, 625–653 (1999)
Acknowledgments
The authors wish to thank the two anonymous referees for careful reading and useful suggestions which helped to improve the presentation of the paper. M. Dür was partially supported by the Netherlands Organisation for Scientific Research (NWO) through Vici grant no.639.033.907.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to the memory of Reiner Horst.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Sponsel, J., Bundfuss, S. & Dür, M. An improved algorithm to test copositivity. J Glob Optim 52, 537–551 (2012). https://doi.org/10.1007/s10898-011-9766-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-011-9766-2