Descrierea problemei şi a metodelor de rezolvare utilizate

BIBFR rezolvă problema min{ƒ(x):x∈ℜn)}, unde ƒ:ℜn→ℜ este o funcţie neliniară, generală, continuu diferenţiabilă pentru care se cunoaşte gradientul f(x) g(x)(expresia analitică). Pentru rezolvarea acestei probleme se utilizează metode de gradient conjugat.

Date de intrare şi ieşire

În principal, în BIBFR sunt implementate doi algoritmi de optimizare fără restricţii CGALL şi SCALCG. Structura acestor programe este formată dintr-un program principal care apelează un număr de subrutine. Datele de intrare şi de ieşire asociate acestor pachete de programe sunt următoarele:

1. CGALL, care implementează cei 23 de algoritmi de gradient conjugat.
2. SCALCG, care implementează algoritmul de gradient conjugat BFGS precondiţionat cu restartare.

Implementarea în mediul Grid

Biblioteca de programe de optimizare în esenţă este o colecţie de programe de optimizare, fiecare dintre acestea având propriile sale definiţii, intrări, ieşiri şi performanţe. Pentru cazul problemelor de optimizare neliniară nu este posibilă o standardizare unanim acceptată. Chiar dacă au fost încercări de impunere a unui standard de prezentare a funcţiilor problemei, introdus în cadrul colecţiei CUTE ^[1], totuşi acesta nu a fost acceptat ca formă tipică de prezentare a funcţiilor problemei. Dificultatea constă în faptul că pe lângă funcţiile de definiţie a problemei este necesar să se introducă şi gradienţi acestora, ceea ce constituie o problemă mai ales pentru cazul problemelor de mari dimensiuni si puternic neliniare.

În GridMOSI arhitectura bibliotecii de programe de optimizare se structurează pe o colecţie de programe Fortran dedicate rezolvării problemelor de minimizare a funcţiilor neliniare suficient de netede (pentru care se poate calcula gradientul şi acesta este o funcţie continuă) în absenţa restricţiilor. Ideea utilizării acestor programe este de a le plasa în secţiunea de repository a lui GridMOSI cu scopul de a fi utilizate de cei interesaţi în aşi rezolva aplicaţii în care intervine o optimizare fără restricţii.

Tehnologia de utilizare a acestor programe de optimizare este următoarea:

1. Utilizatorul îşi defineşte problema de optimizare fără restricţii în sensul de a preciza expresia algebrică a funcţiei de minimizat, precum şi punctul iniţial de unde începe căutarea minimului. Aici este necesar un studiu privind domeniul de definiţie a funcţiei şi a modului cum aceasta este definită. Este important de notat faptul că multe probleme de optimizare provin din discretizarea unor ecuaţii diferenţiale cu derivate parţiale. Ca atare, este necesar să se asigure introducerea condiţiilor la limită, precum şi proceduri de calcul a punctului iniţial.
2. Odată definită funcţia de minimizat următoarea etapă constă în a defini expresia algebrică a gradientului acestei funcţii. Şi în acest caz este necesar un studiu privind buna definire a gradientului şi a domeniului lui de definiţie.
3. În acest moment utilizatorul va elabora o subrutină (Fortran) de calcul a valorii funcţiei şi a gradientului într-un punct dat. Secvenţa de apel şi structura acestei subrutine sunt simple şi au o oarecare standardizare. În pachetele pe care le prezentăm (SCALCG şi CGALL) în aceeaşi subrutină sunt incluse atât expresia Fortran a funcţiei de minimizat, cât şi expresia Fortran a gradientului acesteia. Menţionăm faptul că alte programe de optimizare utilizează două subrutine în acest sens, una pentru funcţia de minimizat şi alta pentru gradient.
4. Pentru rezolvarea problemei este necesară definirea unui punct iniţial de unde să se demareze calculele. Soluţia oferită în cadrul programelor SCALCG şi CGALL este de a construi o mică subrutină care să genereze punctul iniţial. Secvenţa de apel şi structura acestei subrutine este foarte simplă.
5. Următoarea etapă constă în compilarea separată a subrutinei cu funcţia şi gradientul problemei, a celei care precizează punctul iniţial, elaborate de utilizator, precum şi a programului Fortran (SCALCG sau CGALL) care va invoca această subrutină pentru rezolvarea problemei şi care se găseşte în GridMOSI.
6. Odată compilate şi eliminate erorile de compilare, următoarea etapă constă în a executa un link al acestor obiecte în sensul de a construi un program executabil care să rezolve problema. Referitor la modul de comunicare a problemei şi rezolvarea ei în structura GridMOSI, soluţia aleasă constă în a accesa în mod direct GridMOSI de la distanţă în sensul de a transmite subrutinele asociate problemei, lansarea task-bildării şi apoi a execuţiei task-ului generat pe un cluster sau în reţea.

Justificare

Utilizarea unui software de optimizare avansat impune o serie de restricţii utilizatorului în ceea ce priveşte înţelegerea, conştientizarea şi operarea cu secvenţe de program (Fortran) prefabricate. Această manieră de a utiliza subrutine (Fortran) în procesul de rezolvare a unei probleme de optimizare este impusă de faptul că prin natura lucrurilor algoritmii de optimizare sunt deosebiţi de sofisticaţi, care implementează concepte matematice avansate de foarte mare subtilitate. Sarcina utilizatorului este de aşi formula problema ca una de optimizare fără restricţii şi a o exprima într-o secvenţă de instrucţiuni Fortran, precum şi construcţia unui task asociat problemei. În GRIDMOSI utilizatorul trebuie să-şi paralelizeze codul Fortran care implementează aplicaţia. Această cerinţă este cu atât mai stringentă cu cât evaluarea funcţiei şi a gradientului acesteia este mai consumatoare de timp.

Soluţia de implementare

Soluţia de implementare a bibliotecii de programe de înaltă performanţă pentru optimizare fără restricţii constă în elaborarea unor implementări Fortran a algoritmilor de optimizare şi plasarea lor în mediu GRID ca resurse de încredere pentru rezolvarea problemelor de optimizare fără restricţii de mari dimensiuni. În acest context se face o dihotomie clară între pachetul de optimizare propriu-zis şi subrutina (sau subrutinele) care implementează aplicaţia care se rezolvă. În GRIDMOSI pachetul de optimizare este paralelizat. Paralelizarea aplicaţiei, adică a codului Fortran care implementează aplicaţia respectivă revine utilizatorului. Menţionăm faptul că algoritmii de optimizare utilizaţi în acest proiect sunt bazaţi pe gradientul funcţiei de minimizat, implementarea acestora utilizând în esenţă produse scalare a unor vectori. Ideea a fost de a evita pe cât posibil lucrul cu matrice. Aceasta face ca paralelizarea codurilor Fortran să se concentreze numai pe paralelizarea produselor scalare.

Cerinţe privind infrastructura Grid

Din punctul de vedere al optimizării fără restricţii considerate în acest proiect, nu sunt cerinţe speciale referitor la infrastructura Grid

Interfaţa de utilizare

Biblioteca de optimizare este formată dintr-o colecţie de subrutine Fortran. Fiecare dintre acestea are propria secvenţă de apel. Utilizarea acestor subrutine în sensul asamblării unui program Fortran pentru rezolvarea unei aplicaţii concrete implică organizarea şi apelul corect al acestora conform argumentelor formale şi a tipului acestora din secvenţa de apel. Utilizatorul având acces la codul Fortran al acestor subrutine poate introduce secvenţe suplimentare de cod care să implementeze dorinţele sale privind datele de ieşire a procesului de optimizare, sau cantitatea şi formatul în care soluţia se poate prezenta. În principal, interfaţa la intrare este foarte simplă, utilizatorului cerându-i-se furnizarea subrutinelor care implementează aplicaţia şi punctul iniţial.

Avantaje

Migrarea în mediul Grid, cel puţin din punctul de vedere al optimizării, este discutabilă. Biblioteca de programe de înaltă performanţă pentru optimizare fără restricţii implementează algoritmi foarte puternici pentru care s-a demonstrat (în fazele anterioare) convergenţa la soluţie şi în unele cazuri complexitatea super-liniară. Mai mult, aceşti algoritmi au fost implementaţi în coduri Fortran profesionale care au fost comparate cu alte implementări profesionale a unor algoritmi bazaţi pe o altă paradigmă algoritmică computaţională (metoda LBFGS şi Metoda Newton Trunchiată). Implementările algoritmilor care fac obiectul acestei biblioteci sunt paralelizate în sensul paralelizării produselor scalare.

Avantajul utilizării mediului Grid pentru rezolvarea unei aplicaţii concrete, şi deci obţinerea de performanţe superioare, se obţine atunci când aplicaţia este paralelizată. Ideea este că în mediul Grid se impune cu necesitate rezolvarea unor aplicaţii complexe care implică masive mari de date şi calcule numerice intensive pentru determinarea valorilor funcţiei de minimizat şi a gradientului acesteia. În această situaţie biblioteca de programe de optimizare în mediul Grid are o justificare şi prezintă avantaje nete.

Potenţial de utilizare

Descrierea rezultatelor

Biblioteca de programe pentru optimizare fără restricţii permite efectuarea de nenumărate teste numerice privind performanţa algoritmilor implementaţi. În această fază vom prezenta un număr limitat de rezultate privind performanţele pachetului CGALL în mediu Grid. În acest sens am considerat rezolvarea unui tren de 500 de probleme de test cu numărul de variabile cuprins între 1000 şi 10000 pe care le-am rezolvat cu CGALL (betatype=1) şi pentru care codul care le implementează nu a fost paralelizat.

Evaluarea impactului ştiinţific şi social

Biblioteca de programe de înaltă performanţă pentru optimizare fără restricţii conţine, după cum am spus, două pachete Fortran care implementează 24 de algoritmi. Aceste pachete sunt foarte generale şi se pot utiliza pentru rezolvarea oricărei probleme de optimizare fără restricţii pentru care funcţia de minimizate are gradient. În această bibliotecă au fost incluse şi testate un număr de 7 aplicaţii industriale formulate ca probleme de optimizare fără restricţii:

1. Elastic-Plastic Torsion Problem;
2. Pressure Distribution in a Journal Bearing Problem;
3. Optimal Design with Composite Materials Problem;
4. Inhomogeneous Superconductors. 1-dimensional Ginzburg-Landau Problem;
5. Steady State Combustion. Solid Fuel Ignition;
6. Lennard-Jones Cluster Problem;
7. Minimal surface area.

Aceste aplicaţii, conţinute şi în biblioteca MINPACK-2, (The Mathematics and Computer Science Division at Argonne National Laboratory) ^[2] au fost descrise în fazele anterioare ale acestui proiect şi constituie probleme de optimizare de mari dimensiuni din mediul industrial.

Evident, prin modelul matematic foarte general al problemei de optimizare considerate, biblioteca BIBFR se adresează unei comunităţi foarte largi de utilizatori.

Referințe

1. ↑ [Bongartz, Conn, Gould, Toint, 1995]
2. ↑ [Averick, Carter, Moré, 1991]