An Introduction to Optimization

Cover......Page 1
Series......Page 2
Title page......Page 3
Copyright page......Page 4
Dedication......Page 5
Contents......Page 7
Preface......Page 13
Part I Mathematical Review......Page 17
1.1 Methods of Proof......Page 19
1.2 Notation......Page 21
Exercises......Page 22
2.1 Real Vector Spaces......Page 23
2.2 Rank of a Matrix......Page 28
2.3 Linear Equations......Page 32
2.4 Inner Products and Norms......Page 34
Exercises......Page 37
3.1 Linear Transformations......Page 39
3.2 Eigenvalues and Eigenvectors......Page 40
3.3 Orthogonal Projections......Page 43
3.4 Quadratic Forms......Page 44
3.5 Matrix Norms......Page 49
Exercises......Page 53
4.2 Hyperplanes and Linear Varieties......Page 57
4.3 Convex Sets......Page 60
4.4 Neighborhoods......Page 62
4.5 Polytopes and Polyhedra......Page 63
Exercises......Page 65
5.1 Sequences and Limits......Page 67
5.2 Differentiability......Page 73
5.3 The Derivative Matrix......Page 75
5.4 Differentiation Rules......Page 77
5.5 Level Sets and Gradients......Page 78
5.6 Taylor Series......Page 82
Exercises......Page 86
Part II Unconstrained Optimization......Page 89
6.1 Introduction......Page 91
6.2 Conditions for Local Minimizers......Page 93
Exercises......Page 101
7.1 Golden Section Search......Page 109
7.2 Fibonacci Search......Page 113
7.3 Newton\'s Method......Page 121
7.4 Secant Method......Page 124
7.5 Remarks on Line Search Methods......Page 126
Exercises......Page 127
8.1 Introduction......Page 131
8.2 The Method of Steepest Descent......Page 133
8.3.1 Convergence......Page 140
8.3.2 Convergence Rate......Page 147
Exercises......Page 152
9.1 Introduction......Page 157
9.2 Analysis of Newton\'s Method......Page 160
9.3 Levenberg-Marquardt Modification......Page 163
9.4 Newton\'s Method for Nonlinear Least-Squares......Page 164
Exercises......Page 167
10.1 Introduction......Page 169
10.2 The Conjugate Direction Algorithm......Page 171
10.3 The Conjugate Gradient Algorithm......Page 176
10.4 The Conjugate Gradient Algorithm for Non-Quadratic Problems......Page 179
Exercises......Page 182
11.1 Introduction......Page 185
11.2 Approximating the Inverse Hessian......Page 186
11.3 The Rank One Correction Formula......Page 189
11.4 The DFP Algorithm......Page 194
11.5 The BFGS Algorithm......Page 198
Exercises......Page 202
12.1 Least-Squares Analysis......Page 205
12.2 Recursive Least-Squares Algorithm......Page 214
12.3 Solution to $Ax = b$ Minimizing ||x||......Page 217
12.4 Kaczmarz\'s Algorithm......Page 219
12.5 Solving $Ax = b$ in General......Page 222
Exercises......Page 230
13.1 Introduction......Page 237
13.2 Single-Neuron Training......Page 239
13.3 Backpropagation Algorithm......Page 242
Exercises......Page 252
14.1 Basic Description......Page 255
14.1.2 Selection and Evolution......Page 256
14.2 Analysis of Genetic Algorithms......Page 261
14.3 Real-Number Genetic Algorithms......Page 266
Exercises......Page 268
Part III Linear Programming......Page 271
15.1 A Brief History of Linear Programming......Page 273
15.2 Simple Examples of Linear Programs......Page 275
15.3 Two-Dimensional Linear Programs......Page 281
15.4 Convex Polyhedra and Linear Programming......Page 282
15.5 Standard Form Linear Programs......Page 285
15.6 Basic Solutions......Page 290
15.7 Properties of Basic Solutions......Page 294
15.8 A Geometric View of Linear Programs......Page 297
Exercises......Page 300
16.1 Solving Linear Equations Using Row Operations......Page 305
16.2 The Canonical Augmented Matrix......Page 312
16.3 Updating the Augmented Matrix......Page 313
16.4 The Simplex Algorithm......Page 315
16.5 Matrix Form of the Simplex Method......Page 321
16.6 The Two-Phase Simplex Method......Page 325
16.7 The Revised Simplex Method......Page 328
Exercises......Page 333
17.1 Dual Linear Programs......Page 339
17.2 Properties of Dual Problems......Page 346
Exercises......Page 351
18.1 Introduction......Page 357
18.2 Khachiyan\'s Method......Page 358
18.3.1 Basic Algorithm......Page 361
18.3.2 Two-Phase Method......Page 365
18.4.1 Basic Ideas......Page 366
18.4.2 Karmarkar\'s Canonical Form......Page 367
18.4.3 Karmarkar\'s Restricted Problem......Page 369
18.4.4 From General Form to Karmarkar\'s Canonical Form......Page 370
18.4.5 The Algorithm......Page 374
Exercises......Page 378
Part IV Nonlinear Constrained Optimization......Page 381
19.1 Introduction......Page 383
19.2 Problem Formulation......Page 384
19.3 Tangent and Normal Spaces......Page 386
19.4 Lagrange Condition......Page 392
19.5 Second-Order Conditions......Page 401
19.6 Minimizing Quadratics Subject to Linear Constraints......Page 405
Exercises......Page 409
20.1 Karush-Kuhn-Tucker Condition......Page 415
20.2 Second-Order Conditions......Page 424
Exercises......Page 428
21.1 Introduction......Page 435
21.2 Convex Functions......Page 437
21.3 Convex Optimization Problems......Page 445
Exercises......Page 451
22.2 Projections......Page 457
22.3 Projected Gradient Methods......Page 459
22.4 Penalty Methods......Page 463
Exercises......Page 469
References......Page 473
Index......Page 480