Paperback(5th ed. 2021)
-
PICK UP IN STORECheck Availability at Nearby Stores
Available within 2 business hours
Related collections and offers
Overview
The 5th edition of this classic textbook covers the central concepts of practical optimization techniques, with an emphasis on methods that are both state-of-the-art and popular. One major insight is the connection between the purely analytical character of an optimization problem and the behavior of algorithms used to solve that problem. End-of-chapter exercises are provided for all chapters.
The material is organized into three separate parts. Part I offers a self-contained introduction to linear programming. The presentation in this part is fairly conventional, covering the main elements of the underlying theory of linear programming, many of the most effective numerical algorithms, and many of its important special applications. Part II, which is independent of Part I, covers the theory of unconstrained optimization, including both derivations of the appropriate optimality conditions and an introduction to basic algorithms. This part of the book explores the general properties of algorithms and defines various notions of convergence. In turn, Part III extends the concepts developed in the second part to constrained optimization problems. Except for a few isolated sections, this part is also independent of Part I. As such, Parts II and III can easily be used without reading Part I and, in fact, the book has been used in this way at many universities.
New to this edition are popular topics in data science and machine learning, such as the Markov Decision Process, Farkas' lemma, convergence speed analysis, duality theories and applications, various first-order methods, stochastic gradient method, mirror-descent method, Frank-Wolf method, ALM/ADMM method, interior trust-region method for non-convex optimization, distributionally robust optimization, online linear programming, semidefinite programming for sensor-network localization, and infeasibility detection for nonlinear optimization.
Product Details
| ISBN-13: | 9783030854522 |
|---|---|
| Publisher: | Springer International Publishing |
| Publication date: | 10/31/2021 |
| Series: | International Series in Operations Research & Management Science , #228 |
| Edition description: | 5th ed. 2021 |
| Pages: | 609 |
| Product dimensions: | 6.10(w) x 9.25(h) x (d) |
About the Author
He is a Member of the National Academy of Engineering (2008) and has received e.g. the Bode Lecture Prize of the Control Systems Society (1990), the Oldenburger Medal of the American Society of Mechanical Engineers (1995), and the Expository Writing Award of the Institute of Operations Research and Management Science (1999). He is a Fellow of the Institute of Electrical and Electronic Engineers (since 1975).
Yinyu Ye is currently the Kwoh-Ting Li Professor in the School of Engineering at the Department of Management Science and Engineering and Institute of Computational and Mathematical Engineering. He received his B.S. degree in System Engineering from Huazhong University of Science and Technology, China, and his M.S. and Ph.D. degrees in Engineering-Economic Systems and Operations Research from Stanford University. He is an INFORMS (The Institute for Operations Research and The Management Science). Fellow since 2012, and has received several academic awards including: the 2009 John von Neumann Theory Prize for fundamental sustained contributions to theory in Operations Research and the Management Sciences, the 2015 SPS Signal Processing Magazine Best Paper Award, the winner of the 2014 SIAM Optimization Prize awarded (every three years), the inaugural 2012 ISMP Tseng Lectureship Prize for outstanding contribution to continuous optimization (every three years), the inaugural 2006 Farkas Prize on Optimization, the 2009 IBM Faculty Award.
Table of Contents
Introduction 1
Optimization 1
Types of Problems 2
Size of Problems 5
Iterative Algorithms and Convergence 6
Linear Programming
Basic Properties of Linear Programs 11
Introduction 11
Examples of Linear Programming Problems 14
Basic Solutions 19
The Fundamental Theorem of Linear Programming 20
Relations to Convexity 22
Exercises 28
The Simplex Method 33
Pivots 33
Adjacent Extreme Points 38
Determining a Minimum Feasible Solution 42
Computational Procedure-Simplex Method 46
Artificial Variables 50
Matrix Form of the Simplex Method 54
The Revised Simplex Method 56
The Simplex Method and LU Decomposition 59
Decomposition 62
Summary 70
Exercises 70
Duality 79
Dual Linear Programs 79
The Duality Theorem 82
Relations to the Simplex Procedure 84
Sensitivity and Complementary Slackness 88
The Dual Simplex Method 90
The Primal-Dual Algorithm 93
Reduction of Linear Inequalities 98
Exercises 103
Interior-Point Methods 111
Elements of Complexity Theory 112
The Simplex Method is not Polynomial-Time 114
The Ellipsoid Method 115
The Analytic Center 118
The Central Path 121
Solution Strategies 126
Termination and Initialization 134
Summary 139
Exercises 140
Transportation and Network Flow Problems 145
The Transportation Problem 145
Finding a Basic Feasible Solution 148
Basis Triangularity 150
Simplex Method for Transportation Problems 153
The Assignment Problem 159
Basic Network Concepts 160
Minimum Cost Flow 162
Maximal Flow 166
Summary 174
Exercises 175
Unconstrained Problems
Basic Properties of Solutions and Algorithms 183
First-Order Necessary Conditions 184
Examples of Unconstrained Problems 186
Second-Order Conditions 190
Convex and Concave Functions 192
Minimization and Maximization of Convex Functions 197
Zero-Order Conditions 198
Global Convergence of Descent Algorithms 201
Speed of Convergence 208
Summary 212
Exercises 213
Basic Descent Methods 215
Fibonacci and Golden Section Search 216
Line Search by Curve Fitting 219
Global Convergence of Curve Fitting 226
Closedness of Line Search Algorithms 228
Inaccurate Line Search 230
The Method of Steepest Descent 233
Applications of the Theory 242
Newton's Method 246
Coordinate Descent Methods 253
Spacer Steps 255
Summary 256
Exercises 257
Conjugate Direction Methods 263
Conjugate Directions 263
Descent Properties of the Conjugate Direction Method 266
The Conjugate Gradient Method 268
The C-G Method as an Optimal Process 271
The Partial Conjugate Gradient Method 273
Extension to Nonquadratic Problems 277
Parallel Tangents 279
Exercises 282
Quasi-Newton Methods 285
Modified Newton Method 285
Construction of the Inverse 288
Davidon-Fletcher-Powell Method 290
The Broyden Family 293
Convergence Properties 296
Scaling 299
Memoryless Quasi-Newton Methods 304
Combination of Steepest Descent and Newton's Method 306
Summary 312
Exercises 313
Constrained Minimization
Constrained Minimization Conditions 321
Constraints 321
Tangent Plane 323
First-Order Necessary Conditions (Equality Constraints) 326
Examples 327
Second-Order Conditions 333
Eigenvalues in Tangent Subspace 335
Sensitivity 339
Inequality Constraints 341
Zero-Order Conditions and Lagrange Multipliers 346
Summary 353
Exercises 354
Primal Methods 359
Advantage of Primal Methods 359
Feasible Direction Methods 360
Active Set Methods 363
The Gradient Projection Method 367
Convergence Rate of the Gradient Projection Method 374
The Reduced Gradient Method 382
Convergence Rate of the Reduced Gradient Method 387
Variations 394
Summary 396
Exercises 396
Penalty and Barrier Methods 401
Penalty Methods 402
Barrier Methods 405
Properties of Penalty and Barrier Functions 407
Newton's Method and Penalty Functions 416
Conjugate Gradients and Penalty Methods 418
Normalization of Penalty Functions 420
Penalty Functions and Gradient Projection 421
Exact Penalty Functions 425
Summary 429
Exercises 430
Dual and Cutting Plane Methods 435
Global Duality 435
Local Duality 441
Dual Canonical Convergence Rate 446
Separable Problems 447
Augmented Lagrangians 451
The Dual Viewpoint 456
Cutting Plane Methods 460
Kelley's Convex Cutting Plane Algorithm 463
Modifications 465
Exercises 466
Primal-Dual Methods 469
The Standard Problem 469
Strategies 471
A Simple Merit Function 472
Basic Primal-Dual Methods 474
Modified Newton Methods 479
Descent Properties 481
Rate of Convergence 485
Interior Point Methods 487
Semidefinite Programming 491
Summary 498
Exercises 499
Mathematical Review 507
Sets 507
Matrix Notation 508
Spaces 509
Eigenvalues and Quadratic Forms 510
Topological Concepts 511
Functions 512
Convex Sets 515
Basic Definitions 515
Hyperplanes and Polytopes 517
Separating and Supporting Hyperplanes 519
Extreme Points 521
Gaussian Elimination 523
Bibliography 527
Index 541
What People are Saying About This
I have the 1977 edition from my father's MIT days. I am a Mathematician and I can verify that the book written in 1977 is of the same style that good books have today. A book is not made obsolete because some new "elegant" terms arise.
I have profitably used the book to apply constrained minimization procedures in the field of computational contact mechanics. I think it is not a secret that quite often books on mathematics are written from mathematicians for mathematicians. Hence it is quite hard for engineers to read and to extract valuable information from them. With this respect this book is a shining star. It presents the topics in a very precise but clear and understandable way. (Turin, Italy)