Skip to main content
SpringerLink
Log in

A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems

  • Book
  • © 1991

Overview

Authors:
  1. Masakazu Kojima
    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Nimrod Megiddo
    View author publications

    You can also search for this author in PubMed   Google Scholar

  3. Toshihito Noma
    View author publications

    You can also search for this author in PubMed   Google Scholar

  4. Akiko Yoshise
    View author publications

    You can also search for this author in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 538)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (7 chapters)

  1. Front Matter

    Download chapter PDF

  2. Introduction

    Pages 1-5

  3. Summary

    Pages 7-23

  4. The class of linear complementarity problems with P 0-matrices

    Pages 25-34

  5. Basic analysis of the UIP method

    Pages 35-58

  6. Initial points and stopping criteria

    Pages 59-73

  7. A class of potential reduction algorithms

    Pages 75-85

  8. Proofs of convergence theorems

    Pages 87-96

  9. Back Matter

    Download chapter PDF
Back to top

Keywords

About this book

Following Karmarkar's 1984 linear programming algorithm, numerous interior-point algorithms have been proposed for various mathematical programming problems such as linear programming, convex quadratic programming and convex programming in general. This monograph presents a study of interior-point algorithms for the linear complementarity problem (LCP) which is known as a mathematical model for primal-dual pairs of linear programs and convex quadratic programs. A large family of potential reduction algorithms is presented in a unified way for the class of LCPs where the underlying matrix has nonnegative principal minors (P0-matrix). This class includes various important subclasses such as positive semi-definite matrices, P-matrices, P*-matrices introduced in this monograph, and column sufficient matrices. The family contains not only the usual potential reduction algorithms but also path following algorithms and a damped Newton method for the LCP. The main topics are global convergence, global linear convergence, and the polynomial-time convergence of potential reduction algorithms included in the family.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation