Table of Contents
Preface v
Foreword xi
Acknowledgments xiii
1 Semi-algebraic Geometry 1
1.1 Algebraic and semi-algebraic sets 1
1.2 Some lemmas 4
1.3 Cell decomposition 10
1.3.1 Definition of analytic cell decompositions 10
1.3.2 Proof of Theorems 1.1 and 1.2 11
1.3.3 Properties of cells 15
1.4 Stratification of semi-algebraic sets 17
1.5 Dimension of semi-algebraic sets via cell decomposition 17
1.6 The Tarski-Seidenberg theorem 19
1.6.1 Logical formulation of the Tarski-Seidenberg theorem 20
1.6.2 Some examples of semi-algebraic sets and functions 23
1.7 Piecewise analyticity of semi-algebraic functions 25
1.8 Monotonicity theorem 25
1.9 Semi-algebraic Sard's theorem 26
1.10 Curve selection lemma 29
1.11 Growth dichotomy lemma 32
1.12 Connected components of semi-algebraic sets 32
1.13 Lojasiewiez's inequalities 33
2 Critical Points and Tangencies 39
2.1 Regularity 39
2.1.1 Optimality conditions 39
2.1.2 Transversality to large spheres 41
2.2 Critical points 43
2.3 Tangencies 46
2.3.1 Tangency varieties 46
2.3.2 Tangency values 51
3 Hölderian Error Bounds for Polynomial Systems 55
3.1 Preliminaries 55
3.1.1 Subdifferentials 55
3.1.2 The Ekeland variational principle 57
3.2 Non-smooth Lojasiewicz's gradient inequality with explicit exponent for maxima of finitely many polynomials 58
3.3 Bounded Hölderian error bounds with explicit exponents for basic closed semi-algebraic sets 60
3.4 Criteria for the existence of global Hölderian error bounds 65
3.5 The Palais-Smale condition and global Hölderian error bounds 69
3.6 Goodness at infinity and global Hölderian error bounds 72
3.7 Newton polyhedra and non-degeneracy conditions 75
3.7.1 Newton polyhedra 75
3.7.2 Non-degeneracy conditions 78
3.8 Non-degeneracy and global Hölderian error bounds 80
3.9 Global Hölderian error bounds for one quadratic inequality 86
4 Prank-Wolfe Type Theorem for Polynomial Programs 91
4.1 Frank-Wolfe type theorem for convex polynomial programs 91
4.1.1 Some properties of convex polynomials 92
4.1.2 Frank-Wolfe type theorem 94
4.2 Frank-Wolfe type theorem for non-degenerate polynomial programs 96
4.2.1 Non-degeneracy and the Palais- Sin ale condition 96
4.2.2 Non-degeneracy and regularity at infinity 101
4.2.3 Prank-Wolfe type theorem 102
5 Well-Posedness in Unconstrained Polynomial Optimization 109
5.1 Openness and density of Morse polynomials 109
5.2 Openness and density of non-degenerate polynomials 112
5.3 Non-degeneracy and coercivity 116
5.4 Well-posedness in unconstrained polynomial optimization 120
6 Generic Properties in Polynomial Optimization 127
6.1 Regularity 127
6.2 Optimality conditions 128
6.3 Uniqueness of optima] solutions 134
6.4 Goodness at infinity 137
6.5 Coercivity 139
6.6 Genericity in polynomial optimization 143
7 Optimization of Polynomials on Compact Semi-algebraic Sets 153
7.1 Semidefinite programming and sums of squares 153
7.1.1 Semidefinite programming 153
7.1.2 Sums of squares 154
7.2 Representations of positive polynomials on semi-algebraic sets 157
7.3 Optimization of polynomials on compact semi-algebraic sets 160
7.3.1 Case 1: The quadratic module Q(+gi, hj) is Archimedean 161
7.3.2 Case 2: The constraint set S is compact 165
7.4 Optimality conditions and finite convergence of Lasserre's hierarchy 166
7.4.1 Optimality conditions 166
7.4.2 Boundary Hessian conditions 167
7.4.3 Optimality conditions and boundary Hessian conditions 169
7.4.4 Optimality conditions and finite convergence of Lasserre's hierarchy 172
7.4.5 Global optimality conditions 177
7.5 Optimization of polynomials on finite sets 180
7.5.1 Case 1: The algebraic set Z(g1;,…,gl;) is finite 180
7.5.2 Case 2: The constraint set S is finite 183
7.6 Finite convergence to the unique minimizer 185
8 Optimization of Polynomials on Non-compact Semi-algebraic Sets 189
8.1 Unconstrained polynomial optimization I 189
8.1.1 A representation of positive polynomials on semi-algebraic sets 190
8.1.2 Sets of critical points and sums of squares 190
8.1.3 Application in optimization 191
8.2 Unconstrained polynomial optimization II 193
8.2.1 Truncated tangency varieties and sums of squares 194
8.2.2 Application in optimization 196
8.3 Constrained polynomial optimization I 197
8.3.1 Sets of critical points and sums of squares 197
8.3.2 Application in optimization 200
8.4 Constrained polynomial optimization II 202
8.4.1 Truncated tangency varieties and sums of squares 202
8.4.2 Application in optimization 206
8.5 Further remarks 208
9 Convex Polynomial Optimization 211
9.1 Further properties on convex polynomials 211
9.2 Asymptotic convergence 215
9.3 Finite convergence 220
Glossary 227
Bibliography 231
Index 239
