An Introduction to Optimization

Edwin K. P. Chong, PHD, is Professor of Electrical and Computer Engineering as well as Professor of Mathematics at Colorado State University. He is a Fellow of the IEEE and Senior Editor of IEEE Transactions on Automatic Control. Stanislaw H. Zak, PHD, is Professor in the School of Electrical and Computer Engineering at Purdue University. He is former associate editor of Dynamics and Control and IEEE Transactions on Neural Networks

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 Newtons 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 Newtons Method 161 9.1 Introduction 161 9.2 Analysis of Newtons Method 164 9.3 Levenberg-Marquardt Modification 168 9.4 Newtons 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 Kaczmarzs 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 Khachiyans Method 405 18.3 Affine Scaling Method 408 18.4 Karmarkars 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 Exercis