On stable least squares solution to the system of linear inequalities

Evald Übi

Open Mathematics (2007)

  • Volume: 5, Issue: 2, page 373-385
  • ISSN: 2391-5455

Abstract

top
The system of inequalities is transformed to the least squares problem on the positive ortant. This problem is solved using orthogonal transformations which are memorized as products. Author’s previous paper presented a method where at each step all the coefficients of the system were transformed. This paper describes a method applicable also to large matrices. Like in revised simplex method, in this method an auxiliary matrix is used for the computations. The algorithm is suitable for unstable and degenerate problems primarily.

How to cite

top

Evald Übi. "On stable least squares solution to the system of linear inequalities." Open Mathematics 5.2 (2007): 373-385. <http://eudml.org/doc/269489>.

@article{EvaldÜbi2007,
abstract = {The system of inequalities is transformed to the least squares problem on the positive ortant. This problem is solved using orthogonal transformations which are memorized as products. Author’s previous paper presented a method where at each step all the coefficients of the system were transformed. This paper describes a method applicable also to large matrices. Like in revised simplex method, in this method an auxiliary matrix is used for the computations. The algorithm is suitable for unstable and degenerate problems primarily.},
author = {Evald Übi},
journal = {Open Mathematics},
keywords = {System of linear inequalities; method of least squares; Householder transformation; successive projection},
language = {eng},
number = {2},
pages = {373-385},
title = {On stable least squares solution to the system of linear inequalities},
url = {http://eudml.org/doc/269489},
volume = {5},
year = {2007},
}

TY - JOUR
AU - Evald Übi
TI - On stable least squares solution to the system of linear inequalities
JO - Open Mathematics
PY - 2007
VL - 5
IS - 2
SP - 373
EP - 385
AB - The system of inequalities is transformed to the least squares problem on the positive ortant. This problem is solved using orthogonal transformations which are memorized as products. Author’s previous paper presented a method where at each step all the coefficients of the system were transformed. This paper describes a method applicable also to large matrices. Like in revised simplex method, in this method an auxiliary matrix is used for the computations. The algorithm is suitable for unstable and degenerate problems primarily.
LA - eng
KW - System of linear inequalities; method of least squares; Householder transformation; successive projection
UR - http://eudml.org/doc/269489
ER -

References

top
  1. [1] C. Lawson and R. Hanson: Solving Least Squares Problems, Prentice-Hall, New-Jersey, 1974. Zbl0860.65028
  2. [2] E. Übi: “Exact and Stable Least Squares Solution to the Linear Programming Problem”, Centr. Eur. J. Math., Vol. 3(2), (2005), pp. 228–241. http://dx.doi.org/10.2478/BF02479198 Zbl1108.90028
  3. [3] Fan Ky: “On Systems of Linear Inequalities”, In: H. Kuhn and W. Tucker (Eds.): Linear Inequalities and Related Systems, Priceton, 1956. 
  4. [4] E. Übi: “Finding Non-negative Solution of Overdetermined or Underdetermined System of Linear Equations by Method of Least Squares”, Transactions of Tallinn TU, Vol. 738, (1994), pp. 61–68. 
  5. [5] C. Papadimitriou and K. Steiglitz: Combinatorial Optimization:Algorithms and Complexity, Prentice-Hall, New-Jersey, 1982. Zbl0503.90060
  6. [6] L. Khachiyan: “A Polynomial Algorihm in linear programming”, Soviet Mathematics Doklady, Vol. 20, (1979), pp. 191–194. 
  7. [7] L. Khachiyan: “Fourier-Motzkin Elimination Method”, Encyklopedia of Optimization, Vol. 2, (2001), pp. 155–159. 
  8. [8] G. Danzig: Linear Programming and Extensions, Princeton University Press, 1963. 
  9. [9] S. Chernikov: Lineare Ungleichungen, Deutscher Verlag der Wissenschaften, Berlin, 1971. 
  10. [10] D. Gale: The Theory of Linear Economic Models, McGgraw-HILL Book Company, 1960. Zbl0114.12203
  11. [11] A. Björck: “Generalized and Sparse Least Squares Problems”, NATO ASI Series C, Vol. 434, (1994), pp. 37–80. Zbl0828.90100
  12. [12] M. Hath: “Some Extensions of an algorithm for Sparse Linear Least Squares Problems”, SIAM J.Sci. Statist. Comput., Vol. 3, (1982), pp. 223–237. http://dx.doi.org/10.1137/0903014 Zbl0483.65027
  13. [13] L. Bregman: “The Method of Successive Projecton for Finding The Common Point of Convex Set”, Soviet. Math. Dokl., Vol. 6, (1969), pp. 688–692. Zbl0142.16804

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.