A numerically stable least squares solution to the quadratic programming problem
E. Übi
Open Mathematics, Tome 6 (2008), p. 171-178 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

The strictly convex quadratic programming problem is transformed to the least distance problem - finding the solution of minimum norm to the system of linear inequalities. This problem is equivalent to the linear least squares problem on the positive orthant. It is solved using orthogonal transformations, which are memorized as products. Like in the revised simplex method, an auxiliary matrix is used for computations. Compared to the modified-simplex type methods, the presented dual algorithm QPLS requires less storage and solves ill-conditioned problems more precisely. The algorithm is illustrated by some difficult problems.

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:269266 
@article{bwmeta1.element.doi-10_2478_s11533-008-0012-1,
     author = {E. \"Ubi},
     title = {A numerically stable least squares solution to the quadratic programming problem},
     journal = {Open Mathematics},
     volume = {6},
     year = {2008},
     pages = {171-178},
     zbl = {1146.90044},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-008-0012-1}
}

E. Übi. A numerically stable least squares solution to the quadratic programming problem. Open Mathematics, Tome 6 (2008) pp. 171-178. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-008-0012-1/

[1] Goldfarb D., Idnani A., A Numerically stable dual method for solving strictly convex quadratic programs, Math. Programming, 1983, 27, 1–33 http://dx.doi.org/10.1007/BF02591962 | Zbl 0537.90081

[2] Künzi H.P., Krelle W., Nichtlineare Programmirung, Springer, Berlin, 1962 (in German)

[3] Lawson C.L., Hanson R.J., Solving least squares problems, Prentice-Hall, New-Jersey, 1974 | Zbl 0860.65028

[4] Lent A., Censor Y., Extensions of Hildreth’s row action method for quadratic programming, SIAM J. Control Optim., 1980, 18, 444–454 http://dx.doi.org/10.1137/0318033 | Zbl 0444.49025

[5] Powell M.J.D., On the quadratic programming algorithm of Goldfarb and Idnani, Math. Programming Stud., 1985, 25, 46–61 | Zbl 0584.90069

[6] Übi E., On stable least squares solution to the system of linear inequalities, Cent. Eur. J. Math., 2007, 5, 373–385 http://dx.doi.org/10.2478/s11533-007-0003-7 | Zbl 1191.90027

[7] Übi E., Exact and stable least squares solution to the linear programming problem, Cent. Eur. J. Math., 2005, 3, 228–241 http://dx.doi.org/10.2478/BF02479198 | Zbl 1108.90028