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}$$ (4.37)

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)$$ (4.38)

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 $\mathbf{g}(\mathbf{x}_t + \boldsymbol\delta)$ sia esattamente nulla. Trascurando i termini di ordine almeno quadratico, la stima del $\boldsymbol\delta$ che in prima approssimazione fa avvicinare a zero la funzione $\mathbf{g}$ è la soluzione del sistema lineare (4.38) con la condizione (4.37), ovvero

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

sistema che, se $\mathbf{J}_{g}$ non ha deficienze di rango, può essere risolto esattamente oppure, nel caso sovradimensionato, nel senso dei minimi quadrati, con una delle tecniche mostrate in sezione 1.1. L'idea dei metodi iterativi è quella di modificare il punto $\mathbf{x}_t$ della quantità $\boldsymbol\delta_t$

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

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_t)}{g'(x_t)}$$ (4.41)

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

I punti nei quali il gradiente si annulla sono detti punti stazionari. Massimi e minimi locali interni appartengono a questa classe, ma un punto stazionario può anche essere un punto di sella. Si può pertanto applicare questa tecnica per individuare i punti stazionari 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}$$ (4.42)

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$, entrambe calcolate nel punto $\mathbf {x}$. La modifica del punto $\mathbf {x}$ di Newton diventa pertanto

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

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 una 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)$$ (4.44)

attraverso il metodo di ottimizzazione di Newton.