A numerically stable least squares solution to the quadratic programming problem

E. Übi

Open Mathematics (2008)

  • Volume: 6, Issue: 1, page 171-178
  • ISSN: 2391-5455

Abstract

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

How to cite

top

E. Übi. "A numerically stable least squares solution to the quadratic programming problem." Open Mathematics 6.1 (2008): 171-178. <http://eudml.org/doc/269266>.

@article{E2008,
abstract = {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.},
author = {E. Übi},
journal = {Open Mathematics},
keywords = {Quadratic programming; system of linear inequalities; method of least squares; Householder transformation; successive projection},
language = {eng},
number = {1},
pages = {171-178},
title = {A numerically stable least squares solution to the quadratic programming problem},
url = {http://eudml.org/doc/269266},
volume = {6},
year = {2008},
}

TY - JOUR
AU - E. Übi
TI - A numerically stable least squares solution to the quadratic programming problem
JO - Open Mathematics
PY - 2008
VL - 6
IS - 1
SP - 171
EP - 178
AB - 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.
LA - eng
KW - Quadratic programming; system of linear inequalities; method of least squares; Householder transformation; successive projection
UR - http://eudml.org/doc/269266
ER -

References

top
  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 Zbl0537.90081
  2. [2] Künzi H.P., Krelle W., Nichtlineare Programmirung, Springer, Berlin, 1962 (in German) 
  3. [3] Lawson C.L., Hanson R.J., Solving least squares problems, Prentice-Hall, New-Jersey, 1974 Zbl0860.65028
  4. [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 Zbl0444.49025
  5. [5] Powell M.J.D., On the quadratic programming algorithm of Goldfarb and Idnani, Math. Programming Stud., 1985, 25, 46–61 Zbl0584.90069
  6. [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 Zbl1191.90027
  7. [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 Zbl1108.90028

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.