A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization

Ni, Q.; Yuan, Y.

doi:10.1090/S0025-5718-97-00866-1

A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization
HTML articles powered by AMS MathViewer

by Q. Ni and Y. Yuan PDF

Math. Comp. 66 (1997), 1509-1520 Request permission

Abstract:

In this paper we propose a subspace limited memory quasi-Newton method for solving large-scale optimization with simple bounds on the variables. The limited memory quasi-Newton method is used to update the variables with indices outside of the active set, while the projected gradient method is used to update the active variables. The search direction consists of three parts: a subspace quasi-Newton direction, and two subspace gradient and modified gradient directions. Our algorithm can be applied to large-scale problems as there is no need to solve any subproblems. The global convergence of the method is proved and some numerical results are also given.

References

R.H. Byrd, P. Lu, J. Nocedal and C. Zhu, A limited memory algorithm for bound constrained optimization, Report NAM-8, EECS Department, Northwestern University, 1994.
Richard H. Byrd, Jorge Nocedal, and Robert B. Schnabel, Representations of quasi-Newton matrices and their use in limited memory methods, Math. Programming 63 (1994), no. 2, Ser. A, 129–156. MR 1268604, DOI 10.1007/BF01582063
I. Bongartz, A.R. Conn, N. Gould, and Ph.L. Toint, CUTE: constrained and unconstrained testing environment, Research Report, IBM T.J. Watson Research Center, Yorktown, USA.
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 J. Numer. Anal. 25 (1988), no. 2, 433–460. MR 933734, DOI 10.1137/0725029
Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint, Testing a class of methods for solving minimization problems with simple bounds on the variables, Math. Comp. 50 (1988), no. 182, 399–430. MR 929544, DOI 10.1090/S0025-5718-1988-0929544-3
A.R. Conn, N.I.M. Gould and Ph.L. Toint, LANCELOT: a Fortran package for large-scale nonlinear optimization (Release A), Number 17 in Springer Series in Computational Mathematics, Springer Verlag, Heidelberg, New York, 1992.
R. Fletcher, Practical methods of optimization, 2nd ed., A Wiley-Interscience Publication, John Wiley & Sons, Ltd., Chichester, 1987. MR 955799
P. Lu, Bound constrained nonlinear optimization and limited memory methods, Ph.D. Thesis, Dept. of Electrical Engineering and Computer Science, Northwestern University, Evanston, Illinois, 1992.
Jorge J. Moré and Gerardo Toraldo, On the solution of large quadratic programming problems with bound constraints, SIAM J. Optim. 1 (1991), no. 1, 93–113. MR 1094793, DOI 10.1137/0801008
Qin Ni, General large-scale nonlinear programming using sequential quadratic programming methods, Bayreuth. Math. Schr. 45 (1993), 133–236 (English, with German summary). Dissertation, Universität Bayreuth, Bayreuth, 1993. MR 1244187
Jorge Nocedal, Updating quasi-Newton matrices with limited storage, Math. Comp. 35 (1980), no. 151, 773–782. MR 572855, DOI 10.1090/S0025-5718-1980-0572855-7
M. J. D. Powell, A fast algorithm for nonlinearly constrained optimization calculations, Numerical analysis (Proc. 7th Biennial Conf., Univ. Dundee, Dundee, 1977) Lecture Notes in Math., Vol. 630, Springer, Berlin, 1978, pp. 144–157. MR 0483447
C. Zhu, R.H. Byrd, P. Lu, and J. Nocedal, L-BFGS-B Fortran subroutines for large-scale bound constrained optimization, Report NAM-11, EECS Department, Northwestern University, 1994.