Interior Point Polynomial Algorithms in Convex ProgrammingWritten for specialists working in optimization, mathematical programming, or control theory. The general theory of path-following and potential reduction interior point polynomial time methods, interior point methods, interior point methods for linear and quadratic programming, polynomial time methods for nonlinear convex programming, efficient computation methods for control problems and variational inequalities, and acceleration of path-following methods are covered. In this book, the authors describe the first unified theory of polynomial-time interior-point methods. Their approach provides a simple and elegant framework in which all known polynomial-time interior-point methods can be explained and analyzed; this approach yields polynomial-time interior-point methods for a wide variety of problems beyond the traditional linear and quadratic programs. |
Contents
AM13_ch1 | 1 |
AM13_ch2 | 11 |
AM13_ch3 | 57 |
AM13_ch4 | 101 |
AM13_ch5 | 147 |
AM13_ch6 | 217 |
AM13_ch7 | 273 |
AM13_ch8 | 315 |
AM13_appendixa | 361 |
AM13_appendixb | 365 |
AM13_backmatter | 379 |
Other editions - View all
Interior-point Polynomial Algorithms in Convex Programming Yurii Nesterov,Arkadii Nemirovskii Limited preview - 1994 |
Interior Point Polynomial Algorithms in Convex Programming Yurii Nesterov,Arkadii Nemirovskii No preview available - 1987 |
Common terms and phrases
absolute constant affine mapping algorithm arithmetic cost Assume assumptions barrier F barrier for G barrier method bounded CA(E closed convex domain compute conic problem conic representation convergence convex cone convex function convex programming convex representation convex set defined definition denote dual ellipsoid epigraph feasible set fi(x follows functional element gradient homogeneous self-concordant barrier implies int G interior-point methods intersects int iteration latter inequality latter relation Legendre transformation Lemma Let F Let G Let us prove linear programming logarithmically homogeneous main stage matrix minimize monotone operator nonempty interior nonnegative Note optimal value pair parameter path-following method positive-semidefinite potential reduction preliminary stage primal primal-dual Proof Proposition quadratic form quadratic programming self-concordant barrier solvable solve standard step strongly self-concordant subspace suffices symmetric Theorem updating variational inequality vector