Ye Y. Interior Point Algorithms: Theory and Analysis

New York: Wiley-Interscience, 1997. - 438p.The first comprehensive review of the theory and practice of one of today's most powerful optimization techniques.The explosive growth of research into and development of interior point algorithms over the past two decades has significantly improved the complexity of linear programming and yielded some of today's most sophisticated computing techniques. This book offers a comprehensive and thorough treatment of the theory, analysis, and implementation of this powerful computational tool.Interior Point Algorithms provides detailed coverage of all basic and advanced aspects of the subject. Beginning with an overview of fundamental mathematical procedures, Professor Yinyu Ye moves swiftly on to in-depth explorations of numerous computational problems and the algorithms that have been developed to solve them. An indispensable text/reference for students and researchers in applied mathematics, computer science, operations research, management science, and engineering, Interior Point Algorithms: * Derives various complexity results for linear and convex programming * Emphasizes interior point geometry and potential theory * Covers state-of-the-art results for extension, implementation, and other cutting-edge computational techniques * Explores the hottest new research topics, including nonlinear programming and nonconvex optimization.List of FiguresBasic notations
Convex sets
Real functions
Inequalities
System of linear equations
Linear least-squares problem
System of linear inequalities
Linear programming (LP)
Quadratic programming (QP)
Linear complementarity problem (LCP)
Positive semi-definite programming (PSP)
Nonlinear complementarity problem (NCP)
Algorithms and Computation Models
Worst-case complexity
Condition-based complexity
Average complexity
Asymptotic complexity
Basic Computational Procedures
Choleski decomposition method
The Newton method
Solving ball-constrained quadratic problem
Notes
ExercisesGeometry of Convex Inequalities
Center of gravity
Ellipsoids
Analytic center
Dual potential function
Analytic central-section inequalities
Primal potential function
Primal-dual potential function
Primal potential function for LP
Primal-dual potential function for LP
Potential function for LCP
Potential function for PSP
Central path for LP
Central path for PSP
Notes
ExercisesProximity to Analytic Center
Dual Newton procedure
Dual potential algorithm
Central-section algorithm
Primal Newton procedure
Primal potential algorithm
Affine scaling algorithm
Primal-Dual (Symmetric) Algorithms
Primal-dual Newton procedure
Primal-dual potential algorithm
Notes
ExercisesKarmarkar's Algorithm
Path-Following Algorithm
Potential Reduction Algorithm
Primal-Dual (Symmetric) Algorithm
Adaptive Path-Following Algorithms
Predictor-corrector algorithm
Wide-neighborhood algorithm
Affine Scaling Algorithm
Extensions to QP and LCP
Notes
ExercisesWorst-Case Analysis
Arithmetic Operation
Termination
Strict complementarity partition
Project an interior point onto the optimal face
Initialization
A HSD linear program
Solving (HSD)
Further analysis
Infeasible-Starting Algorithm
Notes
ExercisesAverage-Case Analysis
One-Step Analysis
High-probability behavior
Proof of the theorem
Random-Problem Analysis I
High-probability behavior
Random linear problems
Random-Problem Analysis II
Termination scheme
Random model and analysis
Notes
ExercisesRate of Convergence
Order of convergence
Average order
Error function
Technical results
Quadratic convergence
Predictor-corrector algorithm for LCP
Technical results
Quadratic convergence
Variant
Variant
Notes
ExercisesAnalytic Centers of Nested Polytopes
Recursive potential reduction algorithm
Complexity analysis
Convex (Non-Smooth) Feasibility
Max-potential reduction
Compute a new approximate center
Convergence and complexity
Positive Semi-Definite Programming
Potential reduction algorithm
Primal-dual algorithm
Monotone Complementarity Problem
A convex property
A homogeneous MCP model
The central path
An interior-point algorithm
Notes
Exercisesvon Neumann Economic Growth ProblemCentral-section algorithm
Linear Complementarity Problem
Potential reduction algorithm
A class of LCPs
P-matrix LCP
Generalized Linear Complementarity Problem
Potential reduction algorithm
Complexity analysis
Further discussions
Indefinite Quadratic Programming
Potential reduction algorithmSolving the ball-constrained QP problem
Positive semi-definite relaxation
Approximation analysis
Notes
ExercisesPresolver
Solving normal equation
Solving augmented system
Numerical phase
Iterative method
High-order predictor-corrector method
Analysis of a high-order method
Homogeneous and Self-Dual Method
A pivoting algorithm
Theoretical and computational issues
Notes
Exercises