Table of Contents
Preface v
Acknowledgments ix
1 Fourier-Motzkin elimination 1
1.1 Linear inequalities 3
1.2 Linear optimization using elimination 8
1.3 Polyhedra 9
1.4 Exercises 13
2 Affine subspaces 17
2.1 Definition and basics 18
2.2 The affine hull 20
2.3 Affine subspaces and subspaces 21
2.4 Affine independence and the dimension of a subset 22
2.5 Exercises 23
3 Convex subsets 27
3.1 Basics 28
3.2 The convex hull 30
3.3 Faces of convex subsets 32
3.4 Convex cones 36
3.5 Carathéodory's theorem 41
3.6 The convex hull, simplicial subsets and Bland's rule 45
3.7 Exercises 48
4 Polyhedra 55
4.1 Faces of polyhedra 56
4.2 Extreme points and linear optimization 61
4.3 Weyl's theorem 63
4.4 Farkas's lemma 64
4.5 Three applications of Farkas's lemma 66
4.5.1 Markov chains and steady states 66
4.5.2 Gordan's theorem 69
4.5.3 Duality in linear programming 70
4.6 Minkowski's theorem 74
4.7 Parametrization of polyhedra 75
4.8 Doubly stochastic matrices: The Birkhoff polytope 76
4.8.1 Perfect pairings and doubly stochastic matrices 78
4.9 Exercises 82
5 Computations with polyhedra 85
5.1 Extreme rays and minimal generators in convex cones 86
5.2 Minimal generators of a polyhedral cone 87
5.3 The double description method 90
5.3.1 Converting from half space to vertex representation 95
5.3.2 Converting from vertex to half space representation 96
5.3.3 Computing the convex hull 98
5.4 Linear programming and the simplex algorithm 100
5.4.1 Two examples of linear programs 102
5.4.2 The simplex algorithm in a special case 105
5.4.3 The simplex algorithm for polyhedra in general form 109
5.4.4 The simplicial hack 111
5.4.5 The computational miracle of the simplex tableau 113
5.4.6 Computing a vertex in a polyhedron 119
5.5 Exercises 120
6 Closed convex subsets and separating hyperplanes 125
6.1 Closed convex subsets 126
6.2 Supporting hyperplanes 129
6.3 Separation by hyperplanes 133
6.4 Exercises 135
7 Convex functions 141
7.1 Basics 143
7.2 Jensen's inequality 145
7.3 Minima of convex functions 147
7.4 Convex functions of one variable 148
7.5 Differentiable functions of one variable 150
7.5.1 The Newton-Raphson method for finding roots 152
7.5.2 Critical points and extrema 153
7.6 Taylor polynomials 156
7.7 Differentiable convex functions 159
7.8 Exercises 161
8 Differentiable functions of several variables 167
8.1 Differentiability 167
8.1.1 The Newton-Raphson method for several variables 171
8.1.2 Local extrema for functions of several variables 172
8.2 The chain rule 174
8.3 Lagrange multipliers 176
8.4 The arithmetic-geometric inequality revisited 183
8.5 Exercises 184
9 Convex functions of several variables 187
9.1 Subgradients 188
9.2 Convexity and the Hessian 190
9.3 Positive definite and positive semidefinite matrices 193
9.4 Principal minors and definite matrices 196
9.5 The positive semidefinite cone 198
9.6 Reduction of symmetric matrices 201
9.7 The spectral theorem 205
9.8 Quadratic forms 208
9.9 Exercises 214
10 Convex optimization 223
10.1 A geometric optimality criterion 224
10.2 The Karush-Kuhn-Tucker conditions 226
10.3 An example 230
10.4 The Langrangian, saddle points, duality and game theory 232
10.5 An interior point method 236
10.5.1 Newtonian descent, exact line search and bisection 238
10.5.2 Polyhedral constraints 240
10.6 Maximizing convex functions over polytopes 243
10.6.1 Convex functions are continuous on open subsets 244
10.7 Exercises 245
Appendix A Analysis 253
A.1 Measuring distances 253
A.2 Sequences 255
A.2.1 Supremum and infimum 258
A.3 Bounded sequences 258
A.4 Closed subsets and open subsets 259
A.5 The interior and boundary of a set 260
A.6 Continuous functions 261
A.7 The main theorem 262
A.8 Exercises 262
Appendix B Linear (in)dependence and the rank of a matrix 265
B.1 Linear dependence and linear equations 265
B.2 The rank of a matrix 267
B.3 Exercises 270
Bibliography 273
Index 277
