Moments, Positive Polynomials And Their Applications

by Jean Bernard Lasserre

Overview

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.

Product Details

ISBN-13:	9781848164451
Publisher:	Imperial College Press
Publication date:	10/02/2009
Series:	Series On Optimization And Its Applications , #1
Pages:	384
Product dimensions:	6.10(w) x 9.10(h) x 1.00(d)

Table of Contents

Preface vii

Acknowledgments xiii

Part I Moments and Positive Polynomials 1

1 The Generalized Moment Problem 3

1.1 Formulations 4

1.2 Duality Theory 7

1.3 Computational Complexity 10

1.4 Summary 12

1.5 Exercises 13

1.6 Notes and Sources 13

2 Positive Polynomials 15

2.1 Sum of Squares Representations and Semi-definite Optimization 16

2.2 Nonnegative Versus s.o.s. Polynomials 20

2.3 Representation Theorems: Univariate Case 22

2.4 Representation Theorems: Mutivariate Case 24

2.5 Polynomials Positive on a Compact Basic Semi-algebraic Set 28

2.5.1 Representations via sums of squares 28

2.5.2 A matrix version of Putinar's Positivstellensatz 33

2.5.3 An alternative representation 34

2.6 Polynomials Nonnegative on Real Varieties 37

2.7 Representations with Sparsity Properties 39

2.8 Representation of Convex Polynomials 42

2.9 Summary 47

2.10 Exercises 48

2.11 Notes and Sources 49

3 Moments 51

3.1 The One-dimensional Moment Problem 53

3.1.1 The full moment problem 54

3.1.2 The truncated moment problem 56

3.2 The Multi-dimensional Moment Problem 57

3.2.1 Moment and localizing matrix 58

3.2.2 Positive and flat extensions of moment matrices 61

3.3 The K-moment Problem 62

3.4 Moment Conditions for Bounded Density 66

3.4.1 The compact case 67

3.4.2 The non compact case 68

3.5 Summary 70

3.6 Exercises 71

3.7 Notes and Sources 71

4 Algorithms for Moment Problems 73

4.1 The Overall Approach 73

4.2 Semidefinite Relaxations 75

4.3 Extraction of Solutions 80

4.4 Linear Relaxations 86

4.5 Extensions 87

4.5.1 Extensions to countably many moment constraints 87

4.5.2 Extension to several measures 88

4.6Exploiting Sparsity 9

4.6.1 Sparse semidefinite relaxations 94

4.6.2 Computational complexity 96

4.7 Summary 97

4.8 Exercises 98

4.9 Notes and Sources 99

4.10 Proofs 99

4.10.1 Proof of Theorem 4.3 99

4.10.2 Proof of Theorem 4.7 102

Part II Applications 107

5 Global Optimization over Polynomials 109

5.1 The Primal and Dual Perspectives 110

5.2 Unconstrained Polynomial Optimization 111

5.3 Constrained Polynomial Optimization: Semidefinite Relaxations 117

5.3.1 Obtaining global minimizers 119

5.3.2 The univariate case 121

5.3.3 Numerical experiments 122

5.3.4 Exploiting sparsity 123

5.4 Linear Programming Relaxations 125

5.4.1 The case of a convex polytope 126

5.4.2 Contrasting LP and semidefinite relaxations 126

5.5 Global Optimality Conditions 127

5.6 Convex Polynomial Programs 130

5.6.1 An extension of Jensen's inequality 131

5.6.2 The s.o.s.-convex case 132

5.6.3 The strictly convex case 133

5.7 Discrete Optimization 134

5.7.1 Boolean optimization 135

5.7.2 Back to unconstrained optimization 137

5.8 Global Minimization of a Rational Function 138

5.9 Exploiting Symmetry 141

5.10 Summary 143

5.11 Exercises 144

5.12 Notes and Sources 144

6 Systems of Polynomial Equations 147

6.1 Introduction 147

6.2 Finding a Real Solution to Systems of Polynomial Equations 148

6.3 Finding All Complex and/or All Real Solutions: A Unified Treatment 152

6.3.1 Basic underlying idea 155

6.3.2 The moment-matrix algorithm 155

6.4 Summary 160

6.5 Exercises 161

6.6 Notes and Sources 161

7 Applications in Probability 163

7.1 Upper Bounds on Measures with Moment Conditions 163

