×

zbMATH — the first resource for mathematics

Approximate solution of the trust region problem by minimization over two-dimensional subspaces. (English) Zbl 0652.90082
The following problem is considered: \(\min \{g^ Td+(1/2)d^ TBd\); \(\| d\| \leq \Delta \}\), where \(g\in R^ n\), \(B\in R^{n\times n}\) is symmetric, and \(\Delta >0\). Problems of this type arise in trust region algorithms for unconstrained optimization. In a previous paper [SIAM J. Numer. Anal. 22, 47-67 (1985; Zbl 0574.65061)] the authors introduced an approximate solution technique for this problem that involves the solution of a two-dimensional trust region problem. The present paper reports computational results and its main purpose is to show perhaps surprising computational evidence that minimization over a subspace spanned by two reasonably chosen directions gives in many cases the value obtained in exact minimization over \(R^ n\).
Reviewer: W.Kotarski

MSC:
90C25 Convex programming
65K05 Numerical mathematical programming methods
90C55 Methods of successive quadratic programming type
Software:
GQTPAR; minpack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M.R. Celis, J.E. Dennis and R.A. Tapia, ”A trust region strategy for nonlinear equality constrained optimization,” in: P.T. Boggs, R.H. Byrd and R.B. Schnabel, eds.,Numerical Optimization 1984 (SIAM, Philadelphia, 1984) pp. 71–82. · Zbl 0566.65048
[2] J.E. Dennis, Jr. and H.H.W. Mei, ”Two new unconstrained optimization algorithms which use function and gradient values,”Journal of Optimization Theory and its Applications 28 (1979) 453–482. · Zbl 0388.65022
[3] D.M. Gay, ”Computing optimal locally constrained steps,”SIAM Journal on Scientific and Statistical Computing 2 (1981) 186–197. · Zbl 0467.65027
[4] M.D. Hebden, ”An algorithm for minimization using exact second derivatives,” Rept. TP515, A.E.R.E. (Harwell, England, 1973).
[5] J.J. Moré, ”The Levenberg-Marquardt algorithm: implementation and theory,” in: G.A. Watson, ed.,Numerical Analysis Dundee 1977, Lecture Notes in Mathematics 630 (Springer-Verlag, Berlin, 1977) pp. 105–116.
[6] J.J. Moré, B.S. Garbow and K.E. Hillstrom, ”Testing unconstrained optimization software,”ACM Transactions on Mathematical Software 7 (1981) 17–41. · Zbl 0454.65049
[7] J.J. Moré and D.C. Sorensen, ”Computing a trust region step,”SIAM Journal on Scientific and Statistical Computing 4 (1983) 553–572. · Zbl 0551.65042
[8] B.N. Parlett,The Symmetric Eigenvalue Problem (Prentice-Hall, Englewood Cliffs, NJ, 1980). · Zbl 0431.65017
[9] M.J.D. Powell, ”A new algorithm for unconstrained optimization,” in: J.B. Rosen, O. L. Mangasarian and K. Ritter, eds.,Nonlinear Programming (Academic Press, New York, 1970) pp. 31–65. · Zbl 0228.90043
[10] R.B. Schnabel and P. Frank, ”Tensor methods for nonlinear equations,”SIAM Journal on Numerical Analysis 21 (1984) 815–843. · Zbl 0562.65029
[11] R.B. Schnabel and P. Frank, ”Solving systems of nonlinear equations by tensor methods,” Technical Report CU-CS-334-86, Department of Computer Science, University of Colorado at Boulder (Boulder, CO, 1986).
[12] R.B. Schnabel, B.E. Weiss and J.E. Koontz, ”A modular system of algorithms for unconstrained minimization,”ACM Transactions on Mathematical Software 11 (1985) 419–440. · Zbl 0591.65045
[13] L. Schrage, ”A more portable Fortran random number generator,”ACM Transactions on Mathematical Software 5 (1979) 132–138. · Zbl 0403.68041
[14] G. A. Shultz, R. B. Schnabel and R.H. Byrd, ”A family of trust-region-based algorithms for unconstrained minimization with strong global convergence properties”,SIAM Journal on Numerical Analysis 22 (1985) 47–67. · Zbl 0574.65061
[15] D.C. Sorensen, ”Newton’s method with a model trust region modification,”SIAM Journal on Numerical Analysis 19 (1982) 409–426. · Zbl 0483.65039
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.