Real Algebraic Geometry and Optimization

This book provides a comprehensive and user-friendly exploration of the tremendous recent developments that reveal the connections between real algebraic geometry and optimization, two subjects that were usually taught separately until the beginning of the 21st century. Real algebraic geometry studies the solutions of polynomial equations and polynomial inequalities over the real numbers. Real algebraic problems arise in many applications, including science and engineering, computer vision, robotics, and game theory. Optimization is concerned with minimizing or maximizing a given objective function over a feasible set. Presenting key ideas from classical and modern concepts in real algebraic geometry, this book develops related convex optimization techniques for polynomial optimization. The connection to optimization invites a computational view on real algebraic geometry and opens doors to applications. Intended as an introduction for students of mathematics or related fields at an advanced undergraduate or graduate level, this book serves as a valuable resource for researchers and practitioners. Each chapter is complemented by a collection of beneficial exercises, notes on references, and further reading. As a prerequisite, only some undergraduate algebra is required. 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