Unidad 3: Métodos de Búsqueda

 Función Unimodal

La modalidad de las funciones es particularmente importante en optimización, el termino unimodal se refiere a funciones que tienen un solo extremo, mínimo o máximo, mientras que multimodal se refiere a funciones que presentan dos o más extremos.

En la figura siguiente la función es unimodal si se está buscando un máximo -existe uno solo, el punto c- pero no lo sería si se buscase un mínimo, pues hay dos en la zona de soluciones admisibles, los puntos a y b, los extremos del intervalo. Nótese que la unimodalidad no se ve afectada por la discontinuidad -de la función y su derivada- que se presenta en el punto d.

Si bien el concepto de unimodalidad es muy simple de plantear y puede convertirse en una estrategia eficiente para la búsqueda de un óptimo, tiene un inconveniente básico y es que para asegurar su cumplimiento debería conocerse exactamente el comportamiento de la función objetivo, cuestión que, en la práctica, es imposible. Más aún, sin este conocimiento, que es la situación normal, solo se está en condiciones de establecer cuando la función no es unimodal.

Búsqueda por la sección dorada 

La búsqueda (o método) de la sección dorada es una técnica para hallar el extremo (mínimo o máximo) de una función unimodal, mediante reducciones sucesivas del rango de valores en el cual se conoce que se encuentra el extremo. La técnica debe su nombre al hecho de que el algoritmo mantiene los valores de la función en tríos de puntos cuyas distancias forman una proporción dorada. El algoritmo es el límite de la búsqueda de Fibonacci (también descrita debajo) para un largo número de evaluaciones de la función. La búsqueda de Fibonacci y la búsqueda de la sección dorada fueron descubiertos por Kiefer (1953).

Algoritmo: 

Método De Interpolación Cuadrática 

Cuando el polinomio que conviene es de 2º grado la interpolación recibe el nombre de cuadrática. El polinomio interpolador es único, luego como se encuentre da igual., sin embargo, a veces los cálculos son muy laboriosos y es preferible utilizar un método que otro. A la vista de los datos se decide.

En el ejemplo 1 se da el método de resolver el sistema para encontrar los valores que determinan a la función cuadrática (a, b y c)

También podemos utilizar la expresión del polinomio interpolador así:

y= a + b(x-x0) + c(x-x0)(x-x1), con lo que la búsqueda de los coeficientes es muy sencilla.

Lagrange (1736-1813) dio una manera simplificada de calcular los polinomios interpoladores de grado n Para el caso de un polinomio de 2º grado que pasa por los puntos (x0, y0 ), (x1, y1), (x2, y2):

Que es la fórmula de Lagrange para n=2.

Con frecuencia se tienen que estimar valores intermedios entre valores conocidos. El método mas común empleado para este propósito es la interpolación polinomial.

Recuérdese que la fórmula general de un polinomio de n-ésimo orden es:

Para n + 1 puntos, existe uno y sólo un polinomio de n-ésimo orden o menor que pasa a través de todos los puntos. Por ejemplo, hay sólo una línea recta (es decir un polinomio de primer orden) que conecta dos puntos. El polinomio de interpolación consiste en determinar el único polinomio de n-ésimo orden que se ajusta a los n + 1 puntos dados. Este polinomio proporciona una fórmula para calcular los valores intermedios.

Aunque existe uno y sólo un polinomio de n-ésimo orden que se ajusta a los n + 1 puntos, existen una gran variedad de fórmulas matemáticas mediante las cuales se puede expresar este polinomio. En esta unidad se estudian dos técnicas alternativas que están bien condicionadas para implementarse en una computadora. Estos son los polinomios de Newton y de Lagrange.

Método de Búsqueda Multidimensionales 

• a)       Downhill simplex: En el método downhill simplex, cada punto de un simplex representa una posible solución del problema. El simplex correspondiente a una función de N variables se representa por una matriz de (N+1)xN. Cada columna de la matriz contiene las N coordenadas de un vértice

El algoritmo consiste en la búsqueda de un mínimo siguiendo una sucesión de operaciones sobre el simplex: expansión, contracción, y reflexión. Primero se localiza el vértice nmax donde la función objetivo f toma el valor máximo, y se lo refleja respecto de la cara opuesta del simplex determinando un nuevo punto n prueba. Se evalúa la función en una serie de puntos que pertenezcan a la recta perpendicular a dicha cara y que contiene a n prueba.

Si en alguno de esos puntos, la función toma un valor menor que f(nmax), entonces ese punto reemplaza a nmax en el simplex. En caso contrario, se conserva el simplex original y se lo contrae en todas las direcciones alrededor del mínimo y se vuelve a ejecutar el algoritmo. El método invariablemente converge a un mínimo luego de una serie de contracciones.

 

• b) Algoritmos genéticos: El método de optimización por algoritmos genéticos simula un proceso de evolución y selección natural en una población de individuos. Cada individuo de la población representa una posible solución. Por otra parte, un cromosoma caracteriza a un individuo y está formado por un conjunto de genes, cada uno de los cuales es un parámetro de optimización.

Método de Variación Cíclica

Variaciones Cíclicas: (Serie temporales) se refiere a las oscilaciones de larga duración alrededor de la recta o curva de tendencia; estos ciclos, como se llaman a veces, pueden ser o no periódicos, es decir, puede seguir o no exactamente caminos analógicos después de intervalos de tiempo igual

Se caracterizan por tener lapsos de expansión y contracción. En general, los movimientos se consideran cíclicos solo si se produce en un intervalo de tiempo superior al año (3). En el Gráfico los movimientos cíclicos alrededor de la curva de tendencia están trazados en negrita.