×

A note on the computation of an orthonormal basis for the null space of a matrix. (English) Zbl 0539.65020

In certain nonlinearly constrained optimization problems the availability of continuously varying orthonormal bases Z(x) for the null spaces of given continuously varying matrices \(A(x)^ T\) is required. It is shown that in general the standard implementation of the Householder QR- factorization of A(x) does not yield such continuous dependance. The problem of continuity of the QR-factorization is treated in detail and three possible alternations of the standard process are described which can overcome the difficulties. It may be pointed out that the Givens QR- factorization which is mentioned at the end does not have the disadvantage of requiring twice as many operations if employed in factored form (fast Givens rotations).
Reviewer: W.Bunse

MSC:

65F25 Orthogonalization in numerical linear algebra
15A23 Factorization of matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.H. Bartels and A.R. Conn, ”An approach to nonlinearl 1 data fitting”, Numerical Analysis Proceedings, 3rd IIMAS Workshop (Cocoyoc, Mexico, 1982). · Zbl 0477.65012
[2] T.F. Coleman and A.R. Conn, ”Nonlinear programming via an exact penalty function: Asymptotic analysis”,Mathematial Programming 24 (1982a) 123–136. · Zbl 0501.90078
[3] T.F. Coleman and A.R. Conn, ”On the local convergence of a quasi-Newton method for the nonlinear programming problem,” Technical Report 82-509, Department of Computer Science, Cornell University, Ithaca, NY, 1982b). · Zbl 0501.90077
[4] J.A. George and M.T. Health, ”Solution of sparse linear least squares problems using Givens rotations”,Linear Algebra and Its Applications 34 (1980) 69–83. · Zbl 0459.65025
[5] P. Gill and W. Murray,Numerical methods for constrained optimization (Academic Press, London, 1974). · Zbl 0297.90082
[6] P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, ”On computing the null space in nonlinear optimization algorithms”, Technical Report SOL 83-19, Department of Operations Research, Stanford University (1983).
[7] L. Kaufman, ”A variable projection method for solving separable nonlinear least squares problems”,BIT 15 (1975) 49–57. · Zbl 0307.65019
[8] W. Murray and M. Overton, ”A projected Lagrangian algorithm for nonlinear minimax optimization”,SIAM Journal of Scientific and Statistical Computing 1 (1980) 345–370. · Zbl 0461.65052
[9] W. Murray and M. Wright, ”Projected Lagrangian methods based on the trajectories of penalty and barrier functions”, Technical Report 72-8. Stanford Optimization Laboratory (Stanford, CA, 1978).
[10] B.N. Parlett, ”Analysis of algorithms for reflections in bisectors”,SIAM Review 13 (1971) 197–208. · Zbl 0217.52606
[11] B.N. Parlett,The symmetric eigenvalue problem (Prentice-Hall, Englewood Cliffs, NJ, 1980). · Zbl 0431.65017
[12] K. Tanabe, ”Feasibility-improving gradient-acute-projection methods: a unified approach to nonlinear programming”,Lecture Notes in Numerical and Applied Analysis 3 (1981) 57–76. · Zbl 0507.65024
[13] M. Wright, ”Algorithms for nonlinearly constrained optimization” Technical Report 79-24, Stanford Optimization Laboratory (Stanford, CA, 1979).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.