×

Sufficient descent Polak-Ribière-Polyak conjugate gradient algorithm for large-scale box-constrained optimization. (English) Zbl 1470.90157

Summary: A practical algorithm for solving large-scale box-constrained optimization problems is developed, analyzed, and tested. In the proposed algorithm, an identification strategy is involved to estimate the active set at per-iteration. The components of inactive variables are determined by the steepest descent method at first finite number of steps and then by conjugate gradient method subsequently. Under some appropriate conditions, we show that the algorithm converges globally. Numerical experiments and comparisons by using some box-constrained problems from CUTEr library are reported. Numerical comparisons illustrate that the proposed method is promising and competitive with the well-known method – L-BFGS-B.

MSC:

90C52 Methods of reduced gradient type
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gould, N.; Orban, D.; Toint, P., Numerical methods for large-scale nonlinear optimization, Acta Numerica, 14, 299-361 (2005) · Zbl 1119.65337 · doi:10.1017/S0962492904000248
[2] Luenberger, D. G., Introduction to Linear and Nonlinear Programming (1973), Reading, Mass, USA: Addison-Wesley, Reading, Mass, USA · Zbl 0297.90044
[3] Facchinei, F.; Júdice, J.; Soares, J., An active set Newton algorithm for large-scale nonlinear programs with box constraints, SIAM Journal on Optimization, 8, 1, 158-186 (1998) · Zbl 0911.90301 · doi:10.1137/S1052623493253991
[4] Birgin, E. G.; Martínez, J. M., Large-scale active-set box-constrained optimization method with spectral projected gradients, Computational Optimization and Applications, 23, 1, 101-125 (2002) · Zbl 1031.90012 · doi:10.1023/A:1019928808826
[5] Facchinei, F.; Lucidi, S.; Palagi, L., A truncated Newton algorithm for large scale box constrained optimization, SIAM Journal on Optimization, 12, 4, 1100-1125 (2002) · Zbl 1035.90103 · doi:10.1137/S1052623499359890
[6] Hager, W. W.; Zhang, H., A new active set algorithm for box constrained optimization, SIAM Journal on Optimization, 17, 2, 526-557 (2006) · Zbl 1165.90570 · doi:10.1137/050635225
[7] Ni, Q.; Yuan, Y., A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization, Mathematics of Computation, 66, 220, 1509-1520 (1997) · Zbl 0886.65065 · doi:10.1090/S0025-5718-97-00866-1
[8] Bertsekas, D. P., Projected Newton methods for optimization problems with simple constraints, SIAM Journal on Control and Optimization, 20, 2, 221-246 (1982) · Zbl 0507.49018 · doi:10.1137/0320018
[9] Hager, W. W.; Zhang, H., A survey of nonlinear conjugate gradient methods, Pacific Journal of Optimization, 2, 1, 35-58 (2006) · Zbl 1117.90048
[10] Zhang, L.; Zhou, W.; Li, D.-H., A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence, IMA Journal of Numerical Analysis, 26, 4, 629-640 (2006) · Zbl 1106.65056 · doi:10.1093/imanum/drl016
[11] Zhang, J.; Xiao, Y.; Wei, Z., Nonlinear conjugate gradient methods with sufficient descent condition for large-scale unconstrained optimization, Mathematical Problems in Engineering, 2009 (2009) · Zbl 1184.65066 · doi:10.1155/2009/243290
[12] Grippo, L.; Lucidi, S., A globally convergent version of the Polak-Ribière conjugate gradient method, Mathematical Programming, 78, 3, 375-391 (1997) · Zbl 0887.90157 · doi:10.1016/S0025-5610(97)00002-6
[13] Zhang, L., Nonlinear conjugate gradient methods for optimization problems [Ph.D. thesis] (2006), Hunan, China: College of Mathematics and Econometrics, Hunan University, Hunan, China
[14] Qi, L.; Tong, X. J.; Li, D. H., Active-set projected trust-region algorithm for box-constrained nonsmooth equations, Journal of Optimization Theory and Applications, 120, 3, 601-625 (2004) · Zbl 1140.65331 · doi:10.1023/B:JOTA.0000025712.43243.eb
[15] Xiao, Y.; Li, D.-H., An active set limited memory BFGS algorithm for large-scale bound constrained optimization, Mathematical Methods of Operations Research, 67, 3, 443-454 (2008) · Zbl 1145.90084 · doi:10.1007/s00186-007-0199-0
[16] Xiao, Y.; Hu, Q., Subspace Barzilai-Borwein gradient method for large-scale bound constrained optimization, Applied Mathematics and Optimization, 58, 2, 275-290 (2008) · Zbl 1173.90584 · doi:10.1007/s00245-008-9038-9
[17] Xiao, Y.-H.; Hu, Q.-J.; Wei, Z., Modified active set projected spectral gradient method for bound constrained optimization, Applied Mathematical Modelling, 35, 7, 3117-3127 (2011) · Zbl 1221.90081 · doi:10.1016/j.apm.2010.09.011
[18] Yang, Y.-F.; Li, D.-H.; Qi, L., A feasible sequential linear equation method for inequality constrained optimization, SIAM Journal on Optimization, 13, 4, 1222-1244 (2003) · Zbl 1101.90394 · doi:10.1137/S1052623401383881
[19] Bongartz, I.; Conn, A. R.; Gould, N.; Toint, P. L., CUTE: constrained and unconstrained testing environment, ACM Transactions on Mathematical Software, 21, 1, 123-160 (1995) · Zbl 0886.65058 · doi:10.1145/200979.201043
[20] Byrd, R. H.; Lu, P.; Nocedal, J.; Zhu, C. Y., A limited memory algorithm for bound constrained optimization, SIAM Journal on Scientific Computing, 16, 5, 1190-1208 (1995) · Zbl 0836.65080 · doi:10.1137/0916069
[21] Zhu, C.; Byrd, R. H.; Lu, P.; Nocedal, J., Algorithm 778: L-BFGS-B: fortran subroutines for large-scale bound-constrained optimization, ACM Transactions on Mathematical Software, 23, 4, 550-560 (1997) · Zbl 0912.65057 · doi:10.1145/279232.279236
[22] Gilbert, J. C.; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM Journal on Optimization, 2, 1, 21-42 (1992) · Zbl 0767.90082 · doi:10.1137/0802003
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.