Primal-Dual Interior-Point Methods [Paperback]

Stephen J. Wright (Author)

Book Description

Publication Date: January 1, 1987 | ISBN-10: 089871382X | ISBN-13: 978-0898713824

In the past decade, primal-dual algorithms have emerged as the most important and useful algorithms from the interior-point class. This book presents the major primal-dual algorithms for linear programming in straightforward terms. A thorough description of the theoretical properties of these methods is given, as are a discussion of practical and computational aspects and a summary of current software. This is an excellent, timely, and well-written work. The major primal-dual algorithms covered in this book are path-following algorithms (short- and long-step, predictor-corrector), potential-reduction algorithms, and infeasible-interior-point algorithms. A unified treatment of superlinear convergence, finite termination, and detection of infeasible problems is presented. Issues relevant to practical implementation are also discussed, including sparse linear algebra and a complete specification of Mehrotra's predictor-corrector algorithm. Also treated are extensions of primal-dual algorithms to more general problems such as monotone complementarity, semidefinite programming, and general convex programming problems.

Editorial Reviews

Review

'The current hottest topic in optimization is interior-point methods. Steve Wright, a renowned expert in optimization, has written a truly excellent introduction to this topic. We have used this book in a term-long seminar. It was immediately obvious that this book is both comprehensive and 'very readable' to both experts and students new to this area. The book is not just a theoretical text but contains algorithms in enough detail to allow students to write efficient code. Even though the area of interior-points is still under development, this book promises to be an important reference for many years to come.' Professor Henry Wolkowicz, University of Waterloo 'This is a beautifully crafted book on a specialized but very important topic. Primal-dual methods are now recognized by both theoreticians and practitioners as the best available interior-point methods for linear programming. Steve Wright's book is remarkable because it demystifies a very active current research area, synthesizing the important contributions and making the many clever ideas underlying the subject accessible to graduate (or even good undergraduate) students. The book is comprehensive and beautifully written. I could not find a single poorly written sentence or confusing equation. I strongly recommend it to anyone interested in linear programming.' Michael Overton, New York University 'Stephen J. Wright has written an excellent book about primal-dual interior-point methods. The book covers major theoretical developments of the last ten years as well as practical issues related to implementation of the methods. The subject is presented thoroughly, and valuable insight and motivation are also provided. The book can be used as an introduction to interior-point methods for advanced students and is a useful reference book for researchers. I am sure I am going to use the book a lot and cite it often.' Erling D. Andersen, Department of Management, Odense University, Denmark

Product Details

• Paperback: 309 pages
• Publisher: Society for Industrial Mathematics (January 1, 1987)
• Language: English
• ISBN-10: 089871382X
• ISBN-13: 978-0898713824
• Product Dimensions: 9.9 x 6.9 x 0.7 inches
• Shipping Weight: 1.2 pounds (View shipping rates and policies)
• Average Customer Review: 4.7 out of 5 stars  See all reviews (3 customer reviews)
• Amazon Best Sellers Rank: #1,437,530 in Books (See Top 100 in Books)

More About the Author

Steve Wright is a Professor of Computer Sciences at the University of Wisconsin-Madison. He does research in computational optimization and its applications to many other areas of science and engineering. He has also been active in professional roles, most notably as a recent chair of the Mathematical Optimization Society, the leading professional society in optimization. During his career, he has been excited to witness the increasing vitality of optimization and its growing visibility across the whole scientific enterprise. He looks forward to many more years of enjoyable collaborations with excellent colleagues.

Customer Reviews

Most Helpful Customer Reviews

5.0 out of 5 stars Wright is always right, April 3, 2004

By A Customer

This review is from: Primal-Dual Interior-Point Methods (Paperback)

Excelent book, a must-have for everyone that has interest on the subject.

4.0 out of 5 stars Excellent Book, April 19, 2000

By 

Bruce Shen (USA) - See all my reviews

This review is from: Primal-Dual Interior-Point Methods (Paperback)

Very accurate and detailed algorithm. Easy to be used in the real world application.

1 of 2 people found the following review helpful:

5.0 out of 5 stars The easiest explanation of interior point linear programming, August 9, 2004

By 

SamIam (New Mexico) - See all my reviews

This review is from: Primal-Dual Interior-Point Methods (Paperback)

There are basically 2 well-developed practical methods that dominate the solution methods known for solving linear programming (linear optimization) problems on the computer. The first one is the "Simplex Method" which was first developed in the 1940s but has since evolved into an efficient method through the use of many algorithmic and memory storage tricks. The other methods are much newer, starting in 1984, and are called "Interior-Point Methods". Interior-Point Methods are actually subdivided into many possible variations, thus making this field confusing to the newcomer. During the last decade, the Interior-Point Methods have matured and the picture is now much clearer. This book is perhaps the easiest one I know that explains some of the best performing Interior-Point Methods. Should you desire more introductory material about linear programming, an excellent companion to the above book would be "Optimization in Operations Research" by Rardin, although Rardin has only one chapter about Interior-Point Methods (I haven't read this book, but the reviews sound like this book is the best general introduction to linear programming and other optimization problems). It's tempting to say that you should learn the Simplex Method first before going on to Interior-Point methods--but I'm sure there are others who would disagree. As far as I know, the older Simplex Method can still be quite competitive--some problems are solved faster by the Simplex Method while other problems are solved faster using Interior-Point Methods. Nevertheless, this is a dynamic field of research and what is now true about the comparisons between these 2 methods can easily become false in the near future.