Table of Contents

Preface
Notation
Chapter 1: Introduction

• Linear Programming
• Primal-Dual Methods
• The Central Path
• A Primal-Dual Framework
• Potential-Reduction Methods
• Infeasible Starting Points
• Superlinear Convergence
• Extensions
• Mehrota's Predictor-Corrector Algorithm
• Linear Algebra Issues
• Karmarkar's Algorithm

• Standard Form
• Optimality Conditions, Duality, and Solution Sets
• More on Duality
• The ${\cal B}\cup {\cal N}$ Partition and Strict Complementarity
• A Strictly Interior Point
• Rank of the Matrix A
• Bases and Vertices
• Farkas's Lemma and a Proof of the Goldman--Tucker Result
• The Central Path
• Background: Primal Methods
• Primal-Dual Methods: Development of the Fundamental Ideas
• Notes and References

• Polynomial Versus Exponential, Worst Case Versus Average Case
• Storing the Problem Data: Dimension and Size
• The Turing Machine and Rational Arithmetic
• Primal-Dual Methods and Rational Arithmetic
• Linear Programming and Rational Numbers
• Moving to a Solution from an Interior Point
• Complexity of Simplex, Ellipsoid, and Interior-Point Methods
• Polynomial and Strongly Polynomial Algorithms
• Beyond the Turing Machine Model
• More on the Real-Number Model and Algebraic Complexity
• A General Complexity Theorem for Path-Following Methods
• Notes and References

• A Primal-Dual Potential-Reduction Algorithm
• Reducing $\Phi _{\rho }$ Forces Convergence
• A Quadratic Estimate of $\Phi _{\rho }$ Along a Feasible Direction
• Bounding the Coefficients in the Quadratic Approximation
• An Estimate of the Reduction in $\Phi _{\rho }$ and Polynomial Complexity
• What About Centrality?
• Choosing $\rho $ and $\alpha $
• Notes and References

• The Short-Step Path-Following Algorithm
• Technical Results
• The Predictor-Corrector Method
• A Long-Step Path-Following Algorithm
• Limit Points of the Iteration Sequence
• Proof of Lemma 5.3
• Notes and References

• The Algorithm
• Convergence of Algorithm IPF
• Technical Results I: Bounds on $\nu _k ||(x^k,s^k)||$
• Technical Results II: Bounds on $(D^k)^{-1} \Delta x^k$ and $D^k \Delta s^k$
• Technical Results III: A Uniform Lower Bound on $\alpha _k$
• Proofs of Theorems 6.1 and 6.2
• Limit Points of the Iteration Sequence

• Affine-Scaling Steps
• An Estimate of $(\Delta x, \Delta s)$: The Feasible Case
• An Estimate of $(\Delta x, \Delta s)$: The Infeasible Case
• Algorithm PC Is Superlinear
• Nearly Quadratic Methods
• Convergence of Algorithm LPF+
• Convergence of the Iteration Sequence
• $\epsilon (A,b,c)$ and Finite Termination
• A Finite Termination Strategy
• Recovering an Optimal Basis
• More on $\epsilon (A,b,c)$
• Notes and References

• The Monotone LCP
• Mixed and Horizontal LCP
• Strict Complementarity and LCP
• Convex QP
• Convex Programming
• Monotone Nonlinear Complementarity and Variational Inequalities
• Semidefinite Programming
• Proof of Theorem 8.4
• Notes and References

• Self-Duality
• The Simplified HSD Form
• The HSD Form
• Identifying a Solution-Free Region
• Implementations of the HSD Formulations
• Notes and References

• Motivation for Mehrotra's Algorithm
• The Algorithm
• Superquadratic Convergence
• Second-Order Trajectory-Following Methods
• Higher-Order Methods
• Further Enhancements
• Notes and References

• Three Forms of the Step Equation
• The Cholesky Factorization
• Sparse Cholesky Factorization: Minimum-Degree Orderings
• Other Orderings
• Small Pivots in the Cholesky Factorization
• Dense Columns in A
• The Augmented System Formulation
• Factoring Symmetric Indefinite Matrices
• Starting Points
• Termination
• Alternative Formulations for the Linear Program
• Free Variables
• Presolving
• Primal-Dual Codes
• Notes and References

• Order Notation
• Convex Sets and Functions
• KKT Conditions
• Convexity and Global Solutions
• Self-Duality and a Proof of Theorem 9.1
• The Natural log Function and a Proof of Lemma 4.1
• Singular Value Decomposition, Matrix Rank, and QR Factorization
• Hoffman's Lemma
• The Stewart--Todd Result and a Proof of Lemma 7.2
• The Sherman--Morrison--Woodbury Formula
• Asymptotic Convergence
• Storing Sparse Matrices
• The Turing Machine

• BPMPD
• CPLEX/Barrier
• HOPDM
• LIPSOL
• LOQO
• Newton Barrier XPRESS-MP
• OSL/EKKBSLV
• PCx

Donate · Contact Us · Site Map · Join SIAM · My Account