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.

YINYU YE, PhD, is Professor in the Department of Management Sciences at the University of Iowa College of Business Administration and the Program in Applied Mathematical & Computational Sciences.

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

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.