Regola di Armijo

[JohnRich]

Salve a tutti!

Ho una perplessità su una esercitazione di laboratorio di un esame che ho indietro e in questo periodo non posso contattare la prof, quindi chiedo la vostra spiegazione. Ammetto di avere parecchie difficoltà in tutta l'analisi numerica, quindi può essere che non vedo davanti al mio naso.

Mi si chiede di implementare in Matlab il metodo di Newton e successivamente inserire la regola di Armijo, con un opportuna tecnica di backtracking (non è specificato per risolvere quale problema, se \( \displaystyle {f{{\left({x}\right)}}}={0} \) o un problema di minimo). Io ho sempre fatto tutti i discorsi che riguardano le regole di Wolfe per quanto riguarda i problemi di minimo, non per la ricerca degli zeri, invece qui mi si chiede poi di trovare con questo programma gli zeri di alcune funzioni. O è espresso male il testo e devo usare soltanto Newton oppure non capisco cosa devo fare...

Prima cosa, mi serve una direzione di discesa perché io possa scrivere \( \displaystyle {x}_{{{k}+{1}}}={x}_{{k}}+{a}\cdot{p}_{{k}} \). Per i problemi di minimo risolvo ad ogni passo \( \displaystyle {H}_{{k}}\cdot{p}_{{k}}=-{g}_{{k}} \) dove \( \displaystyle {g}_{{k}} \) è il gradiente e H l'hessiana, ma per le proprietà di H so che \( \displaystyle {p}_{{k}} \) è una direzione di discesa, giusto? Come faccio invece a trovare una direzione di discesa con il metodo di Newton per cercare gli zeri?

Poi, la regola di Armijo serve per assicurarmi che l'algoritmo di backtracking mi dia un \( \displaystyle {a} \) sufficientemente piccolo da avvicinarmi al minimo in \( \displaystyle {a} \) della funzione \( \displaystyle {f{{\left({x}_{{k}}+{a}\cdot{p}_{{k}}\right)}}} \), giusto? Ma se devo annullare f e non minimizzarla che cosa posso fare? Non posso prendere il modulo di f...

[Deckard]

Non ho mai sentito usare la regola di Armijo per calcolare gli zeri di una funzione. Esiste il metodo di Newton per ricercare gli zeri, ma NON è lo stesso usato per l'ottimizzazione di una funzione.
Ad ogni modo stai attento che \( \displaystyle {p}_{{k}}=-{{H}}^{{-{1}}}_{\left\lbrace{k}\right\rbrace}\cdot{g}_{{k}} \) non è sempre direzione di discesa: dipende dalla definita-positività di \( \displaystyle {H}_{{k}} \) (ammesso inoltre che \( \displaystyle {H}_{{k}} \) non sia singolare).

Poi, la regola di Armijo serve per assicurarmi che l'algoritmo di backtracking mi dia un \( \displaystyle {a} \) sufficientemente piccolo da avvicinarmi al minimo in \( \displaystyle {a} \) della funzione \( \displaystyle {f{{\left({x}_{{k}}+{a}\cdot{p}_{{k}}\right)}}} \), giusto?

Perché sufficientemente piccolo? \( \displaystyle {a} \) diventa piccolo se non si riesce a soddisfare le due condizioni di Wolfe nelle prime iterazioni dell'algoritmo. A quel punto ci si accontenta di \( \displaystyle {a} \) piccolo purché le soddisfi.

[Deckard]

Piccola osservazione che mi è venuta in mente: il metodo di Newton per l'ottimizzazione non è nient'altro il metodo di Newton per trovare gli zeri ma della derivata della funzione.
La regola di aggiornamento di Newton per gli zeri è:
\( \displaystyle {x}_{{k}}+{1}\:={x}_{{k}}-\frac{{f{{\left({x}_{{k}}\right)}}}}{{{f{'}}{\left({x}_{{k}}\right)}}} \)
Se vogliamo trovare gli zeri della derivata di \( \displaystyle {f} \) abbiamo quindi
\( \displaystyle {x}_{{k}}+{1}\:={x}_{{k}}-\frac{{{f{'}}{\left({x}_{{k}}\right)}}}{{{f{{''}}}{\left({x}_{{k}}\right)}}} \)
che generalizzato a più variabili diventa il metodo di Newton di cui stavamo parlando.