Local minima of the trust region problem. (English) Zbl 0797.90096

Lyle, S.; Szularz, M.

J. Optimization Theory Appl. 80, No. 1, 117-134 (1994).

Summary: We consider the minimization of a quadratic form \(z' Vz+ 2z' q\) subject to the two-norm constraint \(\| z\|=\alpha\). The problem received considerable attention in the literature, notably due to its applications to a class of trust region methods in nonlinear optimization. While the previous studies were concerned with just the global minimum of the problem, we investigate the existence of all local minima. The problem is approached via the dual Lagrangian, and the necessary and sufficient conditions for the existence of all local minima are derived. We also examine the suitability of the conventional numerical techniques used to solve the problem to a class of single-instruction multiple-data computers known as processor arrays (in our case, AMT DAP 610). Simultaneously, we introduce certain hardware-oriented multisection algorithms, showing their efficiency in the case of small to medium size problems.

MSC:

90C30

Nonlinear programming

Keywords:

multisection algorithms; norm constraint; trust region methods

References:

[1]	Forsythe, G. E., andGolub, G. H.,On the Stationary Values of a Second Degree Polynomial on the Unit Sphere, SIAM Journal on Applied Mathematics, Vol. 13, pp. 1050–1068, 1965. · Zbl 0168.03005
[2]	Gander, W., Golub, G. H., andVon Matt, U.,A Constrained Eigenvalue Problem, Linear Algebra and Its Applications, Vols. 114–115, pp 815–839, 1989. · Zbl 0666.15006
[3]	Gay, D. M.,Computing Optimal Locally Constrained Steps, SIAM Journal on Scientific Statistics and Computing, Vol. 2, pp. 186–197, 1981. · Zbl 0467.65027
[4]	Moré, J. J., andSorensen, D. C.,Computing a Trust Region Step, SIAM Journal on Scientific Statistics and Computing, Vol. 4, pp. 553–572, 1983. · Zbl 0551.65042
[5]	Spjötvoll, E.,A Note on a Theorem of Forsythe and Golub, SIAM Journal on Applied Mathematics, Vol. 23, No. 3, pp. 307–311, 1972. · Zbl 0259.15019
[6]	Lyle, S., andSzularz, M.,A Minimum of the Ratio of Two Quadratic Forms Subject to Linear Inequality Constraints, Proceedings of the 2nd International Conference on Industrial and Applied Mathematics, Washington, DC, p. 131, 1991.
[7]	Szularz, M.,Quadratic Programming with Constant Norm with Parallel Applications, PhD Thesis, Kingston Polytechnic, Kingston, Surrey, Englad 1991.
[8]	Reinsch, C. H.,Smoothing by Spline Functions, II, Numerische Matematik, Vol. 16, pp. 451–454, 1971. · Zbl 1248.65020
[9]	Hockney, R. W., andJesshope, C. R.,Parallel Computers, Adam Hilger, Bristol, England, 1986.
[10]	Active Memory Technology,AMT DAP Series: Technical Overview, Reading, England, 1989.
[11]	Gill, P. E., Murray, W., andWright, M. H.,Practical Optimization, Academic Press, London, England, 1982. · Zbl 0503.90062
[12]	Wilkinson, J. H.,The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, England, 1965. · Zbl 0258.65037
[13]	Dongarra, J. J., andSorensen, D. C.,A Fully Parallel Algorithm for the Symmetric Eigenvalue Problem, SIAM Journal on Scientific Statistics and Computing, Vol. 8, pp. 338–342, 1987.
[14]	Freeman, T. L.,Polynomial Root-Finding on a Distributed Memory Parallel Computer, Proceedings of the 3rd SIAM Conference on Optimization, Boston, Massachusetts, p. 22, 1989. · Zbl 0691.65028