marți , 23 aprilie 2019
roen

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 Averescu nr. 8-10, București, 011455, 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.

Vizualizează articolul complet