El objetivo de esta seccón es doble. Por un lado queremos encontrar condiciones necesarias y suficientes para las que un cierto punto x, sea solución de nuestro problema de programación no lineal.
Por otro lado, nos gustaria encontrar un algoritmo con el que podamos llegar a encontrar dicho punto a partir de un cierto punto incial x0 dado.
Programación no Lineal en funciones y regiones Convexas
Conceptos y Principios Básicos
Teoría en extensión
Propiedades de las funciones convexas
1. si f es convexa el conjunto de nivel
Ck = {x ∈ S : f(x) ≤ k, k ∈ R } Es convexo
2. Si f es convexa en S entonces es contínua en el interior de S
3. Si f es convexa en S, conjunto abierto convexo de Rn Entonces f tiene derivadas direccionales en todos los puntos. Es decir
∀ x, d ∈ Rn
f'(x; d) = lim ( f(x + kd) - f(x) ) / k
k → 0
Existe y es finito.
4. f es convexa si y solo sí su Epígrafo:
Epi(f) = { (x, y) ∈ S x R : y ≥ f(x) }
Es un conjunto convexo en Rn+1
5. f es cóncava si y solo sí su Hipógrafo:
Hipo(f) = { (x, y) ∈ S x R : y ≤ f(x) }
Es un conjunto convexo en Rn+1
La convexidad no es una condición suficiente para la diferenciabilidad, por ejemplo la función
f(x) = |x|
No es diferenciable en x = 0, sin embargo es convexa en dicho punto. No obstante, del punto 3 sabemos que f tiene derivadas direccionales en x=0.
Obviamente, en el caso de que una función sea diferenciable podemos definir el gradiente de f. Para funciones no diferenciables definimos el Subgradiente , el cual hace el papel del gradiente en funciones no diferenciables.
El siguiente Teorema, que es otra caracterización de convexidad para funciones diferenciables generaliza la idea de funciones crecientes en funciones diferenciables
Nótese que para dimensión 1, tenemos la condición de la derivada segunda para funciones convexas.
1. si f es convexa el conjunto de nivel
Ck = {x ∈ S : f(x) ≤ k, k ∈ R } Es convexo
2. Si f es convexa en S entonces es contínua en el interior de S
3. Si f es convexa en S, conjunto abierto convexo de Rn Entonces f tiene derivadas direccionales en todos los puntos. Es decir
∀ x, d ∈ Rn
f'(x; d) = lim ( f(x + kd) - f(x) ) / k
k → 0
Existe y es finito.
4. f es convexa si y solo sí su Epígrafo:
Epi(f) = { (x, y) ∈ S x R : y ≥ f(x) }
Es un conjunto convexo en Rn+1
5. f es cóncava si y solo sí su Hipógrafo:
Hipo(f) = { (x, y) ∈ S x R : y ≤ f(x) }
Es un conjunto convexo en Rn+1
La convexidad no es una condición suficiente para la diferenciabilidad, por ejemplo la función
f(x) = |x|
No es diferenciable en x = 0, sin embargo es convexa en dicho punto. No obstante, del punto 3 sabemos que f tiene derivadas direccionales en x=0.
Obviamente, en el caso de que una función sea diferenciable podemos definir el gradiente de f. Para funciones no diferenciables definimos el Subgradiente , el cual hace el papel del gradiente en funciones no diferenciables.
Teorema (Existencia de Subgradiente en funciones Convexas)
Sea f: S ⊂ Rn → R convexa, entonces
f tiene subgradiente en todos los puntos del interior de S.
Sea f: S ⊂ Rn → R convexa, entonces
f tiene subgradiente en todos los puntos del interior de S.
Teorema (Existencia de Subgradiente en funciones Convexas)
Sea f: S ⊂ Rn → R
convexa, entonces
f tiene subgradiente en todos los puntos del interior de S.
Sea f: S ⊂ Rn → R
convexa, entonces
f tiene subgradiente en todos los puntos del interior de S.
Teorema (Caracterización de convexidad para funciones Diferenciables)
Sea f: S ⊂ Rn → R
con f diferenciable y S conjunto convexo, abierto y no vacío, entonces f es convexa si y solo sí
f(x) ≥ f(y) + ∇f(y) (x - y) ∀ x ∈ S
Sea f: S ⊂ Rn → R
con f diferenciable y S conjunto convexo, abierto y no vacío, entonces f es convexa si y solo sí
f(x) ≥ f(y) + ∇f(y) (x - y) ∀ x ∈ S
El siguiente Teorema, que es otra caracterización de convexidad para funciones diferenciables generaliza la idea de funciones crecientes en funciones diferenciables
Teorema (Caracterización 2 de convexidad para funciones Diferenciables)
Sea f: S ⊂ Rn → R con f diferenciable y S conjunto convexo, abierto y no vacío, entonces f es convexa si y solo sí
(∇f(y) - ∇f(x) ) (x - y) ≥ 0 ∀ x, y ∈ S
Sea f: S ⊂ Rn → R con f diferenciable y S conjunto convexo, abierto y no vacío, entonces f es convexa si y solo sí
(∇f(y) - ∇f(x) ) (x - y) ≥ 0 ∀ x, y ∈ S
Nótese que para dimensión 1, tenemos la condición de la derivada segunda para funciones convexas.
Teorema (Condición necesaria y suficientes para que un punto sea solución)
Sea f: S ⊂ Rn → R con S conjunto convexo, abierto y no vacío. Sea el problema de programación no lineal
Min(f(x))
sujeto a x∈S
El punto x0 es solución óptima para el problema si y solo sí f tiene un subgradiente, ξ en x0 tal que
ξt (x - x0) ≥ 0, ∀x∈S
(∇f(y) - ∇f(x) ) (x - y) ≥ 0 ∀ x, y ∈ S
El subgradiente de una funcion en un punto no tiene porque ser único, pero el siguiente corolario nos dice que si existe uno con valor cero en el punto x0, entonces ese punto es la solución óptima del problema
Sea f: S ⊂ Rn → R con S conjunto convexo, abierto y no vacío. Sea el problema de programación no lineal
Min(f(x))
sujeto a x∈S
El punto x0 es solución óptima para el problema si y solo sí f tiene un subgradiente, ξ en x0 tal que
ξt (x - x0) ≥ 0, ∀x∈S
(∇f(y) - ∇f(x) ) (x - y) ≥ 0 ∀ x, y ∈ S
Corolario
En las hipótesis del Teorema, si S es abierto
El punto x0 es solución óptima si y solo sí existe un subradiente 0 de f en el punto x0
El punto x0 es solución óptima si y solo sí existe un subradiente 0 de f en el punto x0
Ha sido util? Alguna idea para complementar el texto?
Deja tu post
Comentarios de otros usuarios
Deja tu post
