donde tanto la función objetivo como las funciones de restricciones son funciones diferenciables.
como hemos dicho, el problema se puede plantear a algo a un problema extendido de máximos y mínimos.
Programación no Lineal en funciones Diferenciables
Conceptos y Principios Básicos
Nos ocuparemos en esta sección de problemas del tipo
donde tanto la función objetivo como las funciones de restricciones son funciones diferenciables.
como hemos dicho, el problema se puede plantear a algo a un problema extendido de máximos y mínimos.
donde tanto la función objetivo como las funciones de restricciones son funciones diferenciables.
como hemos dicho, el problema se puede plantear a algo a un problema extendido de máximos y mínimos.
Teoría en extensión
Sea f continua y diferenciable
Es decir, el gradiente es el vector formado por todas las derivadas de la función f.
A continuación vemos el concepto de derivada direccional, dicha derivada mide la tasa de cambio de la función en la dirección del vector v.
El siguiente Teorema nos asegura la existencia de todas las derivadas direccionales en el caso de funciones diferenciables
Como resultado de que la derivada direcciona mide la tasa de cambio de la función en la dirección de v. Esto es muy interesante en nuestro problema pues dado un punto, nos interesa saber en que dirección la función es creciente o decreciente y sobre todo en que dirección crece o decrece más rápido.
El siguiente problema responde a esta questión
En otras palabras, si queremos saber en que dirección la función f, crece más rápidamente, tenemos que mirar en la dirección del vector grad f(x).
Análogamente, la dirección en la que la función decrece más deprisa es la de -grad f(x)
Esto nos da una idea de un algoritmo, dado un punto (x, f(x)), mediante los métodos de cálculo numérico podemos calcular el vector grad f(x) e iterar en esa dirección (en el sentido creciente o decreciente, según sea nuestro problema de maximizar o minimizar).
El siguiente Teorema nos habla de extremos locales de funciones.
Nota Se puede formular un teorema análogo con la relacción concavidad/Máximos locales
Ahora bien, dado un punto en el que grad f(x) = 0. Como saber si este punto es un máximo, un ménimo o un punto de silla? Lo que resta de sección trata de este asunto.
Si f es dos veces diferenciable, define la matriz Hessiana de f
La convexidad de una función sólo asegura la continuidad de dicha función. Por tanto no podemos hablar genéricamente del gradiente y menos aún de matriz Hessiana.
En lugar de eso, en la próxima sección definirimos el subgradiente, que hace el papel del gradiende para funciones no diferenciables (de echo, el subgradiente es el gradiente cuando la función es diferenciable)
Aquí ya podemos ver la complejidad de un problema de programación no-lineal. En el caso de funciones convexas todo es mucho más sencillo ya que mínimos locales se convierten en mínimos globales.
El gradiente de la función f se define como
Que también denotaremos aquí como grad f(x).
Que también denotaremos aquí como grad f(x).
Es decir, el gradiente es el vector formado por todas las derivadas de la función f.
A continuación vemos el concepto de derivada direccional, dicha derivada mide la tasa de cambio de la función en la dirección del vector v.
Derivada direccional
Dado un vector v, se define la derivada de direccional de f en la direcciên v como
Df(x)v = df(x+tv)/dt, evaluado en t=0
También se puede definir como el límite
Dado un vector v, se define la derivada de direccional de f en la direcciên v como
Df(x)v = df(x+tv)/dt, evaluado en t=0
También se puede definir como el límite
El siguiente Teorema nos asegura la existencia de todas las derivadas direccionales en el caso de funciones diferenciables
Teorema (Existencia de derivadas direccionales en funciones diferenciables)
Sea
función diferenciable, entonces existen todas las derivadas direccionales, y la derivada en un punto x en la dirección v está dada por el producto escalar del Gradiente de f por v:
Df(x)v = <grad f(x) . v >
Sea
función diferenciable, entonces existen todas las derivadas direccionales, y la derivada en un punto x en la dirección v está dada por el producto escalar del Gradiente de f por v:
Df(x)v = <grad f(x) . v >
Como resultado de que la derivada direcciona mide la tasa de cambio de la función en la dirección de v. Esto es muy interesante en nuestro problema pues dado un punto, nos interesa saber en que dirección la función es creciente o decreciente y sobre todo en que dirección crece o decrece más rápido.
El siguiente problema responde a esta questión
Teorema
Si el grad f(x) ≠ 0, entonces grad f(x) apunta en la dirección de mayor crecimiento de la función
Si el grad f(x) ≠ 0, entonces grad f(x) apunta en la dirección de mayor crecimiento de la función
En otras palabras, si queremos saber en que dirección la función f, crece más rápidamente, tenemos que mirar en la dirección del vector grad f(x).
Análogamente, la dirección en la que la función decrece más deprisa es la de -grad f(x)
Esto nos da una idea de un algoritmo, dado un punto (x, f(x)), mediante los métodos de cálculo numérico podemos calcular el vector grad f(x) e iterar en esa dirección (en el sentido creciente o decreciente, según sea nuestro problema de maximizar o minimizar).
El siguiente Teorema nos habla de extremos locales de funciones.
Teorema (Relacción Mínimos - Convexidad)
Sea f como antes
f tiene un mínimo local en x
y f es convexa en un entorno de x
Sea f como antes
f tiene un mínimo local en x
y f es convexa en un entorno de x
Nota Se puede formular un teorema análogo con la relacción concavidad/Máximos locales
Ahora bien, dado un punto en el que grad f(x) = 0. Como saber si este punto es un máximo, un ménimo o un punto de silla? Lo que resta de sección trata de este asunto.
Si f es dos veces diferenciable, define la matriz Hessiana de f
Teorema (Caracterización de extremos locales)
Sea
y sea x un punto en el cual grad f(x) = 0, entonces
a) Si la matriz Hessiana de f:
es definida positiva entonces x es un mínimo local de f.
b) Si es definida negativa entonces x es un méximo local de f.
c) Si no es ni definida positiva ni definida negativa, entonces x es un punto de silla de f.
Sea
y sea x un punto en el cual grad f(x) = 0, entonces
a) Si la matriz Hessiana de f:
es definida positiva entonces x es un mínimo local de f.
b) Si es definida negativa entonces x es un méximo local de f.
c) Si no es ni definida positiva ni definida negativa, entonces x es un punto de silla de f.
Teorema (Caracterización de convexidad por el Hessiano)
Sea
f es convexa si y solo sí la matriz
es definida positiva
Entonces si f es convexa en toda la región S y tiene un mínimo local en el punto x, entonces x es solución de nuestro Problema pues será un mínimo global .
Sea
f es convexa si y solo sí la matriz
es definida positiva
Entonces si f es convexa en toda la región S y tiene un mínimo local en el punto x, entonces x es solución de nuestro Problema pues será un mínimo global .
La convexidad de una función sólo asegura la continuidad de dicha función. Por tanto no podemos hablar genéricamente del gradiente y menos aún de matriz Hessiana.
En lugar de eso, en la próxima sección definirimos el subgradiente, que hace el papel del gradiende para funciones no diferenciables (de echo, el subgradiente es el gradiente cuando la función es diferenciable)
Aquí ya podemos ver la complejidad de un problema de programación no-lineal. En el caso de funciones convexas todo es mucho más sencillo ya que mínimos locales se convierten en mínimos globales.
Ha sido util? Alguna idea para complementar el texto?
Deja tu post
Comentarios de otros usuarios
Deja tu post
