 Polynomial-Time Interior-Point MethodsYurii Nesterov
Chapter Chapter 5 in Lectures on Convex Optimization, 2018, pp 325-421 from Springer Abstract: Abstract In this section, we present the problem classes and complexity bounds of polynomial-time interior-point methods. These methods are based on the notion of a self-concordant function. It appears that such a function can be easily minimized by the Newton’s Method. On the other hand, an important subclass of these functions, the self-concordant barriers, can be used in the framework of path-following schemes. Moreover, it can be proved that we can follow the corresponding central path with polynomial-time complexity. The size of the steps in the penalty coefficient of the central path depends on the corresponding barrier parameter. It appears that for any convex set there exists a self-concordant barrier with parameter proportional to the dimension of the space of variables. On the other hand, for any convex set with explicit structure, such a barrier with a reasonable value of parameter can be constructed by simple combination rules. We present applications of this technique to Linear and Quadratic Optimization, Linear Matrix Inequalities and other optimization problems. Date: 2018 There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it. Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-91578-4_5 Ordering information: This item can be ordered from DOI: 10.1007/978-3-319-91578-4_5 Access Statistics for this chapter More chapters in Springer Optimization and Its Applications from Springer |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.