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

      Identifiers