1 Dierential Calculus : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1
1.1 Taylor's Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Dierentiation of Functions of Several Variables . . . . . . . . . . . 5
1.3 Dierentiability of Vector-Valued Functions . . . . . . . . . . . . . . . 8
1.4 The Chain Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Taylor's Formula for Functions of Several Variables . . . . . . . . 13
1.6 The Converse of Taylor's Theorem . . . . . . . . . . . . . . . . . . . . . . . 16
1.7 Danskin's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2 Unconstrained Optimization : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 31
2.1 Basic Results on the Existence of Optimizers . . . . . . . . . . . . . . 32
2.2 First-Order Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . 35
2.3 Second-Order Optimality Conditions . . . . . . . . . . . . . . . . . . . . . 37
2.4 Quadratic Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.5 The Inverse Function, Implicit Function, and Lyusternik
Theorems in Finite Dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.6 Morse's Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.7 Semicontinuous Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3 Variational Principles : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 61
3.1 Ekeland's -Variational Principle . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2 Borwein{Preiss Variational Principle . . . . . . . . . . . . . . . . . . . . . 68
3.3 Consistency of Linear Equalities and Inequalities . . . . . . . . . . 71
3.4 Variational Proofs of Some Basic Theorems of Nonlinear
Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4 Convex Analysis : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 85
4.1 Ane Geometry. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.2 Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3 Convex Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.4 Dierentiable Convex Functions . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.5 Optimization on Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.6 Variational Principles on a Closed Convex Set . . . . . . . . . . . . . 106
4.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5 Structure of Convex Sets and Functions : : : : : : : : : : : : : : : : : : : 117
5.1 Algebraic Interior and Algebraic Closure of Convex Sets . . . . 117
5.2 Minkowski Gauge Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.3 Calculus of Relative Algebraic Interior and Algebraic
Closure of Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.4 Topological Interior and Topological Closure of Convex Sets 125
5.5 Facial Structure of Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.6 Homogenization of Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . 134
5.7 Continuity of Convex Functions . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6 Separation of Convex Sets : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 141
6.1 Projection of a Point onto a Finite-Dimensional Closed
Convex Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.2 Separation of Convex Sets in Finite-Dimensional Vector
Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.3 Two Applications of Separation Theorems . . . . . . . . . . . . . . . . 151
6.4 Proper Separation of a Convex Set and a Convex Polyhedron152
6.5 Dubovitskii{Milyutin Theorem in Finite Dimensions . . . . . . . 154
6.6 Separation of Convex Sets in General Vector Spaces . . . . . . . 156
6.7 Separation of Several Convex Sets . . . . . . . . . . . . . . . . . . . . . . . 162
6.8 Hahn{Banach Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
6.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
7 Convex Polyhedra : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 175
7.1 Convex Polyhedral Sets and Cones . . . . . . . . . . . . . . . . . . . . . . 175
7.2 Convex Polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
7.3 Linear Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.4 Ane Version of Farkas's Lemma . . . . . . . . . . . . . . . . . . . . . . . . 185
7.5 Tucker's Complementarity Theorem . . . . . . . . . . . . . . . . . . . . . 188
7.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
8 Linear Programming: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 195
8.1 Fundamental Theorems of Linear Programming . . . . . . . . . . . 195
8.2 An Intuitive Formulation of the Dual Linear Program . . . . . . 198
8.3 Duality Rules in Linear Programming . . . . . . . . . . . . . . . . . . . . 200
8.4 Geometric Formulation of Linear Programs . . . . . . . . . . . . . . . 201
8.5 Strictly Complementary Optimal Solutions . . . . . . . . . . . . . . . 203
8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
9 Nonlinear Programming : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 209
9.1 First-Order Necessary Conditions (Fritz John Optimality
Conditions) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
9.2 Derivation of Fritz John Conditions Using Penalty Functions 213
9.3 Derivation of Fritz John Conditions Using Ekeland's
-Variational Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
9.4 First-Order Sucient Optimality Conditions . . . . . . . . . . . . . . 216
9.5 Constraint Qualications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
9.6 Examples of Nonlinear Programs . . . . . . . . . . . . . . . . . . . . . . . . 220
9.7 Second-Order Conditions in Nonlinear Programming . . . . . . . 229
9.8 Examples of Second-Order Conditions . . . . . . . . . . . . . . . . . . . . 236
9.9 Applications of Nonlinear Programming to Inequalities . . . . . 239
9.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
10 Structured Optimization Problems : : : : : : : : : : : : : : : : : : : : : : : : 251
10.1 Spectral Decomposition of a Symmetric Matrix . . . . . . . . . . . . 251
10.2 Singular-Value Decomposition of a Matrix . . . . . . . . . . . . . . . . 255
10.3 Variational Problems in Quasi-Newton Methods . . . . . . . . . . . 259
10.4 Kantorovich's Inequality. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
10.5 Hadamard's Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
10.6 Maximum-Volume Inscribed Ellipsoid in a Symmetric
Convex Polytope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
10.7 Hilbert's Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
10.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
11 Duality Theory and Convex Programming : : : : : : : : : : : : : : : : : 275
11.1 Perspectives on Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
11.2 Saddle Points and Their Properties . . . . . . . . . . . . . . . . . . . . . . 277
11.3 Nonlinear Programming Duality . . . . . . . . . . . . . . . . . . . . . . . . . 280
11.4 Strong Duality in Convex Programming . . . . . . . . . . . . . . . . . . 283
11.5 Examples of Dual Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
11.6 Conic Programming Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
11.7 The Fermat{Torricelli{Steiner Problem . . . . . . . . . . . . . . . . . . . 297
11.8 Homan's Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
11.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
12 Semi-innite Programming : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 313
12.1 Fritz John Conditions for Semi-innite Programming . . . . . . 313
12.2 Jung's Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
12.3 The Minimum-Volume Circumscribed Ellipsoid Problem . . . . 317
12.4 The Maximum-Volume Inscribed Ellipsoid Problem . . . . . . . . 324