Linear inequalities via least squares; pp. 238–248Full article in PDF format | doi: 10.3176/proc.2013.4.04
The Gaussian elimination method is usually used in solving problems related to systems of linear inequalities. The present review paper describes the application of the least-squares method to studying problems connected with linear inequalities (like redundant inequalities, theorems of alternative, mathematical programming). The minimum norm solution to the system of linear inequalities is found by solving a non-negative least-squares (NNLS) problem. A linear programming (LP) problem is transformed to the system of inequalities in several ways. By solving the corresponding NNLS problem an initial solution to the LP problem is found. The main ideas are explained by simple examples.
Bazaraa, M. S., Jarvis, J. J., and Sherali, H. D. 2005. Linear Programming and Network Flows. John Wiley and Sons, New Jersey.
Björck, A. 1996. Numerical Methods for Least-Squares Problems. SIAM, Linköping.
Bland, R., Goldfarb, D., and Todd, M. 1981. The ellipsoid method. A survey. Oper. Res., 29, 1039–1091.
Censor, Y. and Zenias, S. A. 1997. Parallel Optimization Theory, Algorithms and Applications. Oxford University Press.
Cheng, M. C. 1987. General criteria for redundant and nonredundant linear inequalities. J. Optim. Theory Appl., 1, 37–42.
Chernikov, S. 1971. Lineare Ungleichungen. Deutscher Verlag der Wissenschaften, Berlin.
Dantzig, G. and Thapa, M. 2003. Linear Programming 2: Theory and Extensions. Springer, New York.
Dantzig, G., Orden, A., and Wolfe, P. 1955. Generalized simplex method for minimizing a linear form under linear inequality restraints. Pacif. J. Math., 5, 183–195.
Farkas, J. Über die Theorie der einfachen Ungleichungen. J. Reine Angew. Math., 124, 1902, 1–24.
Gale, D. 1969. How to solve linear inequalities? Amer. Math. Monthly, 6, 589–599.
Harris, P. 1975. Pivot selection methods of the DEVEX LP Code. Math. Prog. Study, 4, 30–57.
Hildreth, C. G. 1957. A quadratic programming procedure. Nav. Res. Logist. Qu., 4, 37–43.
Hu, T. C. 1970. Integer Programming and Network Flows. Addison-Wesley Publishing Company, Massachusetts.
Khachiyan, L. G. 1980. A polynomial algorithm in linear programming. Soviet Math. Dok., 20, 191–194.
Kong, S. 2007. Programming Algorithms Using Least-Squares Method. PhD thesis, Georgia Institute of Technology.
Kuhn, H. and Tucker, W. (eds). 1956. Linear Inequalities and Related Systems. Princeton University Press.
Lawson, C. L. and Hanson, R. J. 1995. Solving Least Squares Problems. SIAM, Philadelphia.
Leichner, S., Dantzig, G., and Davis, J. 1993. Strictly improving linear programming phase I algorithm. An. Oper. Res., 47, 409–430.
Lent, A. and Censor, Y. 1980. Extensions of Hildreth’s row-action method for quadratic programming. SIAM J. Control Optim., 18, 444–454.
Papadimitriou, C. H. and Steiglitz, K. 1982. Combinatorial Optimization, Algorithms and Complexity. Prentice-Hall, New-Jersey.
Telgen, J. 1981. Redundancy and Linear Programs. Mathematical Center, Amsterdam.
Übi, E. 1989. Least-squares method in mathematical programming. Proc. Estonian Acad. Sci., 4, 423–432.
Übi, E. 2005. Exact and stable least-squares solution to the linear programming problem. Cent. Eur. J. Math., 3, 228–241.
Übi, E. 2007. On stable least-squares solution to the system of linear inequalities. Cent. Eur. J. Math., 5, 373–385.
Übi, E. 2008. A numerically stable least-squares solution to the quadratic programming problem. Cent. Eur. J. Math., 6, 171–178.Übi, E. 2010. Mathematical programming via the least-squares method. Cent. Eur. J. Math., 8, 795–806.
Back to Issue