Abstract
Based on the nearest-point projection of geometric convexity we give a general projection approach for solving the feasibility problem of linear programming. Application of Shor's method of space dilation gives rise to a family of polynomial-time ellipsoidal algorithms with improved termination criteria in case of infeasibility. Moreover, the approach renders possible application of various techniques from nonlinear programming. In particular, using a variable metric algorithm with exact line search we obtain a fast and practically well-behaving algorithm for linear programming.
Original language | English |
---|---|
Pages (from-to) | 287-295 |
Number of pages | 9 |
Journal | European Journal of Operational Research |
Volume | 60 |
Issue number | 3 |
DOIs | |
State | Published - 10 Aug 1992 |
Externally published | Yes |
Keywords
- BFGS-method
- DFP-method
- Linear programming
- convex programming
- ellipsoid method
- nearest-point map
- polynomial-time algorithms
- variable metric algorithms