A Primal-Dual Interior Point Algorithm for Linear Programming

Masakazu Kojima, Shinji Mizuno and Akiko Yoshise

Chapter Chapter 2 in Progress in Mathematical Programming, 1989, pp 29-47 from Springer

Abstract: Abstract This chapter presents an algorithm that works simultaneously on primal and dual linear programming problems and generates a sequence of pairs of their interior feasible solutions. Along the sequence generated, the duality gap converges to zero at least linearly with a global convergence ratio (1 — η/n); each iteration reduces the duality gap by at least η/n. Here n denotes the size of the problems and η a positive number depending on initial interior feasible solutions of the problems. The algorithm is based on an application of the classical logarithmic barrier function method to primal and dual linear programs, which has recently been proposed and studied by Megiddo.

Date: 1989
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-9617-8_2

Ordering information: This item can be ordered from
http://www.springer.com/9781461396178

DOI: 10.1007/978-1-4613-9617-8_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().