×

A two-stage active-set algorithm for bound-constrained optimization. (English) Zbl 1398.90170

Summary: In this paper, we describe a two-stage method for solving optimization problems with bound constraints. It combines the active-set estimate described in [F. Facchinei and S. Lucidi, J. Optim. Theory Appl. 85, No. 2, 265–289 (1995; Zbl 0830.90125)] with a modification of the non-monotone line search framework recently proposed in [M. De Santis et al., Comput. Optim. Appl. 53, No. 2, 395–423 (2012; Zbl 1284.90075)]. In the first stage, the algorithm exploits a property of the active-set estimate that ensures a significant reduction in the objective function when setting to the bounds all those variables estimated active. In the second stage, a truncated-Newton strategy is used in the subspace of the variables estimated non-active. In order to properly combine the two phases, a proximity check is included in the scheme. This new tool, together with the other theoretical features of the two stages, enables us to prove global convergence. Furthermore, under additional standard assumptions, we can show that the algorithm converges at a superlinear rate. Promising experimental results demonstrate the effectiveness of the proposed method.

MSC:

90C30 Nonlinear programming
90C06 Large-scale problems in mathematical programming
49M15 Newton-type methods

Software:

CUTEst; GALAHAD; TRICE; TRON
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Conn, A.R., Gould, N.I., Toint, P.L.: Global convergence of a class of trust region algorithms for optimization with simple bounds. SIAM J. Numer. Anal. 25(2), 433-460 (1988) · Zbl 0643.65031 · doi:10.1137/0725029
[2] Lin, C.J., Moré, J.J.: Newton’s method for large bound-constrained optimization problems. SIAM J. Optim. 9(4), 1100-1127 (1999) · Zbl 0957.65064 · doi:10.1137/S1052623498345075
[3] Dennis, J., Heinkenschloss, M., Vicente, L.N.: Trust-region interior-point SQP algorithms for a class of nonlinear programming problems. SIAM J. Control Optim. 36(5), 1750-1794 (1998) · Zbl 0921.90137 · doi:10.1137/S036012995279031
[4] Heinkenschloss, M., Ulbrich, M., Ulbrich, S.: Superlinear and quadratic convergence of affine-scaling interior-point Newton methods for problems with simple bounds without strict complementarity assumption. Math. Program. 86(3), 615-635 (1999) · Zbl 0945.49023 · doi:10.1007/s101070050107
[5] Kanzow, C., Klug, A.: On affine-scaling interior-point Newton methods for nonlinear minimization with bound constraints. Comput. Optim. Appl. 35(2), 177-197 (2006) · Zbl 1151.90552 · doi:10.1007/s10589-006-6514-5
[6] Bertsekas, D.P.: Projected Newton methods for optimization problems with simple constraints. SIAM J. Control Optim. 20(2), 221-246 (1982) · Zbl 0507.49018 · doi:10.1137/0320018
[7] Facchinei, F., Lucidi, S., Palagi, L.: A truncated Newton algorithm for large scale box constrained optimization. SIAM J. Optim. 12(4), 1100-1125 (2002) · Zbl 1035.90103 · doi:10.1137/S1052623499359890
[8] Hager, W.W., Zhang, H.: A new active set algorithm for box constrained optimization. SIAM J. Optim. 17(2), 526-557 (2006) · Zbl 1165.90570 · doi:10.1137/050635225
[9] Schwartz, A., Polak, E.: Family of projected descent methods for optimization problems with simple bounds. J. Optim. Theory Appl. 92(1), 1-31 (1997) · Zbl 0886.90140 · doi:10.1023/A:1022690711754
[10] Facchinei, F., Júdice, J., Soares, J.: An active set Newton algorithm for large-scale nonlinear programs with box constraints. SIAM J. Optim. 8(1), 158-186 (1998) · Zbl 0911.90301 · doi:10.1137/S1052623493253991
[11] Cheng, W., Li, D.: An active set modified Polak-Ribiere-Polyak method for large-scale nonlinear bound constrained optimization. J. Optim. Theory Appl. 155(3), 1084-1094 (2012) · Zbl 1276.90067 · doi:10.1007/s10957-012-0091-9
[12] Andreani, R., Birgin, E.G., Martínez, J.M., Schuverdt, M.L.: Second-order negative-curvature methods for box-constrained and general constrained optimization. Comput. Optim. Appl. 45(2), 209-236 (2010) · Zbl 1187.90265 · doi:10.1007/s10589-009-9240-y
[13] Birgin, E.G., Martínez, J.M.: Large-scale active-set box-constrained optimization method with spectral projected gradients. Comput. Optim. Appl. 23(1), 101-125 (2002) · Zbl 1031.90012 · doi:10.1023/A:1019928808826
[14] De Santis, M., Di Pillo, G., Lucidi, S.: An active set feasible method for large-scale minimization problems with bound constraints. Comput. Optim. Appl. 53(2), 395-423 (2012) · Zbl 1284.90075 · doi:10.1007/s10589-012-9506-7
[15] Facchinei, F., Lucidi, S.: Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems. J. Optim. Theory Appl. 85(2), 265-289 (1995) · Zbl 0830.90125 · doi:10.1007/BF02192227
[16] Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8(1), 141-148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[17] De Santis, M., Lucidi, S., Rinaldi, F.: A Fast Active Set Block Coordinate Descent Algorithm for \[\ell_1\] ℓ1-regularized least squares. SIAM J. Optim. 26(1), 781-809 (2016) · Zbl 1333.65059 · doi:10.1137/141000737
[18] Buchheim, C., De Santis, M., Lucidi, S., Rinaldi, F., Trieu, L.: A feasible active set method with reoptimization for convex quadratic mixed-integer programming. SIAM J. Optim. 26(3), 1695-1714 (2016) · Zbl 1346.90608
[19] Di Pillo, G., Grippo, L.: A class of continuously differentiable exact penalty function algorithms for nonlinear programming problems. In: System Modelling and Optimization, pp. 246-256. Springer, Berlin (1984) · Zbl 0545.90085
[20] Grippo, L., Lucidi, S.: A differentiable exact penalty function for bound constrained quadratic programming problems. Optimization 22(4), 557-578 (1991) · Zbl 0734.90063 · doi:10.1080/02331939108843700
[21] Zhang, H., Hager, W.W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14(4), 1043-1056 (2004) · Zbl 1073.90024 · doi:10.1137/S1052623403428208
[22] Dembo, R.S., Steihaug, T.: Truncated-Newton algorithms for large-scale unconstrained optimization. Math. Program. 26(2), 190-212 (1983) · Zbl 0523.90078 · doi:10.1007/BF02592055
[23] Grippo, L., Lampariello, F., Lucidi, S.: A class of nonmonotone stabilization methods in unconstrained optimization. Numer. Math. 59(1), 779-805 (1991) · Zbl 0724.90060 · doi:10.1007/BF01385810
[24] Gould, N.I., Orban, D., Toint, P.L.: GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization. ACM Trans. Math. Softw. (TOMS) 29(4), 353-372 (2003) · Zbl 1068.90525 · doi:10.1145/962437.962438
[25] Gould, N.I., Orban, D., Toint, P.L.: CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization. Comput. Optim. Appl. 60(3), 545-557 (2015) · Zbl 1325.90004 · doi:10.1007/s10589-014-9687-3
[26] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[27] Birgin, E.G., Gentil, J.M.: Evaluating bound-constrained minimization software. Comput. Optim. Appl. 53(2), 347-373 (2012) · Zbl 1258.90067 · doi:10.1007/s10589-012-9466-y
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.