An Exact Duality Theory for Semidefinite Programming Based on Sums of Squares

References

• Barvinok A. A remark on the rank of positive semidefinite matrices subject to affine constraints. Discrete Comput. Geom. (2001) 25(1):23–31Crossref, Google Scholar
• Barvinok A. A Course in Convexity (2002) 54(American Mathematical Society, Providence, RI) Graduate Studies in MathematicsCrossref, Google Scholar
• Blecher DP, Le Merdy C. Operator Algebras and Their Modules—An Operator Space Approach (2004) (Oxford University Press, Oxford, UK) London Mathematical Society Monographs, New Series, Vol. 30Crossref, Google Scholar
• Bochnak J, Coste M, Roy MF. Real Algebraic Geometry (1998) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Bohnenblust F. Joint positiveness of matrices. (1948) . Technical report, California Institute of Technology, available at http://orion.uwaterloo.ca/~hwolkowi/henry/book/fronthandbk.d/Bohnenblust.pdfGoogle Scholar
• Borwein JM, Wolkowicz H. Facial reduction for a cone-convex programming problem. J. Austral. Math. Soc. Ser. A ((1980/81)) 30(3):369–380Crossref, Google Scholar
• Boyd S, El Ghaoui L, Feron E, Balakrishnan V. Linear Matrix Inequalities in System and Control Theory (1994) 15(SIAM, Philadelphia) Studies in Applied MathematicsCrossref, Google Scholar
• Boyd S, Vandenberghe L. Semidefinite programming. SIAM Rev. (1996) 38(1):49–95Crossref, Google Scholar
• Chesi G. LMI techniques for optimization over polynomials in control: A survey. IEEE Trans. Automat. Control (2010) 55(11):2500–2510Crossref, Google Scholar
• de Klerk E. Aspects of Semidefinite Programming, Interior Point Algorithms and Selected Applications (2002) 65(Kluwer Academic Publishers, Dordrecht, The Netherlands) Applied OptimizationCrossref, Google Scholar
• Dumitrescu B. Positive Trigonometric Polynomials and Signal Processing Applications (2007) (Springer-Verlag, Dordrecht, The Netherlands) Google Scholar
• Effros EG, Ruan Z-J. Operator Spaces (2000) (Oxford University Press, Oxford, UK) London Mathematical Society Monographs, New Series Vol. 23Google Scholar
• Farkas J. Theorie der einfachen Ungleichungen. J. Reine Angew. Math. (1902) 124:1–27Google Scholar
• Goemans M. Semidefinite programming in combinatorial optimization. Math. Program. (1997) 79(1–3, Ser. B):143–161Crossref, Google Scholar
• Gohberg I, Lancaster P, Rodman L. Matrix Polynomials (1982) (Academic Press, New York) Computer Science and Applied MathematicsGoogle Scholar
• Gouveia J, Netzer T. Positive polynomials and projections of spectrahedra. SIAM J. Optim. (2011) 21(3):960–976Crossref, Google Scholar
• Helton JW, Klep I, McCullough S. The matricial relaxation of a linear matrix inequality. Math. Program. (2012) . http://arxiv.org/abs/1003.0908Google Scholar
• Helton JW, Klep I, McCullough S. The convex Positivstellensatz in a free algebra. Adv. Math. (2012) 231:516–534Crossref, Google Scholar
• Nelson C. A perfect Positivstellensatz in a free algebra. (2013) . PreprintGoogle Scholar
• Henrion D, Garulli A. Positive Polynomials in Control (2005) (Springer-Verlag, Berlin) Lecture Notes in Control and Information Sciences, Vol. 312Crossref, Google Scholar
• Henrion D, Lasserre JB. Convergent relaxations of polynomial matrix inequalities and static output feedback. IEEE Trans. Autom. Control (2006) 51(2):192–202Crossref, Google Scholar
• Kojima M. Sums of squares relaxations of polynomial semidefinite programs. (2003) . Technical report, Tokyo Institute of Technology, TokyoGoogle Scholar
• Klep I, Schweighofer M. Pure states, positive matrix polynomials and sums of Hermitian squares. Indiana Univ. Math. J. (2010) 59(3):857–874Crossref, Google Scholar
• Klep I, Schweighofer M. Infeasibility certificates for linear matrix inequalities. Oberwolfach Preprints (2011) 28 http://www.mfo.de/scientific-programme/publications/owp/2011/OWP2011_28.pdfGoogle Scholar
• Lasserre JB. Global optimization with polynomials and the problem of moments. SIAM J. Optim. ((2000/01)) 11(3):796–817Crossref, Google Scholar
• Lasserre JB. Moments, Positive Polynomials and Their Applications (2010) 1(Imperial College Press, London) Optimization SeriesGoogle Scholar
• Laurent M, Putinar M, Sullivant S. Sums of squares, moment matrices and optimization over polynomials. Emerging Applications of Algebraic Geometry (2009) 149(Springer, New York) 157–270The IMA Volumes in Mathematics and its Applications(An updated version is available at http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf)Crossref, Google Scholar
• Marshall M. Positive Polynomials and Sums of Squares (2008) 146(American Mathematical Society, Providence, RI) Mathematical Surveys and MonographsCrossref, Google Scholar
• Nemirovski A. Advances in convex optimization: Conic programming. International Congress of Mathematicians (2007) I(Eur. Math. Soc.)413–444Crossref, Google Scholar
• Nesterov Y, Nemirovski A. Interior-Point Polynomial Algorithms in Convex Programming (1994) 13(SIAM, Philadelphia) Studies in Applied MathematicsCrossref, Google Scholar
• Parrilo PA. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. (2000) . Ph.D. thesis, California Institute of Technology, PasadenaGoogle Scholar
• Pataki G. A simple derivation of a facial reduction algorithm, and extended dual systems. (2000) . Technical report, Columbia University, New York, http://www.unc.edu/~pataki/papers/fr.pdfGoogle Scholar
• Pataki G. Bad semidefinite programs: they all look the same. (2011) . Preprint. http://arxiv.org/abs/1112.1436Google Scholar
• Paulsen V. Completely Bounded Maps and Operator Algebras (2002) 78(Cambridge University Press, Cambridge, UK) Studies in Advanced MathematicsGoogle Scholar
• Prestel A, Delzell CN. Positive Polynomials: From Hilbert's 17th Problem to Real Algebra (2001) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Pisier G. Introduction to Operator Space Theory (2003) (Cambridge University Press, Cambridge, UK) London Mathematical Society Lecture Note, Series Vol. 294Crossref, Google Scholar
• Porkolab L, Khachiyan L. On the complexity of semidefinite programs. J. Global Optim. (1997) 10(4):351–365Crossref, Google Scholar
• Powers V, Scheiderer C. The moment problem for non-compact semialgebraic sets. Adv. Geom. (2001) 1(1):71–88Crossref, Google Scholar
• Putinar M. Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. (1993) 42(3):969–984Crossref, Google Scholar
• Ramana M. An exact duality theory for semidefinite programming and its complexity implications. Math. Program. (1997) 77(2, Ser. B):129–162Crossref, Google Scholar
• Scheiderer C, Putinar M, Sullivant S. Positivity and sums of squares: A guide to recent results. Emerging Applications of Algebraic Geometry (2009) 149(Springer-Verlag, Berlin) 271–324IMA Volumes in Mathematics and its ApplicationsCrossref, Google Scholar
• Scherer CW, Hol CWJ. Matrix sum-of-squares relaxations for robust semi-definite programs. Math. Program. (2006) 107(1–2, Ser. B):189–211Crossref, Google Scholar
• Schmüdgen K. The K-moment problem for compact semi-algebraic sets. Math. Ann. (1991) 289(2):203–206Crossref, Google Scholar
• Schrijver A. Theory of Linear and Integer Programming (1986) (John Wiley & Sons, Chichester, UK) Wiley-Interscience Series in Discrete Mathematics and OptimizationGoogle Scholar
• Sturm J, Frenk H, Roos K, Terlaky T, Zhang S. Theory and algorithms of semidefinite programming. High Performance Optimization (2000) 33(Kluwer Academic Publishers)1–194Applied OptimizationGoogle Scholar
• Todd MJ. Semidefinite optimization. Acta Numer. (2001) 10:515–560Crossref, Google Scholar
• Tuncel L, Wolkowicz H. Strong duality and minimal representations for cone optimization. Comput. Optim. Appl. (2012) 53(2):619–648Crossref, Google Scholar
• Wolkowicz H, Saigal R, Vandenberghe L. Handbook of Semidefinite Programming, Theory, Algorithms, and Applications (2000) (Kluwer Academic Publishers, Norwell, MA) Crossref, Google Scholar
• Zalar A. A note on a matrix version of the Farkas lemma. Comm. Algebra (2012) 40:3420–3429Crossref, Google Scholar