An Introduction to Optimization

Preface xiii PART I MATHEMATICAL REVIEW 1 Methods of Proof and Some Notation 3 1.1 Methods of Proof 3 1.2 Notation 5 Exercises 6 2 Vector Spaces and Matrices 7 2.1 Vector and Matrix 7 2.2 Rank of a Matrix 13 2.3 Linear Equations 17 2.4 Inner Products and Norms 19 Exercises 22 3 Transformations 25 3.1 Linear Transformations 25 3.2 Eigenvalues and Eigenvectors 26 3.3 Orthogonal Projections 29 3.4 Quadratic Forms 31 3.5 Matrix Norms 35 Exercises 40 4 Concepts from Geometry 45 4.1 Line Segments 45 4.2 Hyperplanes and Linear Varieties 46 4.3 Convex Sets 48 4.4 Neighborhoods 50 4.5 Polytopes and Polyhedra 52 Exercises 53 5 Elements of Calculus 55 5.1 Sequences and Limits 55 5.2 Differentiability 62 5.3 The Derivative Matrix 63 5.4 Differentiation Rules 67 5.5 Level Sets and Gradients 68 5.6 Taylor Series 72 Exercises 77 PART II UNCONSTRAINED OPTIMIZATION 6 Basics of Set-Constrained and Unconstrained Optimization 81 6.1 Introduction 81 6.2 Conditions for Local Minimizers 83 Exercises 93 7 One-Dimensional Search Methods 103 7.1 Introduction 103 7.2 Golden Section Search 104 7.3 Fibonacci Method 108 7.4 Bisection Method 116 7.5 Newton's Method 116 7.6 Secant Method 120 7.7 Bracketing 123 7.8 Line Search in Multidimensional Optimization 124 Exercises 126 8 Gradient Methods 131 8.1 Introduction 131 8.2 The Method of Steepest Descent 133 8.3 Analysis of Gradient Methods 141 Exercises 153 9 Newton's Method 161 9.1 Introduction 161 9.2 Analysis of Newton's Method 164 9.3 Levenberg-Marquardt Modification 168 9.4 Newton's Method for Nonlinear Least Squares 168 Exercises 171 10 Conjugate Direction Methods 175 10.1 Introduction 175 10.2 The Conjugate Direction Algorithm 177 10.3 The Conjugate Gradient Algorithm 182 10.4 The Conjugate Gradient Algorithm for Nonquadratic Problems 186 Exercises 189 11 Quasi-Newton Methods 193 11.1 Introduction 193 11.2 Approximating the Inverse Hessian 194 11.3 The Rank One Correction Formula 197 11.4 The DFP Algorithm 202 11.5 The BFGS Algorithm 207 Exercises 211 12 Solving Linear Equations 217 12.1 Least-Squares Analysis 217 12.2 The Recursive Least-Squares Algorithm 227 12.3 Solution to a Linear Equation with Minimum Norm 231 12.4 Kaczmarz's Algorithm 232 12.5 Solving Linear Equations in General 236 Exercises 244 13 Unconstrained Optimization and Neural Networks 253 13.1 Introduction 253 13.2 Single-Neuron Training 256 13.3 The Backpropagation Algorithm 258 Exercises 270 14 Global Search Algorithms 273 14.1 Introduction 273 14.2 The Nelder-Mead Simplex Algorithm 274 14.3 Simulated Annealing 278 14.4 Particle Swarm Optimization 282 14.5 Genetic Algorithms 285 Exercises 298 PART III LINEAR PROGRAMMING 15 Introduction to Linear Programming 305 15.1 Brief History of Linear Programming 305 15.2 Simple Examples of Linear Programs 307 15.3 Two-Dimensional Linear Programs 314 15.4 Convex Polyhedra and Linear Programming 316 15.5 Standard Form Linear Programs 318 15.6 Basic Solutions 324 15.7 Properties of Basic Solutions 327 15.8 Geometric View of Linear Programs 330 Exercises 335 16 Simplex Method 339 16.1 Solving Linear Equations Using Row Operations 339 16.2 The Canonical Augmented Matrix 346 16.3 Updating the Augmented Matrix 349 16.4 The Simplex Algorithm 350 16.5 Matrix Form of the Simplex Method 357 16.6 Two-Phase Simplex Method 361 16.7 Revised Simplex Method 364 Exercises 369 17 Duality 379 17.1 Dual Linear Programs 379 17.2 Properties of Dual Problems 387 Exercises 394 18 Nonsimplex Methods 403 18.1 Introduction 403 18.2 Khachiyan's Method 405 18.3 Affine Scaling Method 408 18.4 Karmarkar's Method 413 Exercises 426 19 Integer Linear Programming 429 19.1 Introduction 429 19.2 Unimodular Matrices 430 19.3 The Gomory Cutting-Plane Method 437 Exercises 447 PART IV NONLINEAR CONSTRAINED OPTIMIZATION 20 Problems with Equality Constraints 453 20.1 Introduction 453 20.2 Problem Formulation 455 20.3 Tangent and Normal Spaces 456 20.4 Lagrange Condition 463 20.5 Second-Order Conditions 472 20.6 Minimizing Quadratics Subject to Linear Constraints 476 Exercises 481 21 Problems with Inequality Constraints 487 21.1 Karush-Kuhn-Tucker Condition 487 21.2 Second-Order Conditions 496 Exercises 501 22 Convex Optimization Problems 509 22.1 Introduction 509 22.2 Convex Functions 512 22.3 Convex Optimization Problems 521 22.4 Semidefinite Programming 527 Exercises 540 23 Algorithms for Constrained Optimization 549 23.1 Introduction 549 23.2 Projections 549 23.3 Projected Gradient Methods with Linear Constraints 553 23.4 Lagrangian Algorithms 557 23.5 Penalty Methods 564 Exercises 571 24 Multiobjective Optimization 577 24.1 Introduction 577 24.2 Pareto Solutions 578 24.3 Computing the Pareto Front 581 24.4 From Multiobjective to Single-Objective Optimization 585 24.5 Uncertain Linear Programming Problems 588 Exercises 596 References 599 Index 609