Algoritmi di ottimizzazione e metodo newton troncato

[toto]

Qualcuno mi puo' aiutare con il metodo in oggetto, pecialmente se ne ha
avuto ewsperienze "applicative"???
Devo realizzae un software che implementi tale algoritmo, fatto e funziona,
solo che non so se funziona come dovrebbe (esempio, un problema di test
viene risolto in 5 iterazioni, il mio programma ne impiega 80)

[Andrea D'Amore]

Post by toto
Devo realizzae un software che implementi tale algoritmo, fatto e funziona,
solo che non so se funziona come dovrebbe (esempio, un problema di test
viene risolto in 5 iterazioni, il mio programma ne impiega 80)

Incolla un po' di codice allora :-)

[toto]

Post by Andrea D'Amore
Incolla un po' di codice allora :-)

Non aspettavo altro.....e' tutta roba matlab (in realtà il programma è in
java, ma funziona molto peggio....probabilmente c'è qualche errore, ma prima
vorrei testare l'algoritmo)

x = [-1.2; 1]; % Punto iniziale
k = 0; % Numero di iterazioni dell'algoritmo
eta = 0.05;
epsilon = 8.4;
arm_delta = 0.5;
arm_gamma = 0.0002;

while norm(grad(x)) >= 1E-5

d = trovaDir(x, epsilon, eta, k); % Ricerco una direzione con il
metodo delle dir coniugate
passo = armijo(x, d, arm_delta, arm_gamma);

x = x + passo * d;
k = k + 1;
end

disp ( ['Ho terminato la minimizzazione in iterazini: ', num2str(k)]);
disp ('il vettore soluzione');
disp(x);
disp('La funzione vale');
val = f(x);
disp(val);

Ora il codice per la ricerca della direzione e quello con il metodo di
Armijo per la ricerca del passo

[ trovaDir ]

h = hessiano(x);
g = grad(x);
s = -g;
q = g;
di = [ 0; 0 ];
i = 0;

while (true)

if s'*h*s <= epsilon * (s'*s)
if i == 0
d = -g;
break;
else
d = di;
break;
end
end

num = q'*s;
den = s'*h*s;

alfa = -1 * (num/den);
di = di + alfa*s;
q = q + alfa*h*s;

tmp = min(k, norm(g));
if norm(q) <= eta * g * tmp
d = di;
break;
end

num = q'*h*s;
beta = num/den;
s = -q + beta * s;

i = i +1;

end

[ /trovaDir ]

[ Armijo ] Che è veramente banale...

alfa = 1;
nf = 0;

while (true)

x_nuovo = x + alfa * d;

if f(x_nuovo)<= f(x) + arm_gamma * grad(x)'*d
passo = 1;
break;
end

alfa = arm_delta * alfa;
nf = nf +1;

if nf == 10
disp('Armijo esce dopo 10 iterazioni....male...');
passo = alfa;
break;
end
end
[ /Armijo ]

Utilizzando la funzione
100*(x(2)-x(1)^2)^2+(1-x(1))^2

trovo la soluzione in 1664 iterazioni (tempo impiegato forse un paio di ms)
mentre dovrebbero essere 5-10 (secondo il professore)....
Io l'algoritmo l'ho preso pari pari dalle sue dispense......

[Andrea D'Amore]

Post by toto
Non aspettavo altro.....e' tutta roba matlab (in realtà il programma è in
java, ma funziona molto peggio....probabilmente c'è qualche errore, ma prima
vorrei testare l'algoritmo)

Non so aiutarti ma con il codice è più probabile che qualcuno ti aiuti.

Post by toto
Utilizzando la funzione
100*(x(2)-x(1)^2)^2+(1-x(1))^2

con l'assegnazione di x della prima riga questo non è un numero
piuttosto che una funzione?

[Andrea Francia]

Post by toto

Post by Andrea D'Amore
Incolla un po' di codice allora :-)

Non aspettavo altro.....e' tutta roba matlab (in realtà il programma è in
java, ma funziona molto peggio....probabilmente c'è qualche errore, ma prima
vorrei testare l'algoritmo)
x = [-1.2; 1]; % Punto iniziale
k = 0; % Numero di iterazioni dell'algoritmo
eta = 0.05;
epsilon = 8.4;
arm_delta = 0.5;
arm_gamma = 0.0002;
while norm(grad(x)) >= 1E-5
d = trovaDir(x, epsilon, eta, k); % Ricerco una direzione con il
metodo delle dir coniugate
passo = armijo(x, d, arm_delta, arm_gamma);
x = x + passo * d;
k = k + 1;
end
disp ( ['Ho terminato la minimizzazione in iterazini: ', num2str(k)]);
disp ('il vettore soluzione');
disp(x);
disp('La funzione vale');
val = f(x);
disp(val);
Ora il codice per la ricerca della direzione e quello con il metodo di
Armijo per la ricerca del passo
[ trovaDir ]
h = hessiano(x);
g = grad(x);
s = -g;
q = g;
di = [ 0; 0 ];
i = 0;
while (true)
if s'*h*s <= epsilon * (s'*s)
if i == 0
d = -g;
break;
else
d = di;
break;
end
end
num = q'*s;
den = s'*h*s;
alfa = -1 * (num/den);
di = di + alfa*s;
q = q + alfa*h*s;
tmp = min(k, norm(g));
if norm(q) <= eta * g * tmp
d = di;
break;
end
num = q'*h*s;
beta = num/den;
s = -q + beta * s;
i = i +1;
end
[ /trovaDir ]
[ Armijo ] Che è veramente banale...
alfa = 1;
nf = 0;
while (true)
x_nuovo = x + alfa * d;
if f(x_nuovo)<= f(x) + arm_gamma * grad(x)'*d
passo = 1;
break;
end
alfa = arm_delta * alfa;
nf = nf +1;
if nf == 10
disp('Armijo esce dopo 10 iterazioni....male...');
passo = alfa;
break;
end
end
[ /Armijo ]
Utilizzando la funzione
100*(x(2)-x(1)^2)^2+(1-x(1))^2
trovo la soluzione in 1664 iterazioni (tempo impiegato forse un paio di ms)
mentre dovrebbero essere 5-10 (secondo il professore)....
Io l'algoritmo l'ho preso pari pari dalle sue dispense......

