Programación no Lineal en funciones y regiones Convexas

Conceptos y Principios Básicos

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.

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.
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.
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.
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

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

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
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





Ha sido util? Alguna idea para complementar el texto?



Deja tu post

Comentarios de otros usuarios





Deja tu post