Muutke küpsiste eelistusi

E-raamat: Interior Point Algorithms - Theory and Analysis: Theory and Analysis [Wiley Online]

Teised raamatud teemal:
  • Wiley Online
  • Hind: 235,78 €*
  • * hind, mis tagab piiramatu üheaegsete kasutajate arvuga ligipääsu piiramatuks ajaks
Interior Point Algorithms - Theory and Analysis: Theory and AnalysisSuurem pilt
Teised raamatud teemal:
Wiley Online e-raamatudRohkem infot Wiley Online kohta
Raamatu kodulehekülg: https://onlinelibrary.wiley.com/doi/book/10.1002/9781118032701
Provides detailed coverage of all basic and advanced aspects of the subject, beginning with an overview of fundamental mathematical procedures. Coverage includes complexity results for linear and convex programming; state-of-the-art results for extension, implementation, and other computational techniques; and new research topics, such as nonlinear programming and nonconvex optimization. Intended for students and researchers in applied mathematics, computer science, operations research, management science, and engineering. Annotation c. by Book News, Inc., Portland, Or.

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.
Preface xiii(2)
List of Figures
xv
1 Introduction and Preliminaries
1(42)
1.1 Introduction
1(4)
1.2 Mathematical Preliminaries
5(10)
1.2.1 Basic notations
5(3)
1.2.2 Convex sets
8(4)
1.2.3 Real functions
12(2)
1.2.4 Inequalities
14(1)
1.3 Decision and Optimization Problems
15(13)
1.3.1 System of linear equations
15(1)
1.3.2 System of nonlinear equations
16(1)
1.3.3 Linear least-squares problem
16(1)
1.3.4 System of linear inequalities
17(1)
1.3.5 Linear programming (LP)
18(4)
1.3.6 Quadratic programming (QP)
22(1)
1.3.7 Linear complementarity problem (LCP)
23(1)
1.3.8 Positive semi-definite programming (PSP)
24(3)
1.3.9 Nonlinear programming (NP)
27(1)
1.3.10 Nonlinear complementarity problem (NCP)
27(1)
1.4 Algorithms and Computation Models
28(6)
1.4.1 Worst-case complexity
29(2)
1.4.2 Condition-based complexity
31(1)
1.4.3 Average complexity
32(1)
1.4.4 Asymptotic complexity
33(1)
1.5 Basic Computational Procedures
34(4)
1.5.1 Gaussian elimination method
35(1)
1.5.2 Choleski decomposition method
35(1)
1.5.3 The Newton method
36(1)
1.5.4 Solving ball-constrained linear problem
37(1)
1.5.5 Solving ball-constrained quadratic problem
37(1)
1.6 Notes
38(1)
1.7 Exercises
39(4)
2 Geometry of Convex Inequalities
43(38)
2.1 Convex Bodies
44(4)
2.1.1 Center of gravity
44(1)
2.1.2 Ellipsoids
45(3)
2.2 Analytic Center
48(11)
2.2.1 Analytic center
48(2)
2.2.2 Dual potential function
50(3)
2.2.3 Analytic central-section inequalities
53(6)
2.3 Primal and Primal-Dual Potential Functions
59(4)
2.3.1 Primal potential function
59(3)
2.3.2 Primal-dual potential function
62(1)
2.4 Potential Functions for LP, LCP, and PSP
63(7)
2.4.1 Primal potential function for LP
63(3)
2.4.2 Dual potential function for LP
66(1)
2.4.3 Primal-dual potential function for LP
66(1)
2.4.4 Potential function for LCP
67(1)
2.4.5 Potential function for PSP
68(2)
2.5 Central Paths of LP, LCP, and PSP
70(5)
2.5.1 Central path for LP
70(4)
2.5.2 Central path for LCP
74(1)
2.5.3 Central path for PSP
74(1)
2.6 Notes
75(2)
2.7 Exercises
77(4)
3 Computation of Analytic Center
81(28)
3.1 Proximity to Analytic Center
81(6)
3.2 Dual Algorithms
87(7)
3.2.1 Dual Newton procedure
87(2)
3.2.2 Dual potential algorithm
89(1)
3.2.3 Central-section algorithm
90(4)
3.3 Primal Algorithms
94(7)
3.3.1 Primal Newton procedure
94(1)
3.3.2 Primal potential algorithm
95(5)
3.3.3 Affine scaling algorithm
100(1)
3.4 Primal-Dual (Symmetric) Algorithms
101(5)
3.4.1 Primal-dual Newton procedure
102(1)
3.4.2 Primal-dual potential algorithm
103(3)
3.5 Notes
106(2)
3.6 Exercises
108(1)
4 Linear Programming Algorithms
109(38)
4.1 Karmarkar's Algorithm
109(8)
4.2 Path-Following Algorithm
117(3)
4.3 Potential Reduction Algorithm
120(6)
4.4 Primal-Dual (Symmetric) Algorithm
126(2)
4.5 Adaptive Path-Following Algorithms
128(8)
4.5.1 Predictor-corrector algorithm
131(3)
4.5.2 Wide-neighborhood algorithm
134(2)
4.6 Affine Scaling Algorithm
136(5)
4.7 Extensions to QP and LCP
141(1)
4.8 Notes
142(3)
4.9 Exercises
145(2)
5 Worst-Case Analysis
147(32)
5.1 Arithmetic Operation
148(4)
5.2 Termination
152(2)
5.2.1 Strict complementarity partition
153(2)
5.2.2 Project an interior point onto the optimal face
155(2)
5.3 Initialization
157(12)
5.3.1 A HSD linear program
159(5)
5.3.2 Solving (HSD)
164(3)
5.3.3 Further analysis
167(2)
5.4 Infeasible-Starting Algorithm
169(4)
5.5 Notes
173(3)
5.6 Exercises
176(3)
6 Average-Case Analysis
179(30)
6.1 One-Step Analysis
181(6)
6.1.1 High-probability behavior
182(1)
6.1.2 Proof of the theorem
183(4)
6.2 Random-Problem Analysis I
187(9)
6.2.1 High-probability behavior
189(4)
6.2.2 Random linear problems
193(3)
6.3 Random-Problem Analysis II
196(10)
6.3.1 Termination scheme
197(4)
6.3.2 Random model and analysis
201(5)
6.4 Notes
206(2)
6.5 Exercises
208(1)
7 Asymptotic Analysis
209(22)
7.1 Rate of Convergence
209(4)
7.1.1 Order of convergence
210(1)
7.1.2 Linear convergence
211(1)
7.1.3 Average order
211(1)
7.1.4 Error function
212(1)
7.2 Superlinear Convergence: LP
213(5)
7.2.1 Technical results
213(3)
7.2.2 Quadratic convergence
216(2)
7.3 Superlinear Convergence: Monotone LCP
218(6)
7.3.1 Predictor-corrector algorithm for LCP
218(2)
7.3.2 Technical results
220(2)
7.3.3 Quadratic convergence
222(2)
7.4 Quadratically Convergent Algorithms
224(3)
7.4.1 Variant 1
224(1)
7.4.2 Variant 2
225(2)
7.5 Notes
227(2)
7.6 Exercises
229(2)
8 Convex Optimization
231(46)
8.1 Analytic Centers of Nested Polytopes
231(5)
8.1.1 Recursive potential reduction algorithm
232(3)
8.1.2 Complexity analysis
235(1)
8.2 Convex (Non-Smooth) Feasibility
236(10)
8.2.1 Max-potential reduction
238(1)
8.2.2 Compute a new approximate center
239(3)
8.2.3 Convergence and complexity
242(4)
8.3 Positive Semi-Definite Programming
246(10)
8.3.1 Potential reduction algorithm
248(6)
8.3.2 Primal-dual algorithm
254(2)
8.4 Monotone Complementarity Problem
256(17)
8.4.1 A Convex property
257(3)
8.4.2 A homogeneous MCP model
260(5)
8.4.3 The central path
265(3)
8.4.4 An interior-point algorithm
268(5)
8.5 Notes
273(2)
8.6 Exercises
275(2)
9 Nonconvex Optimization
277(60)
9.1 von Neumann Economic Growth Problem
277(14)
9.1.1 Max-potential of XXX(XXX)
279(5)
9.1.2 Approximate analytic centers of XXX(XXX)
284(2)
9.1.3 Central-section algorithm
286(5)
9.2 Linear Complementarity Problem
291(12)
9.2.1 Potential reduction algorithm
292(3)
9.2.2 A class of LCPs
295(3)
9.2.3 P-matrix LCP
298(5)
9.3 Generalized Linear Complementarity Problem
303(7)
9.3.1 Potential reduction algorithm
304(2)
9.3.2 Complexity analysis
306(3)
9.3.3 Further discussions
309(1)
9.4 Indefinite Quadratic Programming
310(15)
9.4.1 Potential reduction algorithm
312(4)
9.4.2 Generating an XXX-KKT point
316(2)
9.4.3 Solving the ball-constrained QP problem
318(7)
9.5 Approximating Quadratic Programming
325(7)
9.5.1 Positive semi-definite relaxation
325(2)
9.5.2 Approximation analysis
327(5)
9.6 Notes
332(3)
9.7 Exercises
335(2)
10 Implementation Issues
337(28)
10.1 Presolver
337(3)
10.2 Linear System Solver
340(10)
10.2.1 Solving normal equation
340(3)
10.2.2 Solving augmented system
343(2)
10.2.3 Numerical phase
345(4)
10.2.4 Iterative method
349(1)
10.3 High-Order Method
350(5)
10.3.1 High-order predictor-corrector method
350(2)
10.3.2 Analysis of a high-order method
352(3)
10.4 Homogeneous and Self-Dual Method
355(1)
10.5 Optimal-Basis Identifier
356(3)
10.5.1 A pivoting algorithm
356(2)
10.5.2 Theoretical and computational issues
358(1)
10.6 Notes
359(4)
10.7 Exercises
363(2)
Bibliography 365(44)
Index 409


YINYU YE, PhD, is Professor in the Department of ManagementSciences at the University of Iowa College of BusinessAdministration and the Program in Applied Mathematical &Computational Sciences.
Püsilink: https://www.kriso.ee/db/9781118032701_pe.html
Märksõnad: