duminică , 20 ianuarie 2019
roen

Art. 02 – Vol. 28 – Nr. 4 – 2018

Metoda quasi-Newton diagonală bazată pe minimizarea funcţiei Byrd-Nocedal
pentru optimizare fără restricţii

Neculai ANDREI
Institutul Național de Cercetare-Dezvoltare în Informatică – ICI București
B-dul Mareșal Alexandru Averescu, Nr. 8-10, 011455, București, România
nandrei@ici.ro

Rezumat: În această lucrare prezentăm o nouă paradigmă de optimizare fără restricţii care constă în următoarele ingrediente: 1) aproximarea matricei Hessian a funcţiei de minimizat cu o matrice diagonală, în care elementele diagonale sunt pozitive, 2) determinarea valorilor elementelor diagonale prin minimizarea funcţiei măsură a lui Byrd şi Nocedal referitor la ecuaţia secantei slabă a lui Dennis şi Wolkowicz. Algoritmul obţinut este foarte simplu, şi pentru acesta se demonstrează convergenţa liniară. Performanţele numerice ale algoritmului sunt ilustrate prin rezolvarea unui tren de 80 de probleme de test de optimizare fără restricţii de diverse structuri şi complexităţi, precum şi prin rezolvarea a cinci aplicaţii de optimizare fără restricţii cu 10000 sau 40000 de variabile. Comparaţii numerice intensive ale performanţelor acestui algoritm versus algoritmii pasul descendent, Cauchy cu scalare Oren-Luenberger, sau BFGS arată superioritatea abordării propuse în ceea ce priveşte numărul de iteraţii şi timpul de calcul pentru obţinerea unei soluţii optime locale. Noutatea în această abordare este utilizarea funcţiei măsură, care în esenţa ei este un ingredient foarte puternic pentru demonstrarea proprietăţilor teoretice ale algoritmilor de optimizare fără restricţii. Noi am arătat aici importanţa ei şi în ceea ce priveşte generarea de algoritmi eficienţi de optimizare fără restricţii.

Cuvinte cheie: Optimizare fără restricţii, Ecuaţia secantei slabă, Actualizare diagonală quasi-Newton, Funcţia măsură Byrd-Nocedal, Comparaţii numerice.

Introducere

Importanţa metodelor quasi-Newton a fost foarte repede recunoscută. Pentru a fi implementate, este necesară evaluarea gradientului funcţiei de minimizat. Totuşi, unul dintre defectele majore constă în faptul că această metodă cere memorarea aproximaţiei Hessianului sau a inversei acestuia. Deci, aceste metode sunt potrivite pentru rezolvarea problemelor de optimizare cu un număr mediu de variabile (câteva sute). Pentru a îmbunătăţi performanţele metodelor quasi-Newton, mai multe modificări ale acesteia au fost propuse în literatură. De exemplu, anumite metode modifică calculul lungimii pasului, ca în căutarea liniară nemonotonă [32], altele utilizează o nouă căutare liniară de tip Armijo [44], sau o modificare a metodei BFGS nemonotone [45]. În acest articol vom dezvolta un alt mod de abordare bazat pe actualizarea diagonală a Hessianului utilizând minimizarea funcţiei măsură a lui Byrd şi Nocedal.

Bertsekas [14, p. 67] a accentuat că pentru rezolvarea problemelor dificile, tendinţa este de a utiliza metode sofisticate ca metoda Newton sau metode de tip quasi-Nerwton. Deseori acesta este modul de abordare, mai ales pentru probleme prost condiţionate. Totuşi, metode mai simple cu proceduri simple de calcul a direcţiei de căutare şi a lungimii pasului de deplasare sunt mult mai profitabile dacât metodele sofisticate. Aceasta este motivată şi de faptul că proceduri sofisticate de calcul a direcţiei de căutare şi reguli complicate de calcul a lungimii pasului sunt bazate pe presupuneri care nu sunt verificate în cazul problemelor dificile. Cu alte cuvinte, metode simple de optimizare sunt mult mai atractive şi deseori mult mai eficiente pentru rezolvarea problemelor dificile. Totuşi, trebuie să fie un echilibru, o balanţă între simplu şi simplist. Metoda prezentată în acest articol se încadrează în spiritual acestei observaţii.

