Dirección de Descenso de Newton y Descenso Alternado

Mariano Rivera

septiembre 2018

[1] J. Nocedal and s. Wright, Numerical Optimization, 2ed. Springer (2006).

Descenso de gradiente

Notación. Para simplificar nuestra notación definimos:
$\; f^t \overset{def}{=} \;\;f(x^t) \\ \nabla\,f^t \overset{def}{=} \;\nabla\,f(x^t)\\ \nabla^2 \,f^t \overset{def}{=} \nabla^2\,f(x^t).$

Sea el problema de optimización

(1)
$\underset{x}{\arg\min} \;\; f(x)$
para $f$ suave (2 veces continuamente diferenciable).

Luego, sea $x^t$ el punto actual tal que $\nabla\,f^t \ne 0$, entonces el punto $x^{t+1}$ puede obtenerse mediante la fórmula de actualización

(2)
$\boxed{ x^{t+1} = x^{t} + \alpha \, p^t }$

donde $\alpha$ es el tamaño de paso. Luego para una $\alpha$ suficientemente pequeña que garantiza:

(3)
$f(x^{t} + \alpha \, p^t) < f^{t}$

Usando expansión de Taylor de Primer orden en (3), y dado que $\alpha>0$, tenemos

(4)
$p^\top \nabla\,f^t < 0$
para una $\| p\|$ fija, esta cantidad será mas negativa si

(5)
$\boxed{ p^t = - \nabla\,f^t }$

que es llamada dirección de descenso de gradiente o de máximo descenso.

Método de Newton

Una dirección distinta a la de descenso de gradiente es la de Newton, en ella partimos de usar la fórmula de actualización (2), pero asumimos que $\alpha=1$.

Entonces, $p^t$ se calcula tal que:

(6)
$p^t = \underset{p}{\arg \min} \,\, q(p) \overset{def}{=} f(x^{t} + p)$

Ahora, expandimos en series de Taylor de segundo orden:

(7)
$q^t(p) = f^t + p^\top \nabla\,f^t + \frac{1}{2} p^\top \nabla^2 f^t p$
y encontarmos el óptimo de este modelo cuadrático mediante:

(8)
$\nabla_p q^t(p) = 0 \\$
esto es $\nabla\,f^t + \nabla^2 f^t p =0$. Po r lo que $p^t$ es solución de

(9)
$\boxed{ \nabla^2 f^t p = - \nabla\,f^t }$
que es conocida como la dirección de descenso de Newton o dirección de Newton (Nw).

Note que $p^t$ es óptima con respecto a $q^t(p)$, pero no necesariamnete satisface $f(x^t+p^t) < f^t$. Entonces usamos un tamaño de paso $\alpha$ que permita asegurar descenso, quedando la actualización como (2).

El método tienen convergencia cuadrática (superior a la de descenso de gradiente), sin embargo la desventaje implica que debe calcularse el Hessiano ($\nabla^2 f^t$) de la función objetivo y resolverse, aproximadamente, el sistema lineal (9) en cada iteración.

Note que (9) puede resolverse aproximadamente mediante la detención temprana de métodos iterativos, como el de Descenso de Gradiente. Este método Newton-Gradiente Conjugado, no requiere del cálculo explícito del Hassiano pero si del producto $\nabla^2 f^t p$.

Descenso coordenado

Una variante del método de newton se obtienen si elegimos solo una variabla a actializar en cada iteración; definimos el índice de la variable a actualizar como

(10)
$i = t \% n$

donde $\%$ representa el módulo, $n$ es la dimensión de $x$ y $t$ la iteración actual.

Entonces fijamos la orientación de descenso mediante

(10)
$p^t = e_i$

donde $e_i$ es el $i$-ésimo vector canónico: el que corresponde a la variable $x_i$.

Ahora, usando la fórmula de actualización (2), el tamaño de paso se calcula mediante:

(11)
$\alpha^t = \underset{p}{\arg \min} \,\, q(\alpha) \overset{def}{=} f(x^{t} + \alpha e_i) \approx f^t + \alpha e_i^\top \nabla f^t + \frac{1}{2} \alpha^2 e_i^\top \; \nabla^2 f^t \; e_i$

Donde hemos aproximado $q$ por la serie de Taylor de segundo orden. Abusando de la notacióm, continuamos llamando $q$ al modelo de segundo orden, entonces de $\nabla_\alpha q =0$ tenemos

(11)
$e_i^\top \nabla f^t + \alpha e_i^\top \; \nabla^2 f^t \; e_i =0$

Por lo que es facil resolver para $\alpha$:

(12)
$\alpha = - \frac{ e_i^\top \nabla f^t}{ e_i^\top \; \nabla^2 f^t \; e_i}$

Esto es simplemente

(13)
$\alpha = - \frac{ 1}{H_{ii}} \frac{\partial f^t}{\partial e_i}$

Donde hemos definido
$H \overset{def}{=}\nabla^2 f^t$, por lo que $H_{ii} = e_i^\top \; \nabla^2 f^t \; e_i$ que corresponde al elemento $i$-ésimo de la diagonal de matriz Hassianan $H$. Ahora sustitumos en (2) y tenemos que para la iteración $t$ actualizamos la variable $i$ mediante:

(14)
$\boxed{ x_i^ = \frac{ H_{ii} x_i - \beta [\nabla f^t]_i }{H_{ii}} }$

donde $\beta$ es tamaño de paso que garantice que la funcion $f$ descienda, porque $\alpha$ garantiza descenso en el modelo $q$ pero no en la función objetivo $f$.

Derivación alternativa del método de Gauss-Seidel

Ahora consideremos el caso simple en que la función objetivo es cuadrática, es decir de la forma

(15)
$\underset{x}{\arg\min} \;\; f(x) = \frac{1}{2} x^\top A x - b^\top x$

Entonces, la solución se encuentra mediante la solución de $\nabla_x f$, que corresponde a resolver el sistema lineal:
$Ax-b=0$
donde $A$ es la matriz Hessiana y es simétrica, pues asumimos $f$ suave y sea $a_i^\top$ el renglón $i$-ésimo de $A$:

$A = \begin{bmatrix} a_0^\top\\ a_1^\top\\ a_2^\top\\ \vdots \\ a_{n-1}^\top \end{bmatrix}$

Ahora, la actualización (14) corresponde a

(16)
$\boxed{ x_i = \frac{ a_{ii} x_i - \beta \, ( a_i^\top \, x -b_i ) }{a_{ii}} }$

Que para $\beta=1$ es el Método de Gauss-Seidel (GS); para $\beta \in (0,1)$ es la versión amortiguada y para $\beta>1$ es la sobre-relajada.

Observe que

• la división sobre el elemento de la diagonal $a_{ii}$ en (16) es la razón por la que se realiza pivoteo; esto es, para evitar dividir entre un número muy pequeño; y

• la derivación del método GS partir de un problema de optimización nos permite analizar la importancia de que el sistema sea diagonal dominante: para que los eigenvectores de la matriz Hessianan $A$ estén cercanos a las direcciones de descenso (los vectores canónicos) y, consecuentemente, cada iteración haga un gran avance. Si descendieramos por usando los eigenvectores, el algoritmo convergería en a lo mas $n$ iteraciones; ver la derivación de Gradiente Conjugado en [1]_.