Interior Point Approach to Linear, Quadratic, and Convex Programming: Algorithms and Complexity
In this book the rapidly developing field of Interior Point Methods (IPMs) is described. An extensive analysis of so-called path-following methods for linear programming, quadratic programming and convex programming is given. These methods, which form a subclass of interior point methods, follow the central path, which is an analytic curve defined by the problem. Relatively simple and elegant proofs for polynomiality are given. The theory is illustrated using several explicit examples. Moreover, an overview of other classes of IPMs is given. It is shown that all these methods rely on the same notion as the path-following methods: all these methods use the central path implicitly or explicitly as a reference path to go to the optimum.
What people are saying - Write a review
We haven't found any reviews in the usual places.
The logarithmic barrier method
The center method
Reducing the complexity for LP
5 other sections not shown
Other editions - View all
Interior Point Approach to Linear, Quadratic and Convex Programming ...
D. den Hertog
Limited preview - 2012
affine scaling method analytic center analyzed Anstreicher arithmetic operations barrier function value barrier parameter bTy(z center method central path complexity analysis complexity bound computational constraints convex programming problems convex quadratic programming current iterate decrease distance function feasible region fi(y fo(y following lemma given Gonzaga Hence Hertog inner iterations interior point methods IPMs ISBN iteration bound Karmarkar's Karush-Kuhn-Tucker conditions last inequality follows line search Linear Complementarity Problems linear programming problem ln(l logarithmic barrier function logarithmic barrier method long-step variant lower bound matrix medium-step variant method for linear minimization monotonically monotonically decreasing Moreover Nemirovsky 119 Nesterov and Nemirovsky Newton direction Newton iterations Note number of iterations objective function optimal solution optimal value polynomial potential function potential reduction method primal and dual problem CV Proof quadratic convergence search direction self-concordance condition short-step path-following method slack value smooth convex programming Theorem total number updates upper bound vector x(fi y(fi