Note: Supplemental materials are not guaranteed with Rental or Used book purchases.
Purchase Benefits
What is included with this book?
Preface | p. vii |
Acknowledgments | p. xiii |
Moments and Positive Polynomials | p. 1 |
The Generalized Moment Problem | p. 3 |
Formulations | p. 4 |
Duality Theory | p. 7 |
Computational Complexity | p. 10 |
Summary | p. 12 |
Exercises | p. 13 |
Notes and Sources | p. 13 |
Positive Polynomials | p. 15 |
Sum of Squares Representations and Semi-definite Optimization | p. 16 |
Nonnegative Versus s.o.s. Polynomials | p. 20 |
Representation Theorems: Univariate Case | p. 22 |
Representation Theorems: Mutivariate Case | p. 24 |
Polynomials Positive on a Compact Basic Semi-algebraic Set | p. 28 |
Representations via sums of squares | p. 28 |
A matrix version of Putinar's Positivstellensatz | p. 33 |
An alternative representation | p. 34 |
Polynomials Nonnegative on Real Varieties | p. 37 |
Representations with Sparsity Properties | p. 39 |
Representation of Convex Polynomials | p. 42 |
Summary | p. 47 |
Exercises | p. 48 |
Notes and Sources | p. 49 |
Moments | p. 51 |
The One-dimensional Moment Problem | p. 53 |
The full moment problem | p. 54 |
The truncated moment problem | p. 56 |
The Multi-dimensional Moment Problem | p. 57 |
Moment and localizing matrix | p. 58 |
Positive and flat extensions of moment matrices | p. 61 |
The K-moment Problem | p. 62 |
Moment Conditions for Bounded Density | p. 66 |
The compact case | p. 67 |
The non compact case | p. 68 |
Summary | p. 70 |
Exercises | p. 71 |
Notes and Sources | p. 71 |
Algorithms for Moment Problems | p. 73 |
The Overall Approach | p. 73 |
Semidefinite Relaxations | p. 75 |
Extraction of Solutions | p. 80 |
Linear Relaxations | p. 86 |
Extensions | p. 87 |
Extensions to countably many moment constraints | p. 87 |
Extension to several measures | p. 88 |
Exploiting Sparsity | p. 9 |
Sparse semidefinite relaxations | p. 94 |
Computational complexity | p. 96 |
Summary | p. 97 |
Exercises | p. 98 |
Notes and Sources | p. 99 |
Proofs | p. 99 |
Proof of Theorem 4.3 | p. 99 |
Proof of Theorem 4.7 | p. 102 |
Applications | p. 107 |
Global Optimization over Polynomials | p. 109 |
The Primal and Dual Perspectives | p. 110 |
Unconstrained Polynomial Optimization | p. 111 |
Constrained Polynomial Optimization: Semidefinite Relaxations | p. 117 |
Obtaining global minimizers | p. 119 |
The univariate case | p. 121 |
Numerical experiments | p. 122 |
Exploiting sparsity | p. 123 |
Linear Programming Relaxations | p. 125 |
The case of a convex polytope | p. 126 |
Contrasting LP and semidefinite relaxations | p. 126 |
Global Optimality Conditions | p. 127 |
Convex Polynomial Programs | p. 130 |
An extension of Jensen's inequality | p. 131 |
The s.o.s.-convex case | p. 132 |
The strictly convex case | p. 133 |
Discrete Optimization | p. 134 |
Boolean optimization | p. 135 |
Back to unconstrained optimization | p. 137 |
Global Minimization of a Rational Function | p. 138 |
Exploiting Symmetry | p. 141 |
Summary | p. 143 |
Exercises | p. 144 |
Notes and Sources | p. 144 |
Systems of Polynomial Equations | p. 147 |
Introduction | p. 147 |
Finding a Real Solution to Systems of Polynomial Equations | p. 148 |
Finding All Complex and/or All Real Solutions: A Unified Treatment | p. 152 |
Basic underlying idea | p. 155 |
The moment-matrix algorithm | p. 155 |
Summary | p. 160 |
Exercises | p. 161 |
Notes and Sources | p. 161 |
Applications in Probability | p. 163 |
Upper Bounds on Measures with Moment Conditions | p. 163 |
Measuring Basic Semi-algebraic Sets | p. 168 |
Measures with Given Marginals | p. 175 |
Summary | p. 177 |
Exercises | p. 177 |
Notes and Sources | p. 178 |
Markov Chains Applications | p. 181 |
Bounds on Invariant Measures | p. 183 |
The compact case | p. 183 |
The non compact case | p. 185 |
Evaluation of Ergodic Criteria | p. 187 |
Summary | p. 189 |
Exercises | p. 190 |
Notes and Sources | p. 191 |
Application in Mathematical Finance | p. 193 |
Option Pricing with Moment Information | p. 193 |
Option Pricing with a Dynamic Model | p. 196 |
Notation and definitions | p. 197 |
The martingale approach | p. 198 |
Semidefinite relaxations | p. 200 |
Summary | p. 202 |
Notes and Sources | p. 203 |
Application in Control | p. 205 |
Introduction | p. 205 |
Weak Formulation of Optimal Control Problems | p. 206 |
Semidefinite Relaxations for the OCP | p. 210 |
Examples | p. 212 |
Summary | p. 215 |
Notes and Sources | p. 216 |
Convex Envelope and Representation of Convex Sets | p. 219 |
The Convex Envelope of a Rational Function | p. 219 |
Convex envelope and the generalized moment problem | p. 220 |
Semidefinite relaxations | p. 223 |
Semidefinite Representation of Convex Sets | p. 225 |
Semidefinite representation of co(K) | p. 226 |
Semidefinite representation of convex basic semi-algebraic sets | p. 229 |
Algebraic Certificates of Convexity | p. 234 |
Summary | p. 239 |
Exercises | p. 239 |
Notes and Sources | p. 240 |
Multivariate Integration | p. 243 |
Integration of a Rational Function | p. 243 |
The multivariable case | p. 245 |
The univariate esse | p. 246 |
Integration of Exponentials of Polynomials | p. 250 |
The moment approach | p. 251 |
Semidcfinite relaxations | p. 253 |
The univariate case | p. 254 |
Maximum Entropy Estimation | p. 256 |
The entropy approach | p. 257 |
Gradient and Hessian computation | p. 259 |
Summary | p. 260 |
Exercises | p. 262 |
Notes and Sources | p. 262 |
Min-Max Problems and Nash Equilibria | p. 265 |
Robust Polynomial Optimization | p. 265 |
Robust Linear Programming | p. 267 |
Robust Semidefinite Programming | p. 269 |
Minimizing the Sup of Finitely Many Rational Functions | p. 270 |
Application to Nash Equilibria | p. 273 |
N-player games | p. 273 |
Two-player zero-sum polynomial games | p. 276 |
The univariate case | p. 280 |
Exercises | p. 251 |
Notes and Sources | p. 282 |
Rounds on Linear PDE | p. 285 |
Linear Partial Differential Equations | p. 285 |
Notes and Sources | p. 288 |
Final Remarks | p. 291 |
Background from Algebraic Geometry | p. 293 |
Fields and Cones | p. 293 |
Ideals | p. 295 |
Varieties | p. 296 |
Preordering | p. 298 |
Algebraic and Semi-algebraic Sets over a Real Closed Field | p. 300 |
Notes and Sources | p. 302 |
Measures, Weak Convergence and Marginals | p. 305 |
Weak Convergence of Measures | p. 305 |
Measures with Given Marginals | p. 308 |
Notes and Sources | p. 310 |
Some Basic Results in Optimization | p. 311 |
Non Linear Programming | p. 311 |
Semidefinite Programming | p. 313 |
Infinite-dimensional Linear Programming | p. 316 |
Proof of Theorem 1.3 | p. 318 |
Notes and Sources | p. 319 |
The GloptiPoly Software | p. 321 |
Presentation | p. 321 |
Installation | p. 321 |
Getting started | p. 322 |
Description | p. 323 |
Multivariate polynomials (mpol) | p. 324 |
Measures (meas) | p. 325 |
Moments (mom) | p. 325 |
Support constraints (supcen) | p. 327 |
Moment constraints (momcon) | p. 327 |
Floating point numbers (double) | p. 328 |
Solving Moment Problems (msdp) | p. 329 |
Unconstrained minimization | p. 329 |
Constrained minimization | p. 331 |
Several measures | p. 335 |
Notes and Sources | p. 337 |
Glossary | p. 339 |
Bibliography | p. 341 |
Index | p. 359 |
Table of Contents provided by Ingram. All Rights Reserved. |