METODI E ALGORITMI PER PROBLEMI NON LINEARI STRUTTURATI IN OTTIMIZZAZIONE NUMERICA E CONTROLLO.

 

 

.

Nei problemi non lineari, formulati come sistemi di equazioni o come problemi di minimo, non sembra che sia stata prestata sinora sufficiente attenzione alla presenza di particolari proprietà del problema e al loro sfruttamento per ottenere adeguati metodi risolutivi, anche se recentemente sono stati fatti alcuni tentativi di codificare la questione.

In analogia con quanto è ben compreso nel caso di problemi lineari algebrici, possiamo parlare di struttura del problema.

Possiamo considerare strutturati per esempio problemi di minimo in cui la funzione obiettivo abbia una forma particolare (per esempio in problemi di "traffico" spesso è vista come somma di funzioni più semplici o dipendenti solo da alcune delle variabili in gioco) o i vincoli presentino proprietà significative come la convessità; analogamente sistemi di equazioni non lineari possono presentare struttura per la forma della funzione da annullare o per la presenza di vincoli che limitino il campo di ricerca degli zeri.

Per concretizzare meglio la portata della questione conviene considerare alcuni casi esemplari.

  1. Sistemi non lineari con vincoli.

Il problema di risolvere sistemi non lineari riveste una persistente importanza in matematica applicata e nella sua versione tradizionale consiste nel cercare un vettore in uno spazio euclideo di dimensione finita che soddisfi ad un sistema di equazioni definito da una funzione non lineare a valori vettoriali sufficientemente regolare(smooth). Una generalizzazione di questo classico problema si ottiene richiedendo alla soluzione di appartenere ad un dato insieme chiuso nello spazio euclideo, otteniamo così un sistema non lineare con vincoli (CE). Problemi di questo tipo intervengono per esempio in problemi di chimica, dove i vincoli stabiliscono quali soluzioni hanno significato e si richiedono quindi metodi numerici che tengano conto della struttura imposta dai vincoli per determinare solo le soluzioni significative.

La formulazione CE è comune anche a parecchi problemi di programmazione matematica, includendo problemi di complementarità non lineare (NCP) di vario tipo e sistemi di disequazioni variazionali derivati dalle condizioni di Karush-Kuhn-Tucker (KKT).

I problemi NCP si prestano a varie formulazioni ([FP]), dando luogo a problemi non lineari con struttura: a) problemi di complementarità mista monotona nel cono delle matrici simmetriche semidefinite positive ([MP], [SS]); b) problemi di equilibrio in ingegneria ed economia; c) problemi di lubrificazione ([DF]).

L’applicazione delle condizioni KKT conduce talvolta a formulazioni CE di grandi dimensioni a matrice jacobiana sparsa e a rango incompleto; un modello locale del tipo trust-region porta a sottoproblemi la cui struttura convessa suggerisce algoritmi a convergenza globale ([ET]).

2.Problemi di controllo ottimo.

Problemi di controllo ottimo discretizzati possono essere formulati come problemi di programmazione non lineare di grandi dimensioni con una particolare struttura, che nasce dalla partizione delle variabili in controlli e stati , dal problema in dimensione infinita sottostante e dalla discretizzazione.

Trattandosi di problemi di programmazione non lineare, potrebbero essere risolti in linea di principio usando i risolutori esistenti come LANCELOT, LOQO o SNOPT. Questi risolutori richiedono che l’utente fornisca i sottoprogrammi per il calcolo della funzione obiettivo, del suo gradiente, della funzione vincolare e della sua jacobiana. Ciò può dare luogo a severe limitazioni:

  1. Se si raffina la discretizzazione, i problemi ottenuti tendono ad esaurire la memoria disponibile se si deve conservare la jacobiana;
  2. Risulta spesso assai problematico incorporare nel risolutore generale di programmazione non lineare risolutori basati per esempio su metodi multigrid ed elementi finiti per la soluzione delle equazioni di stato alle derivate parziali linearizzate.
  3. Considerare il problema di controllo ottimo discretizzato come un problema di programmazione non lineare porta ad ignorare la struttura del sottostante problema in dimensione infinita, provocando un deterioramento della convergenza al crescere del raffinamento a causa di una scalatura impropria e a malcondizionamenti artificiali ([CHS] 1997 e 1998).

Recentemente, per superare queste difficoltà tenendo conto della particolare struttura del problema di controllo, è stata proposta una classe di algoritmi basati sui metodi di programmazione quadratica sequenziale (SQP) e sulle tecniche interior-point e trust-region per garantire la convergenza globale ([DHV]).

Si può osservare inoltre che l’approccio ai problemi di controllo ottimo per equazioni differenziali ordinarie basato sulla programmazione dinamica richiede la soluzione di equazioni alle derivate parziali di tipo Hamilton-Jacobi con una struttura particolare (hamiltoniana convessa).La discretizzazione di queste equazioni può essere ottenuta con varie tecniche, quali ad esempio le differenze finite, i volumi finiti e i metodi semi-lagrangiani, ma solo questi ultimi mantengono uno stretto legame con il problema di controllo originario, permettendo di interpretare lo schema numerico come un problema di controllo a stati e tempi discreti. Questa particolarità risulta molto utile nella costruzione dei controlli ottimi in forma feed-back e nella approssimazione delle traiettorie ottime ([F],[T]).

 

