Primal-Dual Interior-Point Methods
In the past decade, primal-dual algorithms have emerged as the most important and useful algorithms from the interior-point class. This book presents the major primal-dual algorithms for linear programming in straightforward terms. A thorough description of the theoretical properties of these methods is given, as are a discussion of practical and computational aspects and a summary of current software. This is an excellent, timely, and well-written work. The major primal-dual algorithms covered in this book are path-following algorithms (short- and long-step, predictor-corrector), potential-reduction algorithms, and infeasible-interior-point algorithms. A unified treatment of superlinear convergence, finite termination, and detection of infeasible problems is presented. Issues relevant to practical implementation are also discussed, including sparse linear algebra and a complete specification of Mehrotra's predictor-corrector algorithm. Also treated are extensions of primal-dual algorithms to more general problems such as monotone complementarity, semidefinite programming, and general convex programming problems.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Other editions - View all
affine-scaling direction Algorithm PC analysis bºx centering parameter central path Chapter Cholesky factorization cºa coefficient matrix complexity result components computational constraints convex programming convex QP corrector defined dual problem duality measure Farkas's lemma feasible set finite termination formulation Framework PD Hence infeasible infeasible-interior-point interior-point algorithms interior-point methods iteration Karmarkar's KKT conditions Lemma limit point linear algebra linear complementarity problem linear programming linear system Mehrotra's mLCP neighborhood Newton's method nonlinear nonnegative nonzero obtain optimal pairwise products path-following algorithm pivot polynomial positive predictor-corrector primal and dual primal solution primal-dual algorithms primal-dual methods primal-dual solution Proof quadratic satisfies search direction semidefinite semidefinite programming sequence solution set Q solve sparse Cholesky starting point step equations step length strictly complementary solution strictly feasible points superlinear convergence supernode trajectory Turing machine vector zero