Testa le varie funzioni a parte e controlla che i risultati siano
sensati, per esempio il calcolo dell'hessiana, del gradiente etc.

[Andrea Francia]

Post by toto
Qualcuno mi puo' aiutare con il metodo in oggetto, pecialmente se ne ha
avuto ewsperienze "applicative"???
Devo realizzae un software che implementi tale algoritmo, fatto e funziona,
solo che non so se funziona come dovrebbe (esempio, un problema di test
viene risolto in 5 iterazioni, il mio programma ne impiega 80)

Chiedi al tuo prof di ottimizzazione.
Quando ho fatto io l'esame succedeva così.
Sbagliavamo qualcosa nell'implementazione il prof vedeva i numeri, e con
la sua capacità (che a noi sembrava) divinatoria diceva "avete sbagliato
a mettere il meno da qualche parte perché il comportamento non è
normale, l'andamento dei numeri dovrebbe essere diverso", e ci prendeva!.

[toto]

Post by Andrea Francia

Post by toto
Qualcuno mi puo' aiutare con il metodo in oggetto, pecialmente se ne
ha avuto ewsperienze "applicative"???
Devo realizzae un software che implementi tale algoritmo, fatto e
funziona, solo che non so se funziona come dovrebbe (esempio, un
problema di test viene risolto in 5 iterazioni, il mio programma ne
impiega 80)

Chiedi al tuo prof di ottimizzazione.
Quando ho fatto io l'esame succedeva così.
Sbagliavamo qualcosa nell'implementazione il prof vedeva i numeri, e
con la sua capacità (che a noi sembrava) divinatoria diceva "avete
sbagliato a mettere il meno da qualche parte perché il comportamento
non è normale, l'andamento dei numeri dovrebbe essere diverso", e ci
prendeva!.

Non mi dire che è il prof. Grippo della Sapienza.....
urtroppo io non riesco a parlarci (nel senso che non riesco mai a
trovarlo.....)

[Andrea Francia]

Post by toto
Non mi dire che è il prof. Grippo della Sapienza.....
urtroppo io non riesco a parlarci (nel senso che non riesco mai a
trovarlo.....)

Mandagli una mail ...

[Andrea Francia]

Post by toto
Non mi dire che è il prof. Grippo della Sapienza.....
urtroppo io non riesco a parlarci (nel senso che non riesco mai a
trovarlo.....)

Vai a chiedere ai dottorandi che ronzano vicino al suo ufficio, magari
qualcuno è abbastanza gentile da interessarsi del tuo problema.

[Andrea Francia]

Post by toto
Qualcuno mi puo' aiutare con il metodo in oggetto, pecialmente se ne ha
avuto ewsperienze "applicative"???
Devo realizzae un software che implementi tale algoritmo, fatto e funziona,
solo che non so se funziona come dovrebbe (esempio, un problema di test
viene risolto in 5 iterazioni, il mio programma ne impiega 80)

Hai già implementato il metodo di newton normale (che mi sembra di
ricordare fosse piu' semplice), implementa prima quello, controlla che
converge velocemente e poi modificalo per farlo diventare troncato.

Se converge piano forse (ma forse) hai sbagliato l'hessiana.
Quanto ci mette il metodo del gradiente? Se ci mette anche lui circa 80
iterazione vuol dire che hai cannato l'hessiana.

[toto]

Post by Andrea Francia

Post by toto
Qualcuno mi puo' aiutare con il metodo in oggetto, pecialmente se ne
ha avuto ewsperienze "applicative"???
Devo realizzae un software che implementi tale algoritmo, fatto e
funziona, solo che non so se funziona come dovrebbe (esempio, un
problema di test viene risolto in 5 iterazioni, il mio programma ne
impiega 80)

Hai già implementato il metodo di newton normale (che mi sembra di
ricordare fosse piu' semplice), implementa prima quello, controlla che
converge velocemente e poi modificalo per farlo diventare troncato.
Se converge piano forse (ma forse) hai sbagliato l'hessiana.
Quanto ci mette il metodo del gradiente? Se ci mette anche lui circa
80 iterazione vuol dire che hai cannato l'hessiana.

L'hessiana e' corretta...il metodo del gradiente tende a + infinito !!!
Mi sa che e' meglio se lascio perdere....

[metodo del gradiente]
k = 0;
x0 = x0(:);
while true
if norm(grad(x0)) <= 1e-5
x = x0;
val = f(x0);
i = k;
break;
end

dk = -grad(x0);

alfa = armijo(x0, dk, 0.4, 0.00002);
x0 = x0 + alfa * dk;
k = k + 1;
disp(f(x0));
end