Real Algebraic Geometry and Optimization, Fall 2015
Office Hours: Thursday 2-3PM and by appointment. Homework Assignments 1, 2 and 3 are due on October 29th. Please hand in two problems from each assignment for a total of 6 problems.
Final Homework assignment is here.
Primary Source: Semidefinite Optimization and Convex Algebraic Geometry edited by Greg Blekherman, Pablo Parrilo and Rekha Thomas
Convex Geometry Reference: A Course in Convexity, Alexander Barvinok
Algebraic Geometry Reference: Ideals, Varieties and Algorithms, David Cox, John Little, Donal O'Shea
Possible Papers to read:
Some Concrete Aspects of Hilbert's 17th Problem, B. Reznick
Real Zeros of Positive Semidefinite Forms I, M. D. Choi, T. Y. Lam, B. Reznick
Nonnegative polynomials and their Carathéodory number, S. Naldi
Some Geometric Results in Semidefinite Programming, M. Ramana, A.J. Goldman
The computational complexity of convex bodies, A. Barvinok, E. Veomett
Theta Bodies for Polynomial Ideals, J. Gouveia, P. Parrilo, R. Thomas
Lifts of convex sets and cone factorizations, J. Gouveia, P. Parrilo, R. Thomas
Combinatorial Bounds on Nonnegative Rank and Extended Formulations, S. Fiorini, V. Kaibel, K. Pashkovich, D.O. Theis
Approximate volume and integration for basic semialgebraic sets, D. Henrion, J. B. Lasserre, C. Savorgnan
Global optimization with polynomials and the problem of moments, J. B.Lasserre
Sums of Squares, Moment Matrices & Optimization over Polynomials, M. Laurent
Determinantal representations of hyperbolic plane curves: an elementary approach, D. Plaumann, C. Vinzant
Lecture 1: Sums of Squares Heuristic in Polynomial Optimization, Sum of Squares relaxation of MAXCUT.
Sources: Sections 2.2.2, 3.2.4.
Lecture 2: Nonnegative Polynomials and Sums of Squares. Homework Problems are here.
Sources: Some Concrete Aspects of Hilbert's 17th Problem, Bruce Reznick
Sections 4.1 and 4.2
Algebra Refresher: Varieties and Ideals, IVA, Sections 1.2, 1.4 and 1.5.
Lecture 3: Cones of Nonnegative Polynomials and Sums of Squares and Dual Cones.
Sources: Section 4.4
Convex Geometry Refresher: Carathéodory's theorem, Krein-Milman Theorem, Biduality Theorem, Section I.2, II.3 and IV.1 of ACiC.
Lecture 4: Dual Cone to the Cone of Nonnegative Polynomials, Moment Problems, Quadrature, Carathéodory's Number.
Sources: Section 4.4
Additional Reading: An Introduction to the Moment Problem
Lecture 5: Dual Cone to the Cone of Sums of Squares, Hankel/Moment Matrices, Carathéodory number of the dual cone of bivariate nonnegative forms.
Sources: Section 4.6 of the main text and Section II.10 of ACiC.
Lecture 6: Cone of Positive Semidefinite Matrices. Homework Problems are here.
Sources: Section II.12 of ACiC.
Lecture 7: Separating Dual Cones of Nonnegative Polynomials and Sums of Squares.
Sources: Section 4.3.
Lecture 8: Hilbert's Proof for Trivariate Sextics, Cayley-Bacharach Theorem.
On Hilbert's Construction of Positive Polynomials, B. Reznick
Some Concrete Aspects of Hilbert's 17th Problem, Bruce Reznick
Cayley-Bacharach Theorems and Conjectures, D. Einsenbud, M. Green, J. Harris
Lecture 9: Veronese Embedding and John's Ellipsoid.
Sources: Lecture 3 of An Elementary Introduction to Modern Convex Geometry, K. Ball.
Lecture 10: Approximating norm by a polynomial. Convex forms.
Sources: Approximating Norm by a Polynomial, A. Barvinok.
Section 4.10.
Lecture 11: Semidefinite Programming Duality. Sums of Squares Programs.
Sources: Sections 2.1 and 3.1.
Section IV.5 and IV.7 of ACiC.
Lecture 12: Stability, Lyapunov Functions and Sums of Squares Methods. DSOS and SDSOS polynomials.
Sources: Pablo Parrilo's lecture slides.
Amir Ali Ahmadi talk slides.
Lecture 13: Introduction to Projective Varieties and Homogeneous Ideals. Hilbert's Basis Theorem and the Nullstellensatz.
Sources: Chapter 5 of IVA
Lecture 14: Sums of Squares on Varieties. Varieties of Minimal Degree. Bertini's Theorem. Homework Problems are here.
Sums of Squares and Varieties of Minimal Degree, G.B., G. Smith, M. Velasco
Lecture 15: Smooth and Singular Points on Varieties. More on Bertini's Theorem.
Lecture 16: Sums of Squares and Varieties of Minimal Degree.
Lecture 17: Introduction to Real Algebraic Geometry, Real Fields, Real Closed Fields.
Lecture 18: Tarski-Seidenberg Principle, Hilbert's 17th Problem, Positivstellensatz.
Lecture 19: Schmudgen and Putinar's Theorems.
Lecture 20: Schmudgen and Putinar's Theorems continued. Stability of quadratic modules.