2.2 Formulazione variazionale del Problema di
usso di costo minimo
In molte circostanze reali possono veri carsi delle situazioni, non prevedibili a priori, in cui siamo costretti a modi care del tutto o in parte i programmi stabiliti e le scelte eettuate in un primo momento.
Ad esempio, se dobbiamo fare un viaggio, prima della partenza scegliamo la strada da percorrere, ma durante il tragitto può capitare di dover cambiare percorso causa tra co, lavori in corso etc...
Se si considera il sistema viario come una rete, il viaggiatore si trova ad essere un utente esterno alla rete nel momento in cui programma il percorso e quindi ad avere costi ssi, un utente interno alla rete durante il viaggio e a dover prendere nuove decisioni in relazione alla variazione delle condizioni del momento. Il problema arontato dall'utente interno può essere schematizzato in forma variazionale.
In questa sezione mostreremo la relazione tra le disequazioni variazionali (VI) e i problemi di usso di costo minimo, presentando il modello varia- zionale come estensione del problema classico, ove il costo c(f) per unità di usso non è necessariamente costante.
In particolare, vedremo come il problema (1.1) si generalizza nel caso variazionale con la ricerca di un vettore di ussi f∗ ∈ K
f tali che f∗ sia
soluzione della seguente disequazione variazionale:
hc(f∗), f − f∗i ≥ 0, ∀ f ∈ Kf (2.7)
2.2 Formulazione variazionale del Problema di usso di costo minimo 43 Equivalentemente, un punto di equilibrio f∗ è caratterizzato dal fatto di
essere soluzione del problema di estremo:
min P
(i,j)∈Acij(f∗)fij
Γf = q 0 ≤ f ≤ d
(2.8)
Possiamo notare che se la nostra funzione obiettivo dei costi non dipende da f il problema si riconduce al caso standard visto nel capitolo precedente. Infatti se c(f∗) = c con c costante per ogni f∗ allora si ha che :
hc(f∗), f − f∗i = hc, f − f∗i ≥ 0 ⇔ hc, f i ≥ hc, f∗i ∀ f ∈ Kf
⇔ hc, f∗i = min
f ∈Kf
hc, f i ⇔ f∗ è un punto di minimo per il problema (1.1) .
Procediamo con il problema di usso di costo minimo nel caso variazio- nale, tenendo conto delle de nizioni e dei teoremi introdotti nel precedente capitolo, utili per la risoluzione del nostro problema di estremo. Andiamo a determinare, quindi, il sistema (LKT) (1.3.1) per il problema (2.8), partendo dalla lagrangiana ad esso associata:
2.2 Formulazione variazionale del Problema di usso di costo minimo 44 Applicando le condizioni (LKT) (1.15) otteniamo:
∇fL(f∗; f, λ, µ, s) = 0 hµ, f − di = 0, hs, f i = 0 Γf = q, 0 ≤ f ≤ d, µ ≥ 0, s ≥ 0 (2.9) da cui: c(f∗) + λΓ + µ − s = 0 hµ, f∗− di = 0, hs, f∗i = 0 Γf∗ = q, 0 ≤ f∗ ≤ d, µ ≥ 0, s ≥ 0 (2.10)
Eliminando i moltiplicatori s da (2.10) otteniamo il seguente sistema: c(f∗) + λΓ + µ = s ≥ 0 hµ, f∗− di = 0, hc(f∗) + λΓ + µ, f∗i = 0 Γf∗ = q, 0 ≤ f∗ ≤ d, µ ≥ 0, (2.11)
I vincoli sono lineari quindi le condizioni oltre ad essere necessarie sono anche su cienti; a tal proposito si ha la seguente proposizione:
Proposizione 2.2.1. f∗ è una soluzione della (2.7) se e solo se esiste
2.2 Formulazione variazionale del Problema di usso di costo minimo 45 Dalla proposizione (2.2.1) segue direttamente il seguente principio di equilibrio:
Teorema 2.2.1. f∗ è una soluzione della (2.7) se e solo se esiste
λ∗ ∈ Rp e µ∗ ∈ Rn+ tali che per ogni (i, j) ∈ A :
0 < fij∗ < dij ⇒ cij(f∗) = λ∗i − λ ∗ j, µ ∗ ij = 0, (2.12) fij∗ = 0 ⇒ cij(f∗) ≥ λ∗i − λ ∗ j, µ ∗ ij = 0, (2.13) fij∗ = dij ⇒ cij(f∗) = λ∗i − λ ∗ j − µ ∗ ij. (2.14)
Dato cij(f∗)possiamo osservare che per le condizioni (2.12), (2.13), (2.14),
trovata una soluzione λ∗, ne esistono in nite che dieriscono tra loro per una
costante. Infatti, nel caso in cui f∗ sia unica, anche la soluzione c
ij(f∗)è unica
perché, perturbando un moltiplicatore di Lagrange di un fattore k, la funzione obiettivo non cambia; esplicitamente abbiamo cij(f∗) = λ∗i + k − λ
∗
j − k =
λ∗i−λ∗
j. Mentre, se è la funzione obiettivo ad essere moltiplicata per un fattore
k, tutti i moltiplicatori di Lagrange verranno moltiplicati per lo stesso fattore k e questo ci dice che il moltiplicatore di Lagrange dà informazioni sul modo in cui il vincolo in uenza la funzione obiettivo.
2.2 Formulazione variazionale del Problema di usso di costo minimo 46 Poniamo cλ∗ ij (f ∗) := c ij(f∗) − λ∗i + λ ∗
j e de niamo queste quantità costi
ridotti; allora le condizioni del teorema 2.2.1 possono essere riscritte nel seguente modo: cλij∗(f∗) := cij(f∗) − λ∗i + λ ∗ j = λ ∗ i − λ ∗ j − λ ∗ i + λ ∗ j = 0 per la (2.12) cλij∗(f∗) := cij(f∗) − λ∗i + λ ∗ j ≥ λ ∗ i − λ ∗ j − λ ∗ i + λ ∗ j = 0 per la (2.13) cλij∗(f∗) := cij(f∗)−λ∗i+λ ∗ j = λ ∗ i−λ ∗ j−µ ∗ ij−λ ∗ i+λ ∗ j = −µ ∗ ij ≤ 0 per la (2.14)
Le condizioni (2.12), (2.13) e (2.14) sono una generalizzazione delle condi- zioni di Bellman per il classico problema di usso di costo minimo e possono essere sintetizzate nel seguente sistema:
cλ∗ ij(f ∗) = 0 se 0 < f∗ ij < dij cλ∗ ij(f ∗) ≥ 0 se f∗ ij = 0 cλij∗(f∗) ≤ 0 se fij∗ = dij (2.15)
2.2 Formulazione variazionale del Problema di usso di costo minimo 47
2.2.1 Esempio
Consideriamo il grafo della gura (2.1):
-1 -5 2 4 0 Figura 2.1: Esempio
Consideriamo la funzione costo de nita nel seguente modo :
c(f ) = 5 − f12 3 , 4 − f13, 4f23+ 2, 20 − 2f24 7 , 2f34+ 3, 5 − f35, 3f45+ 1 2
Il nostro scopo è quello di trovare una f∗ tale che sia soluzione della (2.7)
che, per quanto visto sopra, è soluzione anche del sistema (2.11) per cui risolvendo : c(f∗) + λΓ + µ = s ≥ 0 hµ, f∗− di = 0, hc(f∗) + λΓ + µ, f∗i = 0 Γf∗ = q, 0 ≤ f∗ ≤ d, µ ≥ 0,
2.2 Formulazione variazionale del Problema di usso di costo minimo 48 dove c(f) è la funzione costo associata al grafo e q il vettore dei bilanci, si ottiene come soluzione f∗ = (2, 3, 0, 3, 0, 3, 1). La funzione costo calcolata
in f∗ vale : c(f∗) = 5 − 2 3 , 4 − 3, 4 ∗ 0 + 2, 20 − 2 ∗ 3 7 , 2 ∗ 0 + 3, 5 − 3, 3 ∗ 1 + 1 2 = = (1, 1, 2, 2, 3, 2, 2) .
Nel caso in cui cij(f∗) = cij, ovvero sia costante, le equazioni del teorema
(2.2.1) si trasformano nel seguente sistema:
( cij − λ∗i + λ ∗ j ≥ 0 ∀ (i, j) ∈ L cij − λ∗i + λ∗j ≤ 0 ∀ (i, j) ∈ U (2.16)
Infatti se consideriamo la prima disequazione sopra scritta, essa si ottiene dalla condizione (2.13) : cij ≥ λ∗i − λ ∗ j ⇒ cij − λ∗i + λ ∗ j ≥ 0
2.2 Formulazione variazionale del Problema di usso di costo minimo 49 La seconda disequazione della (2.16) si ottiene facendo lo stesso calcolo nella (2.14): cij = λ∗i − λ ∗ j − µ ∗ ij ⇒ cij − λ∗i + λ ∗ j = −µ ∗ ij ≤ 0
Anche in questo caso possiamo de nire i costi ridotti ponendo cλ∗
ij := cij − λ∗i + λ ∗
j, allora le condizioni (2.16) possono essere riscritte nel
seguente modo: cλij∗ ≥ 0 ∀ (i, j) ∈ L cλij∗ = 0 ∀ (i, j) ∈ T cλij∗ ≤ 0 ∀ (i, j) ∈ U (2.17)
Osserviamo che il usso di base f∗
ij è ammissibile se e solo se il usso sugli
archi appartenenti all'albero di copertura T rispetta i vincoli di capacitá, mentre il potenziale di base λ∗ è ammissibile se e solo se i costi ridotti degli
2.2 Formulazione variazionale del Problema di usso di costo minimo 50 Nella seguente tabella sono riassunti tutti i casi possibili per i ussi e i potenziali di base nel caso lineare.
usso di base potenziale di base 0 ≤ fij∗ ≤ dij cλ ∗ ij ≥ 0 ∀ (i, j) ∈ L ammissibile ∀ (i, j) ∈ T cλ∗ ij ≤ 0 ∀ (i, j) ∈ U
∃ (i, j) ∈ T tale che fij∗ < 0 ∃ (i, j) ∈ L tale che cλ∗ ij < 0
non ammissibile oppure oppure
∃ (i, j) ∈ T tale che fij∗ > dij ∃ (i, j) ∈ U tale che cλ ∗ ij > 0
∃ (i, j) ∈ T tale che fij∗ = 0 ∃ (i, j) ∈ L tale che cλ∗ ij = 0
degenere oppure oppure
∃ (i, j) ∈ T tale che fij∗ = dij ∃ (i, j) ∈ U tale che cλ ∗ ij = 0 fij∗ 6= 0 e f∗ ij 6= dij cλ ∗ ij 6= 0 ∀ (i, j) ∈ L non degenere ∀ (i, j) ∈ T cλ∗ ij 6= 0 ∀ (i, j) ∈ U
Applicando il teorema sulle condizioni su cienti di ottimalità per soluzio- ni di base ai problemi usso - potenziali si ottengono le condizioni di Bellman nel caso capacitato.
2.2 Formulazione variazionale del Problema di usso di costo minimo 51 Le condizioni per il potenziale di base λ∗ sono de nite dalla soluzione del
sistema λTΓ
T = cTT ed i seguenti teoremi mostrano le relazioni tra usso e
potenziale.
Teorema 2.2.2. Data una tripartizione (T, L, U) degli archi che genera un usso di base f∗ ammissibile, se il potenziale di base λ∗ soddisfa le condizioni
di Bellman (2.17) allora il usso f∗ è ottimo.
Il teorema 2.2.2 è una condizione su ciente di ottimalità per il problema Primale, mentre il seguente corollario esprime la corrispondente condizione per il problema Duale.
Corollario 2.2.1. Data una tripartizione (T, L, U) che genera un potenziale di base ammissibile, se il usso di base è ammissibile, allora il potenziale è ottimo.
Se il usso di base f∗ è non degenere allora le condizioni di Bellman sono
anche necessarie per l'ottimalità, infatti abbiamo che:
Teorema 2.2.3. Sia (T, L, U) una tripartizione degli archi che genera un usso di base f∗ ammissibile e non degenere, sia λ∗ il potenziale di base
allora si ha che: f∗ é ottimo ⇔ ( cλ∗ ij ≥ 0 ∀ (i, j) ∈ L cλ∗ ij ≤ 0 ∀ (i, j) ∈ U
2.2 Formulazione variazionale del Problema di usso di costo minimo 52 Dim:
(⇒) Per ipotesi il usso f∗ è ammissibile e non degenere per cui vale che 0 < fij∗ < dij per ogni arco in T , quindi la tripartizione è unica e di
conseguenza gli archi in L e in U devono necessariamente rispettare le condizioni del sistema.
(⇐) Segue dal teorema 2.2.2.
2
Riprendendo il sistema (2.11) possiamo vedere che, anche nel caso va- riazionale, vale la stessa cosa del caso lineare. Infatti se cλ∗
ij (f∗) = 0 con
0 < fij∗ < dij per ogni arco (i, j) ∈ T allora le condizioni
cλ∗ ij (f
∗) ≥ 0 con f∗
ij = 0 per ogni arco (i, j) ∈ L
cλ∗
ij (f∗) ≤ 0 con fij∗ = dij per ogni arco (i, j) ∈ U
sono univocamente determinate, per cui esse diventano anche necessarie come dimostrato nel teorema precedente.
Capitolo 3
Funzioni Gap e algoritmi
risolutivi
In questo capitolo introdurremo le funzioni gap ( o di divergenza), le quali furono inizialmente introdotte per le disequazioni variazionali e successiva- mente utilizzate anche per problemi di programmazione convessa [15]. Una funzione gap è una funzione che risulta essere maggiore o uguale a zero sull'in- sieme su cui è de nita ed è nulla solo in corrispondenza di una soluzione della (VI); per cui è possibile esprimere la (VI) come problema di ottimizzazione tramite la minimizzazione di una funzione gap.
Inoltre essa si è mostrata utile nella de nizione degli algoritmi perché permette di identi care le soluzioni della disequazione variazionale con l'in- sieme dei suoi minimi globali. Come algoritmi analizzeremo quelli dei metodi di discesa, nei quali utilizzeremo l'opposto del gradiente della funzione gap per ottenere una direzione di discesa ammissibile e assicurare la convergenza globale della successione generata dall'algoritmo.
3.1 Funzioni gap 54
3.1 Funzioni gap
De nizione 3.1.1. Sia K ⊆ Rn chiuso, una funzione g : Rn → R si dice
funzione gap per la (VI) se valgono le seguenti condizioni :
g(x) ≥ 0 per ogni x ∈ K,
g(x) = 0 se e solo se x è una soluzione di (VI).
Osserviamo che la seguente funzione, introdotta da Auslender [13], è una funzione gap per la disequazione variazionale V I(K, F ):
g(y) = sup
x∈K
hF (y), y − xi (3.1)
Inoltre osserviamo che la (VI) è equivalente al seguente problema di ottimizzazione:
min
y∈Ksupx∈KhF (y), y − xi (3.2)
In generale la funzione (3.1) non è dierenziabile, ma con un'oppotuna regolazizzazione possiamo ottenere una funzione gap dierenziabile e
3.1 Funzioni gap 55 Sia G una matrice n × n simmetrica e de nita positiva e x ∈ Rn, in [7]
Fukushima considera la seguente funzione regolarizzata:
gF = minhF (x), y − xi + 1
2hy − x, G(y − x)i con y ∈ K (3.3) dove minimizza una funzione convessa su un insieme chiuso e convesso per cui il minimo esiste sempre in quanto la funzione è a valori niti su tutto K.
Lemma 3.1.1. Il problema (3.3) è equivalente per ogni x ∈ Rn al problema:
min ky − (x − G−1F (x))k2G con y ∈ K (3.4)
Dim:
La condizione necessaria e su ciente di ottimalità per il problema min
y∈Kf (y)
è h∇f(y0), z−y0i ≥ 0per ogni z ∈ K. Applicando tale condizione ai problemi
(3.3) e (3.4) otteniamo: per (3.3)
3.1 Funzioni gap 56 per (3.4)
h2G(y0− x + G−1
F (x)), z − y0i = 2hG(y0− x) + F (x), z − y0i ≥ 0
e dividendo per 2 si ha:
hG(y0 − x) + F (x), z − y0i ≥ 0 z ∈ K (3.6) da cui (3.5) è equivalente alla (3.6).
2
Osservazione 3.1.1. Data fx(y) = hy − x, G(x − y)i = ky − xk2G allora
∇fx(y) = G(y − x) + G(y − x) = 2G(y − x).
Per il lemma 3.1.1, per ogni x la soluzione ottima di (3.3) è la proiezione del punto (x − G−1F (x)) rispetto alla norma su G, sull'insieme K.
Proposizione 3.1.1. [7] Per ogni x ∈ Rn, sia H : Rn → Rn la funzione il
cui valore H(x) sia l'unica soluzione ottima del problema (3.3). Allora x è soluzione della disequazione variazionale V I(K, F ) se e solo se H(x) = x, ovvero x è un punto sso di H.
Dim:
Applicando il lemma 3.1.1 con y = H(x) si ottiene la tesi.
3.1 Funzioni gap 57 Il seguente teorema dimostra l'equivalenza tra il problema di ottimizza- zione e la (VI), nel quale de niamo la funzione f : Rn → R nel seguente
modo:
f (x) = −hF (x), H(x) − xi − 1
2hH(x) − x, G(H(x) − x)i (3.7) e consideriamo il seguente problema di ottimizzazione:
min
x∈Kf (x) (3.8)
Teorema 3.1.1. [7] Sia f(x) la funzione de nita in (3.7); allora f(x) è una funzione gap; conseguentemente, x è soluzione della (3.8) ed f(x) = 0 se e solo se è soluzione della V I(K, F ).
Dim:
i) La funzione f può essere scritta nel seguente modo: f (x) = 1 2{kG −1 F (x)k2G− kH(x) − (x − G−1F (x))k2G} (3.9) dove kG−1F (x)k G è la distanza tra x e x − G−1F (x), e kH(x) − (x −
G−1F (x))kG è la distanza tra (x − G−1F (x)) e la sua proiezione H(x)
su K. Di conseguenza f(x) ≥ 0 per ogni x ∈ K e per come abbiamo de nito H(x) tali distanze sono uguali se e solo se H(x) = x. Per la proposizione 3.1.1 si ha la tesi.
ii) Segue direttamente dalla i)
3.1 Funzioni gap 58 Per poter utilizzare sempre il problema (3.8), la funzione obiettivo deve soddisfare alcune proprietà, che nel teorema precedente non vengono con- siderate. Mostriamo quindi che, per ogni insieme K chiuso e convesso, la funzione f è sempre dierenziabile ogni volta che lo è la funzione F . In generale la funzione gap non è dierenziabile, non eredita questa proprietà da F . Una funzione gap dierenziabile con continuità per le disequazioni variazionali fu de nita per la prima volta da Fukushima in [7].
Teorema 3.1.2. [7] Se la funzione F : Rn→ Rn è continua allora lo è anche
f : Rn→ R; se F ∈ C1 ed è dierenziabile allora lo è anche f e il gradiente
è dato da:
∇f (x) = F (x) − [∇F (x) − G](H(x) − x). (3.10)
Dim:
Per dimostrare la continuità di f, supponiamo che F sia continua, allora per come abbiamo de nito H e per le proprietà della proiezione anche H è continua e da questo segue che anche f è continua. Per dimostrare la dierenziabilità de niamo la funzione h : Rn× K → R nel seguente modo:
h(x, y) = hF (x), y − xi + 1
2hy − x, G(y − x)i (3.11) Se F ∈ C1 ed è dierenziabile allora lo è anche h. Per la (3.7) si ha che:
3.1 Funzioni gap 59
f (x) = − min{h(x, y) : y ∈ K} (3.12) e poiché il minimo è univocamente determinato da y = H(x), dal teorema A.0.2 segue che f è dierenziabile e il gradiente è dato da
∇f (x) = −∇xh(x, H(x)). (3.13)
A questo punto la (3.10) segue dalla (3.11) e (3.13).
2 In generale la funzione f non è convessa per cui il problema (3.8) potrebbe avere minimi locali o punti stazionari che non la minimizzano globalmente su tutto K. La maggior parte degli algoritmi esistenti, però, è in grado di trovare soltanto punti stazionari se applicati ad un problema di estremo non convesso e per evitare questo inconveniente è stato formulato il seguente teorema:
Teorema 3.1.3. [7] Sia F : Rn → Rn una funzione C1, dierenziabile e la
cui matrice jacobiana ∇F (x) sia de nita positiva su K. Se x è un punto stazionario per (3.8), cioé:
h∇f (x), y − xi ≥ 0 per ogni y ∈ K, (3.14) allora x è una soluzione ottima globale di (3.8) e quindi risolve la V I(K, F ).
3.1 Funzioni gap 60 Dim:
Supponiamo che x sia soluzione della (3.14) e poniamo y = H(x). Allora se sostituiamo la (3.10) nella (3.14) si ha che:
hF (x) + G(H(x) − x), H(x) − xi ≥ h∇F (x)(H(x) − x), H(x) − xi (3.15) Poiché H(x) = PK,G(x − G−1F (x)), per la (2.2) si ha:
hx − G−1F (x) − H(x), G(y − H(x))i ≤ 0 ∀ y ∈ K (3.16) Sostituendo in quest'ultima y = x si ottiene:
hx − G−1F (x) − H(x), G(x − H(x))i =
hF (x) + G(H(x) − x), H(x) − xi ≤ 0. (3.17) A questo punto per la (3.15) e la (3.17) si ha:
h∇F (x)(H(x) − x), H(x) − xi ≤ 0. (3.18) La disequazione sopra vale se e solo se x = H(x) perché ∇F (x) è de nita positiva. Dalla proposizione 3.1.1 si ha che x risolve la V I(K, F ) e per il teorema 3.1.1 x è una soluzione ottima per (3.8).