Mathematical programming via the least-squares method

Evald Übi

Open Mathematics (2010)

  • Volume: 8, Issue: 4, page 795-806
  • ISSN: 2391-5455

Abstract

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

How to cite

top

Evald Übi. "Mathematical programming via the least-squares method." Open Mathematics 8.4 (2010): 795-806. <http://eudml.org/doc/269070>.

@article{EvaldÜbi2010,
abstract = {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.},
author = {Evald Übi},
journal = {Open Mathematics},
keywords = {Non-negative least-squares solution; System of linear inequalities; Initial solution for linear programming problem; Householder transformation; non-negative least-squares solution; system of linear inequalities; initial solution for linear programming problem},
language = {eng},
number = {4},
pages = {795-806},
title = {Mathematical programming via the least-squares method},
url = {http://eudml.org/doc/269070},
volume = {8},
year = {2010},
}

TY - JOUR
AU - Evald Übi
TI - Mathematical programming via the least-squares method
JO - Open Mathematics
PY - 2010
VL - 8
IS - 4
SP - 795
EP - 806
AB - 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.
LA - eng
KW - Non-negative least-squares solution; System of linear inequalities; Initial solution for linear programming problem; Householder transformation; non-negative least-squares solution; system of linear inequalities; initial solution for linear programming problem
UR - http://eudml.org/doc/269070
ER -

References

top
  1. [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] Zbl1010.90044
  2. [2] Bixby R.E., Implementing the simplex method: The initial basis, ORSA J. Comput., 1992, 4(3), 267–284 Zbl0759.90063
  3. [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 Zbl0064.39402
  4. [4] Gale D., How to solve linear inequalities, Amer. Math. Monthly, 1969, 76(6), 589–599 http://dx.doi.org/10.2307/2316658[Crossref] Zbl0205.04604
  5. [5] Gill P.E., Murray W., Wright M.H., Practical Optimization, Academic Press, London, 1981 Zbl0503.90062
  6. [6] Lawson C.L., Hanson R.J., Solving Least Squares Problems, Classics in Applied Mathematics, 15, SIAM, Philadelphia, 1995 Zbl0860.65029
  7. [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] Zbl0785.90068
  8. [8] Netlib LP Test Problem Set, available at www.numerical.rl.ac.uk/cute/netlib.html 
  9. [9] Kong S., Linear Programming Algorithms Using Least-Squares Method, Ph.D. thesis, Georgia Institute of Technology, Atlanta, USA, 2007 
  10. [10] Übi E., Least squares method in mathematical programming, Proc. Estonian Acad. Sci. Phys. Math., 1989, 38(4), 423–432, (in Russian) 
  11. [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 Zbl0969.90065
  12. [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 Zbl1058.90513
  13. [13] Übi E., Application of orthogonal transformations in the revised simplex method, Proc. Estonian Acad. Sci. Phys. Math., 2001, 50(1), 34–41 Zbl0994.90098
  14. [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] Zbl1191.90027
  15. [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] Zbl1146.90044
  16. [16] Zoutendijk G., Mathematical Programming Methods, North Holland, Amsterdam-New York-Oxford, 1976 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.