Interior methods for constrained optimization
Margaret H. Wright · Acta Numerica · 1992
Interior methods for optimization were widely used in the 1960s, primarily in the form of barrier methods. However, they were not seriously applied to linear programming because of the dominance of the simplex method. Barrier methods fell from favour during the 1970s for a variety of reasons, including their apparent inefficiency compared with the best available alternatives. In 1984, Karmarkar's announcement of a fast polynomial-time interior method for linear programming caused tremendous excitement in the field of optimization. A formal connection can be shown between his method and classical barrier methods, which have consequently undergone a renaissance in interest and popularity. Most papers published since 1984 have concentrated on issues of computational complexity in interior methods for linear programming. During the same period, implementations of interior methods have displayed great efficiency in solving many large linear programs of ever-increasing size. Interior methods have also been applied with notable success to nonlinear and combinatorial problems. This paper presents a self-contained survey of major themes in both classical material and recent developments related to the theory and practice of interior methods.
Cited by 277 works. doi:10.1017/s0962492900002300
Authors
References
- Convex Analysis
- A new polynomial-time algorithm for linear programming
- Iterative Solution of Nonlinear Equations in Several Variables
- Iterative Solution of Nonlinear Equations in Several Variables
- Combinatorial Optimization: Algorithms and Complexity.
- Practical optimization
- Introduction to linear and nonlinear programming
- Practical methods of optimization
- Polynomial algorithms in linear programming
- Nonlinear Programming: Sequential Unconstrained Minimization Techniques