Previous |  Up |  Next

Article

Keywords:
active set; bound constraints; Newton method; strict complementarity
Summary:
A new algorithm for solving large scale bound constrained minimization problems is proposed. The algorithm is based on an accurate identification technique of the active set proposed by Facchinei, Fischer and Kanzow in 1998. A further division of the active set yields the global convergence of the new algorithm. In particular, the convergence rate is superlinear without requiring the strict complementarity assumption. Numerical tests demonstrate the efficiency and performance of the present strategy and its comparison with some existing active set strategies.
References:
[1] Coleman, T. F., Li, Y.: On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds. Math. Program. 67 (1994), 189-224. DOI 10.1007/BF01582221 | MR 1305566 | Zbl 0842.90106
[2] Coleman, T. F., Li, Y.: An interior trust region approach for nonlinear minimization subject to bounds. SIAM J. Optim. 6 (1996), 418-445. DOI 10.1137/0806023 | MR 1387333 | Zbl 0855.65063
[3] 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. ACM Trans. Math. Softw. 7 (1981), 17-41. MR 1438096
[4] 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 (1988), 433-460. DOI 10.1137/0725029 | MR 0933734 | Zbl 0643.65031
[5] Conn, A. R., Gould, N. I. M., Toint, Ph. L.: Correction to the paper on global convergence of a class of trust region algorithms for optimization with simple bounds. SIAM J. Numer. Anal. 26 (1989), 764-767. DOI 10.1137/0726044 | MR 0997667 | Zbl 0673.65033
[6] Dennis, J. E., Moré, J. J.: A characterization of superlinear convergence and its application to quasi-Newton methods. Math. Comput. 28 (1974), 549-560. DOI 10.1090/S0025-5718-1974-0343581-1 | MR 0343581
[7] Dostál, Z.: A proportioning based algorithm with rate of convergence for bound constrained quadratic programming. Numer. Algorithms 34 (2003), 293-302. DOI 10.1023/B:NUMA.0000005347.98806.b2 | MR 2043903 | Zbl 1037.65061
[8] Facchinei, F.: Minimization of SC$^{1}$ functions and the Maratos effect. Oper. Res. Lett. 17 (1995), 131-137. DOI 10.1016/0167-6377(94)00059-F | MR 1342260
[9] Facchinei, F., Fischer, A., Kanzow, C.: On the accurate identification of active constraints. SIAM J. Optim. 9 (1998), 14-32. DOI 10.1137/S1052623496305882 | MR 1660110 | Zbl 0960.90080
[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 (1998), 158-186. DOI 10.1137/S1052623493253991 | MR 1617441
[11] Facchinei, F., Júdice, J., Soares, J.: Generating box-constrained optimization problems. ACM Trans. Math. Softw. 23 (1997), 443-447. DOI 10.1145/275323.275331
[12] Facchinei, F., Lucidi, S.: Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems. J. Optimization Theory Appl. 85 (1995), 265-289. DOI 10.1007/BF02192227 | MR 1333788 | Zbl 0830.90125
[13] Facchinei, F., Lucidi, S., Palagi, L.: A truncated Newton algorithm for large scale box constrained optimization. SIAM J. Optim. 12 (2002), 1100-1125. DOI 10.1137/S1052623499359890 | MR 1922511 | Zbl 1035.90103
[14] 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 (2005), 1889-1918. MR 2249875 | Zbl 1222.68198
[15] Gill, P. E., Murray, W., Wright, M. H.: Practical Optimization. Academic Press London (1981). MR 0634376 | Zbl 0503.90062
[16] Hager, W. W., Zhang, H.: A new active set algorithm for box constrained optimization. SIAM J. Optim. 17 (2006), 526-557. DOI 10.1137/050635225 | MR 2247750 | Zbl 1165.90570
[17] 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 (1999), 615-635. DOI 10.1007/s101070050107 | MR 1733741 | Zbl 0945.49023
[18] Keerthi, S. S., Gilbert, E. G.: Convergence of a generalized SMO algorithm for SVM classifier design. Mach. Learn. 46 (2002), 351-360. DOI 10.1023/A:1012431217818 | Zbl 0998.68109
[19] Lescrenier, M.: Convergence of trust region algorithms for optimization with bounds when strict complementarity does not hold. SIAM J. Numer. Anal. 28 (1991), 476-495. DOI 10.1137/0728026 | MR 1087515 | Zbl 0726.65068
[20] Lin, C. J., Moré, J. J.: Newton's method for large bound-constrained optimization problems. SIAM J. Optim. 9 (1999), 1100-1127. DOI 10.1137/S1052623498345075 | MR 1724778 | Zbl 0957.65064
[21] Moré, J. J., Toraldo, G.: On the solution of large quadratic programming problems with bound constraints. SIAM J. Optim. 1 (1991), 93-113. DOI 10.1137/0801008 | MR 1094793
[22] Ni, Q., Yuan, Y.: A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization. Math. Comput. 66 (1997), 1509-1520. DOI 10.1090/S0025-5718-97-00866-1 | MR 1422793 | Zbl 0886.65065
[23] Nocedal, J., Wright, S. J.: Numerical Optimization. Springer New York (2006). MR 2244940 | Zbl 1104.65059
[24] Oberlin, C., Wright, S. J.: Active set identification in nonlinear programming. SIAM J. Optim. 17 (2006), 577-605. DOI 10.1137/050626776 | MR 2247752 | Zbl 1174.90813
[25] Pillo, G. Di, Facchinei, F., Grippo, L.: An $RQP$ algorithm using a differentiable exact penalty function for inequality constrained problems. Math. Program. 55 (1992), 49-68. DOI 10.1007/BF01581190 | MR 1163293 | Zbl 0767.90060
[26] Polyak, B. T.: The conjugate gradient method in extremal problems. U.S.S.R. Comput. Math. Math. Phys. 9 (1969), 94-112. DOI 10.1016/0041-5553(69)90035-4 | Zbl 0191.49003
[27] Schittkowski, K.: More Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, Vol. 282. Springer Berlin (1987). MR 1117683
[28] Sun, L., He, G. P., Wang, Y. L., Fang, L.: An active set quasi-Newton method with projected search for bound constrained minimization. Comput. Math. Appl. 58 (2009), 161-170. DOI 10.1016/j.camwa.2009.03.085 | MR 2535978 | Zbl 1189.90160
[29] Sun, L., Fang, L., He, G. P.: An active set strategy based on the multiplier function or the gradient. Appl. Math. 55 (2010), 291-304. DOI 10.1007/s10492-010-0022-8 | MR 2737938 | Zbl 1224.90176
[30] Xiao, Y. H., Wei, Z. X.: A new subspace limited memory BFGS algorithm for large-scale bound constrained optimization. Appl. Math. Comput. 185 (2007), 350-359. DOI 10.1016/j.amc.2006.06.119 | MR 2298454 | Zbl 1114.65069
Partner of
EuDML logo