Del 277 - Mathematics and Its Applications

Interior Point Approach to Linear, Quadratic and Convex Programming

Algorithms and Complexity

Inbunden, Engelska, 1994

Av D.den Hertog, D. Den Hertog, D. Den Hertog

709 kr

Beställningsvara. Skickas inom 10-15 vardagar

Fri frakt för medlemmar vid köp för minst 249 kr.

This book describes the rapidly developing field of interior point methods (IPMs). An extensive analysis is given of path-following methods for linear programming, quadratic programming and convex programming. These methods, which form a subclass of interior point methods, follow the central path, which is an analytic curve defined by the problem. Relatively simple and elegant proofs for polynomiality are given. The theory is illustrated using several explicit examples. Moreover, an overview of other classes of IPMs is given. It is shown that all these methods rely on the same notion as the path-following methods: all these methods use the central path implicitly or explicitly as a reference path to go to the optimum. For specialists in IPMs as well as those seeking an introduction to IPMs. The book is accessible to any mathematician with basic mathematical programming knowledge.

Produktinformation

Utgivningsdatum1994-03-31
Mått170 x 244 x 17 mm
Vikt512 g
FormatInbunden
SpråkEngelska
SerieMathematics and Its Applications
Antal sidor210
Upplaga1994
FörlagKluwer Academic Publishers
ISBN9780792327349

Tillhör följande kategorier

1 Introduction of IPMs.- 1.1 Prelude.- 1.2 Intermezzo: Complexity issues.- 1.3 Classifying the IPMs.- 1.4 Scope of the book.- 2 The logarithmic barrier method.- 2.1 General framework.- 2.2 Central paths for some examples.- 2.3 Linear programming.- 2.4 Convex quadratic programming.- 2.5 Smooth convex programming.- 2.6 Miscellaneous remarks.- 3 The center method.- 3.1 General framework.- 3.2 Centers for some examples.- 3.3 Linear programming.- 3.4 Smooth convex programming.- 3.5 Miscellaneous remarks.- 4 Reducing the complexity for LP.- 4.1 Approximate solutions and rank-one updates.- 4.2 Adding and deleting constraints.- 5 Discussion of other IPMs.- 5.1 Path-following methods.- 5.2 Affine scaling methods.- 5.3 Projective potential reduction methods.- 5.4 Affine potential reduction methods.- 5.5 Comparison of IPMs.- 6 Summary, conclusions and recommendations.- Appendices.- A Self-concordance proofs.- A.1 Some general composition rules.- A.2 The dual geometric programming problem.- A.3 The extended entropy programming problem.- A.4 The primal 4-programming problem.- A.5 The dual 4-programming problem.- A.6 Other smoothness conditions.- B General technical lemmas.

`This book presents a general and rigorous foundation for solving nonlinear convex optimization problems. The book is well and clearly written. It is comprehensive and well-balanced ... excellent text for an advanced or seminar course on optimization, primarily addressed to graduate students in mathematics, pure or applied, computer science and engineering schools. ... researchers will also find it a valuable reference because the theorems contained in many of its sections represent the current state of the art. ... extensive bibliographic section is another strong point of the book, quite complete and up to date. I believe this work will remain a basic reference for whomever is interested in convex optimization for years to come. 'Optima, 47, 1995