An Introduction to Optimization

by Chong, Edwin K. P.; Zak, Stanislaw H.

• ISBN13: 9780471758006
• ISBN10: 0471758000
• Edition: 3rd
• Format: Hardcover
• Copyright: 2008-02-25
• Publisher: Wiley-Interscience

Summary

Fully updated to reflect modern developments in the field, An Introduction to Optimization, Third Edition fills the need for an accessible, yet rigorous, introduction to optimization theory and methods. Features of the Third Edition include: new discussions of semi-definite programming and Lagrangian algorithms; a new chapter on global search method; a new chapter on multiple-objective optimization; new and modified examples and exercises in each chapter; and an updated bibliography containing new references.

Author Biography

Edwin K.P. Chong, PHD, is Professor of Electrical and Computer Engineering and Professor of Mathematics at Colorado State University. He currently serves as Editor of Computer Networks and the Journal of Control Science and Engineering. Dr. Chong was the recipient of the 1998 ASEE Frederick Emmons Terman Award.

Stanislaw H.Zak, PHD, is Professor of Electrical and Computer Engineering at Purdue University. He is the former associate editor of Dynamics and Control and the IEEE Transactions on Neural Networks, and his research interests include control, optimization, nonlinear systems, neural networks, and fuzzy logic control.

Table of Contents

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