nach oben

Erschienen in:

2012 | OriginalPaper | Buchkapitel

1. Introduction to Semidefinite, Conic and Polynomial Optimization

verfasst von : Miguel F. Anjos, Jean B. Lasserre

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

KI-gestützte Suche

Aus

Abstract

Conic optimization refers to the problem of optimizing a linear function over the intersection of an affine space and a closed convex cone. We focus particularly on the special case where the cone is chosen as the cone of positive semidefinite matrices for which the resulting optimization problem is called a semidefinite optimization problem.

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

Nächstes Kapitel The Approach of Moments for Polynomial Equations

de Klerk, E.: Aspects of Semidefinite Programming. Kluwer Academic Publishers, Dordrecht, (2002)CrossRef

de Klerk, E., Pasechnik, D.V., Schrijver, A.: Reduction of symmetric semidefinite programs using the regular ⋆ -representation. Math. Program. 109, 613–624 (2007)CrossRef

Gaterman, K., Parrilo, P.: Symmetry group, semidefinite programs and sums of squares. J. Pure Appl. Alg. 192, 95–128 (2004)CrossRef

Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42(6), 1115–1145 (1995)CrossRef

Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins University Press, Baltimore, MD, third edition (1996)

Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, second edition (1993)CrossRef

Henrion, D., Lasserre, J.B., Lofberg, Y.: Gloptipoly 3: moments, optimization and semidefinite programming. Optim. Methods and Software 24, 761–779 (2009)CrossRef

Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1990)

Krivine, J.L.: Anneaux préordonnés. J. Anal. Math. 12, 307–326 (1964)CrossRef

10.

Laraki, R., Lasserre, J.B.: Semidefinite programming for min-max problems and games. Math. Program. 1–28 http://dx.doi.org/10.1007/s10107-010-0353-y

11.

Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001)CrossRef

12.

Lasserre, J.B.: Polynomial programming: LP-relaxations also converge. SIAM J. Optim. 15, 383–393 (2004)CrossRef

13.

Lasserre, J.B.: Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17, 822–843 (2006)CrossRef

14.

Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2009)

15.

Lasserre, J.B.: Convexity in semi-algebraic geometry and polynomial optimization. SIAM J. Optim. 19, 1995–2014 (2009)CrossRef

16.

Laurent, M.: A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0-1 programming. Math. Oper. Res. 28, 470–496 (2003)CrossRef

17.

Laurent, M., Rendl, F.: Semidefinite programming and integer programming. In: Aardal, K., Nemhauser, G., Weismantel, R. (eds.) Handbook on Discrete Optimization, Elsevier (2005)

18.

Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. Ser. B 96, 293–320 (2003)CrossRef

19.

Parrilo, P.A.: Polynomial games and sum of squares optimization. Proceedings of the 45th IEEE Conference on Decision and Control, San Diego, pp. 2855–2860 (2006)

20.

Prajna, S., Papachristodoulou A., Parrilo, P.: Introducing SOSTOOLS: a general purpose sum of squares programming solver. Proceedings of the 41st IEEE Conference on Decison and Control, Las Vegas, pp. 741–746 (2002)

21.

Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42, 969–984 (1993)CrossRef

22.

Ramana, M.V.: An exact duality theory for semidefinite programming and its complexity implications. Math. Program., 77(2, Ser. B), 129–162 (1997)CrossRef

23.

Schmüdgen, K.: The K-moment problem for compact semi-algebraic sets. Math. Ann. 289, 203–206 (1991)CrossRef

24.

Schweighofer, M.: Optimization of polynomials on compact semialgebraic sets. SIAM J. Optim. 15, 805–825 (2005)CrossRef

25.

Vallentin, F.: Symmetry in semidefinite programs. Linear Alg. Appl. 430, 360–369 (2009)CrossRef

26.

Waki, S., Kim, S., Kojima, M., Maramatsu, M.: Sums of squares and semidefinite programming relaxations for polynomial optimization problems witth structured sparsity. SIAM J. Optim. 17, 218–242 (2006)CrossRef

27.

Waki, H., Kim, S., Kojima, M., Muramatsu, M., Sugimoto, H.: SparsePOP: a Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems. ACM Trans. Math. Software 35(2), 15:1–15:13 (2008)CrossRef

28.

Wolkowicz, H., Anjos, M.F.: Semidefinite programming for discrete optimization and matrix completion problems. Discrete Appl. Math., 123(1–2), 513–577 (2002)CrossRef

29.

Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook of Semidefinite Programming. Kluwer Academic Publishers, Boston, MA (2000)

Titel: Introduction to Semidefinite, Conic and Polynomial Optimization
verfasst von: Miguel F. Anjos
Jean B. Lasserre
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_1