Autore	Ye Yinyu
Pubbl/distr/stampa	New York, : Wiley, c1997
Descrizione fisica	1 online resource (438 p.)
Disciplina	511.8
Collana	Wiley-Interscience series in discrete mathematics and optimization
Soggetto topico	Programming (Mathematics) Linear programming
Soggetto genere / forma	Electronic books.
ISBN	1-283-29459-1 9786613294593 1-118-03270-5 1-118-03095-8
Formato	Materiale a stampa
Livello bibliografico	Monografia
Lingua di pubblicazione	eng
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
Record Nr.	UNINA-9910141051203321