 |  |
| |
 |
informatica |
|
OTTIMIZZAZIONE SENZA VINCOLI
In generale si vuole risolvere il problema di trovare un punto x* tale che
f(x*) = min . (1)
N.B. Focalizzarsi sul problema di minimizzazione non fa perdere in generalità, dato che un problema di massimo equivale al problema di minimo della stessa funzione cambiata di segno.
DIFFICOLTA'
Supponiamo quindi, salvo diverso avviso, che f(x) abbia derivate prime e seconde continue e non sia illimitata.
Indicheremo con g(x) il gradiente f(x) e con G(x) l'Hessiano f(x).
Sia x* un ottimo locale per (1) e consideriamo una retta passante per x* data da x* + as dove s è stato normalizzato, cioè ||s||=1.
Allora
f/ a = gTs e f/ a = sTG s.
Dato che x* è un minimo locale dovrà aversi, per qualunque s,
sTg* = 0
dove g*=g(x*), e
sTG*s
dove G*=G(x*).
Si vede facilmente (ad esempio scegliendo a turno come s uno dei versori degli assi) che ciò equivale a porre
g*= 0 (2)
e
sTG*s s. (3)
La (2) è detta condizione necessaria del primo ordine e la (3) condizione necessaria del secondo ordine. Quest' ultima ci dice che G* deve essere una matrice definita non-negativa.
I punti in cui valgono le (2) sono detti stazionari e possono essere punti di massimo, di minimo o di sella.
TEOREMA 1 - Condizioni sufficienti affinché x* sia un punto di ottimo locale isolato (cioè unico in un intorno opportuno) sono che valgano le (2) e che G* sia definita positiva, cioè che
s 0 sia sTG*s > 0. (4)
DIMOSTRAZIONE: l'espansione in serie di Taylor intorno ad x*, dato che vale la (2), è data da
f(x*+ q) = f*+ qTG*q/2 + o(qTq
dove a=o(h) se e solo se a/h tende a 0 quando h tende a 0. La (4) implica che esiste a>0 tale che
qTG*q a(qTq) e quindi che f(x*+ q f* + (a/2 + o(1)) qTq. Quando q e o(1) tendono a 0, a>0 implica che f(x*+ q) > f* . Se per assurdo vi fossero nell'intorno più punti di minimo locale x*+ q, con q che tende a 0,
qTg(x*+ q qTg* + qTG*q + o(qTq
Ma qTG*q a(qTq) contraddicendo il fatto che
g* = g(x*+ q
e quindi x* deve essere isolato.
In alcuni casi la ricerca di x* si riduce quindi alla ricerca di un punto di stazionarietà per cui valga la (4). Ciò richiede di saper verificare se una matrice è o no positiva definita. Ciò è possibile in vari modi computazionalmente efficienti.
Uno di questi richiede di scomporre G con il metodo di Choleski ottenendo G=LLT (dove L è una matrice triangolare inferiore) e verificare che tutti gli elementi sulla diagonale principale di L sono strettamente positivi. Vediamo un esempio.
Si consideri la matrice A:
4 -4
4 10 -l
-4 -l 5
Si ha L11= (16)1/2
L21= (4)/4 = 1
L31= (-4)/4 = -l
L22= (10 - (L21)2)1/2 = 3
L32= (-l- L21 L31)/3 = 0
L33= (5- (L31)2 (L32)2)1/2 = 2
Siccome tutti gli elementi sulla diagonale di L sono positivi, la matrice A è positiva definita.
In generale si applicano le formule
Lii= (aii - Sk=1,.,i-l (Lik)2)1/2
Lji= (aij - Sk=1,.,i-l LikLjk)/Lii , j=i+1,,n.
ITERAZIONE GENERICA DI UN ALGORITMO PER IL PROBLEMA (1):
a) si determini una direzione di discesa sk ;
b) si trovi uno scalare ak che minimizza (almeno approssimatamene) f(xk+a sk) rispetto ad a
c) si pone xk+1= xk+ aksk
L'idea di base per determinare i due ingredienti principali di tale iterazione, cioè la direzione di discesa (se si vuole minimizzare, di ascesa se si vuole massimizzare f) e lo scalare ak è quella di approssimare localmente f con un'altra funzione di cui sia facile trovare l'ottimo. Si dice allora che si approssima f con un modello. Il modello più impiegato è quello quadratico:
f(x+d f(x) + dTg(x) + dTG(x)d (5)
METODO DEL GRADIENTE
Si sceglie per sk la direzione negativa (se stiamo cercando un minimo) del gradiente nel punto in cui ci troviamo.
PROPRIETA'
Il metodo converge globalmente, cioè arriva prima o poi ad un ottimo locale. Tuttavia ciò avviene di solito molto lentamente a causa di un tipico comportamento a zig-zag.
Il valore di ak (Nota Bene: non è un esponente, ma l'indice della k-esima iterazione !) si ottiene cercando il primo punto di minimo della f(x) nella direzione scelta, almeno in modo approssimato (ricerca monodimensionale). Per fare ciò esistono diversi metodi, a seconda che le derivate direzionali di f(x) siano facili o no da calcolare/approssimare.
RICERCA MONODIMENSIONALE
Molto raramente in pratica si può effettuare la minimizzazione esatta della funzione f(a) = f(xk+a sk) e quindi vale la pena elencare i requisiti che si devono raggiungere anche se la minimizzazione esatta non è disponibile:
a) ottenere una riduzione significativa del valore della funzione obiettivo;
b) stare abbastanza lontani dagli estremi dell'intervallo fra il valore 0 di a e il valore al quale la funzione ritorna ad avere il valore che aveva nello 0;
c) l'intervallo di valori tra cui scegliere a deve includere il minimo esatto a
d) tale intervallo deve anche includere il valore di a che corrisponderebbe al minimo se f(a) fosse quadratica con curvatura positiva;
e) un valore di a che soddisfi a questi requisiti deve esistere ed essere ottenibile in un numero finito di passi.
I requisiti elencati sono soddisfatti se valgono le condizioni seguenti, dette di Wolfe-Powell:
f(a f(0) + ar f'(0)
f'(a s f'(0)
dove rI(0,1/2) e sI r,1) sono parametri prefissati.
Con alcuni ulteriori accorgimenti si arriva ad un metodo di ricerca monodimensionale che assicura la convergenza globale del metodo di discesa che ne faccia uso. (Per altri dettagli si rinvia al testo.)
Quando non sono disponibile le derivate si può ricorrere alla loro approssimazione come
gi(x) = (f(x+hei) - f(x-hei))/2h
dove ei è l' i-esimo versore di An
Talvolta però si deve fare ricorso ad un metodo di ricerca monodimensionale che prescinde interamente dall'uso delle derivate, approssimate oppure no. Uno di tali metodi si dice della sezione aurea. Supponiamo di sapere che l'intervallo di valori di a tra cui cercare quello che minimizza la f sia (a,b) e che si voglia determinare il valore in cui si ottiene il minimo a* a meno di un errore pari ad e
Procedure AUR(a,b,e
c:= a + 0,382 (b-a);
d:= b - 0,382 (b-a);
repeat if f(c) f(d) then
b:=d;
d:=c;
c:= a + 0,382 (b-a)
else
a:=c;
c:=d;
d:= b - 0,382 (b-a)
until (d-c) e
return a:=c if f(c) f(d) else a:=d
Metodo di Newton
Costituisce il modo più diretto di utilizzare il modello quadratico (5). Uno dei vantaggi è che questo metodo non richiede alcuna ricerca monodimensionale. Si pone
sk = -(Gk)-lgk ;
xk+1= xk+ sk
Infatti quando il modello quadratico coincide con la funzione f(x), si può dimostrare che la soluzione del sistema Gk d = -gk con d=x-xk fornisce il punto di ottimo purché Gk sia definita positiva.
La velocità di convergenza in vicinanza di un punto di ottimo locale della f(x) è molto buona (quadratica). Il calcolo dell'inversa dell'Hessiano richiede O(n3) operazioni e consente allo stesso tempo di verificare se la matrice da invertire è o no definita positiva.
Purtroppo il Metodo di Newton NON è globalmente convergente e quindi non si presta da solo a funzionare da metodo generale per l'ottimizzazione senza vincoli. Infatti quando l'Hessiano non è definito positivo può addirittura condurre fuori strada e divergere.
Tuttavia il principale difetto del Metodo di Newton è di richiedere il calcolo delle derivate seconde di f(x) per poter disporre dell' Hessiano nel punto in cui siamo. Da tutte queste considerazioni deriva l'importanza dei cosiddetti Metodi Quasi-Newton chiamati anche Metodi a Metrica Variabile. Per questi metodi è però di nuovo necessario ricorrere ad una ricerca monodimensionale ad ogni iterazione oltre ad un passo in più per aggiornare la matrice che prende il ruolo dell'Hessiano nel calcolo della nuova direzione di discesa.
La generica iterazione del metodo di discesa diventa quindi la seguente:
a) sk := - Hkgk;
b) si trovi uno scalare ak che minimizza (almeno approssimatamene) f(xk+a sk) rispetto ad a
c) si pone xk+1= xk+ aksk;
d) si aggiorna opportunamente l'approssimazione dell'inversa dell'Hessiano ottenendo Hk+1
La matrice H1 può essere qualsiasi matrice definita positiva, ma la scelta più frequente è la matrice identità I.
Poniamo
dk := xk+1- xk
gk := gk+1- gk
La formula di aggiornamento usata più di frequente è detta BFGS dalle iniziali dei proponenti, Broyden, Fletcher, Goldfarb e Shanno, che la scopersero nel 1970.
Rimandando al testo per come arrivare a tale formula, la riportiamo qui di seguito, tralasciando il suffisso k per semplicità di scrittura a destra del segno di =.
Hk+1 = H + (1+(gTHg dTg ddT dTg
dgTH + HgdT dTg
La formula BFGS gode delle seguenti proprietà:
per funzioni quadratiche assumendo una ricerca monodimensionale esatta, dopo al massimo n iterazioni si ha Hn+1=G-l;
le Hk sono positive definite se lo è H1;
il metodo richiede O(n2) operazioni per iterazione;
la velocità di convergenza è super-lineare;
BFGS è più robusta di altre formule rispetto agli errori di arrotondamento;
BFGS è più tollerante di altre formule quando la ricerca monodimensionale non è esatta, in particolare la convergenza è globale purché la ricerca monodimensionale soddisfi alle condizioni di Wolfe-Powell.
COSA FARE SE IL CALCOLO DELL' HESSIANO RISULTA TROPPO ONEROSO ?
Una scelta è quella di cercare di accrescere la velocità di convergenza del metodo del gradiente puro, cercando direzioni di discesa che siano coniugate. Quando la ricerca monodimensionale è sufficientemente precisa ad ogni iterazione.
Si pone quindi s1 := -g1 e sk+1 := -gk+1 + bk sk con la condizione iniziale b = 0 e
bk= (gk+1 - gk)Tgk+1/ gkTgk
detta formula di Polak-Ribière.
Anche se meno efficienti e robusti dei metodi quasi-Newton, i metodi di gradiente coniugato possono rivelarsi come l' unica scelta possibile per problemi con molte variabili, dato che abbisognano del calcolo solo del gradiente e quindi lavorano con vettori e non con matrici. In particolare lo spazio di memoria richiesto è solo quello dei 4 vettori n-dimensionali che si usano nella formula riportata sopra.
CONCLUSIONI
Abbiamo visto il metodo del gradiente, il metodo di Newton, un metodo quasi-Newton, e un metodo di gradiente coniugato.
Quando si vogliono proprietà di convergenza globale più forti (cioè con funzioni particolarmente problematiche), esistono altri metodi, detti a passo ristretto. L' idea di fondo è quella di sorvegliare l' applicazione del metodo di Newton, limitando lo spostamento ad una zona dove il modello quadratico rappresenta abbastanza fedelmente la funzione originale. Tali metodi procedono quindi con passi molto piccoli, ma offrono maggiore robustezza di quelli più elementari visti in precedenza.
Cenni sulla PNL vincolata
Consideriamo il problema:
min (1)
La funzione Lagrangiana di (1) è:
L (x,l) = f(x) + aiID U li ci(x) (2)
Per semplicità riportiamo solo le condizioni necessarie del primo ordine e quelle sufficienti del secondo ordine per un ottimo locale (senza cercare di presentare le condizioni più generali possibile).
Condizioni necessarie del primo ordine
Perché un punto x* sia un ottimo locale di (1) si richiede che esista un vettore di moltiplicatori di Lagrange l* tale che
x L (x*,l f(x*) + aiIA* li ci(x*) = 0
dove
A* U
è l' insieme dei vincoli attivi in x* e li 0 se iIA* D.
Questo risultato richiede una condizione di qualificazione dei vincoli per essere sicuri che la geometria della regione di ammissibilità sia adeguatamente modellata dalla linearizzazione dei vincoli nell' intorno di x*. Una condizione di qualificazione standard richiede che i vettori ci(x*) siano linearmente indipendenti per iIA* : un punto x* per cui ciò accade è detto regolare.
Condizioni sufficienti del secondo ordine
Oltre a richiedere che siano soddisfatte le condizioni necessarie del primo ordine (vedi sopra), si richiede che l' Hessiano della Lagrangiana
xxL(x*,l f(x*) + aiIA* li ci(x*)
soddisfi wTL(x*,l*)w > 0 per tutti i vettori non-nulli w appartenenti alla regione
dove
D
e
D
Queste condizioni garantiscono che il problema di ottimizzazione in esame è OK nell' intorno di x*. In particolare le condizioni del secondo ordine assicurano che x* è un ottimo locale isolato per il problema (1).
DEFINIZIONE: si dice Jacobiano del problema (1) la matrice J le cui colonne ai sono date dai gradienti delle funzioni di vincolo ci(x). Tali vettori ai sono perpendicolari alla tangente al vincolo corrispondente nel punto x considerato.
Riassumiamo qui di seguito tutte le condizioni necessarie perché un punto x sia minimo locale di (1), dette condizioni di Karush-Kuhn-Tucker (KKT).
KKT
x deve essere un punto regolare
x deve soddisfare ai vincoli di uguaglianza e a quelli di disuguaglianza
i moltiplicatori di Lagrange corrispondenti a
vincoli di disuguaglianza devono essere non
negativi
i, deve aversi li ci(x) = 0
sTWs s I
dove W è l' Hessiano della Lagrangiana (2) rispetto a x
Se in (3) sTWs > 0 si ha un ottimo locale forte (ovvero isolato)
Le KKT sono anche sufficienti se il problema (1) è convesso.
PROGRAMMAZIONE QUADRATICA (PQ)
Si ha quando la funzione da ottimizzare è quadratica con Hessiano G definito positivo e tutti i vincoli sono lineari.
Per questo caso di Programmazione Matematica Non-lineare Convessa esiste un metodo molto efficiente che è stato generalizzato da Goldfarb e Idnani al caso in cui i vincoli siano ancora lineari, ma la funzione obbiettivo sia qualunque, purché convessa.
Uno dei metodi più efficaci per l' ottimizzazione di (1) in generale,
denominato metodo della Programmazione
Quadratica in Sequenza (PQS), si basa sull' idea di approssimare (1) col
suo modello quadratico e applicare con i dovuti accorgimenti
Si può pensare di risolvere (1) cercando tutti i punti che soddisfano alle KKT e fra questi quello ottimo, ma il metodo è molto inefficiente.
|
Privacy
|
© ePerTutti.com : tutti i diritti riservati
:::::
Condizioni Generali - Invia - Contatta
