A Simple, Quadratically Convergent Interior Point Algorithm for Linear Programming and Convex Quadratic Programming

André L. Tits and Jian L. Zhou
Additional contact information
André L. Tits: University of Maryland, Electrical Engineering Department and Institute for Systems Research
Jian L. Zhou: University of Maryland, Institute for Systems Research

A chapter in Large Scale Optimization, 1994, pp 411-427 from Springer

Abstract: Abstract An algorithm for linear programming (LP) and convex quadratic programming (CQP) is proposed, based on an interior point iteration introduced more than ten years ago by J. Herskovits for the solution of nonlinear programming problems. Herskovits’ iteration can be simplified significantly in the LP/CQP case, and quadratic convergence from any initial point can be achieved. Interestingly the linear system solved at each iteration is identical to that of the primal-dual affine scaling scheme recently considered by Monteiro et al. independently of Herskovits’ work. The proposed algorithm, however, uses an iteratively selected step length, different for each component of the dual variable.

Keywords: Linear programming; quadratic programming; global convergence; quadratic convergence; primal-dual iteration; affine scaling (search for similar items in EconPapers)
Date: 1994
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-3632-7_20

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

DOI: 10.1007/978-1-4613-3632-7_20

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 ().