×

Continuity of the null space basis and constrained optimization. (English) Zbl 0598.90072

Authors’ summary: ”Many constrained optimization algorithms use a basis for the null space of the matrix of constraint gradients. Recently, methods have been proposed that enable this null space basis to vary continuously as a function of the iterates in a neighborhood of the solutions. This paper reports results from topology showing that, in general, there is no continuous function that generates the null space basis of all full rank rectangular matrices of a fixed size. Thus constrained optimization algorithms cannot assume an everywhere continuous null space basis. The authors give some indication of where these discontinuities must occur and then propose an alternative implementation of a class of constrained optimization algorithms that uses approximations to the reduced Hessian of the Lagrangian but is independent of the choice of the null space basis. This approach obviates the need for a continuously varying null space basis.”
Reviewer: M.Rijckaert

MSC:

90C30 Nonlinear programming
49M37 Numerical methods based on nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] J.F. Adams, ”Vector fields on spheres”,Annals of Mathematics 75 (1962) 603–632. · Zbl 0112.38102
[2] T.F. Coleman and A.R. Conn, ”On the local convergence of a quasi-Newton method for a nonlinear programming problem”,SIAM Journal on Numerical Analysis 21 (1984) 755–769. · Zbl 0566.65046
[3] T.F. Coleman and D.C. Sorensen, ”A note on the computation of an orthonormal basis for the null space of a matrix”,Mathematical Programming 29 (1984) 234–242. · Zbl 0539.65020
[4] B. Eckmann, ”Stetige Lösungen linearer Gleichungssysteme”,Commentarii Mathematici Helvetici 15 (1942) 318–339. · Zbl 0028.32001
[5] P.E. Gill, W. Murray, M.A. Saunders, G.W. Stewart and M.H. Wright, ”Properties of a representation of a basis for the null space”,Mathematical Programming 33 (1985) 172–186. · Zbl 0579.65035
[6] P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, ”On the representation of a basis for the null space”, Report SOL 83-19, Stanford University (Stanford, California, 1983).
[7] J. Goodman, ”Newton’s Method for Constrained Optimization”,Mathematical Programming 33 (1985) 162–171. · Zbl 0589.90065
[8] P.J. Hilton and S. Wylie,Homology theory (Cambridge University Press, Cambridge, 1962). · Zbl 0091.36306
[9] G.P. McCormick, ”Locating an isolated global minimizer of a constrained nonconvex program”,Mathematics of Operations Research 5 (1980) 435–443. · Zbl 0442.90080
[10] J. Nocedal and M. Overton, ”Projected Hessian updating algorithms for nonlinearly constrained optimization”,SIAM Journal on Numerical Analysis 22 (1985) 821–850. · Zbl 0593.65043
[11] T. Wajewski, ”Sur les matrices dont les éléments sont des fonctions continués,Compositio Mathematica 2 (1935) 63–68.
[12] G.W. Whitehead, ”Note on cross-sections in Stiefel manifolds”,Commentarii Mathematici Helvetici 37 (1963) 239–240. · Zbl 0118.18702
[13] R.S. Womersley and R. Fletcher, ”An algorithm for composite nonsmooth optimization problems”, Department of Mathematics Report NA/60, University of Dundee (Dundee, 1982). · Zbl 0562.90077
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.