7.3: Optimización Continua Multidimensional

Ahora consideramos que la función de costo\(f\) es una función de más de una variable. \(X\)es un espacio multidimensional, y\(x\) es un vector. Consideramos de nuevo funciones continuas. En los mínimos, en cuanto al caso de dimensión única, tenemos ciertas condiciones para la primera y segunda derivada:

\ begin {align}\ nabla f (x*)\, &=\, [f_1,\, f_2,\,\ cdots] _ {x=x*} = [0,\, 0,\,\ cdots]\\ [4pt]\ nabla^2 f (x)\, &=\,\ begin {bmatrix} f_ {x_1 x_1}\ quad f_ {x_1 x_2} &\,\\ [4pt] f_ {x_2 x_1}\ quad f_ {x_2 x_2} &\,\\ [4pt] &\ cdots\ end {bmatrix} _ {x=x*} >\, 0,\ end {align} donde el notación de que una matriz es mayor que cero denota que es definitiva positiva. Presentaremos tres métodos prácticos para encontrar el mínimo. Primero está el método de descenso más empinado. La idea aquí es encontrar la dirección cuesta abajo y dar un paso de\(\delta\) esa manera:

\ begin {align} e\, &=\, -\ nabla f (x)/||\ nabla f (x) ||\\ [4pt]\ delta\, &=\,\ gamma e.\ end {align}

Obsérvese que, tal como está escrito, este es un algoritmo diferente al primer método dado en una dimensión, porque aquí\(e\) se normaliza el vector de dirección, y de ahí la magnitud del paso en\(x\) es la misma sin importar cuál sea la pendiente de la función. Observamos también que existe un valor\(\alpha\) como\(x + \alpha e\) es el argumento minimizando de\(f\), a lo largo de la dirección e y pasando por el punto\(x\). Este es el resultado de la llamada búsqueda de líneas, y un procedimiento de descenso más empinado razonable es realizar iterativamente un procedimiento de dos pasos de un cálculo de gradiente seguido de una búsqueda de líneas en la dirección cuesta abajo.

El desempeño de búsquedas sucesivas de líneas puede ser bastante bueno, o muy pobre. El bajo rendimiento resulta en algunos casos debido a que las sucesivas direcciones de descenso están restringidas a ser ortogonales entre sí. Este tiene que ser el caso porque al mínimo en la línea, el gradiente en la dirección de la línea es cero por definición. De hecho, ninguna de estas direcciones cuesta abajo puede apuntar al mínimo, y se podrían dar tantos pasos inútiles. Una solución a esto es el método de gradiente conjugado, en el que realizamos una modificación útil a las direcciones de descenso utilizadas para cada una de las búsquedas de líneas.

Llamaremos al vector de dirección cuesta abajo correspondiente con la\(k\) 'ésima conjetura\(d_k\). Dejando\(g(x) = \nabla f(x)\) y\(d_0 = -g(x_0)\), vamos a dejar\(d_{k+1} = -g(x_{k+1}) + \beta d_k\). Esto dice que desviaremos la siguiente dirección de búsqueda de la dirección cuesta abajo por el término\(\beta d_k\); el factor escalar\(\beta\) viene dado por

\[ \beta \, = \, \dfrac{g(x_{k+1})^T g(x_{k+1})} {g(x_k)^T g(x_k)}. \]

Tenga en cuenta aquí que no\(d\) está normalizado. El álgebra necesario para derivar esta regla no es difícil, y un simple ejemplo ilustrará que es muy poderosa.

Finalmente, mencionamos el método de segundo orden de Newton en múltiples dimensiones, utilizando la segunda derivada. Proviene de la versión multivariable de la expansión de la serie Taylor:

\[ f(x + \delta) \, \approx \, f(x) + \nabla f(x) \delta + \dfrac{1}{2} \delta^T \nabla^2 f(x) \delta. \]

Siguiendo del caso unidimensional, tratamos de seleccionar\(\delta\) para causar\(\partial f(x + \delta) / \partial \delta\) = 0. Esto da

\ begin {align} -\ nabla f (x)\, &=\,\ delta^t\ nabla^2 f (x)\ largoderrow\\ [4pt]\ delta\, &=\, - [\ nabla^2 f (x)] ^ {-1}\ nabla f (x). \ end {align}

En palabras, el método de Newton toma la primera y segunda información derivada e intenta llegar a una solución específica en un solo paso. El algoritmo tiene propiedades de convergencia extremadamente buenas y se recomienda cuando hay segundas derivadas disponibles.

Es importante entender que tanto el método de gradiente conjugado como el método de segundo orden de Newton obtienen la respuesta exacta en dos (gradiente conjugado) o uno (Newton) intentos, cuando de hecho la función es cuadrática. Pensando en el costo computacional, el algoritmo de gradiente conjugado tiene que tener el vector derivado en dos puntos, mientras que Newton tiene que tener el gradiente más la matriz hessiana, en el punto de partida. Si estos derivados tienen que crearse numéricamente y con precisión, es evidente que el hessiano podría ser bastante caro. Por esta razón, se puede preferir el método de gradiente conjugado.

Figura\(\PageIndex{1}\): gráfica ilustra la diferencia en el comportamiento de los métodos de gradiente de descenso más empinado vs conjugado para determinar el punto óptimo. El método de descenso más empinado desciende por líneas rectas hacia el punto objetivo, el cual es menos eficiente que el método de gradiente conjugado que desciende como una curva suave.