Skip to content
Register Sign in Wishlist
Primal-Dual Interior-Point Methods

Primal-Dual Interior-Point Methods

  • Date Published: December 1997
  • availability: This item is not supplied by Cambridge University Press in your region. Please contact Soc for Industrial & Applied Mathematics for availability.
  • format: Paperback
  • isbn: 9780898713824

Paperback

Add to wishlist

Looking for an inspection copy?

This title is not currently available for inspection. However, if you are interested in the title for your course we can consider offering an inspection copy. To register your interest please contact asiamktg@cambridge.org providing details of the course you are teaching.

Description
Product filter button
Description
Contents
Resources
Courses
About the Authors
  • 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.

    Reviews & endorsements

    '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

    See more reviews

    Customer reviews

    Not yet reviewed

    Be the first to review

    Review was not posted due to profanity

    ×

    , create a review

    (If you're not , sign out)

    Please enter the right captcha value
    Please enter a star rating.
    Your review must be a minimum of 12 words.

    How do you rate this item?

    ×

    Product details

    • Date Published: December 1997
    • format: Paperback
    • isbn: 9780898713824
    • length: 309 pages
    • dimensions: 254 x 172 x 17 mm
    • weight: 0.539kg
    • availability: This item is not supplied by Cambridge University Press in your region. Please contact Soc for Industrial & Applied Mathematics for availability.
  • Table of Contents

    Preface
    Notation
    1. Introduction. Linear Programming
    Primal-Dual Methods
    The Central Path
    A Primal-Dual Framework
    Path-Following Methods
    Potential-Reduction Methods
    Infeasible Starting Points
    Superlinear Convergence
    Extensions
    Mehrotra's Predictor-Corrector Algorithm
    Linear Algebra Issues
    Karmarkar's Algorithm
    2. Background. Linear Programming and Interior-Point Methods
    Standard Form
    Optimality Conditions, Duality, and Solution Sets
    The B {SYMBOL 200 \f "Symbol"} N Partition and Strict Complementarity
    A Strictly Interior Point
    Rank of the Matrix A
    Bases and Vertices
    Farkas's Lemma and a Proof of the Goldman–Tucker Result
    The Central Path
    Background. Primal Method
    Primal-Dual Methods. Development of the Fundamental Ideas
    Notes and References
    3. Complexity Theory. Polynomial Versus Exponential, Worst Case vs Average Case
    Storing the Problem Data. Dimension and Size
    The Turing Machine and Rational Arithmetic
    Primal-Dual Methods and Rational Arithmetic
    Linear Programming and Rational Numbers
    Moving to a Solution from an Interior Point
    Complexity of Simplex, Ellipsoid, and Interior-Point Methods
    Polynomial and Strongly Polynomial Algorithms
    Beyond the Turing Machine Model
    More on the Real-Number Model and Algebraic Complexity
    A General Complexity Theorem for Path-Following Methods
    Notes and References
    4. Potential-Reduction Methods. A Primal-Dual Potential-Reduction Algorithm
    Reducing Forces Convergence
    A Quadratic Estimate of \Phi _{\rho } along a Feasible Direction
    Bounding the Coefficients in The Quadratic Approximation
    An Estimate of the Reduction in \Phi _{\rho } and Polynomial Complexity
    What About Centrality?
    Choosing {SYMBOL 114 \f "Symbol"} and {SYMBOL 97 \f "Symbol"}
    Notes and References
    5. Path-Following Algorithms. The Short-Step Path-Following Algorithm
    Technical Results
    The Predictor-Corrector Method
    A Long-Step Path-Following Algorithm
    Limit Points of the Iteration Sequence
    Proof of Lemma 5.3
    Notes and References
    6. Infeasible-Interior-Point Algorithms. The Algorithm
    Convergence of Algorithm IPF
    Technical Results I. Bounds on \nu _k \delimiter "026B30D (x^k,s^k) \delimiter "026B30D
    Technical Results II. Bounds on (D^k)^{-1} \Delta x^k and D^k \Delta s^k
    Technical Results III. A Uniform Lower Bound on {SYMBOL 97 \f "Symbol"}k
    Proofs of Theorems 6.1 and 6.2
    Limit Points of the Iteration Sequence
    7. Superlinear Convergence and Finite Termination. Affine-Scaling Steps
    An Estimate of ({SYMBOL 68 \f "Symbol"}x, {SYMBOL 68 \f "Symbol"} s). The Feasible Case
    An Estimate of ({SYMBOL 68 \f "Symbol"} x, {SYMBOL 68 \f "Symbol"} s). The Infeasible Case
    Algorithm PC Is Superlinear
    Nearly Quadratic Methods
    Convergence of Algorithm LPF+
    Convergence of the Iteration Sequence
    {SYMBOL 206 \f "Symbol"}(A,b,c) and Finite Termination
    A Finite Termination Strategy
    Recovering an Optimal Basis
    More on {SYMBOL 206 \f "Symbol"} (A,b,c)
    Notes and References
    8. Extensions. The Monotone LCP
    Mixed and Horizontal LCP
    Strict Complementarity and LCP
    Convex QP
    Convex Programming
    Monotone Nonlinear Complementarity and Variational Inequalities
    Semidefinite Programming
    Proof of Theorem 8.4. Notes and References
    9. Detecting Infeasibility. Self-Duality
    The Simplified HSD Form
    The HSDl Form
    Identifying a Solution-Free Region
    Implementations of the HSD Formulations
    Notes and References
    10. Practical Aspects of Primal-Dual Algorithms. Motivation for Mehrotra's Algorithm
    The Algorithm
    Superquadratic Convergence
    Second-Order Trajectory-Following Methods
    Higher-Order Methods
    Further Enhancements
    Notes and References
    11. Implementations. Three Forms of the Step Equation
    The Cholesky Factorization
    Sparse Cholesky Factorization. Minimum-Degree Orderings
    Other Orderings
    Small Pivots in the Cholesky Factorization
    Dense Columns in A
    The Augmented System Formulat

  • Author

    Stephen J. Wright, Argonne National Laboratory, Illinois

Sign In

Please sign in to access your account

Cancel

Not already registered? Create an account now. ×

Sorry, this resource is locked

Please register or sign in to request access. If you are having problems accessing these resources please email lecturers@cambridge.org

Register Sign in
Please note that this file is password protected. You will be asked to input your password on the next screen.

» Proceed

You are now leaving the Cambridge University Press website. Your eBook purchase and download will be completed by our partner www.ebooks.com. Please see the permission section of the www.ebooks.com catalogue page for details of the print & copy limits on our eBooks.

Continue ×

Continue ×

Continue ×

Find content that relates to you

Join us online

This site uses cookies to improve your experience. Read more Close

Are you sure you want to delete your account?

This cannot be undone.

Cancel

Thank you for your feedback which will help us improve our service.

If you requested a response, we will make sure to get back to you shortly.

×
Please fill in the required fields in your feedback submission.
×