Esercizi - 4.5
Esercizio n. 4.5.1
Si considerino le due funzioni quadratiche
- f(x, y) = ( x - 2 )^2 + ( y + 1 )^2
- f(x, y) = 4( x - 2 )^2 + ( y + 1 )^2
Si applichi ad entrambe il Metodo del Gradiente a partire dal punto (9/4, 0),
fermandosi dopo al più 5 iterazioni. Si determini quindi, per entrambe
le funzioni e per ogni iterazione, la velocità di convergenza
f( X[ k + 1 ] ) / f( X[ k ] ), e la si confronti con la minima convergenza
prevista dalla teoria (convergenza lineare con rapporto ( ( LM - Lm ) / ( LM +
Lm ) )^2, dove LM ed Lm sono il massimo ed il minimo autovalore della matrice
Hessiana nell'ottimo). Si ripeta l'operazione coi diversi punti iniziali
(0, 2) e (2, -1). Che conclusioni se ne possono trarre?
Esercizio n. 4.5.2
Sia dato il politopo (poliedro limitato) P = { x :
Ax <= b }; si assuma inoltre l'esistenza di un
punto interno a P, ossia tale che Ax <
b. Il centro analitico di P è definito come
il punto w di P che massimizza il prodotto delle
slacks dei vincoli, dove la slack del vincolo i-esimo relativa a
w è s[ i ] = b[ i ] -
A[i ]w.
a) Si formuli il problema della determinazione di w come
un problema di PNL non vincolata (suggerimento: si sfruttino le
proprietà dei logaritmi).
b Si discuta la complessità di un passo del Metodo di Newton
applicato alla soluzione di tale problema.
Esercizio n. 4.5.3
Dato il quadrato di vertici (-2, 2), (2, 2), (2, -2) e (-2, -2), si
applichino:
- il metodo dei Gradienti Coniugati;
- il Metodo di Newton con ricerca lineare;
- il Metodo di Newton senza ricerca lineare;
alla determinazione del centro analitico di tale politopo (si usi come
criterio di stop || f'( X[ k ] ) ||^2 <= .01).
Esercizio n. 4.5.4
Si applichi il Metodo di Newton senza ricerca lineare alla minimizzazione
della funzione
f(x, y) = 10^8 * ( y - x^2 )^2 + ( 1 - x )^2
a partire dal punto (-1.2, 1) (la computazione deve terminare in 3 passi).