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_003

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

Ottimizzazione numerica e risoluzione di sistemi di grandi dimensioni.

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

7. Finanziamenti assegnati all'unità di ricerca

8. Obiettivo della ricerca eseguita

Analisi e sviluppo di metodi numerici per la risoluzione di problemi di ottimizzazione di grandi dimensioni (problemi dei minimi quadrati, problemi di gestione del traffico, problemi di controllo ottimo e problemi mal posti retti da equazioni integrali di I specie) e per la risoluzione di problemi retti da leggi di conservazione non lineari (equazioni cinetiche, sistemi iperbolici con rilassamento). 
Particolare attenzione e' rivolta allo sviluppo su architetture di calcolo parallele.

9. Descrizione della Ricerca eseguita e dei risultati ottenuti

La ricerca eseguita ha prodotto risultati originali che riguardano le seguenti tematiche: 
1) risoluzione di problemi di ottimizzazione di grandi dimensioni 
2) risoluzione di problemi retti da leggi di conservazione non lineari. 


Tematica n. 1

Nell'ambito dell'Ottimizzazione Numerica ci si e' occupati di metodi iterativi per problemi di programmazione quadratica (QP) convessi con vincoli lineari con Hessiana sparsa e/o con struttura, di medio-grandi dimensioni, puntando l'attenzione su tre classi di metodi: i metodi di tipo proiezione, quelli del punto interno e quello di Hestenes. 
In particolare e' stata svolta un'analisi completa, teorica e sperimentale, sui metodi di tipo proiezione [4]: e' stato elaborato uno schema iterativo generale basato sulla risoluzione di una sequenza di sottoproblemi QP aventi gli stessi vincoli del problema originario, con una matrice Hessiana dipendente da un parametro positivo (che puo' variare ad ogni iterazione), definita positiva e semplice da invertire (diagonale o diagonale a blocchi). Entro tale schema, di cui e' stata dimostrata la convergenza sotto l'ipotesi della sola limitatezza della successione dei parametri di proiezione, sono stati unificati gli algoritmi classici di decomposizione, di proiezione e di proiezione modificata di Bertsekas e i nuovi metodi proposti a proiezione variabile [5,8]. 
Sono state valutate le caratteristiche di efficienza computazionale di questi nuovi schemi, proponendo alcune regole di aggiornamento adattivo del parametro di proiezione, non costose ed efficaci numericamente. I metodi a proiezione variabile sono stati valutati numericamente su problemi test con prefissate caratteristiche operando un confronto con routine della libreria NAG, con metodi classici di decomposizione, di proiezione e con i recenti metodi di proiezione modificata [6,8]. 
La costruzione dei suddetti problemi test e' uno dei prodotti software della ricerca, disponibile in rete (http://www.unife.it/AnNum97/software.htm) e documentato dalla monografia n. 6 del progetto (C. Durazzi, V. Ruggiero, L. Zanni: A Random Generator for Large-Scale Linearly Constrained Quadratic Programming Test-Problems). 
Le potenzialita' dei metodi a proiezione variabile sono state valutate sia su una serie di applicazioni che riguardano l'analisi dei dati (interpolazione bivariata mediante superfici di classe C1, riconoscimento di forme, ecc.)[7], sia come solutori interni per metodi di approssimazione del costo per la risoluzione di disequazioni variazionali che capitano nella determinazione dell'equilibrio di reti di trasporto e che presentano vincoli molto sparsi con struttura particolare. 
L'individuazione di opportuni risolutori interni per i sottoproblemi QP che capitano entro i metodi di tipo proiezione ha portato a confrontare vari algoritmi paralleli, e a proporne uno originale, per il problema misto di complementarita' lineare (LCP), cui e' conveniente ricondurre un sottoproblema QP quando il numero di vincoli e' rilevante. Di conseguenza, sono stati sviluppati codici relativi a metodi di proiezione su Cray T3E, valutando i risolutori interni paralleli presi in esame in dipendenza della sparsita' della matrice di complementarita' lineare, della dimensione del problema e del numero di processori disponibili [2]. 
I prodotti di tale ricerca, realizzati in collaborazione con l'Unita' di Modena, sono costituiti da una serie di pubblicazioni scientifiche e di comunicazioni a convegni e da un software per la valutazione numerica dei metodi di tipo proiezione, disponibile in rete (http://www.unife.it/AnNum97/software.htm) e documentato dalla monografia n. 5 del progetto (E. Galligani, V. Ruggiero, L. Zanni: Projectin-Type Methods for Large Convex Quadratic Programs: Theory and Computational Experience). 
E' stata intrapresa un'indagine sui metodi di punto interno ottenendo risultati teorici e numerici significativi sui parametri caratterizzanti tali metodi e sulla loro relazione con i metodi di Newton inesatti [10,12]. In particolare l'analisi sul parametro di perturbazione (presente nelle equazioni derivanti dalle condizioni di complementarita') e' stata utilizzata nell'applicazione di tali metodi a problemi di controllo [9]. 
Per problemi QP con vincoli lineari di uguaglianza e' stata affrontata l'analisi del metodo di Hestenes: si e' provato che tale metodo coincide con la tecnica di raffinamento iterativo di Van Loan per il metodo delle pesate usato per la risoluzione del problema dei minimi quadrati con vincoli di uguaglianza. Il metodo di Hestenes e' stato impiegato entro un algoritmo di minimizzazione con un solo vincolo di uguaglianza a convergenza rapida per il problema speciale degli autovalori di matrici simmetriche sparse e di grandi dimensioni. 
Oltre all'analisi teorica dell'algoritmo, per il quale viene provata una convergenza del quart'ordine, vengono forniti i criteri per una sua applicazione pratica. Esperimenti numerici sul Cray C90 mostrano il buon comportamento del metodo di minimizzazione come tecnica di accelerazione dell'iterazione inversa [1]. 
In [11] il metodo di Hestenes e' stato usato per la risoluzione di problemi di controllo ottimo lineari-quadratici discreti con vincoli di uguaglianza sullo stato iniziale e finale. Per tali problemi sono state date trascrizioni in termini di problemi QP con vincoli lineari di uguaglianza, fornendo le condizioni necessarie e sufficienti per l'esistenza e l'unicita' della soluzione di entrambe le trascrizioni. Tali condizioni assicurano anche la convergenza del metodo di Hestenes; quest'ultimo, accoppiato con il metodo del gradiente coniugato e con una tecnica di normalizzazione, ben si presta ad una implementazione parallela e risulta conveniente per problemi mediamente mal condizionati [3]. 
L'attivita' finora illustrata e' stata realizzata in collaborazione con il Prof. E. Galligani ed il Prof. L. Zanni dell'Universita' di Modena. Grazie a questa ricerca, si e' instaurata una collaborazione con il Prof. M. Patriksson dell'Universita' di Goteborg (Svezia). 
Come applicazione nell'ambito della soluzione numerica di sistemi di equazioni non lineari su architetture a memoria distribuita, sono state analizzate alcune modifiche a metodi iterativi quasi-newtoniani applicati a sistemi non lineari bordati a blocchi, che conservano le caratteristiche di convergenza superlineare locale e di convergenza globale e sfruttano efficientemente la struttura intrinsecamente parallela del sistema [21,22]. L'introduzione di tecniche di globalizzazione basate su minimizzazioni non monotone ha consentito di migliorare sensibilmente l'efficienza e di evitare alcune delle tipiche difficoltà che s'incontrano nella soluzione di sistemi non lineari con metodi classici [23,24]. Grazie a questa ricerca, si e' instaurata una collaborazione con il Prof. Oleg Burdakov dell'Universita' di Linkoping (Svezia). 
Come applicazione all'ottimizzazione, in collaborazione con le Unita' di Bologna e di Firenze sono state studiate le tecniche per la ricostruzione di dati dinamici sottocampionati in Risonanza Magnetica Nucleare Funzionale (fMRI), realizzando un toolbox di MATLAB, chiamato MRITool e disponibile in rete (http://www.unife.it/software.htm), che permette di usare diverse tecniche di ricostruzione con regolarizzazione (TSVD, Lavrent'yev, gradienti coniugati) e di confrontarne i risultati sulla base di dati reali [25]. Il toolbox e' documentato nella monografia n. 2 del progetto (E. Loli Piccolomini, F. Zama, G. Zanghirati, A.R. Formiconi, S. Martini: "MRITool: a Matlab tool for functional Magnetic Resonance Imaging reconstruction"). 


Tematica n. 2

Sono state studiate l'accuratezza spettrale e la stabilità di un metodo spettrale di Fourier-Galerkin per l'approssimazione dell'operatore integrale di Boltzmann. In particolare si è dimostrata la consistenza del metodo e sono stati determinati algoritmi semplificati per le situazioni di maggiore interesse fisico. Recentemente tale metodo è stato generalizzato ed esteso anche ad altre equazioni integrodifferenziali, quale ad esempio l'equazione di Landau-Fokker-Planck della fisica dei plasmi [19]. Questo ha consentito di sviluppare algoritmi rapidi dal costo ridotto di O(N log N) rispetto al costo convenzionale di O(N2). Tale ricerca è stata condotta in collaborazione con il Prof. G. Russo dell'Università dell'Aquila e il Prof. G. Toscani dell'Università di Pavia. 
Sono stati costruiti alcuni metodi Monte Carlo basati sulla discretizzazione temporale introdotta in [14]. Tali metodi, denominati metodi Monte Carlo a Tempo Rilassato (TRMC) consentono di approssimare problemi stiff in gas dinamica con una accuratezza ed una efficienza maggiore rispetto ai tradizionali metodi Monte Carlo. Classicamente il problema viene affrontato tramite metodi di decomposizione del dominio, dividendo il dominio in una regione aereodinamica dove si risolvono le equazioni di Eulero, ed una regione cinetica, dove si risolve l'equazione di Boltzmann. I metodi Monte Carlo sviluppati rappresentano un alternativa a tale approccio, o quantomeno garantiscono una realizzazione più efficiente di tale tecnica, in quanto consentono di utilizzare lo stesso risolutore Monte-Carlo, senza un incremento del costo computazionale, anche per grandi variazioni del parametro di stiffness dato dal libero cammino medio tra le particelle [16]. La ricerca e' stata condotta in collaborazione con ricercatori R. E. Caflisch di UCLA, Los Angeles, USA e B.Perthame dell'Ecole Normale Superieure di Parigi, Francia. 
Sono stati analizzati problemi che coinvolgono scale multiple nello spazio e nel tempo o in altri parametri fisicamente rilevanti [20]. Questi problemi sono caratterizzati da una notevole complessità e rappresentano una sfida dal punto di vista analitico e computazionale. Uno strumento efficace per la comprensione dei fenomeni e' dato dall'approssimazione asintotica. Spesso questo consente di scartare le scale più piccole e di sostituirle con equazioni di tipo semplificato. Da un punto di vista numerico, il calcolo di problemi multiscala solitamente richiede una qualche risoluzione delle scale piccole. D'altro canto nella maggioranza delle applicazioni si richiede una buona descrizione delle proprietà fisiche a livello macroscopico. In tali casi, è desiderabile avere metodi numerici in cui i parametri di discretizzazione sono indipendenti dalle piccole scale ma che descrivano in modo corretto il comportamento delle equazioni limite. In [13] abbiamo costruito uno schema numerico semi-implicito che risulta efficace per approssimare la soluzione vicino ai regimi stiff. Una tecnica generale per la costruzione di tali metodi è stata sviluppata successivamente [15]. Utilizzando il metodo delle linee combinato ad un metodo Runge-Kutta si sono costruiti schemi robusti per valori arbitrari dei parametri di stiffness. Lo stesso tipo di tecnica è stata poi estesa al caso generale di sistemi di leggi di conservazione multiscala. Tali metodi sono stati studiati in collaborazione con il Prof. G. Naldi e il Prof. T. Scapolla dell'Unità di Pavia e il Prof. S. Jin del Georgia Tech di Atlanta, USA. 



1. Galligani E., Ruggiero V., Zanni L.: A minimization method for the solution of large symmetric eigenproblems -Intern. J. Computer Math. 70 (1998), 99-115. 
2. Galligani E., Ruggiero V, Zanni L.: Parallel solution of large scale quadratic programs - High Performance Algorithms and Software in Nonlinear Optimization (R. De Leone, A. Murli, P. Pardalos, G. Toraldo eds.) Kluwer Academic Publ., Dordrecht (1998), 189-205. 
3. Galligani E., Durazzi C.: Numerical solution of discrete quadratic optimal control problems - NMA '98 Proceedings, World Scientific Publishing Company (1998). 
4. Ruggiero V, Zanni L.: On a class of iterative methods for convex large--scale quadratic programs - Numerical Methods in Optimization, Maugeri A., Galligani E. eds, Rend. Circ. Matem. Palermo, Serie II Suppl. 58 (1999), 213-227. 
5. Ruggiero V., Zanni L.: A modified projection algorithm for large strictly convex quadratic programs - Journal of Optimization Theory and Applications 104, n. 2 (2000), 255-279. 
6. Ruggiero V., Zanni L.: On the efficiency of splitting and projection methods for large strictly convex quadratic programs - Nonlinear Optimization and Related Topics (G. Di Pillo, F. Giannessi eds.), Kluwer Academic Publishers (2000), 401-414. 
7. Ruggiero V., Zanni L.: Splitting and Projection-Type Methods for Large Convex Quadratic Programs - Annali Universita' di Ferrara, Suppl. n. 46 (2000), 521-540. 
8. Ruggiero V., Zanni L.: An Overiview on Projection-Type Methods for Convex Large-Scale Quadratic Programs - Equilibrium Problems and Variational Models (A. Maugeri, F. Giannessi P. Pardalos eds.), Kluwer Academic Press (2000). 
9. Durazzi C., Galligani E.: Nonlinear Programming Methods for Solving Optimal Control Problems - Equilibrium Problems and Variational Models (A. Maugeri, F. Giannessi P. Pardalos eds.), Kluwer Academic Press (2000). 
10. Durazzi C., Galligani E.: Solution of discrete Optimal Control Problems via Mathematical Programmino - Annali Universita' di Ferrara, Suppl. n. 46 (2000), 493-505. 
11. Durazzi C.: Numerical solution of discrete quadratic optimal control problems by Hestenes' method - Rend. Circ. Matem. Parlemo, Serie II Suppl. 58 (1999), 133-154. 
12. Durazzi C.: On the Newton Interior-Point Method for Nonlinear Programming Problems - Journal of Optimization Theory and Applications 104, n. 1 (2000), 73-90. 
13. Naldi G., Pareschi L.: Numerical schemes for kinetic equations in diffusive regimes - Applied Mathematical Letters 11, n. 2 (1998), 29-35. 
14. Pareschi L.: Characteristic-based relaxation methods for hyperbolic conservation laws with stiff nonlinear terms - Rend. Circ. Matem. Parlemo, Serie II Suppl. 57 (1998), 375-380 
15. Jin S., Pareschi L., Toscani G.: Diffusive relaxation schemes for multiscale discrete-velocity kinetic equations -SIAM Journal on Numerical Analysis 35, n.6 (1998), 2405-2439. 
16. Pareschi L., Caflisch R.E.: An Implicit Monte-Carlo methods for rarefied gas dynamics I: the space homogeneous case -J. Comp. Phys. 154 (1999), 90-116. 
17. Pareschi L., Naldi G., Toscani G.: Hyperbolic relaxation approximation to nonlinear parabolic problems -Proceedings 7th Conference on Hyperbolic Problems: Theory, Numerics, Applications, ETH Zurich, International Series in Num. Math 130, Birkhauser (1999), 747-756. 
18. Pareschi L., Naldi G., Toscani G.: Convergence of kinetic approximation to nonlinear diffusion problems, Proceedings Conference on Godunov Methods: Theory and Applications, 18-22 October 1999, Oxgord, England……. 
19. Pareschi L., Russo G.: Fast spectral methods for Boltzmann and Landau integral operators of gas and plasma kinetic theory - Annali Universita' di Ferrara, Suppl. n. 46 (2000), 329-341. 
20. Comincioli V., Naldi G., Pareschi L., Toscani G.: Numerical methods for multiscale hyperbolic systems and nonlinear parabolic equations- Annali Universita' di Ferrara, Suppl. n. 46 (2000), 255-266. 
21. Zanghirati G.: Some theoretical properties of Feng-Schnabel algorithm for block bordered nonlinear systems -Optimization Methods and Software 10, n. 6 (1999), 783-801. 
22. Zanghirati G.: Global convergence of nonmonotone strategies in parallel methods for block bordered nonlinear systems -Applied Mathematics and Computation 107 (2000), 137-168. 
23. Zanghirati G.: Parallel computational experience and dynamic scaling for a class of nonlinear systems - Numerical Methods in Optimization, Maugeri A., Galligani E. eds, Rend. Circ. Matem. Palermo, Serie II Suppl. 58 (1999), 229-245. 
24. Zanghirati G.: Metodi paralleli per sistemi di equazioni non lineari bordati a blocchi - Boll. U.M.I. n. 8, supplemento 1-A (1998), 205-208. 
25. Formiconi A.R., Loli Piccolomini E., Martini S., Zama F., Zanghirati G.: Numerical methods and software for functional magnetic resonance images reconstruction - Annali Universita' di Ferrara, Suppl. n. 46 (2000), 87-102.

10. Pubblicazioni

11. Prodotti della Ricerca eseguita

n. 25 pubblicazioni di cui 10 su riviste nazionali con referee, 8 su riviste internazionali con referee e 7 inseriti in volumi monografici a carattere internazionale dopo sottomissione e valutazione con referee. 
L'elenco delle pubblicazioni e' fornito al punto 9 del presente modello. 

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)

In merito all'assegno di ricerca della Dott. Durazzi, sono state inviate due comunicazioni all'Ufficio III del MURST in data 18/12/98 e in data 10/10/98.

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")