7.2 Measuring Basic Semi-algebraic Sets 168

7.3 Measures with Given Marginals 175

7.4 Summary 177

7.5 Exercises 177

7.6 Notes and Sources 178

8 Markov Chains Applications 181

8.1 Bounds on Invariant Measures 183

8.1.1 The compact case 183

8.1.2 The non compact case 185

8.2 Evaluation of Ergodic Criteria 187

8.3 Summary 189

8.4 Exercises 190

8.5 Notes and Sources 191

9 Application in Mathematical Finance 193

9.1 Option Pricing with Moment Information 193

9.2 Option Pricing with a Dynamic Model 196

9.2.1 Notation and definitions 197

9.2.2 The martingale approach 198

9.2.3 Semidefinite relaxations 200

9.3 Summary 202

9.4 Notes and Sources 203

10 Application in Control 205

10.1 Introduction 205

10.2 Weak Formulation of Optimal Control Problems 206

10.3 Semidefinite Relaxations for the OCP 210

10.3.1 Examples 212

10.4 Summary 215

10.5 Notes and Sources 216

11 Convex Envelope and Representation of Convex Sets 219

11.1 The Convex Envelope of a Rational Function 219

11.1.1 Convex envelope and the generalized moment problem 220

11.1.2 Semidefinite relaxations 223

11.2 Semidefinite Representation of Convex Sets 225

11.2.1 Semidefinite representation of co(K) 226

11.2.2 Semidefinite representation of convex basic semi-algebraic sets 229

11.3 Algebraic Certificates of Convexity 234

11.4 Summary 239

11.5 Exercises 239

11.6 Notes and Sources 240

12 Multivariate Integration 243

12.1 Integration of a Rational Function 243

12.1.1 The multivariable case 245

12.1.2 The univariate esse 246

12.2 Integration of Exponentials of Polynomials 250

12.2.1 The moment approach 251

12.2.2 Semidcfinite relaxations 253

12.2.3 The univariate case 254

12.3 Maximum Entropy Estimation 256

12.3.1 The entropy approach 257

12.3.2 Gradient and Hessian computation 259

12.4 Summary 260

12.5 Exercises 262

12.6 Notes and Sources 262

13 Min-Max Problems and Nash Equilibria 265

13.1 Robust Polynomial Optimization 265

13.1.1 Robust Linear Programming 267

13.1.2 Robust Semidefinite Programming 269

13.2 Minimizing the Sup of Finitely Many Rational Functions 270

13.3 Application to Nash Equilibria 273

13.3.1 N-player games 273

13.3.2 Two-player zero-sum polynomial games 276

13.3.3 The univariate case 280

13.4 Exercises 251

13.5 Notes and Sources 282

14 Rounds on Linear PDE 285

14.1 Linear Partial Differential Equations 285

14.2 Notes and Sources 288

Final Remarks 291

Appendix A Background from Algebraic Geometry 293

A.1 Fields and Cones 293

A.2 Ideals 295

A.3 Varieties 296

A.4 Preordering 298

A.5 Algebraic and Semi-algebraic Sets over a Real Closed Field 300

A.6 Notes and Sources 302

Appendix B Measures, Weak Convergence and Marginals 305

B.1 Weak Convergence of Measures 305

B.2 Measures with Given Marginals 308

B.3 Notes and Sources 310

Appendix C Some Basic Results in Optimization 311

C.1 Non Linear Programming 311

C.2 Semidefinite Programming 313

C.3 Infinite-dimensional Linear Programming 316

C.4 Proof of Theorem 1.3 318

C.5 Notes and Sources 319

Appendix D The GloptiPoly Software 321

D.1 Presentation 321

D.2 Installation 321

D.3 Getting started 322

D.4 Description 323

D.4.1 Multivariate polynomials (mpol) 324

D.4.2 Measures (meas) 325

D.4.3 Moments (mom) 325

D.4.4 Support constraints (supcen) 327

D.4.5 Moment constraints (momcon) 327

D.4.6 Floating point numbers (double) 328

D.5 Solving Moment Problems (msdp) 329

D.5.1 Unconstrained minimization 329

D.5.2 Constrained minimization 331

D.5.3 Several measures 335

D.6 Notes and Sources 337

Glossary 339

Bibliography 341

Index 359