1 Mathematical Preliminaries 1
1.1 Notation and Preliminary Definitions 2
1.1.1 Integers, Rationals, Reals, Rn 2
1.1.2 Inner Product, Norm, Metric 4
1.2 Sets and Sequences in Rn 7
1.2.1 Sequences and Limits 7
1.2.2 Subsequences and Limit Points 10
1.2.3 Cauchy Sequences and Completeness 11
1.2.4 Suprema, Infima, Maxima, Minima 14
1.2.5 Monotone Sequences in R 17
1.2.6 The Lim Sup and Lim Inf 18
1.2.7 Open Balls, Open Sets, Closed Sets 22
1.2.8 Bounded Sets and Compact Sets 23
1.2.9 Convex Combinations and Convex Sets 23
1.2.10 Unions, Intersections, and Other Binary Operations 24
1.3 Matrices 30
1.3.1 Sum, Product, Transpose 30
1.3.2 Some Important Classes of Matrices 32
1.3.3 Rank of a Matrix 33
1.3.4 The Determinant 35
1.3.5 The Inverse 38
1.3.6 Calculating the Determinant 39
1.4 Functions 41
1.4.1 Continuous Functions 41
1.4.2 Differentiable and Continuously Differentiable Functions 43
1.4.3 Partial Derivatives and Differentiability 46
1.4.4 Directional Derivatives and Differentiability 48
1.4.5 Higher Order Derivatives 49
1.5 Quadratic Forms: Definite and Semidefinite Matrices 50
1.5.1 Quadratic Forms and Definiteness 50
1.5.2 Identifying Definiteness and Semidefiniteness 53
1.6 Some Important Results 55
1.6.1 Separation Theorems 56
1.6.2 The Intermediate and Mean Value Theorems 60
1.6.3 The Inverse and Implicit Function Theorems 65
1.7 Exercises 66
2 Optimization in Rn 74
2.1 Optimization Problems in Rn 74
2.2 Optimization Problems in Parametric Form 77
2.3 Optimization Problems: Some Examples 78
2.3.1 Utility Maximization 78
2.3.2 Expenditure Minimization 79
2.3.3 Profit Maximization 80
2.3.4 Cost Minimization 80
2.3.5 Consumption-Leisure Choice 81
2.3.6 Portfolio Choice 81
2.3.7 Identifying Pareto Optima 82
2.3.8 Optimal Provision of Public Goods 83
2.3.9 Optimal Commodity Taxation 84
2.4 Objectives of Optimization Theory 85
2.5 A Roadmap 86
2.6 Exercises 88
3 Existence of Solutions: The Weierstrass Theorem 90
3.1 The Weierstrass Theorem 90
3.2 The Weierstrass Theorem in Applications 92
3.3 A Proof of the Weierstrass Theorem 96
3.4 Exercises 97
4 Unconstrained Optima 100
4.1 “Unconstrained” Optima 100
4.2 First-Order Conditions 101
4.3 Second-Order Conditions 103
4.4 Using the First- and Second-Order Conditions 104
4.5 A Proof of the First-Order Conditions 106
4.6 A Proof of the Second-Order Conditions 108
4.7 Exercises 110
5 Equality Constraints and the Theorem of Lagrange 112
5.1 Constrained Optimization Problems 112
5.2 Equality Constraints and the Theorem of Lagrange 113
5.2.1 Statement of the Theorem 114
5.2.2 The Constraint Qualification 115
5.2.3 The Lagrangean Multipliers 116
5.3 Second-Order Conditions 117
5.4 Using the Theorem of Lagrange 121
5.4.1 A “Cookbook” Procedure 121
5.4.2 Why the Procedure Usually Works 122
5.4.3 When It Could Fail 123
5.4.4 A Numerical Example 127
5.5 Two Examples from Economics 128
5.5.1 An Illustration from Consumer Theory 128
5.5.2 An Illustration from Producer Theory 130
5.5.3 Remarks 132
5.6 A Proof of the Theorem of Lagrange 135
5.7 A Proof of the Second-Order Conditions 137
5.8 Exercises 142
6 Inequality Constraints and the Theorem of Kuhn and Tucker 145
6.1 The Theorem of Kuhn and Tucker 145
6.1.1 Statement of the Theorem 145
6.1.2 The Constraint Qualification 147
6.1.3 The Kuhn-Tucker Multipliers 148
6.2 Using the Theorem of Kuhn and Tucker 150
6.2.1 A “Cookbook” Procedure 150
6.2.2 Why the Procedure Usually Works 151
6.2.3 When It Could Fail 152
6.2.4 A Numerical Example 155
6.3 Illustrations from Economics 157
6.3.1 An Illustration from Consumer Theory 158
6.3.2 An Illustration from Producer Theory 161
6.4 The General Case: Mixed Constraints 164
6.5 A Proof of the Theorem of Kuhn and Tucker 165
6.6 Exercises 168
7 Convex Structures in Optimization Theory 172
7.1 Convexity Defined 173
7.1.1 Concave and Convex Functions 174
7.1.2 Strictly Concave and Strictly Convex Functions 176
7.2 Implications of Convexity 177
7.2.1 Convexity and Continuity 177
7.2.2 Convexity and Differentiability 179
7.2.3 Convexity and the Properties of the Derivative 183
7.3 Convexity and Optimization 185
7.3.1 Some General Observations 185
7.3.2 Convexity and Unconstrained Optimization 187
7.3.3 Convexity and the Theorem of Kuhn and Tucker 187
7.4 Using Convexity in Optimization 189
7.5 A Proof of the First-Derivative Characterization of Convexity 190
7.6 A Proof of the Second-Derivative Characterization of Convexity 191
7.7 A Proof of the Theorem of Kuhn and Tucker under Convexity 194
7.8 Exercises 198
8 Quasi-Convexity and Optimization 203
8.1 Quasi-Concave and Quasi-Convex Functions 204
8.2 Quasi-Convexity as a Generalization of Convexity 205
8.3 Implications of Quasi-Convexity 209
8.4 Quasi-Convexity and Optimization 213
8.5 Using Quasi-Convexity in Optimization Problems 215
8.6 A Proof of the First-Derivative Characterization of Quasi-Convexity 216
8.7 A Proof of the Second-Derivative Characterization ofQuasi-Convexity 217
8.8 A Proof of the Theorem of Kuhn and Tucker under Quasi-Convexity 220
8.9 Exercises 221
9 Parametric Continuity: The Maximum Theorem 224
9.1 Correspondences 225
9.1.1 Upper- and Lower-Semicontinuous Correspondences 225
9.1.2 Additional Definitions 228
9.1.3 A Characterization of Semicontinuous Correspondences 229
9.1.4 Semicontinuous Functions and Semicontinuous Correspondences 233
9.2 Parametric Continuity:The Maximum Theorem 235
9.2.1 The Maximum Theorem 235
9.2.2 The Maximum Theorem under Convexity 237
9.3 An Application to Consumer Theory 240
9.3.1 Continuity of the Budget Correspondence 240
9.3.2 The Indirect Utility Function and Demand Correspondence 242
9.4 An Application to Nash Equilibrium 243
9.4.1 Normal-Form Games 243
9.4.2 The Brouwer/Kakutani Fixed Point Theorem 244
9.4.3 Existence of Nash Equilibrium 246
9.5 Exercises 247
10 Supermodularity and Parametric Monotonicity 253
10.1 Lattices and Supermodularity 254
10.1.1 Lattices 254
10.1.2 Supermodularity and Increasing Differences 255
10.2 Parametric Monotonicity 258
10.3 An Application to Supermodular Games 262
10.3.1 Supermodular Games 262
10.3.2 The Tarski Fixed Point Theorem 263
10.3.3 Existence of Nash Equilibrium 263
10.4 A Proof of the Second-Derivative Characterization of Supermodularity 264
10.5 Exercises 266
11 Finite-Horizon Dynamic Programming 268
11.1 Dynamic Programming Problems 268
11.2 Finite-Horizon Dynamic Programming 268
11.3 Histories, Strategies, and the Value Function 269
11.4 Markovian Strategies 271
11.5 Existence of an Optimal Strategy 272
11.6 An Example: The Consumption-Savings Problem 276
11.7 Exercises 278
12 Stationary Discounted Dynamic Programming 281
12.1 Description of the Framework 281
12.2 Histories, Strategies, and the Value Function 282
12.3 The Bellman Equation 283
12.4 A Technical Digression 286
12.4.1 Complete Metric Spaces and Cauchy Sequences 286
12.4.2 Contraction Mappings 287
12.4.3 Uniform Convergence 289
12.5 Existence of an Optimal Strategy 291
12.5.1 A Preliminary Result 292
12.5.2 Stationary Strategies 294
12.5.3 Existence of an Optimal Strategy 295
12.6 An Example: The Optimal Growth Model 298
12.6.1 The Model 299
12.6.2 Existence of Optimal Strategies 300
12.6.3 Characterization of Optimal Strategies 301
12.7 Exercises 309
Appendix A Set Theory and Logic: An Introduction 315
A.1 Sets, Unions, Intersections 315
A.2 Propositions: Contrapositives and Converses 316
A.3 Quantifiers and Negation 318
A.4 Necessary and Sufficient Conditions 320
Appendix B The Real Line 323
B.1 Construction of the Real Line 323
B.2 Properties of the Real Line 326
Appendix C Structures on Vector Spaces 330
C.1 Vector Spaces 330
C.2 Inner Product Spaces 332
C.3 Normed Spaces 333
C.4 Metric Spaces 336
C.4.1 Definitions 336
C.4.2 Sets and Sequences in Metric Spaces 337
C.4.3 Continuous Functions on Metric Spaces 339
C.4.4 Separable Metric Spaces 340
C.4.5 Subspaces 341
C.5 Topological Spaces 342
C.5.1 Definitions 342
C.5.2 Sets and Sequences in Topological Spaces 343
C.5.3 Continuous Functions on Topological Spaces 343
C.5.4 Bases 343
C.6 Exercises 345
Bibliography 349
Index 351