3.Progettazione di forme ottimali.

Una classe di problemi vicina a quella dei problemi di controllo ottimo è quella della progettazione di forme ottimali, che interviene per esempio nella progettazione di ugelli, di profili alari, di tomografi. Il calcolo della soluzione è in genere un problema molto costoso in quanto la discretizzazione conduce di solito a problemi di ottimizzazione di grande scala, che richiedono la soluzione di parecchi problemi al contorno per equazioni alle derivate parziali. Sono stati fatti primi tentativi di usare metodi quasi-Newton per risolvere questi problemi di grandi dimensioni ([KS], [KW], [K]). La chiave per costruire metodi efficienti per tali problemi è sempre lo sfruttamento della specifica struttura del problema in considerazione ([L]).

Problemi analoghi, per struttura e per dimensione, sorgono nella discretizzazione di problemi di controllo per equazioni alle derivate parziali di tipo parabolico e iperbolico. Pur avendo questi problemi una grande rilevanza industriale (ad esempio nel controllo della dinamica dei fluidi intorno a profili alari o nei serbatoi/condutture) i risultati esistenti in letteratura sono molto limitati a causa dell’estrema complessità di questi problemi ([DKK], [BF]).

.

 

 

Bibliografia.

[BCD] Bardi, Capuzzo Dolcetta, Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations, Birkhauser, Boston 1997

[KMS] Kozakivich,Martinez,Santos Solving nonlinear systems of equations with simple constraints CAM 1997

[MR] Melhem, Rheinboldt A comparison of methods for determining turning points of nonlinear equations Computing 29 (1982)

[ET] El Hallabi, Tapia An inexact trust region feasible point algorithm for nonlinear systems of equalities and inequalities CRPC-TR 99543 Rice Univ. 1995

[CHS] Cliff, Heinkenschloss, Shendov An optimal control problem for flows with discontinuities JOTA 94 (1997)

[CHS] idem Airfoil design by an all-at- once method Int, J, for Comput. Fluid Mech. 11(1998)

[DHV] Dennis, Hienkenschloss, Vincente Trust region interir point SQP algorithms for a class of nonlinear programming problem Tech. Rep. Rice Univ, 1997

[DKK] Desch, Kappel, Kunisch eds., Control and estimation of distributed parameter systems, Int. Series of Numer. Maths . , Birkhauser 1998

[F] Falcone, Numerical solution of dynamic programming equations, Appendice a [BCD]

[KS] Kelley, Sachs Quasi-Newton methods and unconstrained optimal control problems SIAM J.Cintrol Optim, 25 (1997)

[KW] Kelley, Wright Sequential quadratic programming for certain parameter identification problems Numer Anal. 29 (1992)

[K] Kupfer An infinite-dimensional convergence theory for reduced SQP methods in Hilbert space SIAM J. Optim: 6 (1996)

[L] Laumen Newton’s method for a class of optimal shape design problems SIASM J. Optim. 10 (2000)

[FP]Ferris, Pang Engeenering and economic applications of complementarity problems SIAM Rev. 39 (1997)

[DF] Dirkse, Ferris MCPLIB: A collection of nonlinear mixed complementarity problems 1994

[SS] Solodov. Svaiter, A truly globally convergent Newton-type method for monoton NCP ,

SIAM J. Optim. 10 (2000)605-625

[MP] Monteiro, Pang, A potential reduction Newton method for constrained equations.

 

Obiettivi e metodologia.

 

La grande importanza dei problemi con struttura in molte applicazioni, la necessità di metodi numerici che risolvano in modo efficiente questi problemi, la validità di alcune proposte, limitate ma in qualche caso autorevoli ([DHV], [MP], [SS]), che tengono conto vantaggiosamente della struttura dei problemi considerati nella progettazione dei metodi e degli algoritmi risolutivi, fanno ritenere che questo campo di ricerca sia di grande interesse e si presti ad ottenere risultati innovativi.

Questo progetto di ricerca si propone di individuare metodi per l’approssimazione numerica delle soluzioni di problemi non lineari con struttura , partendo dallo studio della possibilità di adeguamento di metodi di portata generale(Newton-like, interior-point, etc) a questa classe di problemi, cercando di sfruttare nel modo migliore la struttura per ottenere una maggior efficienza dei procedimenti risolutivi.

Successivamente si intende procedere alla costruzione di metodi specifici per le varie classi di problemi strutturati come quelli formulati come CE e derivati dal controllo ottimo, dalla progettazione di forme ottimali, dai problemi di equilibrio.

Si intende sviluppare sia l’analisi numerica che la sperimentazione numerica, attraverso adeguate implementazioni, dei metodi proposti.

Per problemi di grandi dimensioni può essere utile studiare sia metodi inesatti che sviluppare algoritmi paralleli.

Si ritiene che per ottenere risultati significativi in tempi ragionevoli, sia necessaria la confluenza di competenze già consolidate nel settore della risoluzione di sistemi non lineari, delle tecniche di ottimizzazione e della risoluzione dei problemi di controllo ottimo. Tali competenze esistono nell’ambito dei gruppi di ricerca delle sedi( Ferrara, Firenze, Modena, Roma) coinvolte in questa proposta, come risulta dalla produzione scientifica allegata.