An Introduction to Optimization Book

Preface     xiii
Mathematical Review
Methods of Proof and Some Notation     3
Methods of Proof     3
Notation     5
Exercises     6
Vector Spaces and Matrices     7
Vector and Matrix     7
Rank of a Matrix     13
Linear Equations     17
Inner Products and Norms     19
Exercises     22
Transformations     23
Linear Transformations     23
Eigenvalues and Eigenvectors     24
Orthogonal Projections     27
Quadratic Forms     29
Matrix Norms     33
Exercises     38
Concepts from Geometry     43
Line Segments     43
Hyperplanes and Linear Varieties     44
Convex Sets     46
Neighborhoods     48
Polytopes and Polyhedra     50
Exercises     51
Elements of Calculus     53
Sequences and Limits     53
Differentiability     60
The Derivative Matrix     61
Differentiation Rules     65
Level Sets and Gradients     66
Taylor Series     70
Exercises     75
Unconstrained Optimization
Basics of Set-Constrained and Unconstrained Optimization     79
Introduction     79
Conditions for Local Minimizers     81
Exercises     91
One-Dimensional Search Methods     101
Golden Section Search     101
Fibonacci Search     105
Newton's Method     113
Secant Method     117
Remarks on Line Search Methods     119
Exercises     121
Gradient Methods     125
Introduction     125
The Method of Steepest Descent     127
Analysis of Gradient Methods     135
Exercises     147
Newton's Method     155
Introduction     155
Analysis of Newton's Method     158
Levenberg-Marquardt Modification     162
Newton's Method for Nonlinear Least Squares     162
Exercises     165
Conjugate Direction Methods     169
Introduction     169
The Conjugate Direction Algorithm     171
The Conjugate Gradient Algorithm     176
The Conjugate Gradient Algorithm for Nonquadratic
Problems      180
Exercises     182
Quasi-Newton Methods     187
Introduction     187
Approximating the Inverse Hessian     188
The Rank One Correction Formula     191
The DFP Algorithm     196
The BFGS Algorithm     201
Exercises     205
Solving Linear Equations     211
Least-Squares Analysis     211
The Recursive Least-Squares Algorithm     221
Solution to a Linear Equation with Minimum Norm     225
Kaczmarz's Algorithm     226
Solving Linear Equations in General     230
Exercises     238
Unconstrained Optimization and Neural Networks     247
Introduction     247
Single-Neuron Training     250
The Backpropagation Algorithm     252
Exercises     264
Global Search Algorithms     267
Introduction     267
The Nelder-Mead Simplex Algorithm     268
Simulated Annealing     272
Particle Swarm Optimization     276
Genetic Algorithms     279
Exercises     292
Linear Programming
Introduction to Linear Programming     299
Brief History of Linear Programming     299
Simple Examples of Linear Programs     301
Two-Dimensional Linear Programs     308
Convex Polyhedra and Linear Programming     310
Standard Form Linear Programs     312
Basic Solutions     318
Properties of Basic Solutions     321
Geometric View of Linear Programs     324
Exercises     329
Simplex Method     333
Solving Linear Equations Using Row Operations     333
The Canonical Augmented Matrix     340
Updating the Augmented Matrix     342
The Simplex Algorithm     343
Matrix Form of the Simplex Method     350
Two-Phase Simplex Method     354
Revised Simplex Method     358
Exercises     363
Duality     371
Dual Linear Programs     371
Properties of Dual Problems     379
Exercises     386
Nonsimplex Methods     395
Introduction     395
Khachiyan's Method     397
Affine Scaling Method     400
Karmarkar's Method     405
Exercises     418
Nonlinear Constrained Optimization
Problems with Equality Constraints     423
Introduction     423
Problem Formulation     425
Tangent and Normal Spaces     426
Lagrange Condition     433
Second-Order Conditions     442
Minimizing Quadratics Subject to Linear Constraints     446
Exercises     450
Problems with Inequality Constraints     457
Karush-Kuhn-Tucker Condition     457
Second-Order Conditions     466
Exercises     471
Convex Optimization Problems     479
Introduction     479
Convex Functions     482
Convex Optimization Problems     491
Semidefinite Programming     497
Exercises     506
Algorithms for Constrained Optimization     513
Introduction     513
Projections     513
Projected Gradient Methods with Linear Constraints     517
Lagrangian Algorithms     521
Penalty Methods     528
Exercises     535
Multiobjective Optimization     541
Introduction     541
Pareto Solutions     542
Computing the Pareto Front     545
From Multiobjective to Single-Objective Optimization     549
Uncertain Linear Programming Problems     552
Exercises     560
References     563
Index     571