Two linear programming algorithms for the linear discrete 𝐿₁ norm problem

Armstrong, Ronald D.; Godfrey, James P.

doi:10.1090/S0025-5718-1979-0525398-2

Two linear programming algorithms for the linear discrete $L_{1}$ norm problem
HTML articles powered by AMS MathViewer

by Ronald D. Armstrong and James P. Godfrey PDF

Math. Comp. 33 (1979), 289-300 Request permission

Abstract:

Computational studies by several authors have indicated that linear programming is currently the most efficient procedure for obtaining ${L_1}$, norm estimates for a discrete linear problem. However, there are several linear programming algorithms, and the "best" approach may depend on the problem’s structure (e.g., sparsity, triangularity, stability). In this paper we shall compare two published simplex algorithms, one referred to as primal and the other referred to as dual, and show that they are conceptually equivalent.

References

Nabih N. Abdelmalek, On the discrete linear $L_{1}$ approximation and $L_{1}$ solutions of overdetermined linear equations, J. Approximation Theory 11 (1974), 38–53. MR 388750, DOI 10.1016/0021-9045(74)90037-9
Nabih N. Abdelmalek, An efficient method for the discrete linear $L_{1}$ approximation problem, Math. Comp. 29 (1975), 844–850. MR 378354, DOI 10.1090/S0025-5718-1975-0378354-8

Naval Res. Logist. Quart

Ronald D. Armstrong and John W. Hultz, An algorithm for a restricted discrete approximation problem in the $L_{1}$ norm, SIAM J. Numer. Anal. 14 (1977), no. 3, 555–565. MR 438660, DOI 10.1137/0714034
I. Barrodale and F. D. K. Roberts, An improved algorithm for discrete $l_{1}$ linear approximation, SIAM J. Numer. Anal. 10 (1973), 839–848. MR 339449, DOI 10.1137/0710069
A. Charnes, Optimality and degeneracy in linear programming, Econometrica 20 (1952), 160–170. MR 56264, DOI 10.2307/1907845
A. Charnes and W. W. Cooper, Management models and industrial applications of linear programming, John Wiley & Sons, Inc., New York-London, 1961. MR 0157773
A. Charnes and W. W. Cooper, Optimal estimation of executive compensation by linear programming, Management Sci. 1 (1955), 138–151. MR 73914, DOI 10.1287/mnsc.1.2.138

Comm. Statist.

G. Hadley, Linear programming, Addison-Wesley Series in Industrial Management, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1962. MR 0135622
Otto J. Karst, Linear curve fitting using least deviations, J. Amer. Statist. Assoc. 53 (1958), 118–132. MR 134453, DOI 10.1080/01621459.1958.10501430
G. F. McCormick and V. A. Sposito, Using the $L_{2}$-estimator in $L_{1}$-estimation, SIAM J. Numer. Anal. 13 (1976), no. 3, 337–343. MR 448808, DOI 10.1137/0713030
Michel Simonnard, Linear programming, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1966. Translated from the French by William S. Jewell. MR 0201195
Harvey M. Wagner, The dual simplex algorithm for bounded variables, Naval Res. Logist. Quart. 5 (1958), 257–261. MR 101168, DOI 10.1002/nav.3800050306
Harvey M. Wagner, Linear programming techniques for regression analysis, J. Amer. Statist. Assoc. 54 (1959), 206–212. MR 130753, DOI 10.1080/01621459.1959.10501506