An Introduction to Optimization

[BOOK DESCRIPTION]

Praise for the Third Edition "...guides and leads the reader through the learning path ...[e]xamples are stated very clearly and the results are presented with attention to detail." -MAA Reviews Fully updated to reflect new developments in the field, the Fourth Edition of Introduction to Optimization fills the need for accessible treatment of optimization theory and methods with an emphasis on engineering design. Basic definitions and notations are provided in addition to the related fundamental background for linear algebra, geometry, and calculus. This new edition explores the essential topics of unconstrained optimization problems, linear programming problems, and nonlinear constrained optimization. The authors also present an optimization perspective on global search methods and include discussions on genetic algorithms, particle swarm optimization, and the simulated annealing algorithm.Featuring an elementary introduction to artificial neural networks, convex optimization, and multi-objective optimization, the Fourth Edition also offers: * A new chapter on integer programming * Expanded coverage of one-dimensional methods * Updated and expanded sections on linear matrix inequalities * Numerous new exercises at the end of each chapter * MATLAB exercises and drill problems to reinforce the discussed theory and algorithms * Numerous diagrams and figures that complement the written presentation of key concepts * MATLAB M-files for implementation of the discussed theory and algorithms (available via the book's website) Introduction to Optimization, Fourth Edition is an ideal textbook for courses on optimization theory and methods. In addition, the book is a useful reference for professionals in mathematics, operations research, electrical engineering, economics, statistics, and business.

[TABLE OF CONTENTS]
 

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