An accurate active set Newton algorithm for large scale bound constrained optimization

Li Sun; Guoping He; Yongli Wang; Changyin Zhou

Applications of Mathematics (2011)

  • Volume: 56, Issue: 3, page 297-314
  • ISSN: 0862-7940

Abstract

top
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.

How to cite

top

Sun, Li, et al. "An accurate active set Newton algorithm for large scale bound constrained optimization." Applications of Mathematics 56.3 (2011): 297-314. <http://eudml.org/doc/116526>.

@article{Sun2011,
abstract = {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.},
author = {Sun, Li, He, Guoping, Wang, Yongli, Zhou, Changyin},
journal = {Applications of Mathematics},
keywords = {active set; bound constraints; Newton method; strict complementarity; active set; bound constraints; Newton method; strict complementarity},
language = {eng},
number = {3},
pages = {297-314},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {An accurate active set Newton algorithm for large scale bound constrained optimization},
url = {http://eudml.org/doc/116526},
volume = {56},
year = {2011},
}

TY - JOUR
AU - Sun, Li
AU - He, Guoping
AU - Wang, Yongli
AU - Zhou, Changyin
TI - An accurate active set Newton algorithm for large scale bound constrained optimization
JO - Applications of Mathematics
PY - 2011
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 56
IS - 3
SP - 297
EP - 314
AB - 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.
LA - eng
KW - active set; bound constraints; Newton method; strict complementarity; active set; bound constraints; Newton method; strict complementarity
UR - http://eudml.org/doc/116526
ER -

References

top
  1. Coleman, T. F., Li, Y., 10.1007/BF01582221, Math. Program. 67 (1994), 189-224. (1994) Zbl0842.90106MR1305566DOI10.1007/BF01582221
  2. Coleman, T. F., Li, Y., 10.1137/0806023, SIAM J. Optim. 6 (1996), 418-445. (1996) Zbl0855.65063MR1387333DOI10.1137/0806023
  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. (1981) MR1438096
  4. Conn, A. R., Gould, N. I. M., Toint, Ph. L., 10.1137/0725029, SIAM J. Numer. Anal. 25 (1988), 433-460. (1988) Zbl0643.65031MR0933734DOI10.1137/0725029
  5. Conn, A. R., Gould, N. I. M., Toint, Ph. L., 10.1137/0726044, SIAM J. Numer. Anal. 26 (1989), 764-767. (1989) Zbl0673.65033MR0997667DOI10.1137/0726044
  6. Dennis, J. E., Moré, J. J., 10.1090/S0025-5718-1974-0343581-1, Math. Comput. 28 (1974), 549-560. (1974) MR0343581DOI10.1090/S0025-5718-1974-0343581-1
  7. Dostál, Z., 10.1023/B:NUMA.0000005347.98806.b2, Numer. Algorithms 34 (2003), 293-302. (2003) Zbl1037.65061MR2043903DOI10.1023/B:NUMA.0000005347.98806.b2
  8. Facchinei, F., 10.1016/0167-6377(94)00059-F, Oper. Res. Lett. 17 (1995), 131-137. (1995) MR1342260DOI10.1016/0167-6377(94)00059-F
  9. Facchinei, F., Fischer, A., Kanzow, C., 10.1137/S1052623496305882, SIAM J. Optim. 9 (1998), 14-32. (1998) Zbl0960.90080MR1660110DOI10.1137/S1052623496305882
  10. Facchinei, F., Júdice, J., Soares, J., 10.1137/S1052623493253991, SIAM J. Optim. 8 (1998), 158-186. (1998) MR1617441DOI10.1137/S1052623493253991
  11. Facchinei, F., Júdice, J., Soares, J., 10.1145/275323.275331, ACM Trans. Math. Softw. 23 (1997), 443-447. (1997) DOI10.1145/275323.275331
  12. Facchinei, F., Lucidi, S., 10.1007/BF02192227, J. Optimization Theory Appl. 85 (1995), 265-289. (1995) Zbl0830.90125MR1333788DOI10.1007/BF02192227
  13. Facchinei, F., Lucidi, S., Palagi, L., 10.1137/S1052623499359890, SIAM J. Optim. 12 (2002), 1100-1125. (2002) Zbl1035.90103MR1922511DOI10.1137/S1052623499359890
  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. (2005) Zbl1222.68198MR2249875
  15. Gill, P. E., Murray, W., Wright, M. H., Practical Optimization, Academic Press London (1981). (1981) Zbl0503.90062MR0634376
  16. Hager, W. W., Zhang, H., 10.1137/050635225, SIAM J. Optim. 17 (2006), 526-557. (2006) Zbl1165.90570MR2247750DOI10.1137/050635225
  17. Heinkenschloss, M., Ulbrich, M., Ulbrich, S., 10.1007/s101070050107, Math. Program. 86 (1999), 615-635. (1999) Zbl0945.49023MR1733741DOI10.1007/s101070050107
  18. Keerthi, S. S., Gilbert, E. G., 10.1023/A:1012431217818, Mach. Learn. 46 (2002), 351-360. (2002) Zbl0998.68109DOI10.1023/A:1012431217818
  19. Lescrenier, M., 10.1137/0728026, SIAM J. Numer. Anal. 28 (1991), 476-495. (1991) Zbl0726.65068MR1087515DOI10.1137/0728026
  20. Lin, C. J., Moré, J. J., 10.1137/S1052623498345075, SIAM J. Optim. 9 (1999), 1100-1127. (1999) Zbl0957.65064MR1724778DOI10.1137/S1052623498345075
  21. Moré, J. J., Toraldo, G., 10.1137/0801008, SIAM J. Optim. 1 (1991), 93-113. (1991) MR1094793DOI10.1137/0801008
  22. Ni, Q., Yuan, Y., 10.1090/S0025-5718-97-00866-1, Math. Comput. 66 (1997), 1509-1520. (1997) Zbl0886.65065MR1422793DOI10.1090/S0025-5718-97-00866-1
  23. Nocedal, J., Wright, S. J., Numerical Optimization, Springer New York (2006). (2006) Zbl1104.65059MR2244940
  24. Oberlin, C., Wright, S. J., 10.1137/050626776, SIAM J. Optim. 17 (2006), 577-605. (2006) Zbl1174.90813MR2247752DOI10.1137/050626776
  25. Pillo, G. Di, Facchinei, F., Grippo, L., 10.1007/BF01581190, Math. Program. 55 (1992), 49-68. (1992) Zbl0767.90060MR1163293DOI10.1007/BF01581190
  26. Polyak, B. T., 10.1016/0041-5553(69)90035-4, U.S.S.R. Comput. Math. Math. Phys. 9 (1969), 94-112. (1969) Zbl0191.49003DOI10.1016/0041-5553(69)90035-4
  27. Schittkowski, K., More Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, Vol. 282, Springer Berlin (1987). (1987) MR1117683
  28. Sun, L., He, G. P., Wang, Y. L., Fang, L., 10.1016/j.camwa.2009.03.085, Comput. Math. Appl. 58 (2009), 161-170. (2009) Zbl1189.90160MR2535978DOI10.1016/j.camwa.2009.03.085
  29. Sun, L., Fang, L., He, G. P., 10.1007/s10492-010-0022-8, Appl. Math. 55 (2010), 291-304. (2010) Zbl1224.90176MR2737938DOI10.1007/s10492-010-0022-8
  30. Xiao, Y. H., Wei, Z. X., 10.1016/j.amc.2006.06.119, Appl. Math. Comput. 185 (2007), 350-359. (2007) Zbl1114.65069MR2298454DOI10.1016/j.amc.2006.06.119

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.