Top

Published in:

2012 | OriginalPaper | Chapter

1. Introduction to Semidefinite, Conic and Polynomial Optimization

Authors : Miguel F. Anjos, Jean B. Lasserre

Published in: Handbook on Semidefinite, Conic and Polynomial Optimization

Publisher: Springer US

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

next chapter 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)

Title: Introduction to Semidefinite, Conic and Polynomial Optimization
Authors: Miguel F. Anjos
Jean B. Lasserre
Publisher: Springer US
Book: Handbook on Semidefinite, Conic and Polynomial Optimization
Print ISBN: 978-1-4614-0768-3

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

Copyright Year: 2012
DOI: https://doi.org/10.1007/978-1-4614-0769-0_1