On stable least squares solution to the system of linear inequalities
Evald Übi
Open Mathematics, Tome 5 (2007), p. 373-385 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2007-01-01
EUDML-ID : urn:eudml:doc:269489 
@article{bwmeta1.element.doi-10_2478_s11533-007-0003-7,
     author = {Evald \"Ubi},
     title = {On stable least squares solution to the system of linear inequalities},
     journal = {Open Mathematics},
     volume = {5},
     year = {2007},
     pages = {373-385},
     zbl = {1191.90027},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-007-0003-7}
}

Evald Übi. On stable least squares solution to the system of linear inequalities. Open Mathematics, Tome 5 (2007) pp. 373-385. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-007-0003-7/

[1] C. Lawson and R. Hanson: Solving Least Squares Problems, Prentice-Hall, New-Jersey, 1974. | Zbl 0860.65028

[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 | Zbl 1108.90028

[3] Fan Ky: “On Systems of Linear Inequalities”, In: H. Kuhn and W. Tucker (Eds.): Linear Inequalities and Related Systems, Priceton, 1956.

[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] C. Papadimitriou and K. Steiglitz: Combinatorial Optimization:Algorithms and Complexity, Prentice-Hall, New-Jersey, 1982. | Zbl 0503.90060

[6] L. Khachiyan: “A Polynomial Algorihm in linear programming”, Soviet Mathematics Doklady, Vol. 20, (1979), pp. 191–194.

[7] L. Khachiyan: “Fourier-Motzkin Elimination Method”, Encyklopedia of Optimization, Vol. 2, (2001), pp. 155–159.

[8] G. Danzig: Linear Programming and Extensions, Princeton University Press, 1963.

[9] S. Chernikov: Lineare Ungleichungen, Deutscher Verlag der Wissenschaften, Berlin, 1971.

[10] D. Gale: The Theory of Linear Economic Models, McGgraw-HILL Book Company, 1960. | Zbl 0114.12203

[11] A. Björck: “Generalized and Sparse Least Squares Problems”, NATO ASI Series C, Vol. 434, (1994), pp. 37–80. | Zbl 0828.90100

[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 | Zbl 0483.65027

[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. | Zbl 0142.16804