O idee recentă de a genera algoritmi simpli de minimizare pentru optimizarea fără restricţii constă în aproximarea Hessianului funcţiei de minimizat ca o matrice diagonală cu elemente positive pe diagonala principală. Acest mod de abordare a fost introdus de Nazareth [39], unde aproximarea diagonală a Hessianului este obţinută utilizând ecuaţia secantei propusă de Dennis şi Wolkowicz [21]. Zhu, Nazareth şi Wolkowicz [48] au utilizat un principiu variaţional pentru a determina elementele diagonale care satisfac: ecuaţia secantei, ecuaţia secantei modificată, metoda quasi-Cauchy, sau metoda quasi-Cauchy slabă. Variante ale acestui mod de abordare care nu implică căutarea liniară au fost date de Hassan, Leong şi Farid [31] şi de Leong, Hassan şi Farid [33]. Alte metode îmbunătăţite bazate pe metoda quasi-Cauchy modificată, care utilizează principiul variaţional, au fost dezvoltate şi analizate de Leong, Farid şi Hassan [34] şi Farid, Leong şi Zheng [24]. Toate aceste metode pentru calculul unei actualizări diagonale a Hessianului sunt bazate pe tehnica variaţională introdusă şi utilizată pentru prima dată pentru a se obţine actualizările quasi-Newton Powell-Symmetric-Broyden (PSB) sau Symmetric Rank One (SR1) (vezi Dennis şi Schnabel [20]). La fel ca în metodele quasi-Newton PSB şi SR1, defectul major constă în faptul că aceste actualizări bazate pe tehnici variaţionale pot conduce la matrice care nu sunt pozitiv definite, astfel ruinând complet convergenţa metodei. Pentru a remedia acest defect, Leong, Farid şi Hassan [35] au prezentat metode de scalare a actualizărilor diagonale quasi-Newton care conservă pozitiv definirea acestora.

În acest articol propunem o altă abordare în care Hessianul funcţiei de minimizat este aproximat ca o matrice diagonală pozitiv definită. Elementele acestei aproximări diagonale a Hessianului sunt determinate prin minimizarea funcţiei măsură a lui Byrd şi Nocedal referitor la ecuaţia secantei slabă. Mai precis, elementele diagonale ale matricei care aproximează Hessianul funcţiei de minimizat sunt calculate prin minimizarea funcţiei măsură φ a lui Byrd şi Nocedal [17] referitor la ecuaţia secantei slabă a lui Dennis şi Wolkowicz [21]. Pentru a determina multiplicatorul Lagrange asociat acestei restricţii se sugerează utilizarea condiţiei de conjugare într-o schemă adaptivă bazată pe polii ecuaţiei secantă slabe.

Convergenţa globală se demonstrează pentru funcţii convexe, mărginite inferior şi diferenţiabile, utilizând operatorii trace şi determinant a matricei de iteraţie. Se demonstrează că atât pentru funcţii pătratice cât şi pentru cele nepătratice convergenţa este liniară. Experimente numerice intensive şi comparaţii cu algoritmul lui Barzilai şi Borwein [12], sau cu algoritmul Cauchy cu scalarea Oren şi Luenberger în formă complementară [42] sau cu metoda BFGS clasică arată că metoda sugerată şi algoritmul corespunzător este mult mai eficient şi robust. Experimentele numerice utilizează 80 probleme de test de optimizare fără restricţii descrise în [1], precum şi aplicaţii inginereşti din colecţia MINPACK-2  [8].

Vizualizează articolul complet

COORDONATELE PENTRU CITAREA ACESTUI ARTICOL SUNT URMĂTOARELE:
Neculai ANDREI, Metoda quasi-Newton diagonală bazată pe minimizarea funcţiei Byrd-Nocedal pentru optimizare fără restricţii, Revista Română de Informatică şi Automatică, ISSN 1220-1758, vol. 28(4), pp. 13-36, 2018.

5. Concluzii

Noutatea metodei prezentată în acest articol constă în faptul că elementele diagonale ale matricei diagonale care înmulţeşte gradientul cu semn schimbat sunt determinate prin minimizarea funcţiei măsură a lui Byrd şi Nocedal referitor la ecuaţia secantei slabă a lui Dennis şi Wolkowicz. Algoritmul este simplu. Totuşi, complicaţiile apar când trebuie determinată o valoare a multiplicatorului Lagrange corespunzător problemei de minimizare a funcţiei măsură referitor la ecuaţia secantei slabă. Pentru a evita aceste complicaţii (date de complexitatea funcţiei F (λ)) am introdus şi utilizat condiţia de conjugare proprie algoritmilor de gradient conjugat, precum şi o schemă iterativă bazată pe polul maxim al funcţiei F (λ)). Convergenţa algoritmului este bazată pe operatorii trace şi determinant a matricei de iteraţie, care este numai liniară. Experimentele computaţionale arată că acest mod de abordare care implică funcţia măsură Byrd-Nocedal este superior algoritmului pasului descendent, algoritmului Cauchy cu scalarea Oren şi Luenberger, precum şi algoritmului BFGS pentru clase mari de probleme de optimizare fără restricţii cu diverse structuri şi complexităţi, incluzând aplicaţii complexe din colecţia MINPACK-2. Performanţele algoritmului sunt comparabile cu cele ale algoritmului lui Barzilai şi Borwein. Ceea ce relevă această abordare, bazată pe aproximarea diagonală a matricei Hessian a funcţiei de minimizat, în care elementele diagonale se determină prin minimizarea funcţiei măsură a lui Byrd şi Nocedal referitor la ecuaţia secantei slabă Dennis-Wolkowicz, este faptul că algoritmii quasi-Newton nu sunt foarte tare dependenţi de aproximarea Hessianului funcţiei de minimizat. Observăm că o matrice diagonală (cea mai simplă matrice) poate înlocui cu succes aproximarea n x n-dimensională a Hessianului aşa cum este de exemplu utilizată în metoda BFGS. Evident, preţul pe care trebuie să-l plătim este convergenţa liniară.

