Real Algebraic Geometry and Optimization

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

Author(s): Thorsten Theobald
Series: Graduate Studies in Mathematics 241
Publisher: American Mathematical Society
Year: 2024

Language: English
Pages: 293

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