Interior point algorithms : theory and analysis / / Yinyu Ye

• Record Nr.: UNINA9911019669003321
• Autore: Ye Yinyu
• Pubbl/distr/stampa: New York, : Wiley, c1997
• ISBN: 9786613294593; 9781283294591; 1283294591; 9781118032701; 1118032705; 9781118030950; 1118030958
• Descrizione fisica: 1 online resource (438 p.)
• Collana: Wiley-Interscience series in discrete mathematics and optimization
• Disciplina: 519.7/2
• Soggetti: Programming (Mathematics); Linear programming
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references (p. 365-408) and index.
• Nota di contenuto: Interior Point Algorithms: Theory and Analysis; Contents; Preface; List of Figures; 1 Introduction and Preliminaries; 1.1 Introduction; 1.2 Mathematical Preliminaries; 1.2.1 Basic notations; 1.2.2 Convex sets; 1.2.3 Real functions; 1.2.4 Inequalities; 1.3 Decision and Optimization Problems; 1.3.1 System of linear equations; 1.3.2 System of nonlinear equations; 1.3.3 Linear least-squares problem; 1.3.4 System of linear inequalities; 1.3.5 Linear programming (LP); 1.3.6 Quadratic programming (QP); 1.3.7 Linear complementarity problem (LCP); 1.3.8 Positive semi-definite programming (PSP); 1.3.9 Nonlinear programming (NP)1.3.10 Nonlinear complementarity problem (NCP); 1.4 Algorithms and Computation Models; 1.4.1 Worst-case complexity; 1.4.2 Condition-based complexity; 1.4.3 Average complexity; 1.4.4 Asymptotic complexity; 1.5 Basic Computational Procedures; 1.5.1 Gaussian elimination method; 1.5.2 Choleski decomposition method; 1.5.3 The Newton method; 1.5.4 Solving ball-constrained linear problem; 1.5.5 Solving ball-constrained quadratic problem; 1.6 Notes; 1.7 Exercises; 2 Geometry of Convex Inequalities; ; 2.1 Convex Bodies; 2.1.1 Center of gravity; 2.1.2 Ellipsoids; 2.2 Analytic Center2.2.1 Analytic center; 2.2.2 Dual potential function; 2.2.3 Analytic central-section inequalities; 2.3 Primal and Primal-Dual Potential Functions; 2.3.1 Primal potential function; 2.3.2 Primal-dual potential function; 2.4 Potential Functions for LP, LCP, and PSP; 2.4.1 Primal potential function for LP; 2.4.2 Dual potential function for LP; 2.4.3 Primal-dual potential function for LP; 2.4.4 Potential function for LCP; 2.4.5 Potential function for PSP; 2.5 Central Paths of LP, LCP, and PSP; 2.5.1 Central path for LP; 2.5.2 Central path for LCP; 2.5.3 Central path for PSP; 2.6 Notes2.7 Exercises; 3 Computation of Analytic Center; 3.1 Proximity to Analytic Center; 3.2 Dual Algorithms; 3.2.1 Dual Newton procedure; 3.2.2 Dual potential algorithm; 3.2.3 Central-section algorithm; 3.3 Primal Algorithms; 3.3.1 Primal Newton procedure; 3.3.2 Primal potential algorithm; 3.3.3 Affine scaling algorithm; 3.4 Primal-Dual (Symmetric) Algorithms; 3.4.1 Primal-dual Newton procedure; 3.4.2 Primal-dual potential algorithm; 3.5 Notes; 3.6 Exercises; 4 Linear Programming Algorithms; 4.1 Karmarkar's Algorithm; 4.2 Path-Following Algorithm; 4.3 Potential Reduction Algorithm; 4.4 Primal-Dual (Symmetric) Algorithm4.5 Adaptive Path-Following Algorithms; 4.5.1 Predictor-corrector algorithm; 4.5.2 Wide-neighborhood algorithm; 4.6 Affine Scaling Algorithm; 4.7 Extensions to QP and LCP; 4.8 Notes; 4.9 Exercises; 5 Worst-Case Analysis; 5.1 Arithmetic Operation; 5.2 Termination; 5.2.1 Strict complementarity partition; 5.2.2 Project an interior point onto the optimal face; 5.3 Initialization; 5.3.1 A HSD linear program; 5.3.2 Solving (HSD); 5.3.3 Further analysis; 5.4 Infeasible-Starting Algorithm; 5.5 Notes; 5.6 Exercises; 6 Average-Case Analysis; 6.1 One-Step Analysis; 6.1.1 High-probability behavior
• Sommario/riassunto: 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 th