Metodo di Newton-Raphson

Il problema di trovare i minimi di una funzione può essere ricondotto al problema di trovare gli zeri di una funzione, nel caso specifico la derivata prima della funzione costo $S$.

Sia pertanto $\mathbf{g}: \mathbb{R}^{m} \mapsto \mathbb{R}^{n}$ una funzione multivariata derivabile di cui sia richiesto di trovare

$$\mathbf{g}(\mathbf{x})=\mathbf{0}$$ (3.29)

Espandendo in serie di Taylor la funzione $\mathbf{g}$, localmente intorno a un punto $\mathbf {x}$ opportuno, si ottiene

$$\mathbf{g}(\mathbf{x} + \boldsymbol\delta) = \mathbf{g}(\ma... ...}) + \mathbf{J}_{g} \boldsymbol\delta + O(\boldsymbol\delta^2)$$ (3.30)

dove $\mathbf{J}_{g}$ è la matrice $n \times m$ Jacobiano della funzione $\mathbf{g}$ calcolato in $\mathbf {x}$.

L'obiettivo è modificare il valore di $\mathbf {x}$ di un valore $\boldsymbol\delta$ in maniera tale che la funzione costo calcolata in $\mathbf{x}_t + \boldsymbol\delta$ sia esattamente zero. Ignorando i contributi di ordine di ordine superiore a $\boldsymbol\delta^{2}$, la stima del $\boldsymbol\delta$ che in prima approssimazione fa avvicinare a zero la funzione $\mathbf{g}$ è la soluzione del sistema lineare (3.30) con la condizione (3.29), ovvero

$$\mathbf{J}_{g} \boldsymbol\delta = - \mathbf{g}(\mathbf{x})$$ (3.31)

sistema che, se $\mathbf{J}_{g}$ non ha deficienze di rango, è un semplice sistema lineare volendo anche sovradimensionato, che si può risolvere con una delle tecniche mostrate in sezione 1.1. L'idea dei metodi iterativi è quello di modificare il punto $\mathbf{x}_t$ della quantità $\boldsymbol\delta_t$

$$\mathbf{x}_{t+1} = \mathbf{x}_t + \boldsymbol\delta_t$$ (3.32)

per le iterazioni $t=1,2,\ldots$, così calcolata in modo da avvicinarsi progressivamente allo zero della funzione.

Nel caso di singola variabile $n=m=1$ il metodo di Newton si riduce a

$$x_{t+1} = x_t - \dfrac{g(x)}{g'(x)}$$ (3.33)

In calcolo numerico questo è il cosiddetto metodo di Newton (o di Newton-Raphson) per trovare gli zeri di una funzione.

I punti di massimo e minimo di una funzione sono i punti per i quali si riesce ad annullare il gradiente. Si può pertanto applicare questa tecnica per trovare i massimi e minimi di una funzione $f(\mathbf{x}): \mathbb{R}^{m} \mapsto \mathbb{R}$ definendo

$$\begin{array}{l} \mathbf{g}(\mathbf{x}) = \nabla f(\mathbf... ...bf{J}_g(\mathbf{x}) = \mathbf{H}_f(\mathbf{x}) \\ \end{array}$$ (3.34)

dove $\nabla f(\mathbf{x})$ è la funzione gradiente $\mathbb{R}^{m} \mapsto \mathbb{R}^{m}$ mentre $\mathbf{H}_f(\mathbf{x})$ la matrice Hessiana $m \times m$, funzioni gradiente ed Hessiana di $f$ calcolate in $\mathbf {x}$. La modifica del punto $\mathbf {x}$ di Newton diventa pertanto

$$\mathbf{H}_f(\mathbf{x}) \boldsymbol\delta_t = - \nabla f(\mathbf{x})$$ (3.35)

Quando viene utilizzato per ottimizzazione il metodo di Newton approssima di fatto la funzione $f(\mathbf{x})$ nell'intorno di $\mathbf {x}$ con una quadrica. Se $f(\mathbf{x})$ è una funzione quadratica, la convergenza è garantita in un sola iterazione.

Ora, nel caso specifico dei metodi di ottimizzazione, la funzione $f(\mathbf{x})$ è la funzione costo $S(\boldsymbol\beta)$. Pertanto, quando la matrice Hessiana di $S(\boldsymbol\beta)$ è non singolare, si ottiene l'equazione di variazione dei parametri

$$\boldsymbol\delta_t = -\mathbf{H}_{S}^{-1}(\boldsymbol\beta_t) \nabla S(\boldsymbol\beta_t)$$ (3.36)

`attraverso il metodo di ottimizzazione di Newton.