×

zbMATH — the first resource for mathematics

An active set quasi-Newton method with projected search for bound constrained minimization. (English) Zbl 1189.90160
Summary: We analyze an active set quasi-Newton method for large scale bound constrained problems. Our approach combines the accurate active set identification function and the projected search. Both of these strategies permit fast change in the working set. The limited memory method is employed to update the inactive variables, while the active variables are updated by simple rules. A further division of the active set enables the global convergence of the new algorithm. Numerical tests demonstrate the efficiency and performance of the present strategy and its comparison with some existing active set strategies.

MSC:
90C30 Nonlinear programming
65K10 Numerical optimization and variational techniques
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Moré, J.; Toraldo, G., On the solution of large quadratic programming problems with bound constraints, SIAM J. optim., 1, 93-113, (1991) · Zbl 0752.90053
[2] Dostál, Z., A proportioning based algorithm with rate of convergence for bound constrained quadratic programming, Numer. algorithms, 34, 293-302, (2003) · Zbl 1037.65061
[3] Hager, W.W.; Zhang, H.C., A new active set algorithm for box constrained optimization, SIAM J. optim., 17, 526-557, (2006) · Zbl 1165.90570
[4] Forsgren, A.; Murray, W., Newton methods for large-scale linear inequality-constrained minimization, SIAM J. optim., 7, 162-176, (1997) · Zbl 0869.65039
[5] Lin, C.J.; Moré, J., Newton’s method for large bound-constrained optimization problems, SIAM J. optim., 9, 1100-1127, (1999) · Zbl 0957.65064
[6] Facchinei, F.; Júdice, J.; Soares, J., An active set Newton algorithm for large-scale nonlinear programs with box constraints, SIAM J. optim., 8, 158-186, (1998) · Zbl 0911.90301
[7] Facchinei, F.; Lucidi, S.; Palagi, L., A truncated Newton algorithm for large scale box constrained optimization, SIAM J. optim., 12, 1100-1125, (2002) · Zbl 1035.90103
[8] Facchinei, F.; Lucidi, S., Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems, J. optim. theory appl., 85, 265-289, (1995) · Zbl 0830.90125
[9] Facchinei, F.; Liuzzi, G.; Lucidi, S., A truncated Newton method for the solution of large-scale inequality constrained minimization problems, Comput. optim. appl., 25, 85-122, (2003) · Zbl 1038.90099
[10] Facchinei, F.; Fischer, A.; Kanzow, C., On the accurate identification of active constraints, SIAM J. optim., 9, 14-32, (1998) · Zbl 0960.90080
[11] Byrd, R.H.; Nocedal, J.; Schnabel, R.B., Representation of quasi-Newton matrices and their use in limited memory methods, Math. program., 63, 129-156, (1994) · Zbl 0809.90116
[12] Liu, D.C.; Nocedal, J., On the limited memory BFGS method for large scale optimization, Math. program., 45, 503-528, (1989) · Zbl 0696.90048
[13] Byrd, R.H.; Lu, P.; Nocedal, J.; Zhu, C., A limited memory algorithm for bound constrained optimization, SIAM J. sci. comput., 16, 1190-1208, (1995) · Zbl 0836.65080
[14] Xiao, Y.H.; Wei, Z.X., A new subspace limited memory BFGS algorithm for large-scale bound constrained optimization, Appl. math. comput., 185, 350-359, (2007) · Zbl 1114.65069
[15] Y.H. Xiao, D.H. Li, An active set limited memory BFGS algorithm for large-scale bound constrained optimization, Math. Methods Oper. Res. doi:10.1007/s00186-007-0199-0 · Zbl 1145.90084
[16] L. Sun, L. Fang, G.P. He, An accurate accurate active set quasi-Newton algorithm for large scale bound constrained optimization, Appl. Math. (2009) (in press)
[17] Conn, A.R.; Gould, N.I.M.; Toint, Ph.L., Testing a class of methods for solving minimization problems with simple bounds on the variables, Math. comput., 50, 399-430, (1988) · Zbl 0645.65033
[18] Conn, A.R.; Gould, N.I.M.; Toint, Ph.L., LANCELOT, A Fortran package for large-scale nonlinear optimization, (1992), Springer Verlag Berlin · Zbl 0809.65066
[19] Conn, A.R.; Gould, N.I.M.; Toint, Ph.L., Global convergence of a class of trust region algorithms for optimization with simple bounds, SIAM J. numer. anal., 25, 433-460, (1988), See also same journal 26 (1989) 764-767 · Zbl 0643.65031
[20] Conn, A.R.; Gould, N.I.M.; Toint, Ph.L., An introduction to the structure of large scale nonlinear optimization problems and the LANCELOT project, (), 42-54
[21] Keerthi, S.S.; Gilbert, E.G., Convergence of a generalized SMO algorithm for SVM classifier design, Mach. learn., 46, 351-360, (2002) · Zbl 0998.68109
[22] Fan, R.E.; Chen, P.H.; Lin, C.J., Working set selection using second order information for training support vector machines, J. Mach. learn. res., 6, 1889-1918, (2005) · Zbl 1222.68198
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.