## Interior Point Methods for Linear OptimizationInterior Point Methods for Linear Optimization is a comprehensive, thorough textbook on interior point methods (IPMs). The era of IPMs was initiated by N. Karmarkar’s 1984 paper, which triggered turbulent research and reshaped almost all areas of optimization theory and computational practice. This book gives a comprehensive review of the main results of more than a decade of IPM research. Numerous exercises are provided to aid in understanding the material. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Theory and Complexity | 13 |

A Polynomial Algorithm for the Selfdual Model | 47 |

Solving the Canonical Problem | 71 |

The Logarithmic Barrier Approach | 85 |

The Dual Logarithmic Barrier Method | 107 |

The PrimalDual Logarithmic Barrier Method 149 | 148 |

Initialization | 213 |

The PrimalDual Newton Method | 235 |

More Properties of the Central Path 307 | 306 |

Partial Updating | 317 |

HigherOrder Methods | 329 |

Parametric and Sensitivity Analysis | 361 |

Implementing Interior Point Methods 401 | 400 |

Appendix A Some Results from Analysis | 431 |

Transformation to canonical form | 445 |

Appendix E The Dikin step algorithm | 451 |

Applications 247 | 246 |

The Dual Newton Method | 259 |

The Primal Newton Method | 269 |

Karmarkars Projective Method | 289 |

Bibliography 461 | 460 |

479 | |

494 | |

### Other editions - View all

Interior Point Methods for Linear Optimization Cornelis Roos,Tamás Terlaky,J.-Ph. Vial Limited preview - 2006 |

Interior Point Methods for Linear Optimization Cornelis Roos,Tamás Terlaky,J.-Ph. Vial No preview available - 2006 |

### Common terms and phrases

adaptive updates afﬁne algorithm analysis analytic center barrier method barrier parameter break point central path Chapter coefﬁcient computational coordinates CPLEX damped Newton step deﬁned deﬁnition denote derive Dikin dual feasible dual logarithmic barrier dual problem duality gap equation Exercise feasible region ﬁnd ﬁrst ﬁxed follows full Newton step given Hence higher-order implies infeasible inﬁnity interior-point methods IPM’s IPMs iteration bound Karmarkar Lemma linear programming linearity interval logarithmic barrier function logarithmic barrier method matrix matrix norm maximal minimizer Newton’s method nonnegative norm null space number of iterations objective value obtain optimal basis optimal partition optimal set optimal solution optimal value orthogonal polynomial positive vector primal feasible primal-dual pair proof prove proximity measure quadratic convergence result row space satisﬁes search direction self-dual problem shadow prices Simplex Method solving step-size strictly complementary solution target sequence target-following Terlaky Theorem u-center upper bound w-space yields zero