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.
Author(s): Hans Frenk, Kees Roos, Tamás Terlaky, Shuzhong Zhang (auth.), Hans Frenk, Kees Roos, Tamás Terlaky, Shuzhong Zhang (eds.)
Series: Applied Optimization 33
Edition: 1
Publisher: Springer US
Year: 2000
Language: English
Pages: 474
Tags: Mathematics, general; Calculus of Variations and Optimal Control; Optimization; Systems Theory, Control; Number Theory; Optimization
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
