Moments, Positive Polynomials and Their Applications

by Lasserre, Jean-Bernard

• ISBN13: 9781848164451
• ISBN10: 1848164459
• Format: Hardcover
• Copyright: 2009-11-30
• Publisher: Imperial College Pr

Summary

Many important applications in global optimization, algebra, probability and statistics, applied mathematics, control theory, financial mathematics, inverse problems, etc. can be modeled as a particular instance of the Generalized Moment Problem (GMP). This book introduces a new general methodology to solve the GMP when its data are polynomials and basic semi-algebraic sets. This methodology combines semidefinite programming with recent results from real algebraic geometry to provide a hierarchy of semidefinite relaxations converging to the desired optimal value. Applied on appropriate cones, standard duality in convex optimization nicely expresses the duality between moments and positive polynomials. In the second part, the methodology is particularized and described in detail for various applications, including global optimization, probability, optimal control, mathematical finance, multivariate integration, etc., and examples are provided for each particular application.

Table of Contents

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.