Optimización sin restricciones Condiciones de primero y segundo orden para la existencia de extremos Búsqueda Lineal Métodos básicos de descenso para funciones de varias variables
Derivada direccional La derivada direccional permite tener información del comportamiento de la función si sus variables se modifican siguiendo el sentido indicado por el vector gradiente
La Derivada direccional de f en p según el vector unitario ? [ D? f(p) ] es el producto escalar del gradiente en p, por ? : D? f(p) = ?f(p)T ?
¿En qué sentido deberían desplazarse las variables de f, partiendo del punto p, para que los valores de f crezcan más rápidamente?
Derivada direccional Como la rapidez está dada por : ?f(p)T ?
En esta expresión se suponen ya conocidos f y p; faltando conocer “?” que haga máximo el producto escalar
Siendo ?f(p)T ? = ??f(p)?. ??? Cos ? = ??f(p)?.(1). Cos ?
Donde : ? , es el ángulo formado por los vectores ?f(p) y ?
?f(p)T ?, será máximo si y sólo si Cos ? es máximo, ósea cuando ? = 0 y ?f(p) con ? son colineales. Lo cual significa que el vector unitario ? debe tener el mismo sentido que el vector gradiente de f en p significa que el vector gradiente de una función f en un punto p, ?f(p), de su dominio se orienta en el sentido en el cual f crece mas rápidamente
Gradiente El gradiente de una función escalar de n variables f(x1, x2,…, xn,), denotado por ?f, es el vector n-dimensional
El gradiente de una función en un punto indica la dirección, a partir de ese punto, en la que dicha función crece más rápidamente y, además, la dirección ortogonal a las curvas de nivel de f (curvas en las que la función tiene un valor constante)
Optimización Sin Restricciones Formulación del problema de optimización Cualquier problema de optimización, por complejo que sea, puede expresarse en los siguientes términos
Encontrar un vector x tal que se minimice una función objetivo f(x) Sujeto a restricciones de la forma:
donde x es un vector de variables independientes
La función objetivo puede tener un solo mínimo, en cuyo caso se denomina unimodal, o varios mínimos locales o globales, en cuyo caso se denomina multimodal
Clasificación de problemas de optimización De acuerdo a la forma de f(x) y las restricciones: Programación Lineal: f(x) y las restricciones son lineales Programación No-lineal: f(x) es no-lineal y las restricciones pueden ser no-lineales De acuerdo a la presencia o no de restricciones: Optimización no restringida: El problema de optimización no tiene restricciones Optimización restringida: El problema de optimización tiene restricciones Según su dimensionalidad: Optimización unidimensional: función objetivo de una variable Optimización multidimensional: función objetivo de varias variables Según el número de funciones objetivo: Optimización con un objetivo: Una sola función objetivo Optimización con múltiples objetivos: varias funciones objetivo
Clasificación de problemas de optimización Existen varios métodos para resolver un problema de optimización Estos métodos pueden agruparse en dos grandes clases: Métodos de optimización basados en derivadas Métodos de optimización no basados en derivadas
Métodos de optimización basados en derivadas Métodos básicos de descenso Son técnicas básicas utilizadas en la solución iterativa de problemas de minimización sin restricciones
Ofrecen la forma más simple y directa de resolver estos problemas
Ofrecen en términos prácticos una referencia con relación a la dificultad de implementación y velocidad de convergencia
En general, las técnicas avanzadas se comparan con estas técnicas básicas
Estructura básica de los métodos básicos de descenso Se inicia en un punto, x0 Se determina la dirección de descenso mediante una regla fija (Primera diferencia entre algoritmos) Luego, se busca el mínimo en esa dirección (Búsqueda lineal)
La forma general de los métodos básicos de descenso se puede expresar como,
Búsqueda Lineal Las técnicas de búsqueda lineal son realmente procedimientos de optimización para una sola variable, los cuales son realizados repetidamente en problemas de varias variables La elección de una dirección de búsqueda tiene un alto costo computacional, es por ello que los métodos de descenso basados en gradiente sufren modificaciones con el objeto de minimizar o reducir el número de cálculos de gradiente, Hessiano, e inversión de matrices La modificación fundamental consiste en reducir el problema a uno de optimización a lo largo de la dirección de descenso
Búsqueda Lineal Específicamente se debe resolver el sub-problema de optimización: Encontrar ?, tal quedonde d es la dirección de descenso
Hallado el ? óptimo se inicia una nueva iteración de descenso
Búsqueda Lineal Este sub-problema es sensiblemente más sencillo que la optimización general ya que es un problema de una dimensión con una única variable, ? La elección de un método adecuado de búsqueda lineal es de gran importancia en un algoritmo de optimización La búsqueda lineal es responsable de un alto porcentaje del costo de la evaluación de la función objetivo
Página siguiente  |