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_013
1. Area Scientifico Disciplinare principale 01: Scienze matematiche
2. Coordinatore Scientifico del programma di ricerca
| RUGGIERO | Valeria |
| (cognome) | (nome) |
| Universita' degli Studi di FERRARA | Facolta' di SCIENZE MATEMATICHE FISICHE e NATURALI |
| (università) | (facoltà) |
| MATEMATICA | |
| (dipartimento/istituto) |
3. Titolo del programma di ricerca
4. Responsabile Scientifico dell'Unità di ricerca
| ZANNI | Luca |
| (cognome) | (nome) |
| Universita' degli Studi di MODENA e REGGIO EMILIA | Facolta' di SCIENZE MATEMATICHE FISICHE e NATURALI |
| (università) | (facoltà) |
| MATEMATICA PURA E APPLICATA | |
| (dipartimento/istituto) |
5. Titolo del programma dell'unità di ricerca
6. Settore principale del Programma di Ricerca: A04A - Analisi numerica
7. Finanziamenti assegnati all'unità di ricerca
| (in lire) | |
|---|---|
| Quota ateneo | 20.000.000 |
| Cofin assegnato | 30.000.000 |
| Totale complessivo | 50.000.000 |
8. Obiettivo della ricerca eseguita
9. Descrizione della Ricerca eseguita e dei risultati ottenuti
1) RISOLUZIONE DI PROBLEMI DI PROGRAMMAZIONE QUADRATICA DI GRANDI DIMENSIONI CON VINCOLI.
E' stata valutata l'efficienza numerica di alcuni metodi iterativi del tipo proiezione e di decomposizione per problemi di programmazione quadratica convessa con vincoli lineari di uguaglianza e disuguaglianza. In (3), il comportamento di tali metodi e' stato studiato su una serie di problemi test generati in modo casuale, di grandi dimensioni, sparsi, con differenti condizionamenti e distribuzioni degli autovalori della matrice Hessiana della funzione obiettivo.
Al fine di superare i principali inconvenienti dei metodi di decomposizione (difficolta' nell'individuare decomposizioni dell'Hessiano tali da garantire facili sottoproblemi e rapida convergenza) e dei metodi di tipo proiezione (valori dei parametri soddisfacenti
le condizioni di convergenza spesso implicano lenta convergenza), in (7), per problemi di programmazione quadratica strettamente convessi, e' stato proposto un nuovo metodo detto a Proiezione Variabile. Tale metodo si basa sull'introduzione di un parametro variabile ad ogni iterazione e su un'opportuna formula di correzione che garantisce la sua convergenza sotto ipotesi piu' deboli di quelle dei metodi di decomposizione e di proiezione. Infatti, a differenza dei metodi di decomposizione, nessuna condizione restrittiva e' richiesta sulla matrice Hessiana dei sottoproblemi; inoltre, e' sufficiente che i valori assunti dal parametro variabile siano limitati inferiormente e superiormente da costanti positive, senza necessita' di imporre forti limitazioni su tali costanti come invece avviene nei metodi di proiezione. Di conseguenza, la scelta della successione dei parametri puo' essere fatta in modo da ottenere una buona velocita' di convergenza dello schema. A tale scopo e' stata suggerita una regola di aggiornamento per il parametro computazionalmente non costosa e numericamente efficiente.
Questo metodo e' stato generalizzato al caso solo convesso nel lavoro (9) dove viene anche analizzata l'efficacia di una diversa regola d'aggiornamento per il parametro variabile. Inoltre, in (9) e' stato introdotto un altro schema iterativo in cui il parametro variabile viene scelto in modo adattivo.
Un'ampia sperimentazione numerica su problemi di grandi dimensioni (generati in modo casuale e di libreria) mostra l'efficienza dei metodi a proiezioni variabile in relazione alla routine E04NKF della libreria NAG e ad altri recenti metodi di proiezione modificati ((6),(9),(11)).
L'efficacia del metodo a proiezione variabile e' stata confermata anche dai risultati ottenuti applicandolo alla risoluzione di un particolare problema di programmazione quadratica, con vincoli box ed un solo vincolo di uguaglianza, che interviene nella fase di addestramento di una metodologia di classificazione binaria nota con il nome di Support Vector Machine. I risultati numerici ottenuti in (13) mostrano che tale metodo si presta a sfruttare sia la speciale natura della matrice Hessiana che la particolare struttura dei vincoli presenti in questa applicazione.
Nel caso di problemi di grandi dimensioni con matrici Hessiana e dei vincoli sparse, particolare attenzione e' stata dedicata all'implementazione su architetture parallele dei metodi del tipo proiezione. Tale implementazioni si basano sull'uso di risolutori paralleli per il sottoproblema di complementarita' lineare a cui puo' essere ricondotta ogni iterazione dello schema di proiezione. Per la risoluzione del sottoproblema di complementarita' lineare, sono stati esaminati alcuni classici risolutori paralleli (parallel SOR, parallel gradient projection SOR) ed e' stato sviluppato uno schema parallelo, detto ''overlapping parallel SOR''.
In (2), si e' valutata l'efficienza di tali metodi quando utilizzati come risolutori interni ad uno schema di decomposizione per problemi di programmazione quadratica di grandi dimensioni provenienti dall'interpolazione vincolata di superfici di classe C1 (14). La sperimentazione numerica, eseguita sul calcolatore parallelo CRAY T3E, ha mostrato il comportamento dei risolutori paralleli al variare delle dimensioni del problema, della sparsita' della matrice di complementarita' e del numero di processori disponibili.
Una parte dell'attivita' svolta ha riguardato anche lo studio dei metodi lagrangiani per problemi di programmazione non lineare (in particolare quadratica) e la loro applicazione a problemi di controllo ottimo discreto.
E' noto che le condizioni di Karush-Kuhn-Tuker per problemi di programmazione non lineare possono essere viste come sistemi di equazioni non lineari con restrizione sul segno delle variabili. La risoluzione numerica di tali sistemi, puo' essere affrontata mediante il metodo di Newton del punto interno. Un'analisi della convergenza di tale metodo e' stata sviluppata in (10) e (12).
Problemi discreti di controllo ottimo possono essere riformulati come problemi di programmazione quadratica con vincoli di uguaglianza che si affrontano efficientemente con il metodo dei moltiplicatori di Hestenes.
In (5) si e' dimostrato che condizioni sufficienti per l'esistenza e l'unicita' della soluzione assicurano anche la convergenza del metodo dei moltiplicatori.
Si e' inoltre analizzato (4) il metodo iterativo parallelo della media aritmetica per la risoluzione dell'equazione di Sylvester che interviene in problemi di controllo ottimo lineare-quadratico.
2) RISOLUZIONE DEL PROBLEMA DEI MINIMI QUADRATI LINEARI CON VINCOLI DI UGUAGLIANZA
In (8), utilizzando la tecnica dell'analisi all'indietro dell'errore, e' stata esaminata la stabilita' numerica di un metodo diretto (metodo di eliminazione diretta) per il problema dei minimi quadrati lineari con vincoli di uguaglianza. Il metodo usa la fattorizzazione QR della matrice dei vincoli per eliminare alcune variabili e riconduce il problema originario ad un problema di minimi quadrati lineari non vincolato di dimensione piu' piccola. La stabilita' numerica e' stata studiata teoricamente, confrontando maggiorazioni dell'errore inerente ed algoritmico, e sperimentalmente, valutando il comportamento del metodo su classi di problemi test.
In (1) e' stato studiato il problema dei minimi quadrati lineari con un vincolo di uguaglianza a cui puo' essere ricondotto il calcolo di un autovalore (ad es. l'autovalore minimo) di una matrice simmetrica. Utilizzando le condizioni di Lagrange per il problema di minimo vincolato, si puo' definire un procedimento iterativo con convergenza del quarto ordine per il calcolo di un autovalore e dell'autovettore associato. Sono state esaminate alcune tecniche per la risoluzione del sottoproblema di minimo vincolato presente ad ogni iterazione del procedimento.
3) DISCRETIZZAZIONE DI EQUAZIONI DI DIFFUSIONE E TRASPORTO
IN 3D MEDIANTE ELEMENTI SPETTRALI.
E' stato svolto uno studio teorico ed una implementazione di algoritmi numerici per l'approssimazione della soluzione di equazioni alle derivate parziali di tipo ellittico in tre dimensioni spaziali, con l'uso di elementi spettrali (15)-(18).
Si sono adottate tecniche di decomposizione dei domini abbinate a metodi di tipo collocazione su nodi di Legendre. Il dominio computazionale e' supposto essere suddiviso in sottodomini isomorfi a cubi, dove la soluzione viene approssimata mediante polinomi di grado 5, corrispondenti ad una griglia di 216 nodi per ciascun sottodominio. Il sistema lineare che ne deriva viene risolto mediante schemi iterativi opportunamente precondizionati. In prevalenza sono trattati problemi di tipo diffusione-trasporto con termini di trasporto dominanti. Le soluzioni approssimate di tali equazioni vengono "stabilizzate", rispetto al parametro di diffusione, mediante l'uso di opportune griglie di collocazione, dipendenti dall'operatore differenziale discretizzato. Tali griglie di tipo "upwind" sono definite sia all'interno di ciascun sottodominio che all'interfaccia fra un sottodominio e gli adiacenti.
REFERENZE BIBLIOGRAFICHE
(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. M. Pardalos and G. Toraldo eds.) Applied Optimization 24, Kluwer Academic Publ. (1998), 189-205.
(3) Ruggiero V, Zanni L.: On a class of iterative methods for convex large-scale quadratic programs; Rend. Circ. Matem. Palermo, Ser. II, Supp. 58, (A. Maugeri and E. Galligani eds.) (1999), 213-227.
(4) Galligani E.: Parallel solution of large Sylvester equations; Rend. Circ. Matem. Palermo, Ser. II, Supp. 58, (A. Maugeri and E. Galligani eds.) (1999), 155-171.
(5) Durazzi C., Galligani E.: Numerical solution of discrete quadratic optimal control problems; Recent Advances in Numerical Methods and Applications II (O.P. Iliev, M.S. Kaschiev, S.D.Margenov, Bl.H. Sendov, P.S. Vassilevski eds.) World Scientific Publ. (1999), 717-724.
(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 and F. Giannessi, eds.) Kluwer Academic Publ. (1999), 401-413.
(7) Ruggiero V., Zanni L.: A modified projection algorithm for large strictly convex quadratic programs; J. Optim. Theory Appl., Vol. 104, No. 2, (2000), 281-299.
(8) Galligani E., Zanni L.: On the stability of the direct elimination method for equality constrained least squares problems; Computing, (2000).
(9) Ruggiero V., Zanni L.: An overview on projection-type methods for convex large-scale quadratic programs; Equilibrium Problems and Variational Models (A. Maugeri, F. Giannessi and P. Pardalos eds.) Kluwer Academic Publ.(2000).
(10) Durazzi C., Galligani E.: Nonlinear programming methods for solving optimal control problems; Equilibrium Problems and Variational Models (A. Maugeri, F. Giannessi and P. Pardalos eds.) Kluwer Academic Publ. (2000).
(11) Ruggiero V., Zanni L.: Splitting and projection-type methods for large convex quadratic programs; Ann. Univ. Ferrara, Supp. n. 46 (2000), 521-540.
(12) Durazzi C., Galligani E.: Solution of discrete optimal control problems via mathematical programming; Ann. Univ. Ferrara - Sez. VII - Sc. Mat., Supplemento al Vol. XLV,(2000).
(13) Verri A., Zanni L.: Numerical solution of large quadratic programs in training support vector machines; submitted.
(14) Galligani E.: A note on construction of surfaces under tension; submitted.
(15) Funaro D.: A note on second-order finite-difference schemes on uniform meshes for advection-diffusion equations; Numer. Methods Partial Differential Eq., 15 (1999), 581-588.
(16) Funaro D., Pontrelli G.: Spline approximation of advection-diffusion problems using upwind type collocation nodes; Journal of Computational and Applied Mathematics, 110
(1999), 141-153.
(17) Funaro D.: About 3-D spectral element computations; to appear.
(18) Funaro D.: Superconsistent discretizations of integral type equations; submitted.
10. Pubblicazioni
| 1. | Ruggiero V., Zanni L.: A modified projection algorithm for large strictly convex quadratic programs; J. Optim. Theory Appl., Vol. 104, No. 2, pp. 281-299, (2000). |
| 2. | Galligani E., Zanni L.: On the stability of the direct elimination method for equality constrained least squares problems; Computing, (2000). |
11. Prodotti della Ricerca eseguita
L'elenco delle pubblicazioni e' fornito al punto 9 del presente modello.
- Realizzazione di software sui metodi di tipo proiezione per problemi di programmazione quadratica convessa di grandi dimensioni disponibile in rete alla URL http://www.unife.it/AnNum97/software.htm.
- n. 2 monografie:
C. Durazzi, V. Ruggiero, L. Zanni: A Random Generator for Large-Scale Linearly Constrained Quadratic Programming Test Problems;
E. Galligani, V. Ruggiero, L. Zanni: Projection-Type Methods for Large Convex Quadratic Programs: Theory and Computational Experience;
- n. 12 comunicazioni a convegni di cui 7 convegni internazionali e 5 convegni nazionali;
12. Componenti dell'Unità di ricerca che hanno effettivamente partecipato alla ricerca
Personale docente
| nº | cognome | nome | qualifica | facoltà | dipartimento/istituto Università | mesi uomo dal modello I anno | mesi uomo dal modello II anno | mesi uomo effetiv. impegnati I anno | mesi uomo effetiv. impegnati II anno | nota |
|---|---|---|---|---|---|---|---|---|---|---|
| 1. | FUNARO | Daniele | prof. ordinario | Facolta' di SCIENZE MATEMATICHE FISICHE e NATURALI | MATEMATICA PURA E APPLICATA Universita' degli Studi di MODENA e REGGIO EMILIA |
11 | 11 | 11 | 11 | |
| 2. | GALLIGANI | Emanuele | prof. associato | Facolta' di INGEGNERIA | MATEMATICA PURA E APPLICATA Universita' degli Studi di MODENA e REGGIO EMILIA |
11 | 11 | 11 | 11 | |
| 3. | LARATTA | Alfonso | prof. ordinario | Facolta' di SCIENZE MATEMATICHE FISICHE e NATURALI | MATEMATICA PURA E APPLICATA Universita' degli Studi di MODENA e REGGIO EMILIA |
11 | 11 | 11 | 11 | |
| 4. | ZANNI | Luca | ricercatore | Facolta' di SCIENZE MATEMATICHE FISICHE e NATURALI | MATEMATICA PURA E APPLICATA Universita' degli Studi di MODENA e REGGIO EMILIA |
11 | 11 | 11 | 11 | |
| 5. | ZIRONI | Fernando | prof. associato | Facolta' di SCIENZE MATEMATICHE FISICHE e NATURALI | MATEMATICA PURA E APPLICATA Universita' degli Studi di MODENA e REGGIO EMILIA |
11 | 11 | 11 | 11 |
Altro personale
| nº | Cognome | Nome | Qualifica | Facoltà | Dipartimento/Istituto Università/Ente | mesi uomo effetiv. impegnati I anno | mesi uomo effetiv. impegnati II anno | Nota |
|---|
Personale a contratto
| nº | Cognome | Nome | Qualifica | Facoltà | Dipartimento/Istituto Università/Ente | Inizio del contratto | Durata del contratto in mesi | Costo in lire | mesi uomo I anno | mesi uomo II anno | Nota |
|---|
13. Note relative ai componenti (p.12)
14. Risorse umane complessivamente ed effettivamente impegnate
| mesi uomo I anno | mesi uomo II anno | Totale mesi uomo |
|
|---|---|---|---|
| da personale universitario | 55 | 55 | 110 |
| altro personale | 0 | ||
| personale a contratto | 0 |
15. Dati complessivi relativi al programma
| (numero) | |
|---|---|
| partecipazioni a convegni: | |
| in Italia | 8 |
| all'estero | 4 |
| articoli pertinenti pubblicati: | |
| su riviste italiane con referee | 5 |
| su riviste straniere con referee | 13 |
| su altre riviste italiane | |
| su altre riviste straniere | |
| comunicazioni a convegni/congressi internazionali | 7 |
| comunicazioni a convegni/congressi nazionali | 5 |
| rapporti interni | 2 |
| brevetti depositati |
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
| Voce di spesa | Spese indicate nel modello (in altro: voce B - pers. a contratto) | Fondi utilizzati I anno (relaz.) | Pagato I anno | Pagato II anno | Rimane da pagare | Impegnato | Totale spese sostenute | Descrizione |
|---|---|---|---|---|---|---|---|---|
| Materiale inventariabile | 3.000.000 | 0 | 6.741.280 | 13.833.440 | 20.574.720 | Acquisto stampante HP4000N. Pagamento parziale di: Digital Personal Workstation 500au, Compaq Professional Workstation XP1000, Monitor Philips 105B. |
||
| Grandi Attrezzature | 27.000.000 | 6.741.280 | 0 | 0 | Le spese riservate alle Grandi Attrezzature sono state spostate sul Materiale inventariabile, in seguito alla precisazione del MURST che le attrezzature informatiche non sono Grandi Attrezzature. | |||
| Materiale di consumo | 0 | 0 | 0 | 0 | 0 | |||
| Spese per calcolo ed elaborazione dati | 450.000 | 450.000 | 684.327 | 1.134.327 | Utenza Centro Interdipartimentale di Calcolo Automatico e Informatica Applicata dell'Universita'di Modena e Reggio Emilia. | |||
| Personale a contratto | 0 | 0 | 0 | |||||
| Servizi esterni | 0 | 0 | ||||||
| Missioni | 3.624.400 | 3.624.400 | 19.996.700 | 23.621.100 | Pagamenti di missioni dei componenti dell'unita' di ricerca e contributo spese a collaboratori, non afferenti al progetto, per seminari e/o conferenze presso l'Universita' di Modena e Reggio Emilia. |
|||
| Altro(*) | 35.000.000 | 1.800.000 | 1.800.000 | 2.829.180 | 40.673 | 4.669.853 | Rinnovo abbonamento MATLAB. Acquisto software (WINDOWS98 SIGMAPLOT). Spese di pubblicazione. Assistenza tecnica su PC. Impegno per spese di partecipazione a convegno inerente i risultati della ricerca cofinanziata (convegno SIMAI2000, 5 - 9 Giugno 2000, Ischia) |
|
| Totale | 65.000.000 | 12.615.680 | 12.615.680 | 37.343.647 | 0 | 40.673 | 50.000.000 |
| (in lire) | |
|---|---|
| Totale finanziamento assegnato | 50.000.000 |
| Totale spese sostenute | 50.000.000 |
| Fondi non utilizzati (vedi nota n.2235 del 19.10.99) |
0 |
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")
| Data 14/06/2000 22:14 | Firma ................................................................... |
