Indice di convergenza dei metodi PNL
Ciao a tutti!
Sto studiando ricerca operativa però la mia domanda è di analisi quindi posto qui.
Magari la faccio troppo lunga ma preferisco farla lunga che farla troppo breve e non far capire la mia domanda.
L'argomento è la ricerca del minimo di una funzione con un algoritmo (per esempio del gradiente o altri).
Il problema che risolvono questi algoritmi è: quale è il valore $ ul(x) $ che minimizza $ f ( ul(x) ) $ ?
Questi algoritmi non forniscono subito la soluzione (come invece fa il calcolo del minimo con la derivata in modo analitico) ma ritornano una successione di valori $ ul(x)_1 $ ... $ ul(x)_n $ che ad ogni iterazione si avvicinano sempre di più al valore calcolato in modo analitico.
La mia domanda è sul modo in cui valutare la velocità (ovvero il numero di passi $ n $ con cui un algoritmo converge alla soluzione. (assomiglia molto alla convergenza di una serie).
Per fare ciò a lezione è stata scritta questa formula ma purtroppo non ho scritto nessun commento:
$ lim_(k -> oo ) ( f(ul(x)_(k+1)) - f(ul(x)_o ) ) / (( f(ul(x)_k) - f(ul(x)_o) )^p) = a $
$ ul(x)_(k+1) $ e $ ul(x)_k $ sono i valori di $ul(x)$ calcolati all'interazione $k+1$ e $k$ dell'algoritmo.
$ ul(x)_o $ è il punto di minimo di $ul(x)$.
Cosa sono $a$ e $p$?
Pensandoci un pò (forse troppo
) ho dato questa risposta:
1) $a$ ci dice se l'algoritmo converge a $ul(x)_o$ e con quale velocità converge.
Se $0 < a < 1$ allora l'algoritmo ci fornirà prima o poi un valore vicino a $ul(x)_o$
Più $a$ è vicino a 0 e più velocemente (come numero di iterazioni) ci verrà fornito un valore vicino a $ul(x)_o$
2) $p$ invece ci fornisce informazioni sulla sola velocità di convergenza.
Più $p$ è alto, minore è il numero di passi in cui l'algoritmo converge
Forse l'ho fatta davvero troppo lunga, trovate che possa andare?
Grazie
Sto studiando ricerca operativa però la mia domanda è di analisi quindi posto qui.
Magari la faccio troppo lunga ma preferisco farla lunga che farla troppo breve e non far capire la mia domanda.
L'argomento è la ricerca del minimo di una funzione con un algoritmo (per esempio del gradiente o altri).
Il problema che risolvono questi algoritmi è: quale è il valore $ ul(x) $ che minimizza $ f ( ul(x) ) $ ?
Questi algoritmi non forniscono subito la soluzione (come invece fa il calcolo del minimo con la derivata in modo analitico) ma ritornano una successione di valori $ ul(x)_1 $ ... $ ul(x)_n $ che ad ogni iterazione si avvicinano sempre di più al valore calcolato in modo analitico.
La mia domanda è sul modo in cui valutare la velocità (ovvero il numero di passi $ n $ con cui un algoritmo converge alla soluzione. (assomiglia molto alla convergenza di una serie).
Per fare ciò a lezione è stata scritta questa formula ma purtroppo non ho scritto nessun commento:
$ lim_(k -> oo ) ( f(ul(x)_(k+1)) - f(ul(x)_o ) ) / (( f(ul(x)_k) - f(ul(x)_o) )^p) = a $
$ ul(x)_(k+1) $ e $ ul(x)_k $ sono i valori di $ul(x)$ calcolati all'interazione $k+1$ e $k$ dell'algoritmo.
$ ul(x)_o $ è il punto di minimo di $ul(x)$.
Cosa sono $a$ e $p$?
Pensandoci un pò (forse troppo
) ho dato questa risposta:1) $a$ ci dice se l'algoritmo converge a $ul(x)_o$ e con quale velocità converge.
Se $0 < a < 1$ allora l'algoritmo ci fornirà prima o poi un valore vicino a $ul(x)_o$
Più $a$ è vicino a 0 e più velocemente (come numero di iterazioni) ci verrà fornito un valore vicino a $ul(x)_o$
2) $p$ invece ci fornisce informazioni sulla sola velocità di convergenza.
Più $p$ è alto, minore è il numero di passi in cui l'algoritmo converge
Forse l'ho fatta davvero troppo lunga, trovate che possa andare?
Grazie
Risposte
Innanzitutto è ovvio che questa formula* vada considerata solo per algoritmi almeno localmente convergenti. Come hai intuito se $a$ è un numero "piccolo" e $p$ "grande" l'algoritmo converge velocemente. Diciamo che $p$ ci dice quale rate di convergenza vogliamo considerare: lineare, superlineare, ecc. Scelto un determinato valore di $p$ ci sono poi delle restrizioni sul valore di $a$ affinché si possa quindi dire che l'algoritmo ha convergenza lineare, superlineare, quadratica, ecc.
Prova a dare un'occhiata a wiki
* non ci dovrebbe essere un valore assoluto al denominatore?
Prova a dare un'occhiata a wiki
* non ci dovrebbe essere un valore assoluto al denominatore?
"Deckard":
Innanzitutto è ovvio che questa formula* vada considerata solo per algoritmi almeno localmente convergenti. Come hai intuito se $a$ è un numero "piccolo" e $p$ "grande" l'algoritmo converge velocemente. Diciamo che $p$ ci dice quale rate di convergenza vogliamo considerare: lineare, superlineare, ecc. Scelto un determinato valore di $p$ ci sono poi delle restrizioni sul valore di $a$ affinché si possa quindi dire che l'algoritmo ha convergenza lineare, superlineare, quadratica, ecc.
Prova a dare un'occhiata a wiki
* non ci dovrebbe essere un valore assoluto al denominatore?
Grazie della wiki (e della risposta)! Vado a leggermela.
Ho però un altro dubbio.
E' corretto scrivere che: se $f(ul(x)_k) - f(ul(x)_o) > 1$ e $p -> oo$ allora $ a -> 0 $ ?
Scrivendo così sembrebbe che l'indice di convergenza di ogni algoritmo sia $ p = oo$.
Però il fatto che $ k -> oo $, invalida la prima ipotesi che ho scritto?
Infatti: $ lim_( k -> oo ) [f(ul(x)_k) - f(ul(x)_o)] = lim_( k -> oo ) [f(ul(x)_k)] - f(ul(x)_o) = f(ul(x)_o) - f(ul(x)_o) = 0$
"hee136":
Scrivendo così sembrebbe che l'indice di convergenza di ogni algoritmo sia $ p = oo$.
Calma, clama. $p$ è un parametro che si fissa a priori: $p=1$ indica che si vuole studiare la convergenza lineare, $p=2$ quella quadratica ecc. Non è una proprietà dell'algoritmo, $a$ lo è, ma naturalmente ha senso di parlare di questo $a$ solo se si fissa prima il parametro $p$ che si vuole considerare.
Qui viene spiegato bene.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo