mod_C

Ministero dell'Universita' e della Ricerca scientifica e tecnologica

Programmi di ricerca cofinanziati - Modello C
Rendiconto di unita' di ricerca - ANNO 1997
prot. 9701091751_024

1. Area Scientifico Disciplinare principale 01: Scienze matematiche

2. Coordinatore Scientifico del programma di ricerca

3. Titolo del programma di ricerca

ANALISI NUMERICA: METODI E SOFTWARE MATEMATICO

4. Responsabile Scientifico dell'Unità di ricerca

5. Titolo del programma dell'unità di ricerca

Metodi numerici per alcuni problemi di ottimizzazione non lineare

6. Settore principale del Programma di Ricerca: A04A - Analisi numerica

7. Finanziamenti assegnati all'unità di ricerca

8. Obiettivo della ricerca eseguita

Ci si propone di produrre un insieme di efficienti elementi di software matematico per la risoluzione di problemi di programmazione quadratica con vincoli semplici sulle variabili. Particolare interesse è rivolto all'utilizzo di calcolatori paralleli con architettura a memoria distribuita. Si ritiene che i moduli prodotti possano essere elementi di base per la costruzione di efficienti software paralleli per più generali problemi di ottimizzazione vincolata.

9. Descrizione della Ricerca eseguita e dei risultati ottenuti

L'interesse è stato rivolto allo studio di metodi e alla progettazione di algoritmi e software parallelo per la risoluzione di alcuni problemi di ottimizzazione non lineare su calcolatori MIMD a memoria distribuita. In particolare, sono stati affrontati i seguenti problemi. 

1) Problemi di ottimizzazione convessa. 
L'interesse è stato rivolto allo sviluppo di algoritmi paralleli basati sui metodi row-action, che sono stati oggetto di ricerca anche nel campo della risoluzione di sistemi lineari sparsi. L'attenzione è stata rivolta ad un metodo di tipo row-action in cui, ad ogni iterazione, si ha un sottoproblema che consiste nel determinare il minimo della funzione obiettivo sottoposta a uno o due vincoli lineari di uguaglianza, i quali costituiscono una linearizzazione dei vincoli del problema di partenza. Relativamente a tale metodo sono state sviluppate e analizzate sia la versione a blocchi sia quella simultanea. E' stato sviluppato un elemento di software, in linguaggio Fortran, che utilizza routine della libreria LAPACK, per la risoluzione di problemi con funzione obiettivo quadratica e vincoli non lineari. 

2) Programmazione quadratica con vincoli di bound. 
In tale ambito l'attività di ricerca è stata rivolta ad una analisi comparata dei metodi basati su strategie a vincoli attivi con metodi a punto interno. Con tale analisi si è voluto in particolare confrontare l'efficienza dei due approcci su macchine parallele. Se infatti per i suddetti metodi esiste una ampia e consolidata letteratura scientifica che ne descrive i problemi e le caratteristiche di implementazione su macchine ad architettura sequenziale, non esistono risulati altrettanto consolidati circa l'implementazione parallela di metodi per programmazione quadratica. 
Nella attività di ricerca sviluppata dall'unità operativa, in particolare, sono stati sviluppati due elementi di software parallelo per il caso di problemi densi: il primo è basato su un algoritmo che usa il metodo del Gradiente Proiettato (GP) per accelerare l'identificazione dell'active set ottimale; il secondo implementa un metodo interior point (IP) basato sull'idea di ridurre, ad ogni iterazione, una opportuna funzione logaritmica, in modo da garantire la convergenza dei punti interni alla soluzione. Tali metodi sono stati scelti in quanto ben rappresentativi delle due classi di algoritmi sopra menzionate. Il parallelismo è introdotto al livello dei nuclei computazionali di algebra lineare. Il software, scritto in FORTRAN, è stato sviluppato utilizzando il sistema di comunicazione BLACS e la libreria ScaLapack. I risultati ottenuti hanno ampiamente confermato le qualità intrinseche e la robustezza dei due metodi scelti che si sono dimostrati pressocchè equivalenti sulla maggior parte dei problemi test utilizzati, relativamente ad una loro implementazione sequenziale; si osservi comunque che l'implementazione del metodo GP comunque risulta più complessa. 
Dal punto di vista del parallelismo, il metodo IP si è dimostrato di gran lunga più efficiente del GP, essendo l'implementazione di quest'ultimo fortemente penalizzata da problemi di difficile bilanciamento sia del carico computazionale che dei dati sui differenti processori. Al contrario, l'implementazione del metodo IP, basata essenzialmente su pacchetti di software parallelo standard e ben consolidati (es. PBLAS) ha mostrato notevoli doti di efficienza e portabilità. Tali considerazioni, almeno sulla base di esperienze numeriche preliminari, paiono generalizzabili anche a problemi sparsi.

10. Pubblicazioni

11. Prodotti della Ricerca eseguita

La ricerca eseguita ha prodotto, oltre ad alcune pubblicazioni e comunicazioni a convegni nazionali ed internazionali (punto 15 del modello), alcuni elementi di codice in linguaggio di programmazione FORTRAN. In particolare sono stati prodotti elementi software che implementano un metodo Interior Point e un metodo a Gradiente Proiettato per problemi di programmazione quadratica convessa con vincoli semplici; per entrambi è stata prodotta una versione sequenziale e una versione parallela. E' stato inoltre sviluppato un elemento di software, per la risoluzione di problemi con funzione obiettivo quadratica e vincoli non lineari, che implementa un metodo di tipo row-action.

12. Componenti dell'Unità di ricerca che hanno effettivamente partecipato alla ricerca
Personale docente

Altro personale

Personale a contratto

13. Note relative ai componenti (p.12)

14. Risorse umane complessivamente ed effettivamente impegnate

15. Dati complessivi relativi al programma

16. Tabella delle spese sostenute: cifre spese, rimaste da pagare o impegnate(*)
(*) Da Impegnare LIMITATAMENTE a Pubblicazioni e Partecipazioni a Convegni e Congressi SOLAMENTE se inerenti i risultati della Ricerca cofinanziata per i quali si richiedera' successiva rendicontazione

Si ricorda che ogni variazione rispetto al Programma Iniziale sulla composizione delle Unità Operative e sulla diversa utilizzazione dei Fondi, doveva essere comunicata al Dipartimento Affari Economici come da nota n. 1709 del 22.7.98.

(per la copia da depositare presso l’Ateneo e per l’assenso alla diffusione via Internet delle informazioni riguardanti i programmi finanziati legge del 31.12.96 n° 675 sulla "Tutela dei dati personali")