1.3 Programmazione non lineare
1.3.1 Condizioni generali di ottimalità
Nel caso non vincolato, nell'ipotesi che f sia dierenziabile due volte, le condizioni necessarie sono l'annullamento del gradiente di f e la matrice hessiana di f semide nita positiva; vediamo cosa cambia nel caso in cui sono presenti dei vincoli, ponendo in particolare l'attenzione sulle condizioni del primo ordine. Le condizioni di ottimalità si servono delle condizioni di regolarità sui vincoli descritte nel paragrafo precedente.
Il gradiente di una funzione f(x) in un punto è sempre ortogonale alla curva di livello passante per quel punto; per cui, se calcoliamo il gradiente di un vincolo hi(x) = 0 in un punto di minimo vincolato x, la direzione di ∇hi(x)
è ortogonale al vincolo e nel caso di una disequazione punta verso l'interno della regione ammissibile.
Quindi una condizione per il punto di minimo x di una funzione f può essere espressa dicendo che esistono costanti scalari, µj e λi , tale che ∇f(x) =
µj∇hi(x) e ∇f(x) = λi∇gi(x). In generale questa condizione può essere
espressa anche in altri termini introducendo la funzione Lagrangiana:
L(x, λ, µ) = f (x) + Σm
i=1λigi(x) + Σpj=1µjhj(x) (1.13)
∇xL(x, λ, µ) = 0 (1.14)
Con quest'ultima equazione troviamo i punti di minimo del problema vincolato tra i punti stazionari della funzione lagrangiana. I parametri λ, µ presenti nella funzione prendono il nome di moltiplicatori di Lagrange.
1.3 Programmazione non lineare 28 Si può dimostrare che, in ipotesi di regolarità dei vincoli, la (1.14) è una condizione necessaria, ma in generale non è su ciente a nché x sia un punto di minimo per la f nel problema vincolato.
Con queste premesse possiamo enunciare il seguente teorema:
Teorema 1.3.1. [8] Se x è un minimo locale (cfr.De nizione A.0.4) di f su Ωed i vincoli sono regolari in x, allora esistono due vettori λ ∈ Rm e µ ∈ Rp
tali che (x, λ, µ) soddisfa il sistema di Lagrange-Kuhn-Tucker (LKT):
∇xL(x, λ, µ) = ∇f (x) + Σmi=1λi∇gi(x) + Σpj=1µj∇hj(x) = 0 λigi(x) = 0 ∀ i = 1, ..., m λ ≥ 0 g(x) ≤ 0 h(x) = 0 (1.15)
De nizione 1.3.6. x è chiamato punto stazionario se (x, λ, µ) è una soluzione del sistema LKT (1.15).
In generale il teorema 1.3.1 senza l'ipotesi di regolarità dei vincoli non è più valido.
1.3 Programmazione non lineare 29 Esempio
Sia dato il seguente problema: (
min x + 2y x2+ y2 ≤ 0
L'insieme Ω = {(x, y) ∈ R2 : x2+ y2 ≤ 0} = {(0, 0)} e quindi la lagran-
giana è data da L(x, y, λ) = x + 2y + λ(x2+ y2). A questo punto applicando
il teorema 1.3.1 otteniamo che :
∇xL(x, y, λ) = 1 + 2λx = 0 ∇yL(x, y, λ) = 2 + 2λy = 0 λ(x2+ y2) = 0 λ ≥ 0 x2 + y2 ≤ 0
Tale sistema per il punto (x, y) = (0, 0) è impossibile in quanto i vincoli in tale punto non sono regolari.
Infatti il cono delle direzioni ammissibili nel nostro problema è dato dall'insieme D(x, y) = {d ∈ R2 : dT∇g(x, y) ≤ 0}; quindi, poiché vale che:
∇g(x, y) = 2x 2y ! ⇒ ∇g(x, y) = 0 0 ! Di conseguenza d1 d2 0 0 ! ≤ 0 ⇒ 0 ≤ 0
1.3 Programmazione non lineare 30 per cui essendo vero per ogni d = (d1, d2) si ha che D(x, y) = R2 mentre
TΩ(x, y) = TΩ(0, 0) = {(0, 0)}. Questo signi ca che D(x, y) 6= TΩ(x, y) e per
la De nizione (1.3.5) di vincoli regolari in un punto, quelli del nostro proble- ma non sono regolari.
Le funzioni convesse dierenziabili si possono caratterizzare anche tramite le proprietà delle loro derivate e a tal proposito enunciamo i seguenti teoremi: Teorema 1.3.2. [8] Se X ⊆ Rn è un insieme convesso aperto e f : X → R
una funzione di classe C1; allora f è convessa su X se e solo se
f (y) ≥ f (x) + (y − x)T∇f (x) ∀x, y ∈ X.
Osserviamo che f(y) − f(x) ≥ h∇f(x), y − xi per ogni x, y ∈ X e se vale f (y) − f (x) ≥ h∇f (x), y − xi ≥ 0 per ogni y ∈ X allora x è minimo su X.
Infatti per il teorema 1.3.2 una funzione è convessa se e solo se il gra co della funzione sta sopra al piano tangente ad esso in ogni suo punto.
Inoltre in relazione al secondo ordine enunciamo il seguente teorema: Teorema 1.3.3. Se X ⊆ Rn è un insieme convesso aperto e f : X → R una
funzione di classe C2; allora f è convessa ⇔ la matrice ∇2f (x)è semide nita
positiva per ogni x ∈ X.
Teorema 1.3.4. Supponiamo che f sia convessa, i vincoli gi siano convessi
per ogni i = 1, ..., m ed i vincoli hj siano lineari per ogni j = 1, ..., p. Se
(x, λ, µ)è una soluzione del sistema LKT (1.15), allora x è un minimo globale di f su Ω.
1.3 Programmazione non lineare 31 Dim:
Siano λ e µ due vettori ssati, la Lagrangiana L(x, λ, µ) è una funzione convessa rispetto ad x in quanto somma di funzioni convesse. Poiché (x, λ, µ) è una soluzione del sistema LKT (1.15), ovvero ∇xL(x, λ, µ) = 0, si ha che:
L(x, λ, µ) ≥ L(x, λ, µ) ∀ x ∈ Rn.
Osserviamo che L(x, λ, µ) = f(x) e di conseguenza per ogni x ∈ Ω si avrà che:
f (x) ≤ L(x, λ, µ) = f (x) + Σmi=1λigi(x) + Σ p
j=1µjhj(x) ≤ f (x).
A questo punto abbiamo concluso che f(x) ≥ f(x) ∀ x ∈ Rn quindi x è
un minimo globale di f su Ω.
Capitolo 2
Problema di usso di costo
minimo nel caso variazionale
Molti problemi di Economia, Ingegneria, Fisica, Biologia e Ricerca Operativa vengono studiati attraverso le Disequazioni Variazionali, introdotte da Hart- man e Stampacchia nel 1966 nell'ambito del calcolo delle variazioni. La loro formulazione in dimensione nita ha acquisito importanza quando è stato dimostrato che esse consentono di formalizzare la condizione di equilibrio di Wardrop per un problema di usso su reti stradali (Principi di equilibrio di Wardrop 4.1).
Dopo aver descritto le principali proprietà delle disequazioni variazionali, indicate con il termine V I (Variational Inequality), ed i relativi teoremi di esistenza e unicità delle soluzioni, introdurremo esplicitamente il problema del usso di costo minimo formulato mediante una disequazione variaziona- le in dimensione nita, dove l'operatore rappresenta la funzione costo sugli archi del grafo considerato. In particolare, mediante le condizioni di Lagran- ge descritte nel primo capitolo, determineremo una generalizzazione al caso variazionale delle classiche condizioni di Bellman associate ai problemi di programmazione lineare su gra .
2.1 Disequazioni variazionali 33
2.1 Disequazioni variazionali
De nizione 2.1.1. Sia K ⊆ Rn un insieme non vuoto e sia F : K → Rnuna
funzione continua su K. Si de nisce disequazione variazionale V I(K, F ) il problema di trovare un vettore x∗ ∈ K tale che
hF (x∗), x − x∗i ≥ 0, ∀ x ∈ K (VI) dove con h·, ·i indichiamo il prodotto scalare usuale in Rn.
Dal punto di vista geometrico, risolvere la disequazione variazionale (VI) consiste nel trovare un punto x∗ tale che F (x∗) forma un angolo non ottuso
con ogni vettore y − x∗ al variare di y in K.
La connessione tra le disequazioni variazionali e la teoria dell'ottimiz- zazione può essere osservata considerando un problema di ottimizzazione dierenziabile, con f e K opportuni, del tipo:
(
min f (x)
x ∈ K. (2.1)
Se K è convesso allora la (VI) corrisponde alla condizione necessaria di ottimalità del problema (2.1). Se f è convessa allora la condizione diventa anche su ciente cioé
x∗ è soluzione di V I(K, ∇f) ⇔ x∗ risolve (2.1)
Nella de nizione K è un sottoinsieme generico, ma nella maggior parte delle applicazioni K è chiuso e convesso quindi di solito si assume con queste proprietà. In particolare, nel caso in cui K sia convesso, risolvere la disequa- zione V I(K, F ) signi ca trovare x∗ tale che il piano hF (x∗), x − x∗i = 0 sia
2.1 Disequazioni variazionali 34 di supporto per K.
I risultati relativi all'esistenza delle soluzioni di una disequazione varia- zionale sono soprattutto i corollari del teorema di Hartman - Stampacchia, il quale ci garantisce l'esistenza nel caso in cui l'operatore F sia continuo e K sia compatto. L'unicità della soluzione è legata alla stretta monotonia di F . Per arontare i teoremi di esistenza e unicità, abbiamo bisogno di intro- durre alcune condizioni e de nizioni che ci garantiscono tali proprietà.
De nizione 2.1.2. Sia K ⊆ Rn un insieme non vuoto, chiuso e conves-
so, e sia G una matrice n × n simmetrica e de nita positiva. Si de nisce proiezione di un punto y ∈ Rn su un insieme K, rispetto alla norma G,
indicata con PG,K(y), la soluzione del seguente problema:
(
min ky − xkG
x ∈ K
dove la norma di G di un vettore x ∈ Rn è data da kxk
G= (xTGx) 1 2.
Dalla de nizione di proiezione possiamo dedurre direttamente che Osservazione 2.1.1. [1] Per ogni x ∈ Rn e per ogni y ∈ K si ha che
hx − PG,K(x), G(y − PG,K(x))i ≤ 0. (2.2)
De nizione 2.1.3. Sia K ⊆ Rn un chiuso e convesso e sia F : K −→ K
una funzione. Un punto x ∈ K è detto punto sso per F se:
2.1 Disequazioni variazionali 35 Teorema 2.1.1 (Brower). [10] Sia K ⊆ Rn compatto e convesso e sia
F : K −→ K continua. Allora F ammette un punto sso.
Teorema 2.1.2. [10] Sia K ⊆ Rn chiuso, convesso e non vuoto.
Allora y = PG,K(x) se e solo se :
y ∈ K : hy, w − yi ≥ hx, w − yi oppure
hx − y, w − yi ≤ 0 per ogni x ∈ K.