Método del Gradiente o Método del Descenso más Pronunciado

Para la optimización de modelos de Programación No Lineal sin restricciones se dispone de una categoría de métodos denominados «Algoritmos Generales de Descenso» entre los cuales se destaca el Método del Gradiente o Método del Descenso más Pronunciado (conocido adicionalmente como Método de Cauchy) que reducen el cálculo de un mínimo local a una secuencia de problemas de búsqueda lineal (o búsqueda unidimensional).

Consideremos el siguiente problema de Programación No Lineal no restringido:

metodo-gradiente

Es importante observar lo siguiente: El punto de partida para comenzar las iteraciones es arbitrario y al ser evaluado en la función objetivo se alcanza un valor de V(8,7)=-149.

Si evaluamos la coordenada que se alcanza al realizar una iteración del método la función objetivo obtiene el siguiente valor V(12,5)=-169 que como se puede apreciar reduce el valor de la función objetivo.

En resumen el Método del Gradiente consta de 2 pasos principales:

Primero: El cálculo de una dirección de descenso que esta dado por el negativo del gradiente de la función objetivo evaluado en el punto de partida o en el de la k-ésima iteración. En el ejemplo dicha dirección desde la coordenada original x°=(8,7) esta dada en la dirección del vector d°=(8,-4).

Segundo: Obtener la magnitud del paso α (alfa) que determina cuánto se avanza en una determinada dirección de descenso. Esto se logra generando una función unidimensional en términos de este parámetro (respecto a la función objetivo original). En el ejemplo dicha magnitud del paso es α=1/2.

Finalmente se actualiza la coordenada según lo descrito previamente alcanzando (x1,x2)=(12,5) que como se corroboró otorga un valor en la función objetivo menor al punto de partida (arbitrario).

¿Cómo determinar si se ha alcanzado la solución óptima del problema no restringido a través del Método del Gradiente?

Para ello se debe verificar que la dirección de descenso en la k-ésima iteración es nula (cero).

Se puede corroborar en este ejemplo que esto se logra al intentar realizar una nueva iteración a partir de (x1,x2)=(12,5).

Adicionalmente se generan las condiciones de segundo orden calculando la Matriz Hessiana o de segundas derivadas de la función objetivo:

seg-orden-grad

Donde los determinantes son estrictamente mayores a cero: D1=2>0 y D2=4>0 (la Matriz Hessiana por tanto es Positiva Definida) por lo cual la función objetivo es estrictamente convexa y dada la condición anterior es suficiente para garantizar que (x1,x2)=(12,5) es la solución óptima del problema.