High Performance Optimization (Applied Optimization, 33)

For a long time the techniques of solving linear optimization (LP) problems improved only marginally. Fifteen years ago, however, a revolutionary discovery changed everything. A new `golden age' for optimization started, which is continuing up to the current time. What is the cause of the excitement? Techniques of linear programming formed previously an isolated body of knowledge. Then suddenly a tunnel was built linking it with a rich and promising land, part of which was already cultivated, part of which was completely unexplored. These revolutionary new techniques are now applied to solve conic linear problems. This makes it possible to model and solve large classes of essentially nonlinear optimization problems as efficiently as LP problems. This volume gives an overview of the latest developments of such `High Performance Optimization Techniques'. The first part is a thorough treatment of interior point methods for semidefinite programming problems. The second part reviews today's most exciting research topics and results in the area of convex optimization. __Audience:__ This volume is for graduate students and researchers who are interested in modern optimization techniques. Front Matter....Pages i-xxii Front Matter....Pages 1-1 Introduction....Pages 3-20 Duality....Pages 21-60 Polynomiality of Path-Following Methods....Pages 61-91 Self-Dual Embedding Technique....Pages 93-127 Properties of the Central Path....Pages 129-141 Superlinear Convergence....Pages 143-155 Central Region Method....Pages 157-194 Front Matter....Pages 195-195 The Mosek Interior Point Optimizer for Linear Programming: An Implementation of the Homogeneous Algorithm....Pages 197-232 A Simplification to “A Primal-Dual Interior Point Method Whose Running Time Depends Only on the Constraint Matrix”....Pages 233-243 New Complexity Analysis of Primal-Dual Newton Methods for P * ( κ ) Linear Complementarity Problems....Pages 245-265 Numerical Evaluation of SDPA (Semidefinite Programming Algorithm)....Pages 267-301 Robust Modeling of Multi-Stage Portfolio Problems....Pages 303-328 Computational Experience of an Interior-Point SQP Algorithm in a Parallel Branch-and-Bound Framework....Pages 329-347 Solving Linear Ordering Problems with a Combined Interior Point/Simplex Cutting Plane Algorithm....Pages 349-366 Finite Element Methods for Solving Parabolic Inverse Problems....Pages 367-381 Error Bounds for Quadratic Systems....Pages 383-404 Squared Functional Systems and Optimization Problems....Pages 405-440 Interior Point Methods: Current Status and Future Directions....Pages 441-466 Back Matter....Pages 467-476

For a long time the techniques of solving linear optimization (LP) problems improved only marginally. Fifteen years ago, however, a revolutionary discovery changed everything. A new 'golden age' for optimization started, which is continuing up to the current time. What is the cause of the excitement? Techniques of linear programming formed previously an isolated body of knowledge. Then suddenly a tunnel was built linking it with a rich and promising land, part of which was already cultivated, part of which was completely unexplored. These revolutionary new techniques are now applied to solve conic linear problems. This makes it possible to model and solve large classes of essentially nonlinear optimization problems as efficiently as LP problems. This volume gives an overview of the latest developments of such 'High Performance Optimization Techniques'. The first part is a thorough treatment of interior point methods for semidefinite programming problems. The second part reviews today's most exciting research topics and results in the area of convex optimization.
Audience: This volume is for graduate students and researchers who are interested in modern optimization techniques.