Interior-Point Methods

David G. Luenberger and Yinyu Ye
Additional contact information
David G. Luenberger: Stanford University
Yinyu Ye: Stanford University

Chapter Chapter 5 in Linear and Nonlinear Programming, 2016, pp 115-147 from Springer

Abstract: Abstract Linear programs can be viewed in two somewhat complementary ways. They are, in one view, a class of continuous optimization problems each with continuous variables defined on a convex feasible region and with a continuous objective function. They are, therefore, a special case of the general form of problem considered in this text. However, linearity implies a certain degree of degeneracy, since for example the derivatives of all functions are constants and hence the differential methods of general optimization theory cannot be directly used. From an alternative view, linear programs can be considered as a class of combinatorial problems because it is known that solutions can be found by restricting attention to the vertices of the convex polyhedron defined by the constraints. Indeed, this view is natural when considering network problems such as those of early chapters. However, the number of vertices may be large, up to n ! ∕ m ! ( n − m ) $$n!/m!(n - m)$$ !, making direct search impossible for even modest size problems.

Keywords: Interior Point Algorithm; Central Path; Primal-dual Potential Function; Dual Feasibility; Ellipsoid Method (search for similar items in EconPapers)
Date: 2016
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:isochp:978-3-319-18842-3_5

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

DOI: 10.1007/978-3-319-18842-3_5

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().