Mathematical programming via the least-squares method

• Autorzy: Evald Übi
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Non-negative least-squares solution; System of linear inequalities; Initial solution for linear programming problem; Householder transformation

Kategorie tematyczne

• 65K05: Mathematical programming methods
• 90C05: Linear programming

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2010
• Tom: 8
• Numer: 4
• Strony: 795-806

Daty

wydano

2010-08-01

online

2010-07-24

Twórcy

autor

Evald Übi

• School of Economics and Business Administration, Tallinn University of Technology, Tallinn, Estonia

Bibliografia

• [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]
• [2] Bixby R.E., Implementing the simplex method: The initial basis, ORSA J. Comput., 1992, 4(3), 267–284
• [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
• [4] Gale D., How to solve linear inequalities, Amer. Math. Monthly, 1969, 76(6), 589–599 http://dx.doi.org/10.2307/2316658[Crossref]
• [5] Gill P.E., Murray W., Wright M.H., Practical Optimization, Academic Press, London, 1981
• [6] Lawson C.L., Hanson R.J., Solving Least Squares Problems, Classics in Applied Mathematics, 15, SIAM, Philadelphia, 1995
• [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]
• [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
• [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
• [13] Übi E., Application of orthogonal transformations in the revised simplex method, Proc. Estonian Acad. Sci. Phys. Math., 2001, 50(1), 34–41
• [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]
• [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]
• [16] Zoutendijk G., Mathematical Programming Methods, North Holland, Amsterdam-New York-Oxford, 1976

Identyfikatory

DOI

10.2478/s11533-010-0049-9