Metodi di ricerca inesatta

Se F è fortemente monotona, possiamo stabilire un risultato di convergenza più forte che consente l'utilizzo di procedure di ricerca inesatte. Consideria- mo la seguente regola di Armijo:

siano α > 0 e 0 < β < 1 costanti; dato il punto xk _{e la direzione d}k

dell'iterazione k−esima, determiniamo la lunghezza del passo tkcome tk= βl

dove con l indichiamo il più piccolo intero non negativo tale che:

3.2 Algoritmi risolutivi 66 Teorema 3.2.2. [7] Sia {xk_{} la successione generata dall'iterazione}

xk+1 _{= x}k _{+ t}

kd(x)k, dove d(x)k = H(xk) − xk e tk ∈ [0, 1] sono deniti

dalla regola di Armijo (3.24). Supponiamo che K sia compatto e che F : Rn → Rn sia una funzione dierenziabile, F ∈ C1 e fortemente monotona con modulo µ > 0 su K. Supponiamo, inoltre, che F e ∇F siano lipschitziane (cfr.Denizione A.0.8) e continue su K. Allora la successione {xk_}sta in K

e converge all'unica soluzione di V I(K, F ), per ogni punto iniziale x0 _{∈ K}

se nella (3.24) la costante α è scelta tale che α < µ.

Dim:

Poiché le proprietà delle proiezioni e la lipschitzianità di F ci assicurano che Hè lipschitziana, segue che ∇f(x) è lipschitziana e quindi esiste una costante L > 0 tale che

k∇f (x) − ∇f (x0)k ≤ Lkx − x0k per ogni x, x0 ∈ K (3.25) Dalle disequazioni (3.21) e (3.25) si ha che per 0 ≤ t ≤ 1,

f (xk+ td(x)k) − f (xk) = Z t 0 h∇f (xk+ sd(x)k), d(x)kid(x)s = = th∇f (xk), d(x)ki + Z t 0 h∇f (xk+ sd(x)k) − ∇f (xk), d(x)kid(x)s

3.2 Algoritmi risolutivi 67 ≤ −µtkd(x)k_k2₊ Z t 0 Lskd(x)kk2_{d(x)s = (−µt +} 1 2Lt 2_)kd(x)k_k2_.

Dalle precedenti disuguaglianze è facile notare che per ogni 0 ≤ t ≤ min{1,2(µ − α)

L } con α < µ : f (xk+ td(x)k) ≤ f (xk) − αtkd(x)kk2

Di conseguenza, poiché tk= βl vale che per ogni k:

tk > min{β,

2β(µ − α)

L }. (3.26)

La convessità di K, poiché tk ≤ 1, ci assicura che la successione {xk}

generata dall'algoritmo è contenuta in K. Perciò per il teorema 3.1.1 la successione {f(xk_{)}è limitata inferiormente, per la (3.24)}

f (xk+1) ≤ f (xk) − αtkkd(x)kk2, (3.27)

e quindi {f(xk_{)} è monotona descrescente.}

Dalla (3.26) e (3.27) segue

lim

k→∞kd(x)

3.2 Algoritmi risolutivi 68 Poiché K è compatto, la successione {xk_{} ha almeno un punto di accu-}

mulazione, inoltre la (3.28) implica che ogni tale punto di accumulazione é un punto sso per H perché H è continua e d(x)k _{= H(x}k_{) − x}k_{. Dalla pro-}

posizione 3.3 segue che ogni punto di accumulazione della successione {xk_}

risolve la V I(K, F ). La forte monotonia di F garantisce l'unicità della so- luzione della disequazione variazionale (2.7), si ha quindi che la successione generata dall'algoritmo converge all'unica soluzione della V I(K, F ).

2 Anche per questo metodo mostriamo l'algoritmo:

Algoritmo

Passo 1: Siano k = 0 e x0 _{∈ K e ssiamo µ ∈ (0, 1)}

Passo 2: Se f(xk_{) = 0 allora STOP altrimenti vai al passo 3}

Passo 3: Cerca il più piccolo intero l non negativo tale che

f (xk_{+ β}l_d(x)k_{) ≤ f (x}k_{) − αβ}l_kd(x)k_k2_{, con d(x)}k_{= H(x}k_{) − x}k

imponi αk = βl e xk+1 = xk+ αkd(x)k

Passo 4: Se kxk+1_{− x}k_{k < µ allora STOP}

Capitolo 4

Applicazioni

4.1 Il principio di Wardrop

In questa sezione considereremo un problema particolare di ottimizzazione vincolata formalizzato mediante una V I, il cui obiettivo è quello di determi- nare una soluzione di equilibrio di Wardrop.

John Wardrop, ingegnere e studioso dei sistemi di trasporto, sviluppò nel 1952due principi, noti come principi di ottimalità di Wardrop, applicati pro- prio alle reti di trasporto e introdusse l'ipotesi del comportamento alternativo alla minimizzazione dei costi totali di trasporto.

I concetti che stanno alla base di questi principi hanno un forte legame con l'idea dell'equilibrio di Nash sviluppata nella teoria dei giochi, anche se, nelle reti di trasporto, l'analisi è resa più dicile dal fatto che gli utenti sono un numero elevato.

Tali principi aermano che :

1. all'equilibrio il costo di un cammino eettivamente utilizzato per una coppia origine - destinazione è minore o uguale del costo di qualsiasi altro cammino che congiunge la stessa coppia; di conseguenza questo principio è noto come user equilibrium;

4.1 Il principio di Wardrop 70 2. all'equilibrio il tempo medio di viaggio medio su tutti i percorsi è mi- nimo e dunque lo è anche il tempo totale speso complessivamente da tutti gli utenti sulla rete; tale principio è noto come system optimum. Possiamo quindi distinguere due tipi di rete di trasporto.

Nelle reti di trasporto che rispettano il primo principio, gli utenti hanno un comportamento intuitivo, non cooperativo e tendono a minimizzare il proprio tempo di viaggio, scegliendo il percorso che secondo loro è migliore e determinando così un equilibrio dei costi medi, raggiunto quando nessun utente può abbassare il proprio costo di trasporto.

Nelle reti che rispettano il secondo principio, invece, gli utenti hanno un comportamento cooperativo e scelgono il percorso minimizzando il tempo complessivo di viaggio di tutti gli utenti (costo totale della rete); corrisponde, quindi, ad una situazione di ottimo della collettività e determina un equilibrio dei costi marginali.

4.1.1 Modello variazionale di usso sugli archi e sui

cammini

Il problema di usso di equilibrio su reti di trasporto può essere formulato in termini di usso sugli archi o di usso sui cammini. Il modello sugli archi è più facile da gestire nelle applicazioni in quanto è quello che si accosta di più alle situazioni reali.

Introduciamo alcune notazioni:

ˆ W insieme delle coppie di nodi origine e destinazione (O-D);

4.1 Il principio di Wardrop 71 ˆ Cp la funzione costo sul cammino p;

ˆ m il numero totale dei cammini considerati e F = (Fp)p∈Pw il vettore

dei ussi sui cammini dove Fp è il usso sul cammino p;

ˆ d il vettore delle domande per ogni coppia di nodi w ∈ W con dw ≥ 0;

ˆ Φ = (φwp) la matrice di incidenza coppie-cammini i cui elementi sono

dati da:

φwp=

(

1 se p ∈ Pw

0 altrimenti

ˆ ∆ = {δap}la matrice di incidenza archi-cammini, dove

δap =

(

1 se l'arco a appartiene al cammino p 0 altrimenti

ˆ θw il costo minimo tra tutti i cammini in Pw cioé:

θw = min p∈Pw

Cp

Denizione 4.1.1. Un usso F si dice un usso di equilibrio sui cam- mini se per ogni w ∈ W e p ∈ Pw soddisfa le seguenti condizioni:

Se Fp > 0 allora Cp = θw (4.1)

Se Fp = 0 allora Cp ≥ θw (4.2)

Osservazione 4.1.1. Un usso F che soddisfa (4.1) e (4.2), soddisfa il primo principio di Wardrop user equilibrium.

4.1 Il principio di Wardrop 72 A questo punto possiamo scrivere l'insieme dei ussi ammissibili come:

KF := {F ∈ Rm : ΦF = d, F ≥ 0}.

Per ottenere una formulazione sugli archi del modello usso sui cammini è necessario denire ulteriori condizioni.

Il usso fa di un arco è dato dalla somma dei ussi dei cammini che lo

attraversano ovvero :

fa =

X

p∈P

δapFp (4.3)

quindi possiamo esprimere il vettore dei ussi sugli archi in funzione del vettore dei ussi sui cammini f = ∆F .

Se indichiamo con ca(f ) la funzione costo, non negativa, dell'arco a e con

c(f ) = (ca(f ))a∈A il vettore dei costi allora, per la proprietà di additività dei

costi sui cammini, si ha :

Cp(F ) = X a∈A ∆apca(f ) ovvero C(F ) = ∆Tc(∆F )

A questo punto per ottenere una relazione tra usso sugli archi e usso sui cammini è necessario denire il seguente insieme :

Kf,F := {f ∈ Rm : f = ∆F, ΦF = d, F ≥ 0}.

Il problema di assegnamento di traco in una rete di trasporto riguarda la previsione di ussi lungo gli archi della rete derivanti dalle scelte che ogni singolo utente eettua per determinare il cammino dalla propria origine alla

4.1 Il principio di Wardrop 73 propria destinazione. Per chiarire meglio le notazioni sopra indicate facciamo un esempio. Consideriamo il grafo in gura (4.1):

f1 f2

f3 f4

f5

Figura 4.1: Esempio di rete con due coppie (O-D) ˆ W = {w2, w3} = {(2-4), (3-4)}; ˆ Pw2 = {(2-4), (2-1-4)}, Pw3 = {(3-4), (3-1-4)}; ˆ d1 = d2 = 2 ˆ c(f∗_{) = (2, 7, 5, 10, f}3 5 + 1); ˆ Fp = 1 ∀ p ∈ P ; ˆ dalla (4.3) si ha che f∗ _{= (1, 1, 1, 1, 2) f}

5 = 2 perché appartiene a due

cammini;

ˆ il vettore dei costi sui cammini ottenuto sarà C(f∗_{) = (7, 2 + 9, 10, 5 +}

9) = (7, 11, 10, 14).

Osserviamo che i cammini utilizzati per ognuna delle due coppie (O-D) considerate sopra hanno costi diversi, per cui secondo il principio di equi- librio di Wardrop la rete non è in equilibrio. Infatti per esserlo gli utenti

4.1 Il principio di Wardrop 74 si dovrebbero distribuire in modo tale che, per ogni coppia (O-D), tutti i cammini utilizzati abbiano lo stesso costo, e quelli non utilizzati abbiano un costo non inferiore, ma in questo esempio non è così.

Teorema 4.1.1. [9] F∗ _{è un usso di equilibrio sui cammini se e solo se è}

soluzione della seguente disequazione variazionale V I(KF, C):

hC(F∗), F − F∗i ≥ 0 ∀ F ∈ KF (4.4)

Proposizione 4.1.1. [9] V I(KF, C) è equivalente alla V I(Kf,F, c).

Dim:

Il usso sugli archi può essere espresso in termini di usso sui cammini dalla fa =

P

p∈PδapFp , per cui essendo f = ∆F e C(F ) = ∆Tc(∆F ) la relazione

(4.3) porta alla seguente uguaglianza: hC(F∗), F − F∗i = cT_(f∗

)∆(F − F∗) = hc(f∗), f − f∗i. (4.5) 2

A dierenza del modello standard di usso sugli archi dove è necessa- rio che la domanda sia relativa solo ai nodi della rete, nel modello archi- cammini la richiesta di traco è riferita alla coppia (O-D). Quest'ultimo modello ha, però, il vantaggio di poter aggiungere vincoli di capacità sugli archi nell'insieme Kf,F.

4.2 Applicazione a problemi di usso legati al traco 75

4.2 Applicazione a problemi di usso legati al

traco

In questa sezione vediamo un'applicazione delle funzioni gap relativa ad una (V I) per un problema di usso sui cammini descritta in [19].

Consideriamo l'insieme dei ussi sui cammini ammissibili dato da:

X = ( F ≥ 0 : X p∈Pw Fp = dw, ∀w ∈ W ) .

Per ogni arco a la funzione di costo ca(f ) rappresenta il tempo di viaggio

associato all'arco a e dipende dal vettore dei ussi sugli archi f, mentre la cor- rispondente funzione costo sui cammini C(F )p indica il tempo di viaggio sul

cammino p ed è la somma dei tempi di viaggio degli archi che appartengono al cammino p:

Cp(F ) =

X

a∈A

∆apca(f )

Per il principio di equilibrio di Wardrop [17], un usso su tutti i possibili cammini F∗ _{∈ X è detto equilibrio di rete se è positivo solo su cammini di}

costo minimo, ossia per ogni coppia origine/destinazione w ∈ W e per ogni cammino p ∈ Pw si ha l'implicazione:

F_p∗ > 0 =⇒ Cp(F∗) = min q∈Pw

4.2 Applicazione a problemi di usso legati al traco 76 Il problema di trovare un equilibrio di rete è equivalente a risolvere la seguente disuguaglianza variazionale [11]:

trovare F∗ _{∈ X tale che hC(F}∗_{), y − F}∗_{i ≥ 0, ∀y ∈ X. (4.6)}

Consideriamo la rete mostrata in Figura (4.2), con due coppie origi- ne/destinazione:

ˆ w1 = (1, 4) con richiesta d1 = 4,

ˆ w2 = (1, 5) con richiesta d2 = 6.

Figura 4.2: Rete dell'esempio.

Ogni coppia è connessa con due cammini:

ˆ Pw1 = {(1 − 2 − 4); (1 − 3 − 4)},

4.2 Applicazione a problemi di usso legati al traco 77 Denotiamo il usso sui cammini rispettivamente con F1, F2, F3, F4, allora

l'insieme dei ussi sui cammini ammissibili è dato da:

X =F ∈ R4₊ : F1+ F2 = 4, F3+ F4 = 6 .

Assumiamo che le funzioni costo sugli archi siano date come segue:

                       c12 := f12+ 1 = F1+ F3+ 1, c13 := 3f13+ 2 = 3(F2+ F4) + 2, c24 := 2f24+ f34+ 1 = 2F1+ F2+ 1, c25 := 2f25+ f35+ 3 = 2F3+ F4+ 3, c34 := f34+ 2 = F2+ 2, c35 := 4f35+ 1 = 4F4 + 1.

perciò i corrispondenti costi sui cammini saranno:

           C1 = c12+ c24 = 3F1+ F2 + F3+ 2, C2 = c13+ c34 = 4F2+ 3F4+ 4, C3 = c12+ c25 = F1+ 3F3 + F4+ 4, C4 = c13+ c35 = 3F2+ 7F4+ 3,

L'operatore della disequazione variazionale (4.6) è C(F ) = AF + B con

A =       3 1 1 0 0 4 0 3 1 0 3 1 0 3 0 7       e B =       2 4 4 3       .

4.2 Applicazione a problemi di usso legati al traco 78 La matrice A è denita positiva, quindi la mappa C è fortemente mono- tona ed esiste una soluzione unica della disequazione variazionale (4.6), cioé esiste un solo equilibrio di rete.

Consideriamo ora la funzione gap regolarizzata di Fukushima:

gF = max y∈X  hC(F ), F − y)i − 1 2kF − yk 2  .

Tale funzione è dierenziabile con continuità e fortemente convessa, per- ché la matrice A + AT _{− I è denita positiva.}

Non consideriamo le variabili F2 e F4 in quanto i vincoli relativi alla

richiesta di usso permettono di scrivere le variabili F2 e F4 in funzione delle

variabili F1 e F3.

L'algoritmo di discesa 3.2.1 applicato a gF _{può essere utilizzato per cal-}

colare l'equilibrio di rete; la Tabella 4.1 riporta le prime quattro iterazioni dell'algoritmo partendo dal usso ammissibile (4, 0, 6, 0).

Iterazione F1 F2 F3 F4 gF 0 4 0 6 0 1.5000 · 102 1 2.679622 1.320378 4.019434 1.980566 8.8840 · 10−3 2 2.631471 1.368529 4.052452 1.947548 1.5156 · 10−6 3 2.631587 1.368413 4.052626 1.947374 2.5905 · 10−10 4 2.631579 1.368421 4.052632 1.947368 1.1450 · 10−14

Tabella 4.1: Risultati numerici dell'algoritmo di discesa applicato all'esempio.

4.3 Formulazione variazionale del problema dei cammini minimi 79 Notiamo che i costi dei cammini che corrispondono alla soluzione di equilibrio

F∗ = (2.6316, 1.3684, 4.0526, 1.9474)

sono

C(F∗) = (15.3158, 15.3158, 20.7368, 20.7368),

ovvero i due cammini che connettono ogni coppia origine/destinazione hanno lo stesso costo. Inoltre i moltiplicatori di Lagrange λ∗ _{= (15.3158, 20.7368)}

associati a F∗ _{nelle condizioni LKT (1.3.1) coincidono con i costi all'equili-}

brio.

4.3 Formulazione variazionale del problema dei

cammini minimi

Il problema dei cammini minimi, come abbiamo già visto nel paragrafo 1.2.1, è un caso particolare del usso di costo minimo; infatti se su un grafo sono noti i costi degli archi, spesso il problema è quello di trovare un cammino di costo minimo da un nodo di partenza ad uno nodo di arrivo. Problemi di questo tipo sono, ad esempio, la ricerca di un percorso di costo minimo tra una stazione e l'altra o tra un aeroporto ed un altro. Il problema dei cammini minimi nella forma variazionale consiste nel determinare

4.3 Formulazione variazionale del problema dei cammini minimi 80 f∗ ∈ Kf := {f ∈ Rm : Γf = q, f ≥ 0} tale che: hc(f∗_{), f − f}∗_{i ≥ 0 ∀f ∈ K} f (4.7) dove qi = ( −(n − 1) se i = r 1 se i 6= r

Non avendo capacità superiori sugli archi si ha che B è una base se e solo se rappresenta un albero di copertura del grafo; inoltre esso è orientato, cioé contiene un cammino orientato di radice r, se e solo se B è una base ammissibile. Se indichiamo con Tr un albero di copertura, il usso di base

ad esso associato è non degenere in quanto ogni arco ha usso diverso da zero. Inoltre la soluzione della (4.7) è proprio la soluzione di base associata all'albero di copertura del problema lineare di estremo:

       min c(f∗)Tf Γf = q f ≥ 0 (4.8)

Il vettore dei potenziali di base sarà tale che:

4.3 Formulazione variazionale del problema dei cammini minimi 81 quindi λi rappresenta il costo del cammino orientato da r a i.

Poiché i ussi di base sono ammissibili e non degeneri allora le condizioni di Bellman sono necessarie e sucienti per l'ottimalità.

Teorema 4.3.1. Sia Tr un albero di copertura orientato di radice r associato

ad una soluzione di base del problema (4.8) e λ il vettore dei potenziali asso- ciati a Tr. Allora Tr è un albero dei cammini minimi se e solo se Tr verica

le condizioni di Bellman:

cλ_ij(f∗) = cij(f∗) + λi− λj ≥ 0 ∀(i, j) 6∈ Tr

4.3.1 Esempio

Dato il grafo in Figura (4.3):

1 -5 1 1 1 1 Figura 4.3: Esempio

4.3 Formulazione variazionale del problema dei cammini minimi 82 Sia la funzione costo così fatta:

c(f ) = (2+f12, f13 2 , f23+1, f24+f13, f34−1, f35+5f12, f45+ f12 2 , f46+ f34 4 , f56+2f13)

e sia f∗ _{= (1, 4, 0, 0, 3, 0, 1, 1, 0) una soluzione di base di (4.8). Vogliamo tro-}

vare l'albero di copertura ad essa associato e mostrare utilizzando il teorema 4.3.1 che esso rappresenta un albero dei cammini minimi.

Sia T1 l'albero di radice r = 1 come in gura (4.4)

1 -5 1 1 1 1

Figura 4.4: albero di copertura

Se calcoliamo il vettore dei potenziali mediante le equazioni (4.9) otte- niamo il vettore λ = (0, 3, 2, 4, 5, 5) e svolgendo i conti si ha che:

ˆ cλ ij(f

∗_{) = c}

ij(f∗) + λi− λj = 0 per ogni arco dell'albero T1

ˆ cλ ij(f

∗_{) = c}

4.3 Formulazione variazionale del problema dei cammini minimi 83 3 1 2 2 1 -5 1 1 1 1 1

Figura 4.5: albero dei cammini minimi

Le condizioni di Bellman sono vericate, quindi per il teorema 4.3.1 l'albero (4.4) è l'albero dei cammini minimi con c(f∗_{) = (3, 2, 1, 4, 2, 5, 1, 1, 8).}

Osservazione 4.3.1. Osserviamo che se poniamo: qi =

( −(P

i6=rbi) se i = r

bi se i 6= r

con bi > 0 ed i 6= r allora la soluzione del problema dei cammini minimi

in forma variazionale è un usso di equilibrio di Wardrop per il problema ove le coppie origine destinazione siano (r, i) con domanda bi e i 6= r.

Appendice A

Denizioni e teoremi utilizzati

Denizione A.0.1. Un grafo si dice connesso se per ogni coppia di nodi esiste un cammino che li connette non necessariamente orientato.

1

2

3

4

5

Figura A.1: Grafo connesso

1

2

3

4

5

Figura A.2: Grafo non connesso

Denizione A.0.2. Un albero di copertura per un grafo G = (N, A) é un sottoinsieme T ⊆ A dei suoi archi tale che (N, T ) è un grafo connesso, orientato e privo di cicli; un albero di copertura contiene esattamente n − 1 archi. Inoltre chiamiamo foglia di T un nodo raggiunto solo da un arco.

Appendice ADenizioni e teoremi utilizzati 85

1

2

3

4

5

Figura A.3: Albero di copertura

Il grafo (A.3) rappresenta un albero di copertura, mentre quelli nelle gure (A.1) e (A.2) non lo sono perché il primo contiene dei cicli e il secondo non é connesso.

Denizione A.0.3. Un punto x∗ _{∈ Ω si dice punto di minimo globale}

(o assoluto) di f su Ω se f(x∗_{) ≤ f (x) ∀x ∈ Ω.}

Denizione A.0.4. Un punto x∗ _{∈ Ω si dice punto di minimo locale (o}

relativo) di f su Ω se esiste un intorno B(x∗_{, r) di x}∗ _{tale che}

f (x∗) ≤ f (x) ∀x ∈ Ω ∩ B(x∗_{, r).}

Denizione A.0.5. Sia X un aperto di Rn e sia f : X −→ R una funzione.

Si dice che f è semicontinua inferiormente nel punto x0 ∈ X se si ha

f (x0) ≤ lim inf x→x0

f (x)

Denizione A.0.6. Sia X un aperto di Rn _{e sia f : X −→ R una funzione.}

Si dice che f è semicontinua superiormente nel punto x0 ∈ X se si ha

f (x0) ≥ lim sup x→x0

Appendice ADenizioni e teoremi utilizzati 86 Denizione A.0.7. Sia X un aperto di Rn _{e sia f : X −→ R una funzione.}

Si dice che f è semicontinua inferiormente, o superiormente, in X se lo è in ogni punto di X.

Denizione A.0.8. Sia X ⊆ Rn _{e sia F : X → R}m_{. Diciamo che F è}

Lipschitziana, con modulo L > 0, se si ha

kF (x) − F (y)k ≤ Lkx − yk per ogni x, y ∈ X

Denizione A.0.9. Un sottoinsieme K di Rn _{si dice convesso se per ogni}

coppia di punti x e y in K il segmento con estremi x e y è contenuto in K, ossia

λx + (1 − λ)y ∈ K, ∀λ ∈ [0, 1]

Denizione A.0.10. Una funzione F : Rn

→ Rn _{si dice monotona su}

X ⊆ Rn se

hF (x) − F (y), x − yi ≥ 0 ∀x, y ∈ X

Denizione A.0.11. Una funzione F : Rn_{→ R}nsi dice pseudo-monotona

su X ⊆ Rn _se

hF (y), x − yi ≥ 0 ⇒ hF (x), x − yi ≥ 0 ∀x, y ∈ X

Osservazione A.0.1. Se F : Rn _{→ R}n è pseudo-monotona e continua,

X ⊆ Rn _{convesso, allora ∀x, y ∈ X si ha}

hF (y), x − yi ≥ 0 ⇔ hF (x), x − yi ≥ 0

Prendiamo x = (1 − t)u + ty con u, y ∈ X e t ∈ (0, 1), allora sostituendo otteniamo:

Appendice ADenizioni e teoremi utilizzati 87 Se divido per (1−t) > 0, la disequazione diventa hF ((1−t)u+ty), (u−y)i ≥ 0; per ipotesi F è continua per cui avremo che:

lim

t→1hF ((1 − t)u + ty), u − yi = hF (y), u − yi ≥ 0 ∀u, y ∈ R n_.

Denizione A.0.12. Una funzione F : Rn _{→ R}n _{si dice strettamente}

monotona su X ⊆ Rn _se

hF (x) − F (y), x − yi > 0 ∀ x, y ∈ X con x 6= y

Denizione A.0.13. Una funzione F : Rn

→ Rn _{si dice fortemente}

monotona su X ⊆ Rn se esiste α > 0 tale che

hF (x) − F (y), x − yi > αkx − yk2 _{∀x, y ∈ X}

Denizione A.0.14. Una matrice M simmetrica di ordine n a coecienti reali si dice denita positiva se per ogni vettore x ∈ Rn _{si ha che}

xTM x > 0.

Denizione A.0.15. Una funzione f : X → Rm _{con X ⊆ R}n _{aperto è}

dierenziabile in un punto x0 del dominio se esiste un'applicazione lineare

L : Rn→ Rm _{tale che}

lim

khk→0

f (x0+ h) − f (x0) − L(h)

Appendice ADenizioni e teoremi utilizzati 88 Denizione A.0.16. Sia X ⊆ Rn_{. Una multifunzione f : X → R}m _{si dice}

chiusa in un punto x ∈ X se

xk −→ x, yk _{−→ y, con y}k _{∈ f (x}k_{) ∀k =⇒ y ∈ f (x)}

La funzione f si dice chiusa in un sottoinsieme S ⊂ X se è chiusa in ogni punto di S.

Denizione A.0.17. z : X → R è una funzione di discesa (relativa all'algoritmo T ) se é continua ed ha le seguenti proprietà:

1. x 6∈ M implica z(y) < z(x) ∀ y ∈ T (x), 2. x ∈ M implica z(y) ≤ z(x) ∀ y ∈ T (x).

Teorema A.0.1 (Zangwill). [12, 14] Sia T : X → 2X _{una mappa che rap-}

presenta un algoritmo e consideriamo una successione {xk_{} generata dal-}

l'algoritmo che soddisfa xk+1 _{∈ T (x}k_{). Se le tre condizioni seguenti sono}

vericate:

1. Tutti i punti xk _{sono contenuti nell'insieme compatto K ⊂ X;}

2. Esiste una funzione di discesa z : X −→ R;

3. La funzione T è chiusa (cfr. Denizione A.0.16) su X \ M e ∀x ∈ X \ M, T (x) 6= ∅;

allora ogni punto limite appartiene a M.

Teorema A.0.2. Sia ϕ : Rm_{×K −→ R una funzione continua e K ⊂ R}n_{. Si}

indichi con ψ(x) = inf{ϕ(x, y) | y ∈ K}, M(x) = {y ∈ K | ϕ(x, y) = ψ(x)}. Si supponga che per ogni x ∈ Rm_{, M (x) 6= ∅e che M sia limitata nell'intorno}

Appendice ADenizioni e teoremi utilizzati 89 di x. Sia Ω un aperto di Rm _{tale che ϕ}0

x (derivata parziale rispetto a x) esista

su Ω × K e sia continua su Ω × K. Allora per ogni x ∈ Ω, si ha ψ0(x, d) = inf{(ϕ0_{x(x, y), d) | y ∈ M (x)}, ∀ d ∈ R}m.

Se in un punto x ∈ Ω, M(x) è uguale a un solo punto y(x), allora ψ è derivabile nel senso di Gâteaux in quel punto e si ha

Appendice B

Richiami sulla teoria della dualità

lineare

Ad ogni problema P L si può associare un nuovo problema avente con es- so una stretta relazione; infatti, la risoluzione del secondo problema, detto Duale e indicato con (D), permette di dedurre importanti proprietà del pro- blema originario, detto Primale ed indicato con (P ). Da un punto di vista computazionale, è possibile risolvere il problema duale, invece del primale, ed ottenere le stesse informazioni sulla soluzione ottima del primale.

Nella P L è possibile costruire il problema duale partendo dalla possibilità di determinare delle stime inferiori del valore ottimo della funzione obiettivo di un problema primale e procedendo a denire nuovi vincoli e condizioni per restringere il più possibile questa stima. Otteniamo che la matrice dei coecienti dei vincoli del duale si ottiene trasponendo quella del primale, ad ogni variabile di (P ) corrisponde un vincolo di (D) e viceversa e c'é uno scambio tra i termini noti dei vincoli e i coecienti della funzione obiettivo. Proprio per questa costruzione, in maniera simmetrica (P ) risulta il duale di (D)e i due problemi vengono chiamati coppia primale-duale.

La denizione e costruzione del problema duale è possibile anche quando il problema P L è scritto in forma generale, cioé non è legato al fatto che il

Appendice B. Richiami sulla teoria della dualità lineare 91 problema dato abbia solo vincoli di disuguaglianza e variabili non vincolate in segno.

Inoltre la teoria della dualità può essere estesa anche al caso di problemi di Programmazione Non Lineare, dove esistono interessanti interpretazioni del problema duale, soprattutto in ambito di allocazione ottima di risorse ed in ambito di trasporti.

Le caratteristiche fondamentali di una coppia primale-duale possono es- sere riassunte con il seguente schema:

ˆ il problema duale di un problema primale di massimo (minimo) è un problema di minimo (massimo);

ˆ ad ogni vincolo primale di uguaglianza è associata una variabile dua- le non vincolata in segno di costo uguale al termine noto del vincolo primale associato;

ˆ ad ogni vincolo primale di disuguaglianza è associata una variabile dua- le vincolata in segno di costo uguale al termine noto del vincolo primale associato;

ˆ ad ogni variabile primale non vincolata in segno è associato un vincolo duale di uguaglianza il cui termine noto è il costo della variabile primale associata;

ˆ ad ogni variabile primale vincolata in segno è associato un vincolo duale di disuguaglianza il cui termine noto è il costo della variabile primale associata.

Appendice B. Richiami sulla teoria della dualità lineare 92 Volendo schematizzare il tutto, per ogni i, j ∈ I con I insieme di indici, si ha la seguente tabella:

Primale Duale

min cT_{f max y}T_q

Γif ≥ qi ← Vincoli !Variabili → yi ≥ 0

Γif ≤ qi ← Vincoli !Variabili → yi ≤ 0

Γif = qi ← Vincoli !Variabili → yi libera

fj ≥ 0 ← Variabili ! Vincoli → yTΓj ≤ cj

fj ≤ 0 ← Variabili ! Vincoli → yTΓj ≥ cj

Appendice B. Richiami sulla teoria della dualità lineare 93 I seguenti problemi sono un esempio di coppia primale - duale nota come coppia asimmetrica:        min cT_f Γf = q f ≥ 0 ( max yT_q yT_{Γ ≤ c}T

Ogni coppia primale - duale gode di proprietà importanti sia dal punto di vista teorico che pratico e per mettere in evidenza in modo più chiaro la relazione tra i valori delle funzioni obiettivo. I teoremi che enunceremo sono indipendenti dalla particolare forma usata e valgono per ogni coppia primale - duale ove il primale sia un problema di minimo.

Teorema B.0.1 (Debole della Dualità). Se ¯f è soluzione ammissibile per il problema primale ed ¯y è ammissibile per quello duale allora si ha che ¯yT_{q ≤}

cTf¯.

Questo teorema ci dice che il valore della funzione obiettivo duale in qualunque punto ammissibile del duale è minore o uguale del valore della fuzione obiettivo primale in qualunque punto ammissibile del primale. In

Nel documento una formulazione variazionale del problema di flusso di costo minimo (pagine 70-111)