Linear and Nonlinear Programming

by David G. Luenberger, Yinyu Ye

Overview

Linear and Nonlinear Programming is considered a classic textbook in Optimization. While it is a classic, it also reflects modern theoretical insights. These insights provide structure to what might otherwise be simply a collection of techniques and results, and this is valuable both as a means for learning existing material and for developing new results. One major insight of this type is the connection between the purely analytical character of an optimization problem, expressed perhaps by properties of the necessary conditions, and the behavior of algorithms used to solve a problem. This was a major theme of the first edition of this book and the second edition expands and further illustrates this relationship.

Linear and Nonlinear Programming covers the central concepts of practical optimization techniques. It is designed for either self-study by professionals or classroom work at the undergraduate or graduate level for technical students. Like the field of optimization itself, which involves many classical disciplines, the book should be useful to system analysts, operations researchers, numerical analysts, management scientists, and other specialists from the host of disciplines from which practical optimization applications are drawn.

Product Details

ISBN-13:	9780387745022
Publisher:	Springer US
Publication date:	07/07/2008
Series:	International Series in Operations Research & Management Science , #116
Edition description:	3rd ed. 2008
Pages:	546
Product dimensions:	5.80(w) x 9.00(h) x 1.50(d)

About the Author

David G. Luenberger received his B.S. degree from the California Institute of Technology and his M.S. and Ph.D. degrees from Stanford University, all in Electrical Engineering. Since 1963 he has served on the faculty of Stanford University. He helped found the Department of Engineering-Economic Systems, which have since become the Department of Management Science and Engineering, where his is currently a professor.

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

A reader from Greece

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.

Giorgio Azvaris

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)