Real Algebraic Geometry and Optimization

Contents
Preface
Acknowledgments
Part I. Foundations
Chapter 1. Univariate real polynomials
1.1. Descartes’s Rule of Signs and the Budan–Fourier theorem
1.2. Sturm sequences
1.3. Symmetric polynomials in the roots
1.4. The Hermite form
1.5. Exercises
1.6. Notes
Chapter 2. From polyhedra to semialgebraic sets
2.1. Polytopes and polyhedra
2.2. Semialgebraic sets
2.3. A first view on spectrahedra
2.4. Exercises
2.5. Notes
Chapter 3. The Tarski–Seidenberg principle and elimination of quantifiers
3.1. Real fields
3.2. Real closed fields
3.3. The Tarski–Seidenberg principle
3.4. The Projection Theorem and elimination of quantifiers
3.5. The Tarski transfer principle
3.6. Exercises
3.7. Notes
Chapter 4. Cylindrical algebraic decomposition
4.1. Some basic ideas
4.2. Resultants
4.3. Subresultants
4.4. Delineable sets
4.5. Cylindrical algebraic decomposition
4.6. Exercises
4.7. Notes
Chapter 5. Linear, semidefinite, and conic optimization
5.1. Linear optimization
5.2. Semidefinite optimization
5.3. Conic optimization
5.4. Interior point methods and barrier functions
5.5. Exercises
5.6. Notes
Part II. Positive polynomials, sums of squares, and convexity
Chapter 6. Positive polynomials
6.1. Nonnegative univariate polynomials
6.2. Positive polynomials and sums of squares
6.3. Hilbert’s 17th problem
6.4. Systems of polynomial inequalities
6.5. The Positivstellensatz
6.6. Theorems of Pólya and Handelman
6.7. Putinar’s theorem
6.8. Schmüdgen’s theorem
6.9. Exercises
6.10. Notes
Chapter 7. Polynomial optimization
7.1. Linear programming relaxations
7.2. Unconstrained optimization and sums of squares
7.3. The moment view on unconstrained optimization
7.4. Duality and the moment problem
7.5. Optimization over compact sets
7.6. Finite convergence and detecting optimality
7.7. Exercises
7.8. Notes
Chapter 8. Spectrahedra
8.1. Monic representations
8.2. Rigid convexity
8.3. Farkas’s lemma for spectrahedra
8.4. Exact infeasibility certificates
8.5. Containment of spectrahedra
8.6. Spectrahedral shadows
8.7. Exercises
8.8. Notes
Part III. Outlook
Chapter 9. Stable and hyperbolic polynomials
9.1. Univariate stable polynomials
9.2. Real-rooted polynomials in combinatorics
9.3. The Routh–Hurwitz problem
9.4. Multivariate stable polynomials
9.5. Hyperbolic polynomials
9.6. Determinantal representations
9.7. Hyperbolic programming
9.8. Exercises
9.9. Notes
Chapter 10. Relative entropy methods in semialgebraic optimization
10.1. The exponential cone and the relative entropy cone
10.2. The basic AM/GM idea
10.3. Sums of arithmetic-geometric exponentials
10.4. Constrained nonnegativity over convex sets
10.5. Circuits
10.6. Sublinear circuits
10.7. Exercises
10.8. Notes
Appendix A. Background material
A.1. Algebra
A.2. Convexity
A.3. Positive semidefinite matrices
A.4. Moments
A.5. Complexity
Notation
Bibliography
Index