×
Martínez, José Mario; Santos, Sandra Augusta

A trust-region strategy for minimization on arbitrary domains. (English) Zbl 0835.90092

Math. Program. 68, No. 3 (A), 267-301 (1995).
Summary: We present a trust-region method for minimizing a general differentiable function restricted to an arbitrary closed set. We prove a global convergence theorem. The trust-region method defines difficult subproblems that are solvable in some particular cases. We analyze in detail the case where the domain is an Euclidean ball. For this case we present numerical experiments where we consider different Hessian approximations.

Cited in 19 Documents

MSC:

90C30 Nonlinear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Keywords:

differentiable function; global convergence; trust-region method

Software:

LANCELOT; GQTPAR; minpack
Cite Review PDF
Full Text: DOI

References:

[1] J.V. Burke, J.J. Moré and G. Toraldo, ”Convergence properties of trust-region methods for linear and convex constraints,”Mathematical Programming 47 (1990) 305–336. · Zbl 0711.90060 · doi:10.1007/BF01580867
[2] M.R. Celis, J.E. Dennis and R.A. Tapia, ”A trust-region strategy for nonlinear equality constrained optimization,” in: P.T. Boggs, R. Byrd and R. Schnabel, eds.,Numerical Optimization (SIAM, Philadelphia, 1984) pp. 71–82. · Zbl 0566.65048
[3] A.R. Conn, N.I.M. Gould and Ph.L. Toint, ”Global convergence of a class of trust-region algorithms for optimization with simple bounds,”SIAM Journal on Numerical Analysis 25 (1988) 433–460. See alsoSIAM Journal on Numerical Analysis 26 (1989) 764–767. · Zbl 0643.65031 · doi:10.1137/0725029
[4] A.R. Conn, N.I.M. Gould and Ph.L. Toint, ”Testing a class of methods for solving minimization problems with simple bounds on the variables,”Mathematics of Computation 50 (1988) 399–430. · Zbl 0645.65033 · doi:10.1090/S0025-5718-1988-0929544-3
[5] A.R. Conn, N.I.M. Gould and Ph.L. Toint, ”A comprehensive description of LANCELOT,” Hatfield Polytechnique Center, Technical Report, Hatfield (1990).
[6] A.R. Conn, N.I.M. Gould and Ph.L. Toint, ”A globally convergent augmented Lagrangean algorithm for optimization with general constraints and simple bounds,”SIAM Journal on Numerical Analysis 28 (1991) 545–572. · Zbl 0724.65067 · doi:10.1137/0728030
[7] M. Contreras and R.A. Tapia, ”Sizing the BFGS and DFP updates: a numerical study,” Technical Report 91-19, Department of Mathematical Sciences, Rice University, Houston, TX (1991). · Zbl 0796.90054
[8] J.H. Conway and N.J.C. Sloane,Sphere Packings, Lattices and Groups (Springer-Verlag, NY, 1988). · Zbl 0634.52002
[9] J.E. Dennis, J.M. Martínez, R.A. Tapia and K.A. Williamson, ”An algorithm based on a convenient trustregion subproblem for nonlinear programming,” Technical Report, Department of Mathematical Sciences, Rice University, Houston, TX (1990).
[10] J.E. Dennis and R.B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, NJ, 1983). · Zbl 0579.65058
[11] R. Fletcher,Practical Methods of Optimization (John Wiley, Chichester, New York, 1987). · Zbl 0905.65002
[12] D.M. Gay, ”Computing optimal locally constrained steps,”SIAM Journal on Scientific and Statistical Computing 2 (1981) 186–197. · Zbl 0467.65027 · doi:10.1137/0902016
[13] P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, ”Some theoretical properties of an Augmented Lagrangian merit function,” in: P.M. Pardalos, ed.,Advances in Optimization and Parallel Computing (Elsevier, Amsterdam, 1992) pp. 127–143. · Zbl 0814.90094
[14] M.D. Hebden, ”An algorithm for minimization using exact second derivatives,” Technical Report TP515, AERE Harwell, Oxfordshire (1973).
[15] M. Heinkenschloss, ”Mesh independence for nonlinear least squares problems with norm constraints,” Technical Report 90-18, Department of Mathematical Sciences, Rice University, Houston, TX (1990). · Zbl 0771.65030
[16] M. Heinkenschloss, private communication (November 1990).
[17] D.G. Luenberger,Linear and Nonlinear Programming (Addison-Wesley, Massachusetts, California, 1984). · Zbl 0571.90051
[18] J.M. Martínez, ”Local minimizers of quadratic functions on Euclidean balls and spheres,”SIAM Journal on Optimization, 4 (1994) 159–176. · Zbl 0801.65057 · doi:10.1137/0804009
[19] 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, 1978) pp. 105–116.
[20] J.J. Moré, ”Recent developments in algorithms and software for trust-region methods,” in: A. Bachem, M. Grötschel and B. Korte, eds.,Mathematical Programming–The State of Art (Springer-Verlag, Bonn, 1983). · Zbl 0546.90077
[21] J.J. Moré, ”Trust regions and projected gradients,” Technical Memorandum 107, Argonne National Laboratory, Mathematics and Computer Science Division (Argonne, Illinois, 1988).
[22] 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 · doi:10.1145/355934.355936
[23] 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 · doi:10.1137/0904038
[24] S.S. Oren and D.G. Luenberger, ”Self-scaling variable metric (SSVM) algorithms,”Management Science 20 (1974) 845–862. · Zbl 0316.90064 · doi:10.1287/mnsc.20.5.845
[25] S.S. Oren and E. Spedicato, ”Optimal conditioning of self scaling variable metric algorithms,”Mathematical Programming 10 (1976) 70–90. · Zbl 0342.90045 · doi:10.1007/BF01580654
[26] M.J.D. Powell and Y. Yuan, ”A trust-region algorithm for equality constrained optimization,”Mathematical Programming 49 (1990) 189–211. · Zbl 0816.90121 · doi:10.1007/BF01588787
[27] D.F. Shanno and K. Phua, ”Matrix conditioning and nonlinear optimization,”Mathematical Programming 14 (1978) 149–160. · Zbl 0371.90109 · doi:10.1007/BF01588962
[28] D.C. Sorensen, ”Newton’s method with a model trust-region modification,”SIAM Journal on Numerical Analysis 19 (1982) 409–426. · Zbl 0483.65039 · doi:10.1137/0719026
[29] R.J. Stern and H. Wolkowicz, ”Indefinite trust-region subproblems and nonsymmetric eigenvalue perturbations,” Technical Report SOR 93-1, Department of Civil Engineering and Operations Research, Princeton University, Princeton, NJ (1993). · Zbl 0846.49017
[30] A.N. Tikhonov and V.Y. Arsenin,Solutions of ill-posed problems (John Wiley, New York, Toronto, 1977).
[31] Ph.L. Toint, ”Global convergence of a class of trust-region methods for nonconvex minimization in Hilbert space,”IMA Journal on Numerical Analysis 8 (1988) 231–252. · Zbl 0698.65043 · doi:10.1093/imanum/8.2.231
[32] A. Vardi, ”A trust-region algorithm for equality constrained minimization: convergence properties and implementation,”SIAM Journal on Numerical Analysis 22 (1985) 575–591. · Zbl 0581.65045 · doi:10.1137/0722035
[33] S. Vavasis, ”Approximation algorithms for indefinite quadratic programming,” Technical Report 91-1228, Department of Computer Science, Cornell University, Ithaca, NY (1991). · Zbl 0845.90095
[34] C.R. Vogel: ”A constrained least-squares regularization method for nonlinear ill-posed problems,”SIAM Journal on Control and Optimization 28 (1990) 34–49. · Zbl 0696.65096 · doi:10.1137/0328002
[35] K.A. Williamson, ”A robust trust-region algorithm for nonlinear programming,” Ph.D. Thesis, Department of Mathematical Sciences, Rice University, Houston, TX (1990).
[36] Y. Zhang, ”Computing a Celis–Dennis–Tapia trust-region step for equality constrained optimization,” Technical Report 88-16, Department of Mathematical Sciences, Rice University, Houston, TX (1988). · Zbl 0773.90056
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.