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

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