Projection algorithms for linear programming

U. Betke; P. Gritzmann

doi:10.1016/0377-2217(92)90080-S

Projection algorithms for linear programming

U. Betke
, P. Gritzmann

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

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	https://doi.org/10.1016/0377-2217(92)90080-S
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

Access to Document

10.1016/0377-2217(92)90080-S

Cite this

@article{9fb3e8ee30eb4ae5b95a1003481a8bf2,

title = "Projection algorithms for linear programming",

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.",

keywords = "BFGS-method, DFP-method, Linear programming, convex programming, ellipsoid method, nearest-point map, polynomial-time algorithms, variable metric algorithms",

author = "U. Betke and P. Gritzmann",

note = "Funding Information: * Research supported in part by the Alexander von Hum-boldt-foundation, by the Institute for Mathematics and its Applications through grands of the NSF and by the Deutsche Forschungsgemeinschaft.",

year = "1992",

month = aug,

day = "10",

doi = "10.1016/0377-2217(92)90080-S",

language = "English",

volume = "60",

pages = "287--295",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Projection algorithms for linear programming

AU - Betke, U.

AU - Gritzmann, P.

N1 - Funding Information: * Research supported in part by the Alexander von Hum-boldt-foundation, by the Institute for Mathematics and its Applications through grands of the NSF and by the Deutsche Forschungsgemeinschaft.

PY - 1992/8/10

Y1 - 1992/8/10

N2 - 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.

AB - 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.

KW - BFGS-method

KW - DFP-method

KW - Linear programming

KW - convex programming

KW - ellipsoid method

KW - nearest-point map

KW - polynomial-time algorithms

KW - variable metric algorithms

UR - https://www.scopus.com/pages/publications/0026900847

U2 - 10.1016/0377-2217(92)90080-S

DO - 10.1016/0377-2217(92)90080-S

M3 - Article

AN - SCOPUS:0026900847

SN - 0377-2217

VL - 60

SP - 287

EP - 295

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 3

ER -

Projection algorithms for linear programming

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this