Ca o observaţie finală, menţionăm că funcţia măsură Byrd-Nocedal nu este numai un ingredient teoretic foarte important în analiza metodelor quasi-Newton, dar, după cum am arătat, aceasta poate conduce la proiectarea de algoritmi eficienţi şi robuşti de optimizare fără restricţii (vezi [6]).

BIBLIOGRAFIE

  1. Andrei N. An unconstrained optimization test functions collection, Advanced Modeling and Optimization – An Electronic International Journal 2008;10:147-161;
  2. Andrei N. An adaptive conjugate gradient algorithm for large-scale unconstrained optimization. Journal of Computational and Applied Mathematics 2016;292:83-91;
  3. Andrei N. Eigenvalues versus singular values study in conjugate gradient algorithms for largescale unconstrained optimization, Optimization Methods and Software 2017;32(3): 534-551;
  4. Andrei N. Continuous Nonlinear Optimization for Engineering Applications in GAMS Technology. Springer Optimization and Its Applications 121. Springer, Berlin, 2017;
  5. Andrei N. A new three-term conjugate gradient algorithm for unconstrained optimization. Numerical Algorithms 2015;68:305-321;
  6. Andrei, N., A diagonal quasi-Newton updating method based on minimizing the measure function of Byrd and Nocedal for unconstrained optimization. Optimization, DOI: 10.1080/02331934.2018.1482298;
  7. Aris, R., The mathematical theory of diffusion and reaction in permeable catalysts. Oxford, 1975;
  8. Averick BM, Carter RG, Moré JJ, Xue G. The MINPACK-2 test problem collection. Preprint MCS-P153-0692, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, 1992;
  9. Averick, B.M., Carter, R.G., Moré, J.J., The MINPACK-2 test problem collection (Preliminary version), Mathematics and Computer Science Division, Argonne National Laboratory, Thechnical Memorandum No. 150, May 1991;
  10. Babaie-Kafaki S. On optimality of the parameters of self-scaling memoryless quasi-Newton updating formulae. Journal of Optimization Theory and Applications 2015;167(1):91-101;
  11. Babaie-Kafaki S. A modified scaling parameter for the memoryless BFGS updating formula. Numerical Algorithms 2016;72(2):425-433;
  12. Barzilai, J., Borwein, J.M., Two-point step size gradient methods. IMA Journal of Numerical Analysis 1988;8:141-148;
  13. Bebernes, J., Eberly, D., Mathematical problems from combustion theory. Applied Mathematical Sciences 83, Springer-Verlag, 1989;
  14. Bertsekas D.P. Nonlinear Programming. Athena Scientific, Belmont, Massachusetts, 1995;
  15. Boyd, S., Vandenberghe, L., Convex Optimization. Cambridge University Press, Cambridge, 2004;
  16. Broyden CG. The convergence of a class of double-rank minimization algorithms. I. General considerations, J. Inst. Math. Appl. 1970;6:76-90;
  17. Byrd R, Nocedal J. A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM Journal on Numerical Analysis 1989;26:727-739;
  18. Cimatti, G., Menchi, O., On the numerical solution of a variational inequality connected with the hydrodynamic lubrication of a complete journal bearing. Calcolo, 15, (1978), pp.249-258;
  19. Davidon WC. Variable metric method for minimization. Technical Report ANL-5990 (revised), Argonne National Laboratory, Argonne, Il, 1959;
  20. Dennis JE, Schnabel RB, Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice Hall Series in Computational Mathematics, Prentice Hall, Englewood Cliffs, NJ, 1983;
  21. Dennis JE, Wolkowicz H. Sizing and least-change secant methods, SIAM J. Numerical Analysis, 1993;30(5):1291-1314;
  22. Dolan ED, Moré JJ. Benchmarking optimization software with performance profiles, Mathematical Programming 2002;91:201-213;
  23. Elliot, C.M., Ockendon, J.R., Weak and variational methods for moving boundary problems. Research Notes in Mathematics, vol.59, Pittman, 1982;
  24. Farid M. Leong WJ, Zheng L. A new diagonal gradient-type method for large scale unconstrained optimization. U.P.B. Sci. Bull., Series A, 2013;75(1):57-64;
  25. Fletcher R, Powell MJD. A rapidly convergent descent method for minimization. Computer Journal, 1963;6:163-168;
  26. Fletcher R. A new approach to variable metric algorithms, The Computer Journal 1970;13: 317-322;
  27. Fletcher R. A new variational result for quasi-Newton formulae. SIAM Journal on Optimization 1991;1:18-21;
  28. Glowinski, R., Numerical Methods for Nonlinear Variational Problems. Springer-Verlag, Berlin, 1984;
  29. Goldfarb D. A family of variable metric methods derived by variation mean, Mathematics of Computation 1970;23:23-26;
  30. Goodman, J., Kohn, R., Reyna, L., Numerical study of a relaxed variational problem from optimal design. Comput. Methods Appl. Mech. Engrg., 57, 1986, pp.107-127;
  31. Hassan MA, Leong WJ, Farid M. A new gradient method via quasi-Cauchy relation which guarantees descent. J. Comput. Appl. Math. 2009;230(1):300-305;
  32. Huang, S., Wan, Z., Zhang, J. An extended nonmonotone line search technique for large-scale unconstrained optimization. Journal of Computational and Applied Mathematics 2018;330:586-604;
  33. Leong WJ, Hassan MA, Farid M. A monotone gradient method via weak secant equation for unconstrained optimization. Taiwanese J. Math. 2010;14(2):413-423;
  34. Leong WJ, Farid M, Hassan MA. Improved Hessian approximation with modified quasiCauchy relation for a gradient-type method. AMO–Advanced Modeling and Optimization, 2010;12(1):37-44;
  35. Leong WJ, Farid M, Hassan MA. Scaling on diagonal quasi-Newton update for large-scale unconstrained optimization. Bull. Malays. Math. Sci. Soc. 2012;35(2):247-256;
  36. Lin, Y., Cryer, C.W., An alternating direction implicit algorithm for the solution of linear complementarity problems arising from free boundary problems. Appl. Math. Optim., 13, 1985, pp.1-17;
  37. Luenberger, DG, Ye, Y. Linear and Nonlinear Programming. Fourth Edition. Springer, International Series in Operations Research & Management Science. New York, 2016;
  38. Moré, J.J., Toraldo, G., On the solution of large quadratic programming problems with bound constraints. SIAM J. Optimization, 1, 1991, pp.93-113;
  39. Nazareth J.L., If quasi-Newton then why not quasi-Cauchy? SIAG/Opt Views-and-news 1995; 6:11-14;
  40. Nitsche, J.C.C., Lectures on minimal surfaces. Vol.1, Cambridge University Press, 1989;
  41. O’Leary, D.P., Yang, W.H., Elastoplastic torsion by quadratic programming, Comput. Methods Appl. Mech. Engrg., 16, 1978, pp.361-368;
  42. Oren SS, Luenberger DG. Self-scaling variable metric (SSVM) algorithms. Management Science. 1974;20(5):845-862;
  43. Shanno DF. Conditioning of quasi-Newton methods for function minimization, Mathematics of Computation 1970;24:647-656;
  44. Wan, Z., Teo, KL., Shen, XL. New BFGS method for unconstrained optimization problem based on modified Armijo line search. Optimization: A Journal of Mathematical Programming and Operations Research 2014;63(2):285-304;
  45. Wan, Z., Chen, Y., Huang, S., DongFeng, D. A modified nonmonotone BFGS algorithm for solving smooth nonlinear equations. Optimization Letters 2014;8:1845-1860;
  46. Wolfe P. Convergence conditions for ascent methods. SIAM Review, 1969;11:226-235;
  47. Wolfe P. Convergence conditions for ascent methods. II: Some corrections. SIAM Review 1971;13:185-188;
  48. Zhu M, Nazareth JL, Wolkowicz H. The quasi-Cauchy relation and diagonal updating. SIAM Journal on Optimization 1999;9(4):1192-1204;
  49. Zoutendjik G. Nonlinear programming, computational methods. In J. Abadie (Ed.) Integer and Nonlinear Programming, North-Holland, Amsterdam, 1970;37-86.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.