Primal-Dual Interior-Point Methods
By addebook • Nov 15th, 2008 • Category: Mathematics •
•
Primal-Dual Interior-Point Methods
by Stephen J. Wright
Primal-Dual Interior-Point Methods
By Stephen J. Wright
Publisher: Society for Industrial Mathematics
Number Of Pages: 309
Publication Date: 1987-01-01
ISBN-10 / ASIN: 089871382X
ISBN-13 / EAN: 9780898713824
Binding: Paperback
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.
Summary: The easiest explanation of interior point linear programming
Rating: 5
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.
Summary: Wright is always right
Rating: 5
Excelent book, a must-have for everyone that has interest on the subject.
Summary: Excellent Book
Rating: 4
Very accurate and detailed algorithm. Easy to be used in the real world application.
Please Login or Register to read the rest of this content.
Related Posts
