OPTIMIZACIÓN DE FUNCIONES SIN RESTRICCIÓN:
BÚSQUEDA UNIDIMENSIONAL
Métodos numéricos para optimizar funciones univariables
UNA BUENA TÉCNICA para la optimización de una función de una sola
variable es fundamental por dos razones:
1) Algunos problemas no restringidos involucran intrínsecamente solo
una variable.
2) Las técnicas para problemas de optimización sin restricciones
generalmente implican el uso repetido de una búsqueda
unidimensional.
La mayoría de los algoritmos para la optimización restringida y sin
restricciones hacen uso de una técnica de optimización unidimensional
eficiente para localizar un mínimo local de una función de una variable.
3
Procedimientos de exploración y delimitación
Algunos procedimientos de búsqueda unidimensionales requieren que
se obtenga una delimitación del mínimo como la primera parte de la
estrategia, y luego el espacio delimitado se reduce. Junto con el
enunciado de la función objetivo debe haber algún enunciado de
límites en o, de lo contrario, el supuesto implícito de que no está
acotado . Por ejemplo, el problema
Esta función tienen un mínimo en . Claramente no se espera
empezar en e intentar tratar de acotar el mínimo. Por lo tanto, se
espera que exista un sentido común al tratar de realizar la búsqueda del
mínimo.
4
Procedimientos de exploración y delimitación
En el trabajo de ingeniería y científico, los límites físicos de temperatura,
presión, concentración y otras variables físicamente significativas colocan
límites prácticos en la región de búsqueda que podrían usarse como una
delimitación inicial.
Existen varias estrategias para explorar el espacio de la variable
independiente y determinar un rango aceptable para buscar el mínimo de
.
A continuación se exponen algunos de los métodos más empleados;
métodos de descenso para la minimización porque un paso dado se sigue
solo si produce un valor mejorado para la función objetivo. Primero
cubrimos los métodos que usan valores de función de primera o segunda
derivada, luego se hará una revisión de varios métodos que usan solo valores
de función.
5
MÉTODOS NEWTON Y QUASI-NEWTON PARA LA BÚSQUEDA
UNIDIMENSIONAL
Tres procedimientos básicos para encontrar un extremo de una función
de una variable han evolucionado a partir de la aplicación de las
condiciones de optimalidad necesarias a la función:
1. Método de Newton
2. Aproximación en diferencias finitas del método de Newton
3. Métodos Quasi Newton
MÉTODOS NEWTON Y QUASI-NEWTON PARA LA BÚSQUEDA
UNIDIMENSIONAL
Al comparar la efectividad de estas técnicas, es útil examinar la tasa de
convergencia de cada método. Las tasas de convergencia se pueden expresar
de varias formas, pero una clasificación común es la siguiente:
Lineal
Orden p
Si , el orden de convergencia se dice que es cuadrático.
7
Método de Newton
Recuerde que la condición necesaria de primer orden para un mínimo local
es . En consecuencia, puede resolver la ecuación
mediante el método de Newton para obtener
(A)
Asegurando en cada etapa k que para un mínimo. Para ver
lo que implica el método de Newton sobre , suponga que se
aproxima mediante una función cuadrática en .
Método de Newton
Si se toma la derivada de .
(B)
Este resultado es el mismo que la ecuación (A).
Aplique el método de Newton para encontrar el mínimo en las siguientes
funciones:
9
Aproximaciones en diferencias finitas a derivadas
Si no viene dada por una fórmula, o la fórmula es tan complicada
que no se pueden formular derivadas analíticas, puede reemplazar la
ecuación (A) con una aproximación en diferencias finitas
Donde h representa el tamaño de paso seleccionado, este valor
representara a su vez la precisión con la que se calculará la solución.
10
Método Quasi Newton
En el método quasi Newton o también llamado método de la secante, el modelo análogo
aproximado (B) puede ser resuelto
Donde m es la pendiente de la línea que conecta el punto y el segundo punto dado por
Este método imita el método de Newton
Donde es la aproximación de obtenida en una iteración k.
11
CÓMO SE APLICA LA BÚSQUEDA UNIDIMENSIONAL EN UN
PROBLEMA MULTIDIMENSIONAL
Al minimizar una función de varias variables, el procedimiento general es (a) calcular una
dirección de búsqueda y (b) reducir el valor de dando uno o más pasos en esa dirección de
búsqueda.
Por ejemplo si tenemos la siguiente función:
Si se consideran búsquedas unidimensionales entonces:
En la dirección :
En la dirección :
Donde representa la distancia de desplazamiento en una dirección de búsqueda y s representa la
componente de dirección, está en función del gradiente.
*Ver programa Matlab
12
CÓMO SE APLICA LA BÚSQUEDA UNIDIMENSIONAL EN UN
PROBLEMA MULTIDIMENSIONAL
Para la función: . Partiendo
del punto .
Paso 1) Se calcula el gradiente negativo
Paso 2) Se calcula
Paso 3) Se inicia con un valor de
Paso 4) Se calcula y
Paso 5) Se repite el paso 2 n veces
13
