Please enable JavaScript.
Coggle requires JavaScript to display documents.
Métodos Numéricos de Optimización: Problemas de Optimización sin…
Métodos Numéricos de Optimización: Problemas de Optimización sin restricciones
Introducción: Programación Matemática
Forman la base teórica para el desarrollo de varios algoritmos para la optimización de funciones con y sin restricciones.
Los algoritmos para la optimización no lineal sin restricciones con múltiples variables se pueden clasificar como: (i) Búsqueda sin el uso de derivadas (ii) búsqueda usando información de la derivada primera, y (iii) búsqueda usando información de la derivada segunda.
En la optimización no lineal con restricciones los diferentes métodos pertenecen a las clases: (i) métodos de penalización exterior. (ii) métodos de penalización interior (barrera) (iii) métodos de proyección de gradiente. (iv) método de gradiente reducido generalizado (v) programación lineal sucesiva (vi) programación cuadrática sucesiva
Las funciones de penalización exterior exactas diferenciables suelen definir una lagrangiana aumentada añadiendo a la lagrangiana original términos cuadráticos para penalizar las restricciones de igualdad y desigualdad.
Los métodos de barrera transforman el problema original con restricciones en una sucesión de problemas sin restricciones introduciendo una función de barrera que evita la generación de puntos externos a la región factible.
:
La programación cuadrática sucesiva trata de mejorar la convergencia de la programación lineal sucesiva utilizando aproximaciones de segundo orden. En este caso se aplica el método de Newton.
Métodos indirectos: Métodos de Segundo orden.
Las direcciones de búsqueda el método del máximo descenso se puede interpretar como un movimiento ortogonal a una aproximación lineal (tangente) a la función objetivo en el punto 𝑥^𝑘.
El Método de Newton.
Hace uso de la aproximación de segundo orden de la función utilizando las derivadas segundas con respecto a cada una de las variables independientes.
Si f(x) es una función cuadrática el mínimo se alcanza en un único paso. Pero para una función general no lineal el óptimo no se alcanza en un único paso.
Estrictamente hablando el valor de λ es la unidad.
Desventajas del método
Es el método de minimización más rápido
No encuentra necesariamente un óptimo global (pero esto es una característica de todos los métodos
Requiere la inversión de matrices
Necesita de las derivadas primera y segunda
Forzando a la matriz Hessiana a ser Definida Positiva
La matriz Hessiana de f(x) puede ser modificada para obligarla a ser definida positiva y bien condicionada en cada etapa de búsqueda.
donde β es una constante positiva para asegurar que (H)x sea definida positiva
Métodos de la Secante
Comienzan con la misma ecuación usada en el método de Newton
Conseguir una actualización de la matriz H(x), a la que llamaremos (H^)x usando solamente las derivadas parciales primeras de la función
Si queremos aproximar la matriz inversa, los métodos de secante o quasi-Newton calculan un nuevo vector x a partir de otro de una etapa
Debido a que tenemos solamente n ecuaciones y un total de n^2 incógnitas aparece un número infinito de posibles soluciones a las ecuaciones anteriores.
OPTIMIZACIÓN NUMÉRICA MULTIVARIABLE SIN RESTRICCIONES
La optimización numérica de funciones no lineales requiere la utilización de técnicas de optimización eficientes y robustas, es importante porque la solución de estos problemas se lleva a cabo por un procedimiento iterativo. La robustez (habilidad para encontrar la solución) es una propiedad deseable dado que el comportamiento de las funciones no lineales puede ser impredecible: pueden presentar máximos, mínimos y puntos de silla.
La mayor parte de los procedimientos iterativos que son efectivos, alternan la optimización en dos fases
(a)
Elección de una dirección sk
(b)
Movimiento en la dirección s, (en alguna extensión, o hasta encontrar un mínimo) para encontrar un nuevo punto xk+ xk x = + 1 D donde Dxk se suele llamar el tamaño del paso.
MÉTODOS DIRECTOS
Los métodos directos no hacen uso de la información proporcionada por las derivadas. Bajo estas circunstancias, estos métodos se pueden usar con bastante efectividad, pero son muy ineficientes comparados con los métodos discutidos en las siguientes secciones. Tienen la ventaja de que estos métodos son muy simples de entender y muy fáciles de ejecutar.
Métodos de búsqueda aleatoria
Un método aleatorio simplemente selecciona un vector inicial x0, evalúa la función objetivo en ese punto y entonces aleatoriamente selecciona otro vector x1. Tanto la dirección de búsqueda como la longitud de búsqueda son elegidas simultáneamente. Después de una o más etapas, el valor de f(xk) se compara con el mejor valor previo de f(x) y se toma la decisión de continuar o terminar el procedimiento. Existen diversas variaciones de este algoritmo, aunque estrictamente hablando sólo se alcanza la solución cuando k → ∞, pero desde un punto de vista práctico, si el objetivo tiene una forma muy plana se pueden encontrar soluciones subóptimas bastante aceptables.
Métodos de búsqueda en rejilla.
Los métodos básicos de diseño de experimentos discutidos en muchos textos de estadística, se pueden aplicar también a minimización de funciones. Se pueden seleccionar una serie de puntos alrededor de un punto base de referencia, de acuerdo con algunos de los diseños del tipo que se muestra en la siguiente figura. Después se pasa al punto que más mejora la función objetivo y se continua la búsqueda.
Búsqueda Univariante
Otro método muy sencillo de optimización consiste en seleccionar n direcciones fijas de búsqueda, para n variables, (habitualmente los ejes coordenados) de tal manera que f(x) se minimiza de forma secuencial usando búsquedas unidimensionales en cada una de las direcciones previamente seleccionadas. El método suele ser bastante ineficaz incluso llegando a puntos muy alejados del óptimo de los cuales no puede salir.
Método simplex flexible.
Este método se basa en tomar una figura regular (conocida como simplex) como base. Así en 2 dimensiones tal figura debería ser un triángulo equilátero. Los experimentos se localizan de tal manera que la función objetivo se evalúa en cada uno de los vértices que forman la figura geométrica. Los valores de la función objetivo obtenida en cada uno de los vértices se comparan entre sí rechazando el peor valor de todos formando una nueva figura geométrica por reflexión del peor de los puntos respecto a los que no han sido rechazados. En el simplex original se mantiene la figura geométrica, mientras que la modificación de Neadler y Mead permite distorsiones de ésta para acelerar el proceso de búsqueda.
Selección de la figura “simplex” inicial:
Para visualizarlo de forma sencilla comenzaremos con el caso de dos dimensiones. Así la
distancia entre un punto x1=(x11, x12) y otro x2=(x21, x22) viene dada por la expresión:
procediendo de tal manera las distancias entre dos puntos vendrán dadas por una
expresión similar.
De forma similar en n dimensiones tenemos n+1 puntos. La tabla siguiente es una
propuesta para comenzar un simplex de n variables cuando x1 es el origen
Paso 0:
Calcular la función objetivo en cada uno de los puntos (vértices), hallar el vértice
con el valor máximo ‘Qmax’ el vértice con valor mínimo ‘Qmin’ y el centroide de
todos los vértices excepto aquel que ha dado el peor valor:
Paso 1: Reflexión:
Se calcula un nuevo vértice Q*
®
cuyas coordenadas son:
donde g r es el llamado coeficiente de reflexión, una cantidad positiva que
generalmente suele ser la unidad. Realmente lo que hemos hecho ha sido reflejar
el punto con el peor valor respecto del centroide. Las siguientes figuras lo ilustran
para el caso de 2 y 3 variables.
Direcciones conjugadas. Método de Powell
La experiencia ha demostrado que las direcciones llamadas conjugadas son mucho más efectivas como direcciones de búsqueda que otras como pueden ser la búsqueda univariante o las direcciones ortogonales
Método de Newton en diferencias finitas
Los métodos en diferencias finitas tipo Newton, se utilizan si la derivada de la función objetivo es difícil de calcular, o ésta viene dada de forma numérica. Se basan en sustituir las derivadas por aproximaciones en diferencias finitas.
Métodos de secante
BÚSQUEDA UNIDIRECCIONAL: MÉTODOS DE ELIMINACIÓN DE REGIÓN
Los métodos de eliminación de región para una búsqueda unidimensional se basan en eliminar una región, en cada etapa, del intervalo en el que está comprendido el mínimo..
El elemento básico dentro del sistema de eliminación de regiones es la comparación de valores de f(x) en dos o más puntos dentro del intervalo de x. Debemos asumir que f(x) es unimodal, y que tiene un mínimo (es convexa) dentro de [a, b].
búsqueda de dos puntos a intervalos iguales
.
El intervalo de incertidumbre se reduce en 1/3 en cada iteración. Así si L0 es la longitud del intervalo original (b-a) y Lk es el intervalo después de k iteraciones, como en cada iteración se llevan a cabo dos evaluaciones de la función objetivo, entonces Lk tras k iteraciones viene dado por:
método de la bisección o búsqueda dicotómica.
La incertidumbre del intervalo después de k iteraciones vendrá dada por:
SECCIÓN ÁUREA
los cuales usan una relación constante para dividir el intervalo en segmentos.
La estrategia empleada en el método de la sección áurea es localizar dos puntos interiores del intervalo eliminado en cada iteración de tal manera que se cumpla la relación:
BÚSQUEDA UNIDIRECCIONAL: MÉTODOS DE APROXIMACIÓN POLINÓMICA
localizan un punto x cercano a x*, el valor de la variable independiente correspondiente al mínimo de f(x), por interpolación y extrapolación utilizando aproximaciones polinómicas a f(x).
Se han propuesto tanto aproximaciones cuadráticas como cúbicas usando tanto los valores de la función solamente como los de sus derivadas primeras.
Interpolación cuadrática.
por ejemplo x1, x2, x3 en orden creciente, y no necesariamente igualmente espaciados, pero contenidos dentro de la zona de búsqueda (a,b), podemos aproximarlos a un polinomio de grado 2, de tal manera que dicho polinomio.
Interpolación cúbica
La interpolación cúbica en la búsqueda de un óptimo se basa en la aproximación de la función objetivo por un polinomio de tercer grado dentro del intervalo de interés, y determinar el punto estacionario asociado con el polinomio.
Método del Gradiente (Máximo descenso)
El gradiente es un vector en un punto x que proporciona la dirección (local) de máxima variación de la función, es un vector ortogonal al contorno de la función en el punto.
El gradiente negativo da la dirección de movimiento, pero no la longitud de dicho movimiento
1.- Elegir un valor inicial x0. En pasos sucesivos será xk.
2.- Calcular, analítica o numéricamente las derivadas parciales ()∂∂fxjnjx=1 2 3, , ....
,3.- Calcular el vector de búsqueda ()sx= −∇fk
4.- Usar la relación xxskkkk+=+1λ para obtener el siguiente punto. El valor de λkpuede ser de valor fijo o calculado en cada paso mediante una búsqueda unidireccional.
5.- Comparar ()fkx+1 con ()fkx. Si el cambio es menor que una tolerancia pre-especificada terminar, en caso contrario volver al paso dos y continuar con las iteraciones.
MÉTODOS INDIRECTOS:MÉTODOS DE PRIMER ORDEN
El método del gradiente conjugado, esencialmente, combina la información obtenida del vector gradiente con la información acerca del vector gradiente de iteraciones previas. Lo que hace el método es calcular la nueva dirección de búsqueda utilizando una combinación lineal del gradiente en la etapa considerada y el de la etapa anterior.
2.5.3.2.- Método del gradiente conjugado
Optimización de funciones sin restricciones
Razones
En muchos problemas las restricciones se pueden incluir dentro de la función objetivo, por lo que la dimensionalidad del problema se reduce a una variable.
Algunos problemas sin restricciones, inherentemente incluyen una única variable.
Las técnicas de optimización con y sin restricciones, generalmente incluyen pasos de búsqueda unidireccional en sus algoritmos.
Búsqueda unidireccional
Los métodos de optimización estaban prácticamente limitados a los métodos indirectos en los cuales el cálculo del extremo potencial estaba restringido al uso de derivadas y la condiciones necesaria de optimalidad
Los métodos indirectos tienen la ventaja inherente de que la convergencia es generalmente más rápida incluso aun cuando se utilicen métodos numéricos para calcular las derivadas.
Los métodos numéricos directos, tienen la ventaja de que pueden tratar fácilmente con problemas que incluyan discontinuidades, puntos de inflexión y puntos finales.
Para resolver un problema de optimización no lineal sin restricciones bastaría derivar cada una de las funciones e igualar a cero.
Para aplicar los métodos de búsqueda directa se debe comenzar por acotar el punto donde se encuentra el óptimo, y asegurarse de que la función es unimodal en el intervalo considerado.
Acotación del Óptimo
Se pueden usar para acotar el óptimo, la más sencilla consiste en fijar un punto y comenzar a movernos una distancia fija en una dirección.
Los métodos de búsqueda unidimensional se pueden clasificar en métodos directos, métodos indirectos de búsqueda secuencial, y métodos de interpolación polinómica
Métodos Indirectos
Básicamente tres métodos para llevar a cabo la búsqueda directa unidireccional, basados en las condiciones de optimalidad.
Para comparar la eficacia de cada método, es útil examinar la velocidad de convergencia de cada uno de ellos.
Método de Newton
De acuerdo con la primera condición necesaria para que una función tuviera un mínimo local se debe cumplir que f '( x) = 0.
Las Ventajas:
1.- El procedimiento es cuadráticamente convergente (p=2), siempre que f ''(x) ¹ 0
2.- Para una función cuadrática el mínimo se obtiene en una única iteración.
Las Desventajas
1.- Se debe calcular tanto f’(x) como f’’(x).
2.- Si f’’(x)®0 el método converge muy lentamente.
3.- Si existe más de un extremo, el método podría no converger al extremo deseado.
Además el método podría oscilar.
Los métodos de secante toman dos puntos, xp y x q y resuelve una ecuación similar a la dada en el método de Newton:
