Su di un problema di visita ottima

Introduzione
Il problema così formulato è ovviamente reminiscente del famoso problema
del commesso viaggiatore (Travelling Salesman Problem), in cui, data una
rete di città collegate tramite strade, è richiesto di determinare il percorso di
minore lunghezza che un commesso viaggiatore deve seguire per visitare tutte
le città una ed una sola volta, a partire da una città base e tornando ad essa.
La semplicità della definizione del problema è ingannevole, in realtà il Travel-
ling Salesman Problem è uno dei problemi di matematica computazionale più
studiati e di cui non si conosce un metodo risolutivo efficace computazional-
mente per il caso generale, infatti c'è in palio un premio promosso dal Clay
Mathematics Institute. La questione più citata per motivare la complessità
computazionale di questo problema è che, con un numero elevato di città,
provando a procedere con l'elaborazione di tutti i possibili cammini così da
poter scegliere a posteriori il migliore, non si è più in grado di controllare
uno alla volta i singoli percorsi.
Recentemente un problema di visita ottima, collegato a quello studiato in
questa tesi, è stato argomento di una gara indetta dall' ESA (agenzia spaziale
europea). Qui si assumeva che una navicella spaziale fosse lanciata dalla Ter-
ra e che, in un massimo di 10 anni dalla partenza, dovesse raggiungere il mag-
gior numero di asteroidi, tra quelli assegnati in una lista, ed infine dovesse
concludere la sua missione con un giro completo attorno ad uno di questi aste-
roidi. A parità del numero di asteroidi visitati era richiesto di massimizzare
la massa finale, costituita dalla massa propria della navicella spaziale e dalla
massa del carburante (si veda il sito internet http://cct.cnes.fr/cct02/gtoc4/
index.htm).
Lo scopo di questa tesi è quello di applicare la teoria dei problemi di con-
trollo ottimo (vedi per esempio Macki-Strauss [12]) e, in particolare, il cosid-
detto metodo della Programmazione Dinamica al problema di visita ottima.
Ovvero vogliamo dedurre, da un sistema dinamico controllato del tipo (1),
un'opportuna equazione di Hamilton-Jacobi e provare che la funzione tempo
minimo T è l'unica soluzione di tale equazione. Poichè la funzione valore
(nel nostro caso la funzione T ) non è necessariamente derivabile o differen-
ziabile, non sempre soddisfa in senso classico l'equazione di Hamilton-Jacobi
trovata, nasce quindi l'esigenza di dare un'appropriata nuova definizione di
soluzione in senso debole. Gli studi di questo tipo di equazioni derivanti
2
Introduzione
dal metodo della Programmazione Dinamica portarono Lions e Crandall a
dare una definizione di soluzione di viscosità (vedi Lions [10], Crandall-Lions
[6], Crandall-Evans-Lions [7], Bardi-Capuzzo Dolcetta [2] e Bardi-Crandall-
Evans [3]). Ricordiamo che, in generale, per un problema di controllo ottimo,
l'equazione di Hamilton-Jacobi è intimamente legata al cosiddetto Principio
del Massimo, che fornisce condizioni necessarie affinché un controllo sia ot-
timo. Inoltre, il gradiente della funzione valore, qualora esso esista, fornisce
proprio la variable aggiunta (co-stato) necessaria per utilizzare il Principio
del Massimo. È ben noto, comunque, che tale gradiente in generale non esiste
e quindi il poter in ogni caso dare un senso all'equazione di Hamilton-Jacobi,
caratterizzando la funzione valore come la sua unica soluzione, seppur in
un senso debole (viscosità), riveste molta importanza da un punto di vista
applicativo, oltre che teorico (si veda Bardi-Capuzzo Dolcetta [2]).
Il problema di visita ottima ovviamente risente della medesima complessità
computazionale del problema del commesso viaggiatore. In particolare per
poterlo risolvere (cioè per costruire l'eventuale controllo ottimo α∗ e quin-
di la traiettoria ottima y∗, oppure per determinare la funzione T ), sembra
necessario passare attraverso la risoluzione di una quantità molto grande
di sottoproblemi. L'idea motivante di questa tesi è quella che, tramite
la programmazione dinamica, sia possibile scrivere un'unica equazione di
Hamilton-Jacobi (cioè senza ricorre a sottoproblemi) che caratterizzi la fun-
zione T come sua unica soluzione (ovviamente il problema della complessità
computazionale può, e forse deve, ritornare nel momento in cui ci si occupi
direttamente del calcolo di T a partire dell'equazione, tramite ad esempio
metodi numerici; ma è chiaro che l'aver dimostrato a priori l'uncità della
funzione T come soluzione dell'equazione (e di una sola equazione!), è un
necessario punto di partenza per qualunque metodo numerico).
Il Principio della Programmazione Dinamica (che risale a Bellman ed alla sua
scuola negli anni '60), vale in generale per problemi di controllo ottimo ed è
il punto di partenza per dedurre e studiare l'equazione di Hamilton-Jacobi.
Esso può essere formulato a parole nel seguente modo:
I pezzi di traiettorie ottime sono ottimi,
cioè, fissando un punto qualunque lungo una traiettoria ottima, si ottiene un
pezzo rimanente di traiettoria che risulta esser ottimo per il punto fissato.
3
Introduzione
Purtroppo, come è facile convicersi, tale principio non vale più per il proble-
ma di visita ottima quando il numero di targets sia maggiore di 1 (nel caso
in cui ci sia un solo target, si ricade nel classico problema di tempo minimo).
Sembra emergere la necessità di tenere in memoria, per ciascun target, se è
stato visitato o meno. Questo significa aumentare la dimensione dello spazio,
perchè si devono introdurrem nuove variabili, ciascuna associata ad un target
Tj. L'idea di aggiungere nuove variabili di stato per avere la programmazione
dinamica per il problema del commesso viaggiatore, non è certo nuova, si ve-
da ad esempio Bellman [5], in cui si associa ad ogni città una variabile e
si usa poi un procedimento iterativo per mostrare che questo problema può
essere facilmente formulato e risolto computazionalmente solo fino a 17 cit-
tà. In [5] comunque non si studia alcuna equazione di Hamilton-Jacobi.
Inoltre le nostre variabili aggiunte sono evolutive (dipendono dal tempo) e
sono continue. In particolare esse presentano effetti di isteresi, ovvero una
particolare relazione input-output caratterizzata dalle due seguenti proprie-
tà: (memoria) il valore dell'output al tempo t non dipende solo dal valore
dell'input allo stesso istante, ma anche da tutta la storia passata dell'input;
(rate independence) il valore dell'output al tempo t non dipende dalla `veloc-
ità' dell'input, bensì dipende esclusivamente dalla sequenza di valori raggiunti
dall'input durante la sua storia. Queste variabili aggiunte, inoltre, soddisfano
un'opportuna proprietà di semigruppo, che rende valido il Principio della
Programmazione Pinamica. L'evoluzione di tali variabili è descritta tramite
un operatore tra spazi funzionali, detto operatore di isteresi (si veda Vi-
sintin [14], [15] per una trattazione generale e per numerosi esempi di tali
operatori), quindi introduciamo nel nostro problema una parte riguardante
l'operatore di isteresi SemiPlay, che definiremo modificando l'operatore Play.
Ora il problema di visita ottima è descritto dal seguente sistema controllato
con due variabili di stato (x,w) ∈ Rn × Rm:
(2)



y′(t) = f(y(t), α(t)) t > 0
wj(t) = SP [gj(y);w0j ](t) ∀j = 1, . . . ,m
y(0) = x x ∈ Rn
w0j ≤ gj(x) ∀j = 1, . . . ,m
dove SP è l'operatore di SemiPlay con output wj(t), tale che wj(t) = 0
4
Introduzione
se e solo se la traiettoria è passata per Tj in [0, t], e gj sono delle fun-
zioni scalari Lipschitziane a valori sempre positivi che rappresentano i targets
(gj(x) = 0⇔ x ∈ Tj).
Operando in questo modo e provando a risolvere il problema di tempo mi-
nimo generato da (2) si perde la continuità della funzione tempo minimo
T . Allora, per riuscire a procedere senza far riemergere la complessità com-
putazionale, abbiamo pensato di formalizzare il problema di visita ottima
anzitutto attraverso un problema ad orizzonte infinito e poi come un proble-
ma di Mayer, che è un particolare tipo di problema ad orizzonte finito. Più
in dettaglio il problema è caratterizzare la funzione valore
V (x,w) = inf
α
J(x,w, α) = inf
α
∫ +∞
0
e−λt(w1(t) + . . .+ wm(t))dt
per l'orizzonte infinito (λ > 0) e
V (x,w, t) = inf
α
J(x,w, t, α) = inf
α
(w1(t) + . . .+ wm(t))
per il problema di Mayer. Sotto ragionevoli ipotesi questi ultimi due pro-
blemi approssimano, o addirittura sono in un qualche senso equivalenti, al
problema iniziale, almeno per quanto riguarda le traiettorie ed i controlli ot-
timi. Per esempio notiamo che t = inf{t ≥ 0 : V (x,w, t) = 0} se e solo se
t = T (x,w).
Nonostante tutto, le m variabili aggiunte sono responsabili della discontinui-
tà dell'equazione di Hamilton-Jacobi associata a questi problemi. Quindi,
per procedere oltre, consideriamo un'adeguata variazione della definizione
di soluzione di viscosità che sfrutta gli inviluppi semicontinui inferiore e su-
periore dell'Hamiltoniana (si veda, in generale, Ishii [8] e [9]). Nel caso
specifico dei nostri problemi ad orizzonte infinito e di Mayer, si trovano,
rispettivamente, le seguenti equazioni di Hamilton-Jacobi:
λV (y, w) +H(y, w,DyV (y, w), DwV (y, w)) = 0 con
H(y, w, p, q) := sup
a∈A
{
− f(y, a) · p+
m∑
j=1
qjχ(gj(y), wj)(Dgj(y) · f(y, a))−−
−
m∑
j=1
wj(t)
}
,
5
Introduzione
Vt(y, w, t) +H(y, w,DyV (y, w, t), DwV (y, w, t)) = 0 con
H(y, w, p, q) := sup
a∈A
{
− f(y, a) · p+
m∑
j=1
qjχ(gj(y), wj)(Dgj(y) · f(y, a))−
}
,
dove Vt, DyV,DwV indicano le derivate parziali e χ la funzione caratteristica
della bisettrice del primo quadrante nel piano gj(y)−wj. Per riuscire a con-
cludere con la caratterizzazione della funzione valore V , dobbiamo effettuare,
con alcune considerazioni sulle Hamiltoniane, un ulteriore passaggio: dall'e-
quazione di Hamilton-Jacobi discontinua ad un problema con condizioni di
Neumann per Hamiltoniana continua, per il cui studio facciamo riferimento
ai lavori di Lions [11] e Barles-Lions [4].
Nella tesi, dunque, formalizziamo il problema di visita ottima con il sistema
dinamico controllato (2) e lo descriviamo come un problema ad orizzonte
infinito e di Mayer dandone, in entrambe i casi, uno studio completo e det-
tagliato secondo il metodo della Programmazione Dinamica, fino alla carat-
terizzazione delle rispettive funzioni valore come uniche soluzioni di viscosità
dell'opportuna equazione di Hamilton-Jacobi trovata. Un risultato per pro-
blemi di controllo ottimo con isteresi, simile a quelli studiati in questa tesi,
ma per un modello unidimensionale, è presentato in Bagagiolo [1].
La principale base teorica è introdotta nel capitolo 1, dove capiamo che cos'è
un problema di controllo ottimo e vediamo nello specifico gli esempi stan-
dard: problema ad orizzonte infinito, finito e di tempo minimo. L'analisi di
questi tre problemi modello, è occasione di descrivere in modo dettagliato an-
che il metodo della Programmazione Dinamica. Per comprendere in maniera
completa questo capitolo sulla teoria del controllo, richiamiamo la definizione
di soluzione di viscosità per equazioni di Hamilton-Jacobi e la relativa parte
teorica riassunta in appendice A.
Il capitolo 2 è dedicato a raccontare il problema di visita ottima. In parti-
colare mostriamo i vari possibili approcci cercando di trovare il più adatto
per formalizzarlo matematicamente e permetterne uno studio con il metodo
della Programmazione Dinamica.
I tre capitoli seguenti si specializzano in un'analisi dettagliata del problema
di visita ottima. All'interno del capitolo 3 riprendiamo il sistema dinamico
controllato (2) e, sotto opportune ipotesi, enunciamo e dimostriamo alcune
tra le più importanti proprietà soddisfatte dalle traiettorie (soluzioni di (2)).
6
Introduzione
Negli ultimi due capitoli si passa dunque allo studio del problema secondo
il metodo della Programmazione Dinamica. Nello specifico, nel capitolo 4 si
vede la formalizzazione come un problema controllato ad orizzonte infinito,
mentre il capitolo 5 descrive il problema di visita ottima seguendo il modello
del problema di Mayer.
Infine le due appendici completano la parte teorica richiamata nella tesi. In
appendice A, oltre alle definizioni ed alle proprietà delle soluzioni di visco-
sità, vengono esposti i risultati di unicità di tali soluzioni per problemi con
equazioni di Hamilton-Jacobi associate a diversi tipi di condizioni al bordo
(Dirchlet, Cauchy e Neumann). Poi si trova anche la definizione di soluzione
di viscosità per equazioni di Hamilton-Jacobi con Hamiltoniana discontinua.
La definizione e le proprietà principali degli operatori di isteresi e, nello
specifico, dell'operatore SemiPlay sono mostrate in appendice B.
7