| Title:
|
An accurate active set Newton algorithm for large scale bound constrained optimization (English) |
| Author:
|
Sun, Li |
| Author:
|
He, Guoping |
| Author:
|
Wang, Yongli |
| Author:
|
Zhou, Changyin |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
56 |
| Issue:
|
3 |
| Year:
|
2011 |
| Pages:
|
297-314 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
active set |
| Keyword:
|
bound constraints |
| Keyword:
|
Newton method |
| Keyword:
|
strict complementarity |
| MSC:
|
90C06 |
| MSC:
|
90C30 |
| MSC:
|
90C53 |
| idZBL:
|
Zbl 1224.90177 |
| idMR:
|
MR2800580 |
| DOI:
|
10.1007/s10492-011-0018-z |
| . |
| Date available:
|
2011-05-17T08:29:02Z |
| Last updated:
|
2020-07-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/141488 |
| . |
| Reference:
|
[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. Zbl 0842.90106, MR 1305566, 10.1007/BF01582221 |
| Reference:
|
[2] Coleman, T. F., Li, Y.: An interior trust region approach for nonlinear minimization subject to bounds.SIAM J. Optim. 6 (1996), 418-445. Zbl 0855.65063, MR 1387333, 10.1137/0806023 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 0643.65031, MR 0933734, 10.1137/0725029 |
| Reference:
|
[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. Zbl 0673.65033, MR 0997667, 10.1137/0726044 |
| Reference:
|
[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. MR 0343581, 10.1090/S0025-5718-1974-0343581-1 |
| Reference:
|
[7] Dostál, Z.: A proportioning based algorithm with rate of convergence for bound constrained quadratic programming.Numer. Algorithms 34 (2003), 293-302. Zbl 1037.65061, MR 2043903, 10.1023/B:NUMA.0000005347.98806.b2 |
| Reference:
|
[8] Facchinei, F.: Minimization of SC$^{1}$ functions and the Maratos effect.Oper. Res. Lett. 17 (1995), 131-137. MR 1342260, 10.1016/0167-6377(94)00059-F |
| Reference:
|
[9] Facchinei, F., Fischer, A., Kanzow, C.: On the accurate identification of active constraints.SIAM J. Optim. 9 (1998), 14-32. Zbl 0960.90080, MR 1660110, 10.1137/S1052623496305882 |
| Reference:
|
[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. MR 1617441, 10.1137/S1052623493253991 |
| Reference:
|
[11] Facchinei, F., Júdice, J., Soares, J.: Generating box-constrained optimization problems.ACM Trans. Math. Softw. 23 (1997), 443-447. 10.1145/275323.275331 |
| Reference:
|
[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. Zbl 0830.90125, MR 1333788, 10.1007/BF02192227 |
| Reference:
|
[13] Facchinei, F., Lucidi, S., Palagi, L.: A truncated Newton algorithm for large scale box constrained optimization.SIAM J. Optim. 12 (2002), 1100-1125. Zbl 1035.90103, MR 1922511, 10.1137/S1052623499359890 |
| Reference:
|
[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. Zbl 1222.68198, MR 2249875 |
| Reference:
|
[15] Gill, P. E., Murray, W., Wright, M. H.: Practical Optimization.Academic Press London (1981). Zbl 0503.90062, MR 0634376 |
| Reference:
|
[16] Hager, W. W., Zhang, H.: A new active set algorithm for box constrained optimization.SIAM J. Optim. 17 (2006), 526-557. Zbl 1165.90570, MR 2247750, 10.1137/050635225 |
| Reference:
|
[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. Zbl 0945.49023, MR 1733741, 10.1007/s101070050107 |
| Reference:
|
[18] Keerthi, S. S., Gilbert, E. G.: Convergence of a generalized SMO algorithm for SVM classifier design.Mach. Learn. 46 (2002), 351-360. Zbl 0998.68109, 10.1023/A:1012431217818 |
| Reference:
|
[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. Zbl 0726.65068, MR 1087515, 10.1137/0728026 |
| Reference:
|
[20] Lin, C. J., Moré, J. J.: Newton's method for large bound-constrained optimization problems.SIAM J. Optim. 9 (1999), 1100-1127. Zbl 0957.65064, MR 1724778, 10.1137/S1052623498345075 |
| Reference:
|
[21] Moré, J. J., Toraldo, G.: On the solution of large quadratic programming problems with bound constraints.SIAM J. Optim. 1 (1991), 93-113. MR 1094793, 10.1137/0801008 |
| Reference:
|
[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. Zbl 0886.65065, MR 1422793, 10.1090/S0025-5718-97-00866-1 |
| Reference:
|
[23] Nocedal, J., Wright, S. J.: Numerical Optimization.Springer New York (2006). Zbl 1104.65059, MR 2244940 |
| Reference:
|
[24] Oberlin, C., Wright, S. J.: Active set identification in nonlinear programming.SIAM J. Optim. 17 (2006), 577-605. Zbl 1174.90813, MR 2247752, 10.1137/050626776 |
| Reference:
|
[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. Zbl 0767.90060, MR 1163293, 10.1007/BF01581190 |
| Reference:
|
[26] Polyak, B. T.: The conjugate gradient method in extremal problems.U.S.S.R. Comput. Math. Math. Phys. 9 (1969), 94-112. Zbl 0191.49003, 10.1016/0041-5553(69)90035-4 |
| Reference:
|
[27] Schittkowski, K.: More Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, Vol. 282.Springer Berlin (1987). MR 1117683 |
| Reference:
|
[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. Zbl 1189.90160, MR 2535978, 10.1016/j.camwa.2009.03.085 |
| Reference:
|
[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. Zbl 1224.90176, MR 2737938, 10.1007/s10492-010-0022-8 |
| Reference:
|
[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. Zbl 1114.65069, MR 2298454, 10.1016/j.amc.2006.06.119 |
| . |
