Primal-Dual Interior-Point Methods

• PrefaceNotationChapter 1: Introduction. Linear ProgrammingPrimal-Dual MethodsThe Central PathA Primal-Dual FrameworkPath-Following MethodsPotential-Reduction MethodsInfeasible Starting PointsSuperlinear ConvergenceExtensionsMehrotra's Predictor-Corrector AlgorithmLinear Algebra IssuesKarmarkar's AlgorithmChapter 2: Background: Linear Programming and Interior-Point MethodsStandard FormOptimality Conditions, Duality, and Solution SetsThe B * N Partition and Strict ComplementarityA Strictly Interior PointRank of the Matrix ABases and VerticesFarkas's Lemma and a Proof of the Goldman–Tucker ResultThe Central PathBackground: Primal MethodPrimal-Dual Methods: Development of the Fundamental IdeasNotes and ReferencesChapter 3: Complexity Theory. Polynomial Versus Exponential, Worst Case vs Average CaseStoring the Problem Data: Dimension and SizeThe Turing Machine and Rational ArithmeticPrimal-Dual Methods and Rational ArithmeticLinear Programming and Rational NumbersMoving to a Solution from an Interior PointComplexity of Simplex, Ellipsoid, and Interior-Point MethodsPolynomial and Strongly Polynomial AlgorithmsBeyond the Turing Machine ModelMore on the Real-Number Model and Algebraic ComplexityA General Complexity Theorem for Path-Following MethodsNotes and ReferencesChapter 4: Potential-Reduction Methods. A Primal-Dual Potential-Reduction AlgorithmReducing Forces ConvergenceA Quadratic Estimate of \Phi _{\rho } along a Feasible DirectionBounding the Coefficients in The Quadratic ApproximationAn Estimate of the Reduction in \Phi _{\rho } and Polynomial ComplexityWhat About Centrality?Choosing * and *Notes and ReferencesChapter 5: Path-Following Algorithms. The Short-Step Path-Following AlgorithmTechnical ResultsThe Predictor-Corrector MethodA Long-Step Path-Following AlgorithmLimit Points of the Iteration SequenceProof of Lemma 5.3Notes and ReferencesChapter 6: Infeasible-Interior-Point Algorithms. The AlgorithmConvergence of Algorithm IPFTechnical Results I: Bounds on \nu _k \delimiter ""026B30D (x^k,s^k) \delimiter ""026B30DTechnical Results II: Bounds on (D^k)^{-1} \Delta x^k and D^k \Delta s^kTechnical Results III: A Uniform Lower Bound on *kProofs of Theorems 6.1 and 6.2Limit Points of the Iteration SequenceChapter 7: Superlinear Convergence and Finite Termination. Affine-Scaling StepsAn Estimate of (*x, * s): The Feasible CaseAn Estimate of (* x, * s): The Infeasible CaseAlgorithm PC Is SuperlinearNearly Quadratic MethodsConvergence of Algorithm LPF+Convergence of the Iteration Sequence*(A,b,c) and Finite TerminationA Finite Termination StrategyRecovering an Optimal BasisMore on * (A,b,c)Notes and ReferencesChapter 8: Extensions. The Monotone LCPMixed and Horizontal LCPStrict Complementarity and LCPConvex QPConvex ProgrammingMonotone Nonlinear Complementarity and Variational InequalitiesSemidefinite ProgrammingProof of Theorem 8.4Notes and ReferencesChapter 9: Detecting Infeasibility. Self-DualityThe Simplified HSD FormThe HSDl FormIdentifying a Solution-Free RegionImplementations of the HSD FormulationsNotes and ReferencesChapter 10: Practical Aspects of Primal-Dual Algorithms. Motivation for Mehrotra's AlgorithmThe AlgorithmSuperquadratic ConvergenceSecond-Order Trajectory-Following MethodsHigher-Order MethodsFurther EnhancementsNotes and ReferencesChapter 11: Implementations. Three Forms of the Step EquationThe Cholesky FactorizationSparse Cholesky Factorization: Minimum-Degree OrderingsOther OrderingsSmall Pivots in the Cholesky FactorizationDense Columns in AThe Augmented System FormulationFactoring Symmetric Indefinite MatricesStarting PointsTerminationAlternative Formulations for the Linear ProgramFree VariablesPresolvingPrimal-Dual CodesNotes and ReferencesAppendix A: Basic Concepts and Results

'The current hottest topic in optimization is interior-point methods. Steve Wright, a renowned expert in optimization, has written a truly excellent introduction to this topic. We have used this book in a term-long seminar. It was immediately obvious that this book is both comprehensive and 'very readable' to both experts and students new to this area. The book is not just a theoretical text but contains algorithms in enough detail to allow students to write efficient code. Even though the area of interior-points is still under development, this book promises to be an important reference for many years to come.' Professor Henry Wolkowicz, University of Waterloo 'This is a beautifully crafted book on a specialized but very important topic. Primal-dual methods are now recognized by both theoreticians and practitioners as the best available interior-point methods for linear programming. Steve Wright's book is remarkable because it demystifies a very active current research area, synthesizing the important contributions and making the many clever ideas underlying the subject accessible to graduate (or even good undergraduate) students. The book is comprehensive and beautifully written. I could not find a single poorly written sentence or confusing equation. I strongly recommend it to anyone interested in linear programming.' Michael Overton, New York University 'Stephen J. Wright has written an excellent book about primal-dual interior-point methods. The book covers major theoretical developments of the last ten years as well as practical issues related to implementation of the methods. The subject is presented thoroughly, and valuable insight and motivation are also provided. The book can be used as an introduction to interior-point methods for advanced students and is a useful reference book for researchers. I am sure I am going to use the book a lot and cite it often.' Erling D. Andersen, Department of Management, Odense University, Denmark