This book introduces the applications, theory, and algorithms of linear and nonlinear optimization, with an emphasis on the practical aspects of the material. Its unique modular structure provides flexibility to accommodate the varying needs of instructors, students, and practitioners with different levels of sophistication in these topics. The succinct style of this second edition is punctuated with numerous real-life examples and exercises, and the authors include accessible explanations of topics that are not often mentioned in textbooks, such as duality in nonlinear optimization, primal-dual methods for nonlinear optimization, filter methods, and applications such as support-vector machines. Part I of Linear and Nonlinear Optimization, Second Edition provides fundamentals that can be taught in whole or in part at the beginning of a course on either topic and then referred to as needed. Part II on linear programming and Part III on unconstrained optimization can be used together or separately, and Part IV on nonlinear optimization can be taught without having studied the material in Part II. In the preface the authors suggest course outlines that can be adjusted to the requirements of a particular course on both linear and nonlinear optimization, or to separate courses on these topics. Three appendices provide information on linear algebra, other fundamentals, and software packages for optimization problems. A supplemental website offers auxiliary data sets that are necessary for some of the exercises. Audience: This book is primarily intended for use in linear and nonlinear optimization courses for advanced undergraduate and graduate students. It is also appropriate as a tutorial for researchers and practitioners who need to understand the modern algorithms of linear and nonlinear optimization to apply them to problems in science and engineering. Contents: Preface; Part I: Basics; Chapter 1: Optimization Models; Chapter 2: Fundamentals of Optimization; Chapter 3: Representation of Linear Constraints; Part II: Linear Programming; Chapter 4: Geometry of Linear Programming; Chapter 5: The Simplex Method; Chapter 6: Duality and Sensitivity; Chapter 7: Enhancements of the Simplex Method; Chapter 8: Network Problems; Chapter 9: Computational Complexity of Linear Programming; Chapter 10: Interior-Point Methods of Linear Programming; Part III: Unconstrained Optimization; Chapter 11: Basics of Unconstrained Optimization; Chapter 12: Methods for Unconstrained Optimization; Chapter 13: Low-Storage Methods for Unconstrained Problems; Part IV: Nonlinear Optimization; Chapter 14: Optimality Conditions for Constrained Problems; Chapter 15: Feasible-Point Methods; Chapter 16: Penalty and Barrier Methods; Part V: Appendices; Appendix A: Topics from Linear Algebra; Appendix B: Other Fundamentals; Appendix C: Software; Bibliography; Index
Author(s): Igor Griva, Stephen G. Nash, Ariela Sofer
Edition: 2
Publisher: Society for Industrial Mathematics
Year: 2008
Language: English
Pages: 765
Contents......Page 6
Preface......Page 14
Part I: Basics......Page 24
1.1 Introduction......Page 26
1.2 Optimization: An Informal Introduction......Page 27
1.3 Linear Equations......Page 30
1.4 Linear Optimization......Page 33
1.5 Least-Squares Data Fitting......Page 35
1.6 Nonlinear Optimization......Page 37
1.7 Optimization Applications......Page 41
1.8 Notes......Page 63
2.2 Feasibility and Optimality......Page 66
2.3 Convexity......Page 71
2.4 The General Optimization Algorithm......Page 77
2.5 Rates of Convergence......Page 81
2.6 Taylor Series......Page 85
2.7 Newton’s Method for Nonlinear Equations......Page 90
2.8 Notes......Page 99
3.1 Basic Concepts......Page 100
3.2 Null and Range Spaces......Page 105
3.3 Generating Null-Space Matrices......Page 109
3.4 Notes......Page 116
Part II: Linear Programming......Page 118
4.1 Introduction......Page 120
4.2 Standard Form......Page 123
4.3 Basic Solutions and Extreme Points......Page 129
4.4 Representation of Solutions; Optimality......Page 140
4.5 Notes......Page 147
5.1 Introduction......Page 148
5.2 The Simplex Method......Page 149
5.3 The Simplex Method (Details)......Page 167
5.4 Getting Started—Arti.cial Variables......Page 172
5.5 Degeneracy and Termination......Page 185
5.6 Notes......Page 194
6.1 The Dual Problem......Page 196
6.2 Duality Theory......Page 202
6.3 The Dual Simplex Method......Page 212
6.4 Sensitivity......Page 218
6.5 Parametric Linear Programming......Page 227
6.6 Notes......Page 234
7.1 Introduction......Page 236
7.2 Problems with Upper Bounds......Page 237
7.3 Column Generation......Page 245
7.4 The Decomposition Principle......Page 250
7.5 Representation of the Basis......Page 263
7.6 Numerical Stability and Computational Ef.ciency......Page 282
7.7 Notes......Page 293
8.2 Basic Concepts and Examples......Page 294
8.3 Representation of the Basis......Page 303
8.4 The Network Simplex Method......Page 310
8.5 Resolving Degeneracy......Page 318
8.6 Notes......Page 322
9.1 Introduction......Page 324
9.2 Computational Complexity......Page 325
9.3 Worst-Case Behavior of the Simplex Method......Page 328
9.4 The Ellipsoid Method......Page 331
9.5 The Average-Case Behavior of the Simplex Method......Page 337
9.6 Notes......Page 339
10.1 Introduction......Page 342
10.2 The Primal-Dual Interior-Point Method......Page 344
10.3 Feasibility and Self-Dual Formulations......Page 354
10.4 Some Concepts from Nonlinear Optimization......Page 357
10.5 Af.ne-Scaling Methods......Page 359
10.6 Path-Following Methods......Page 367
10.7 Notes......Page 376
Part III: Unconstrained Optimization......Page 378
11.2 Optimality Conditions......Page 380
11.3 Newton’s Method for Minimization......Page 387
11.4 Guaranteeing Descent......Page 394
11.5 Guaranteeing Convergence: Line Search Methods......Page 398
11.6 Guaranteeing Convergence: Trust-Region Methods......Page 414
11.7 Notes......Page 422
12.1 Introduction......Page 424
12.2 Steepest-Descent Method......Page 425
12.3 Quasi-Newton Methods......Page 434
12.4 Automating Derivative Calculations......Page 445
12.5 Methods That Do Not Require Derivatives......Page 454
12.6 Termination Rules......Page 464
12.7 Historical Background......Page 469
12.8 Notes......Page 471
13.1 Introduction......Page 474
13.2 The Conjugate-Gradient Method for Solving Linear Equations......Page 475
Exercises......Page 482
13.3 Truncated-Newton Methods......Page 483
Exercises......Page 488
13.4 Nonlinear Conjugate-Gradient Methods......Page 489
Exercises......Page 492
13.5 Limited-Memory Quasi-Newton Methods......Page 493
Exercises......Page 496
13.6 Preconditioning......Page 497
Exercises......Page 500
13.7 Notes......Page 501
Part IV: Nonlinear Optimization......Page 504
14.1 Introduction......Page 506
14.2 Optimality Conditions for Linear Equality Constraints......Page 507
14.3 The Lagrange Multipliers and the Lagrangian Function......Page 514
14.4 Optimality Conditions for Linear Inequality Constraints......Page 517
14.5 Optimality Conditions for Nonlinear Constraints......Page 525
14.6 Preview of Methods......Page 533
14.7 Derivation of Optimality Conditions for Nonlinear Constraints......Page 538
14.8 Duality......Page 545
14.9 Historical Background......Page 566
14.10 Notes......Page 569
15.2 Linear Equality Constraints......Page 572
15.3 Computing the Lagrange Multipliers......Page 579
15.4 Linear Inequality Constraints......Page 586
15.5 Sequential Quadratic Programming......Page 596
15.6 Reduced-Gradient Methods......Page 604
15.7 Filter Methods......Page 611
15.8 Notes......Page 621
16.1 Introduction......Page 624
16.2 Classical Penalty and Barrier Methods......Page 625
16.3 Ill-Conditioning......Page 641
16.4 Stabilized Penalty and Barrier Methods......Page 642
16.5 Exact Penalty Methods......Page 646
16.6 Multiplier-Based Methods......Page 649
16.7 Nonlinear Primal-Dual Methods......Page 663
16.8 Semide.nite Programming......Page 672
16.9 Notes......Page 679
Part V: Appendices......Page 682
A.2 Eigenvalues......Page 684
A.3 Vector and Matrix Norms......Page 685
A.4 Systems of Linear Equations......Page 687
A.5 Solving Systems of Linear Equations by Elimination......Page 689
A.6 Gaussian Elimination as a Matrix Factorization......Page 692
A.7 Other Matrix Factorizations......Page 699
A.8 Sensitivity (Conditioning)......Page 706
A.9 The Sherman–Morrison Formula......Page 709
A.10 Notes......Page 711
B.2 Computer Arithmetic......Page 714
B.3 Big-O Notation,......Page 716
B.4 The Gradient, Hessian, and Jacobian......Page 717
B.5 Gradient and Hessian of a Quadratic Function......Page 719
B.6 Derivatives of a Product......Page 720
B.7 The Chain Rule......Page 721
B.8 Continuous Functions; Closed and Bounded Sets......Page 722
B.9 The Implicit Function Theorem......Page 723
C.1 Software......Page 726
Bibliography......Page 730
Index......Page 750
