An exterior-point method for linear programming problems. (English) Zbl 0866.90086
Summary: This paper proves the convergence of an algorithm for solving linear programming problems in \(O(mn^2)\) arithmetic operations. The method is called an exterior-point procedure, because it obtains a sequence of approximations falling outside the set \(U\) of feasible solutions. Each iteration consists of a single step within some constraining hyperplane, followed by one or more projections which force the new approximation to fall within some envelope about \(U\). The paper also discusses several numerical applications. In some types of problems, the method is considerably faster than a standard simplex method program when the size of the problem is sufficiently large.
MSC:
| 90C05 | Linear programming |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | Andrus, J. F.,An Exterior-Point Method for the Convex Programming Problem, Journal of Optimization Theory and Applications, Vol. 72, pp. 37–63, 1992. · Zbl 0793.90051 · doi:10.1007/BF00939949 |
| [2] | Gonzaga, C. C.,An Algorithm for Solving Linear Programming Problems in O(n 3L)Operations, Progress in Mathematical Programming: Interior and Related Methods, Edited by N. Megiddo, Springer Verlag, New York, New York, pp. 1–28, 1989. |
| [3] | Karmarkar, N.,A New Polynomial Time Algorithm for Linear Programming, Combinatorica, Vol. 4, pp. 373–395, 1984. · Zbl 0557.90065 · doi:10.1007/BF02579150 |
| [4] | Khachian, L. G.,Polynomial Algorithms in Linear Programming, USSR Computational Mathematics and Mathematical Physics, Vol. 20, pp. 53–72, 1980. · Zbl 0459.90047 · doi:10.1016/0041-5553(80)90061-0 |
| [5] | Monteiro, R. D. C., andAdler, I.,Interior Path Following Primal-Dual Algorithms, Part 1: Linear Programming, Mathematical Programming, Vol. 44, pp. 27–41, 1989. · Zbl 0676.90038 · doi:10.1007/BF01587075 |
| [6] | Renegar, J.,A Polynomial-Time Algorithm, Based on Newton’s Method, for Linear Programming, Mathematical Programming, Vol. 40, pp. 59–93, 1988. · Zbl 0654.90050 · doi:10.1007/BF01580724 |
| [7] | Vaidya, P. M.,An Algorithm for Linear Programming Which Requires O(((m+n)n 2+(m+n)1.5 n)L)Arithmetic Operations, Mathematical Programming, Vol. 47, pp. 175–201, 1990. · Zbl 0708.90047 · doi:10.1007/BF01580859 |
| [8] | Domich, P. D., Hoffman, K. L., Jackson, R. H. F., Saunders, P. S., andShier, D. R.,Comparison of Mathematical Programming Software: A Case Study Using Discrete L 1-Approximation Codes, Computers and Operations Research, Vol. 14, pp. 435–447, 1987. · Zbl 0626.90075 · doi:10.1016/0305-0548(87)90040-2 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
