The least-squares method is used to obtain a stable algorithm for a system of linear inequalities as well as linear and nonlinear programming. For these problems the solution with minimal norm for a system of linear inequalities is found by solving the non-negative least-squares (NNLS) problem. Approximate and exact solutions of these problems are discussed. Attention is mainly paid to finding the initial solution to an LP problem. For this purpose an NNLS problem is formulated, enabling finding the initial solution to the primal or dual problem, which may turn out to be optimal. The presented methods are primarily suitable for ill-conditioned and degenerate problems, as well as for LP problems for which the initial solution is not known. The algorithms are illustrated using some test problems.
@article{bwmeta1.element.doi-10_2478_s11533-010-0049-9,
author = {Evald \"Ubi},
title = {Mathematical programming via the least-squares method},
journal = {Open Mathematics},
volume = {8},
year = {2010},
pages = {795-806},
zbl = {1203.90111},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-010-0049-9}
}
Evald Übi. Mathematical programming via the least-squares method. Open Mathematics, Tome 8 (2010) pp. 795-806. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-010-0049-9/
[1] Barnes E., Chen V., Gopalakrishnan B., Johnson E.L., A least-squares primal-dual algorithm for solving linear programming problems, Oper. Res. Lett., 2002, 30(5), 289–294 http://dx.doi.org/10.1016/S0167-6377(02)00163-3[Crossref] | Zbl 1010.90044
[2] Bixby R.E., Implementing the simplex method: The initial basis, ORSA J. Comput., 1992, 4(3), 267–284 | Zbl 0759.90063
[3] Dantzig G.B., Orden A., Wolfe P., The generalized simplex method for minimizing a linear form under linear inequality restraints, Pacific J. Math., 1955, 5, 183–195 | Zbl 0064.39402
[4] Gale D., How to solve linear inequalities, Amer. Math. Monthly, 1969, 76(6), 589–599 http://dx.doi.org/10.2307/2316658[Crossref] | Zbl 0205.04604
[5] Gill P.E., Murray W., Wright M.H., Practical Optimization, Academic Press, London, 1981 | Zbl 0503.90062
[6] Lawson C.L., Hanson R.J., Solving Least Squares Problems, Classics in Applied Mathematics, 15, SIAM, Philadelphia, 1995 | Zbl 0860.65029
[7] Leichner S.A., Dantzig G. B., Davis J.W., A strictly improving linear programming Phase I algorithm, Ann. Oper. Res., 1993, 46–47(2), 409–430 http://dx.doi.org/10.1007/BF02023107[Crossref] | Zbl 0785.90068
[8] Netlib LP Test Problem Set, available at www.numerical.rl.ac.uk/cute/netlib.html
[9] Kong S., Linear Programming Algorithms Using Least-Squares Method, Ph.D. thesis, Georgia Institute of Technology, Atlanta, USA, 2007
[10] Übi E., Least squares method in mathematical programming, Proc. Estonian Acad. Sci. Phys. Math., 1989, 38(4), 423–432, (in Russian)
[11] Übi E., An approximate solution to linear and quadratic programming problems by the method of least squares, Proc. Estonian Acad. Sci. Phys. Math., 1998, 47(4), 19–28 | Zbl 0969.90065
[12] Übi E., On computing a stable least squares solution to the linear programming problem, Proc. Estonian Acad. Sci. Phys. Math., 1998, 47(4), 251–259 | Zbl 1058.90513
[13] Übi E., Application of orthogonal transformations in the revised simplex method, Proc. Estonian Acad. Sci. Phys. Math., 2001, 50(1), 34–41 | Zbl 0994.90098
[14] Übi E., On stable least squares solution to the system of linear inequalities, Cent. Eur. J. Math., 2007, 5(2), 373–385 http://dx.doi.org/10.2478/s11533-007-0003-7[WoS][Crossref] | Zbl 1191.90027
[15] Übi E., A numerically stable least squares solution to the quadratic programming problem, Cent. Eur. J. Math., 2008, 6(1), 171–178 http://dx.doi.org/10.2478/s11533-008-0012-1[Crossref][WoS] | Zbl 1146.90044
[16] Zoutendijk G., Mathematical Programming Methods, North Holland, Amsterdam-New York-Oxford, 1976