Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction to Semidefinite, Conic and Polynomial Optimization Kapitel lesen Erstes Kapitel lesen

2012 | OriginalPaper | Buchkapitel

8. Copositive Programming

verfasst von : Samuel Burer

Erschienen in: Handbook on Semidefinite, Conic and Polynomial Optimization

Verlag: Springer US

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This chapter provides an introduction to copositive programming, which is linear programming over the convex conic of copositive matrices. Researchers have shown that many NP-hard optimization problems can be represented as copositive programs, and this chapter recounts and extends these results.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Relaxations of Combinatorial Problems Via Association Schemes
Nächstes Kapitel Invariant Semidefinite Programs
Fußnoten
1
The paper [20] has established a similar result concurrently with this chapter, and the paper [19] studies the generalized notion of copositivity over an arbitrary set, analyzing important properties of the resulting convex cone.
 
2
If \(\mathcal{K}\) is a semidefinite cone, than \(\mathcal{K}\) must be encoded in its “vectorized” form to match the development in this chapter. For example, the columns of a d ×d semidefinite matrix could be stacked into a single, long column vector of size d2, and then the CP matrices yyT over \({\mathfrak{R}}_{+} \times \mathcal{K}\) would have size \(({d}^{2} + 1) \times ({d}^{2} + 1)\).
 
Literatur
1.
Anstreicher, K.M., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Mathematical Programming (series B) 124, 33–43 (2010)CrossRef
2.
Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: Analysis, algorithms, and engineering applications. MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2001)CrossRef
3.
Berman, A., Rothblum, U.G.: A note on the computation of the CP-rank. Linear Algebra Appl. 419, 1–7 (2006)CrossRef
4.
Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific (2003)
5.
Bomze, I., Jarre, F.: A note on Burer’s copositive representation of mixed-binary QPs. Optimization Letters 4, 465–472 (2010)CrossRef
6.
Bomze, I.M., de Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. Dedicated to Professor Naum Z. Shor on his 65th birthday. J. Global Optim. 24(2), 163–185 (2002)CrossRef
7.
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. Global Optim. 18(4), 301–320 (2000)CrossRef
8.
Bundfuss, S., Dür, M.: An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim. 20(1), 30–53 (2009)CrossRef
9.
Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Mathematical Programming 120, 479–495 (2009)CrossRef
10.
Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Mathematical Programming Computation 2(1), 1–19 (2010)CrossRef
11.
Burer, S., Anstreicher, K.M., Dür, M.: The difference between 5 ×5 doubly nonnegative and completely positive matrices. Linear Algebra Appl. 431(9), 1539–1552 (2009)CrossRef
12.
Burer, S., Dong, H.: Separation and relaxation for cones of quadratic forms. Manuscript, University of Iowa (2010) Submitted to Mathematical Programming.
13.
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)CrossRef
14.
de Klerk, E., Sotirov, R.: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Programming 122(2, Ser. A), 225–246 (2010)CrossRef
15.
16.
Dukanovic, I., Rendl, F.: Copositive programming motivated bounds on the stability and the chromatic numbers. Math. Program. 121(2, Ser. A), 249–268 (2010)
17.
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 (2010)
18.
Dür, M., Still, G.: Interior points of the completely positive cone. Electron. J. Linear Algebra 17, 48–53 (2008)
19.
Eichfelder, G., Jahn, J.: Set-semidefinite optimization. Journal of Convex Analysis 15, 767–801 (2008)
20.
Eichfelder, G., Povh, J.: On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints. Manuscript, Faculty of Information Studies, Slovenia, December (2010)
21.
Faye, A., Roupin, F.: Partial lagrangian relaxation for general quadratic programming. 4OR 5, 75–88 (2007)CrossRef
22.
Gvozdenović, N., Laurent, M.: Semidefinite bounds for the stability number of a graph via sums of squares of polynomials. In Lecture Notes in Computer Science, 3509, pp. 136–151. IPCO XI (2005)
23.
Gvozdenović, N., Laurent, M.: Computing semidefinite programming lower bounds for the (fractional) chromatic number via block-diagonalization. SIAM J. Optim. 19(2), 592–615 (2008)CrossRef
24.
Gvozdenović, N., Laurent, M.: The operator Ψ for the chromatic number of a graph. SIAM J. Optim. 19(2), 572–591 (2008)CrossRef
25.
Hiriart-Urruty, J.-B., Seeger, A.: A variational approach to copositive matrices. SIAM Review, 52(4), 593–629 (2010)CrossRef
26.
Maxfield, J.E., Minc, H.: On the matrix equation X′X = A. Proc. Edinburgh Math. Soc. (2) 13, 125–129 (1962/1963)
27.
Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Programming 39(2), 117–129 (1987)CrossRef
28.
Natarajan, K., Teo, C., Zheng, Z.: Mixed zero-one linear progams under objective uncertainty: A completely positive representation. Operations Research, 59(3), 713–728, (2011)CrossRef
29.
Nesterov, Y.E., Nemirovskii, A.S.: Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics, Philadelphia (1994)CrossRef
30.
Parrilo, P.: Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology (2000)
31.
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)CrossRef
32.
Povh, J.: Towards the optimum by semidefinite and copositive programming : new approach to approximate hard optimization problems. VDM Verlag (2009)
33.
Povh, J., Rendl, F.: A copositive programming approach to graph partitioning. SIAM J. Optim. 18(1), 223–241 (2007)CrossRef
34.
Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6(3), 231–241 (2009)CrossRef
35.
Sturm, J.F., Zhang, S.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28(2), 246–267 (2003)CrossRef
36.
Wen, Z., Goldfarb, D., Yin, W.: Alternating direction augmented lagrangian methods for semidefinite programming. Manuscript, Department of Industrial Engineering and Operations Research, Columbia University, New York, NY, USA (2009)
37.
Yildirim, E.A.: On the accuracy of uniform polyhedral approximations of the copositive cone. Manuscript, Department of Industrial Engineering, Bilkent University, 06800 Bilkent, Ankara, Turkey (2009) To appear in Optimization Methods and Software.
38.
Zhao, X., Sun, D., Toh, K.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1737–1765 (2010)CrossRef
Metadaten
Titel
Copositive Programming
verfasst von
Samuel Burer
Copyright-Jahr
2012
Verlag
Springer US
Buch
Handbook on Semidefinite, Conic and Polynomial Optimization

Print ISBN: 978-1-4614-0768-3

Electronic ISBN: 978-1-4614-0769-0

Copyright-Jahr: 2012

DOI
https://doi.org/10.1007/978-1-4614-0769-0_8

Premium Partner

    Bildnachweise