The Use of<i>QR</i>Factorization in Sparse Quadratic Programming and Backward Error Issues (Q4943662)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1416888
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The Use of<i>QR</i>Factorization in Sparse Quadratic Programming and Backward Error Issues |
scientific article; zbMATH DE number 1416888 |
Statements
The Use of<i>QR</i>Factorization in Sparse Quadratic Programming and Backward Error Issues (English)
0 references
19 March 2000
0 references
QR factorization
0 references
sparse quadratic programming
0 references
augmented systems
0 references
orthogonal factorization
0 references
roundoff error propagation
0 references
backward stability
0 references
null space algorithm
0 references
numerical experiments
0 references
0.8886247277259827
0 references
0.7769070267677307
0 references
0.7568378448486328
0 references
The paper deals with a null space method for solving quadratic programming problem with equality constraints: \[ \text{Min}\{\textstyle{{1\over 2}} x^T Mx+ q^Tx\mid A^Tx= b\},\tag{1} \] where \(M\in \mathbb{R}^{n\times n}\) is a symmetric and positive semidefinite matrix, \(A\in \mathbb{R}^{n\times m}\), \(m\leq n\), is a real full rank matrix, \(q\in \mathbb{R}^n\) and \(b\in\mathbb{R}^m\). Introducing the vector \(u\in \mathbb{R}^m\) of the Lagrangian parameters the problem (1) is equivalent to the augmented system: \[ \left[\begin{matrix} M & A\\ A^T & 0\end{matrix}\right]\left[\begin{matrix} x\\ u\end{matrix}\right]= \left[\begin{matrix} -q\\ b\end{matrix}\right]. \] The null space method presented in this paper combines the use of a direct QR factorization of the constraints with an iterative solver on the corresponding null space. The roundoff error propagation is analyzed and upper bounds for the error affecting the computed solutions are given. By numerical tests the backward stability of the null space algorithm for solving augmented systems is proved. Moreover, the numerical experiments give evidence of the good applicability of the method in the sparse case.
0 references