×

zbMATH — the first resource for mathematics

A new subspace limited memory BFGS algorithm for large-scale bound constrained optimization. (English) Zbl 1114.65069
A new algorithm that combines an active set strategy with the gradient projection method is presented. As in the work by F. Facchinei, S. Lucidi and L. Palagi [SIAM J. Opt., 12, 1100–1125 (2002; Zbl 1035.90103)] the authors avoid the necessity of finding an exact minimizer of a quadratic subproblem with bound constraints. The algorithm has the following properties: All iterates are feasible and the sequence of the objective function values is decreasing; rapid changes in the active set are allowed; a global convergence theory is established.
Moreover, it reserves the advantage of the effective active set identified technique by Facchinei, Lucidi and Palagi [loc. cit.] and uses the superiority of the subspace limited memory Broyden-Fletcher-Goldfarb-Shanno (BFGS) method [see Q. Ni and Y. X. Yuan, Math. Comp., 66, 1509–1520 (1997; Zbl 0886.65065)] which has been proved much suit for solving large-scale problems. Namely, the active sets are based on a guessing technique to be identified at each iteration, the search direction in the free subspace is determined by a limited memory BFGS algorithm, which provides an efficient means for attacking large-scale optimizatuin problems. The implementations of the method on CUTE test problems are described.

MSC:
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C06 Large-scale problems in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bertsekas, D.P., Projected Newton methods for optimization problems with simple constrains, SIAM J. contr. opt., 20, 221-246, (1982) · Zbl 0507.49018
[2] Birgin, E.G.; Martínez, J.M., Large−scale active-set box-constrained optimization method with spectral projected gradients, Comput. opt. appl., 23, 101-125, (2002) · Zbl 1031.90012
[3] Burke, J.V.; Moré, J.J., On the identification of active constraints, SIAM J. numer. anal., 25, 1197-1211, (1988) · Zbl 0662.65052
[4] Burke, J.V.; Moré, J.J., Exposing constrints, SIAM J. opt., 4, 573-595, (1994) · Zbl 0809.65058
[5] Ryrd, R.H.; Lu, P.H.; Nocedal, J., A limited memory algorithm for bound constrained optimization, SIAM J. statist. sci. comput., 16, 1190-1208, (1995) · Zbl 0836.65080
[6] Ryrd, R.H.; Nocedal, J.; Schnabel, R.B., Representations of quasi-Newton matrices and their use in limited memory methods, Math. program., 63, 129-156, (1994) · Zbl 0809.90116
[7] Calamai, P.; Moré, J.J., Projected gradient for linearly constrained programs, Math. program., 39, 93-116, (1987) · Zbl 0634.90064
[8] Ccoleman, T.F.; Li, Y., An interior trust region approach for nonlinear minimization subject to bounds, SIAM J. opt., 6, 418-445, (1996) · Zbl 0855.65063
[9] Conn, A.R.; Gould, N.I.M.; Toint, Ph. L., Global convergence of a class of trust region algorithm for optimization with simple bounds, SIAM J. numer. anal., 25, 433-460, (1988) · Zbl 0643.65031
[10] Conn, A.R.; Gould, N.I.M.; Toint, Ph. L., : constrained and unconstrained testing environment, ACM trans. math. softw., 21, 123-160, (1995) · Zbl 0886.65058
[11] Conn, A.R.; Gould, N.I.M.; Toint, Ph. L., : A Fortran package for large-scale nonlinear optimization (release A), Springer series in computational mathematics, (1992), Springer Verlag Heidelberg, Berlin, New York
[12] Facchinei, F.; Júdice, J.; Soares, J., An active set Newton algorithm for large-scale nonlinear programs with box canstranits, SIAM J. opt., 8, 158-186, (1998) · Zbl 0911.90301
[13] Facchinei, F.; Lucidi, S.; Palagi, L., A truncated Newton algorithm for large scale box constrained optimization, SIAM J. opt., 12, 1100-1125, (2002) · Zbl 1035.90103
[14] Gould, N.I.M.; Orban, D.; Toint, Ph.L., Numerical methods for large-scale nonlinear optimization, Acta numer., 14, 299-361, (2005) · Zbl 1119.65337
[15] Goldfarb, D., Extension of davidon’s variable metric algorithm to maximization under linear inequality and constraints, SIAM J. appl. math., 17, 739-764, (1969) · Zbl 0185.42602
[16] C.T. Kelley, Iterative methods for optimization, Philadelphia, PA, 1999. · Zbl 0934.90082
[17] Lin, C.J.; Moré, J.J., Nowton’s method for large bound-constrained optimization problems, SIAM J. opt., 9, 1100-1127, (1999) · Zbl 0957.65064
[18] Lescrenier, M., Convergence of trust region algorithm for optimization with bounds when strict complementarity does not hold, SIAM J. numer. anal., 28, 467-695, (1991) · Zbl 0726.65068
[19] Luenberger, D.G., Introduction to linear and nonlinear programming, (1973), Addison-Wesley Reading, MA, Ch. 11 · Zbl 0241.90052
[20] Moré, J.J.; Toraldo, G., On the solution of large quadratic programming problems with bound constraints, SIAM J. opt., 1, 93-113, (1991) · Zbl 0752.90053
[21] B.A. Murtagh, M.A. Saunders, User’s Guide, Report SOL 83-20R, Systems Optimization Laboratory, Stanford University (revised July 1998).
[22] Ni, Q., A subspace projected conjuagte gradient algorithm for large bound constrained quadratic programming, Numer. math. (a journal of Chinese universities), 7, 51-60, (1998) · Zbl 0909.65036
[23] Ni, Q.; Yuan, Y.X., A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization, Math. comp., 66, 1509-1520, (1997) · Zbl 0886.65065
[24] Powell, M.J.D., A fast algorithm for nonlinearly constrained optimization calculations, Numer. anal., 155-157, (1978) · Zbl 0374.65032
[25] R.J. Vanderbei, : An interior point code for quadratic programming, Technical Report, Statistics and Operation Research, Princeton University, SOR-94-15, 1994.
[26] Zhu, C.Y.; Byrd, R.H.; Lu, P.H.; Nocedal, J., Fortran subroutines for large-scale bound constrained optimization, ACM trans. math. softw., 23, 550-560, (1997) · Zbl 0912.65057
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.