CONCAVIDAD Y CONVEXIDAD

CONJUNTOS CONVEXOS

El concepto de conjunto convexo es algo sencillo de entender desde un punto de vista geométrico.

Son conjuntos convexos aquellos que tienen la propiedad de que al unir con un segmento dos puntos cualesquiera del conjunto, el segmento queda completamente contenido en el propio conjunto.

Definición: Un conjunto S ∀ X,Y ∈S y ∀ λ ∈ [0,1] es convexo cuando: se cumple:

λX +(1-λ)Y ∈ S. Ejemplos:

Para comprender mejor la definición de conjunto convexo debe tenerse en cuenta que dados dos puntos X y Y, los puntos de la forma corresponden justamente con los puntos del segmento que une X y Y.

λX +(1-λ)Y con λ ∈ [0,1] Por tanto, es un conjunto convexo cuando el segmento que une cualquier par de puntos del conjunto está completamente contenido en el conjunto.

CONJUNTO NO CONVEXO

Como generalización del concepto de segmento entre dos puntos, se define lo que se entiende como combinación lineal convexa de una serie de puntos.

Definición: Un punto es una combinación lineal convexa de m puntos cuando puede expresarse en la forma:

X=  λ₁x₁ +  λ₂x₂ +…+  λ_nx_n  donde λ_i ≥ 0 y  λ₁+ λ₂+…+ λ_n = 1

Un conjunto es convexo si y sólo si toda combinación lineal convexa de puntos del conjunto pertenece al propio conjunto.

Propiedades de los conjuntos convexos

• La intersección de un número finito de conjuntos convexos sigue siendo un conjunto convexo.

• Por el contrario, la unión de conjuntos convexos no es necesariamente un conjunto convexo.

• Otra operación que efectuada sobre conjuntos convexos hace que el resultado pueda perder la convexidad es la diferencia entre conjuntos.

• Los conjuntos formados por un número finito de puntos no son convexos, salvo el caso de los que únicamente tienen un punto.

Para los casos en que un conjunto no sea convexo, resultaría interesante analizar si de alguna manera se podría completar dicho conjunto para hacerlo convexo; se plantea entonces la necesidad de intentar encontrar el menor conjunto convexo que contiene a uno dado. Este conjunto siempre existe y recibe el nombre de envoltura convexa.

De la definición anterior pueden deducirse dos formas de construir la envoltura convexa de un conjunto dado:

• Intersección de todos los conjuntos convexos que lo contienen.

• Conjunto formado por todas las combinaciones lineales convexas de puntos del conjunto.

Vértices de un conjunto convexo

Otro concepto importante dentro de la teoría de conjuntos convexos es el de vértice, su interés se verá más adelante al entrar en el estudio de los programas lineales. El concepto de vértice de un polígono desde un punto de vista geométrico está claro, pero expresado en un lenguaje matemático podría darse la siguiente definición.

Definición: Un punto x de un conjunto convexo S es extremo o vértice de S si no puede expresarse como combinación lineal convexa de otros dos puntos de S. Es decir, un vértice nunca puede ser un punto intermedio de un segmento contenido completamente en el conjunto.

No todo conjunto convexo tiene vértices, y en el caso de tenerlos puede tener tanto un número finito como un número infinito de ellos.

Todo conjunto no vacío, convexo, cerrado y acotado tiene al menos un vértice.

Algunos tipos especiales de conjuntos convexos

• Un cono convexo es un conjunto convexo S verificando que para todo punto x de S y todo número 

a > 0 el punto ax sigue perteneciendo al conjunto. Esto quiere decir que para que un conjunto sea un cono, todas las semirrectas que partiendo del origen pasan por cualquiera de sus puntos, deben estar completamente contenidas en el propio conjunto.

• El cono convexo generado por m puntos es el conjunto de todas las combinaciones lineales con coeficientes positivos de esos puntos. En este caso los m puntos se llaman generadores del cono.

• Otro grupo importante de conjuntos convexos lo constituyen los hiperplanos y los semiespacios.

• Se llama polítopo convexo a todo conjunto que puede expresarse como intersección de un número finito de semiespacios cerrados. Si un polítopo tiene vértices, siempre es un número finito de ellos.

• Un poliedro convexo es un polítopo acotado.

• Se llama poliedro convexo generado por m puntos al conjunto de todas las combinaciones lineales convexas de ellos. En este caso, el conjunto de vértices del conjunto constituye un subconjunto del de generadores.

Funciones convexas

Esta sección trata los conceptos de convexidad y concavidad aplicados a funciones. En primer lugar, se introduce la definición matemática de función convexa.

Definición: Una función f(x) definida sobre un conjunto convexo S es convexa cuando verifica la siguiente condición:

∀ X,Y ∈S y ∀ λ ∈ [0,1] se cumple: f(λX +(1-λ)Y) ≤ λf(X )+(1-λ)f(Y)

Cuando en la condición anterior el signo de desigualdad es estricto y λ ∈ [0,1]   la función se dice estrictamente convexa.

Los conceptos de función cóncava y estrictamente cóncava son similares cambiando los signos de desigualdad. De hecho, una función f(x) es cóncava si y sólo si su opuesta -f (x) es convexa.

Gráficamente, las funciones convexas son aquellas en las cuales los segmentos que unen cualquier par de puntos de su gráfica quedan siempre por encima de la gráfica. Si la función es estrictamente convexa, los segmentos no pueden tocar a la gráfica, salvo en los puntos extremos.

Propiedades de las funciones convexas

• Las funciones lineales son a la vez cóncavas y convexas pero no estrictamente.

• La suma de funciones convexas sigue siendo una función convexa.

• Como generalización de la propiedad anterior, puede decirse que cualquier combinación lineal con coeficientes positivos de funciones convexas es una función convexa.

• Si f (x) es una función convexa, entonces - f (x) es una función cóncava. Más aún, al multiplicar una función convexa por una constante negativa el resultado es una función cóncava.

• Si la función f (x) es convexa, el conjunto S_k = {X∈ Rⁿ/ f(X) ≤ k} es convexo para todo valor de k. De una manera similar podría probarse la propiedad que asegura que si la función g(x) es cóncava, entonces el conjunto T_k = {X∈ Rⁿ/ g(X) ≥ k}  es convexo.

Funciones convexas diferenciables

Reconocer si una función es convexa utilizando la definición resulta una tarea en muchos casos complicada, por esa razón son necesarios resultados que permitan identificar funciones convexas con base en otras propiedades; por supuesto, no toda función convexa es diferenciable. Además, desgraciadamente, en las situaciones que se presentan en los casos reales muchas veces surgen funciones que no son diferenciables, por lo que los resultados aquí expuestos no son siempre aplicables; en tales casos, la convexidad de funciones se convierte más en una categoría de análisis que en un concepto operativo.

Primera caracterización

El primero de los resultados utiliza el vector gradiente para estudiar la convexidad de una función de varias variables.

Una función diferenciable f (X) es cionvexa si y sólo si verifica la condición:

F(X) ≤ f(Y) + ▼f(Y)(X-Y)  ∀ X,Y ∈ CS

Rápidamente puede darse una interpretación geométrica a este resultado: una función convexa se caracteriza por el hecho de que el hiperplano tangente a la función en cualquier punto de su dominio siempre está por debajo de la propia función.

En el caso de que la desigualdad anterior se verifique para un punto Y fijo y para puntos X variando en un entorno de Y, se tiene el concepto de convexidad local en el punto Y. Por otro lado, si se cambia el signo de la desigualdad se obtiene una caracterización de las funciones cóncavas diferenciables.

Segunda caracterización

La primera caracterización de las funciones convexas tiene el inconveniente de que sigue utilizando desigualdades para poder ser aplicada y no en todos los casos resulta sencillo probar una desigualdad funcional. En la segunda caracterización de las funciones convexas es necesario que la función sea dos veces derivable con respecto a todas sus variables, ya que está basada en la construcción y clasificación de la matriz Hessiana.

Dada una función f(x) dos veces diferenciable, se tiene:

• f(x) es convexa si y sólo si su matriz Hessiana Hf (x) es semidefinida positiva para cualquier x en su dominio.

• f(x) es cóncava si y sólo si su matriz Hessiana Hf (x) es semidefinida negativa para cualquier x en su dominio.

• Si su matriz Hessiana Hf (x) es definida positiva para cualquier x entonces f (x) es estrictamente convexa.

• Si su matriz Hessiana Hf (x) es definida negativa para cualquier x entonces f (x) es estrictamente cóncava.

Estas dos últimas propiedades enuncian condiciones suficientes pero no necesarias. Es decir, pueden existir funciones estrictamente convexas cuyo Hessiano no sea definido positivo sino únicamente semidefinido positivo.

En el caso de funciones de una variable, el análisis de su convexidad o concavidad se reduce al estudio del signo de su derivada segunda.

TEOREMA FUNDAMENTAL DE LA PROGRAMACIÓN CONVEXA

En los casos que se plantean normalmente en la práctica, lo deseado siempre es encontrar soluciones globales, es decir, la mejor en términos absolutos, muchas veces no basta con encontrar la mejor entre unas cuantas. Pero, desafortunadamente, la mayor parte de las técnicas de optimización (principalmente las que están basadas en la derivabilidad) están encaminadas a la búsqueda de óptimos locales. Por esa razón, son necesarios resultados que permitan reconocer cuándo los óptimos locales son también globales. El más importante de tales resultados es el conocido como teorema fundamental de la programación convexa.

Teorema (Teorema fundamental de la programación convexa)

Todo óptimo de un programa convexo es global.

Existencia y unicidad de soluciones

Antes de plantearse la resolución de un problema de Optimización, se puede analizar desde un punto de vista teórico si dicho problema tiene solución y, en caso afirmativo, si la solución es única.

Teorema de Weierstrass

Si la función objetivo f (x) es una función continua y la región factible CS es un conjunto compacto (cerrado y acotado), entonces el problema admite al menos un mínimo y un máximo globales.

Este teorema establece una condición suficiente para garantizar la existencia de óptimos, pero no es una condición necesaria, es decir, existen problemas que tienen óptimos y, sin embargo, no cumplen las hipótesis del Teorema de Weierstrass.

Salvado el problema de la existencia de solución, el siguiente aspecto a analizar es si dicha solución es única. El concepto de convexidad toma de nuevo especial importancia al permitir obtener un resultado que garantiza la unicidad de soluciones de un programa matemático.

Teorema (unicidad de solución para problemas estrictamente convexos)

En un problema estrictamente convexo el óptimo, en caso de existir, es único.

Un problema estrictamente convexo es aquel en el que se minimiza una función estrictamente convexa sobre un conjunto convexo, o se maximiza una función estrictamente cóncava sobre un conjunto convexo.

Cuando un problema no es estrictamente convexo, sino que es únicamente convexo, no se está en condiciones de asegurar que la solución sea única. Sin embargo, se cumple una interesante propiedad.

Teorema

En un problema convexo cualquier combinación lineal convexa de óptimos sigue siendo un óptimo.

Curvas de nivel de una función de dos variables

De la misma forma que una función de una variable tiene una representación gráfica mediante una curva en el plano, cuando la función tiene dos variables podría representarse mediante una superficie en el espacio tridimensional. Dicha superficie estaría formada por los puntos de la forma 

(X, Y, f (X, Y)). No obstante, existe una forma de representar gráficamente funciones de dos variables en el plano: mediante las conocidas como curvas de nivel de la función. Dichas curvas se obtienen al cortar la superficie mediante planos horizontales a distintas alturas, de forma que todos esos cortes forman una familia de curvas que se proyectan sobre el plano OXY. Las curvas de nivel surgen, por ejemplo, en cartografía cuando se representan las distintas altitudes de una montaña mediante un conjunto de curvas; de esta forma se hace una representación en el plano de la superficie tridimensional de la montaña. En meteorología, las isóbaras no son más que las curvas de nivel de la función que determina la presión atmosférica, es decir, son las curvas formadas por los puntos de igual presión atmosférica.

La siguiente figura muestra la representación gráfica de la función sen(X Y) mediante su superficie en el espacio y sus curvas de nivel en el plano.

Definición

Las curvas de nivel de la función f (X,Y) son la familia de curvas de la forma: f (X,Y) = k para cada valor de k en R. Ejemplo:

Este ejemplo muestra la construcción de la familia de curvas de nivel de la función

f (X,Y) = 3 X -Y.

Las curvas de nivel tienen la forma 3 X - Y = k o si se prefiere Y = 3 X - K, por tanto, son una familia de rectas paralelas como muestra la figura.

En el caso de funciones lineales, las curvas de nivel son siempre una familia de rectas paralelas.

El vector gradiente y las curvas de nivel

Dada una función de n variables, su vector gradiente es el vector formado por las n derivadas parciales primeras. A todo punto del plano se le puede asociar un vector gradiente evaluando las derivadas parciales en dicho punto, de esta forma se construye lo que se conoce como campo gradiente, que no es más que el conjunto de puntos del plano con sus respectivos vectores gradientes asociados.

El vector gradiente tiene dos importantes propiedades que le hacen muy útil en el método de resolución geométrica:

• Una primera propiedad es que en cada punto indica la dirección de crecimiento de la función.

• La segunda propiedad es que siempre en cada punto es ortogonal a las curvas de nivel. La

ortogonalidad en este caso significa que dicho vector forma un ángulo de 90 grados con las rectas tangentes de las curvas de nivel.

Estas propiedades pueden apreciarse en la siguiente figura, en la que junto a las curvas de nivel de la función f (X,Y) = sen (X Y) aparece el correspondiente campo gradiente. Los vectores gradientes asociados a cada punto no están representados en su verdadera escala, pero en este caso lo importante es su dirección y sentido.

Los ejemplos resueltos anteriormente, ponen de manifiesto una importante propiedad que relaciona los vectores gradientes de las restricciones y de la función objetivo:

El opuesto del vector gradiente de la función objetivo en el óptimo está dentro del cono generado por los vectores gradientes en el óptimo de las restricciones saturadas del problema, tal como muestra la figura de la derecha. Esto significa que dicho vector puede expresarse como combinación lineal con coeficientes positivos de los vectores gradientes de las restricciones saturadas.

Una restricción se dice saturada cuando en el óptimo se verifica en forma de igualdad y una restricción se dice no saturada cuando en el óptimo se verifica en forma de desigualdad estricta.

Deducción de propiedades de los programas lineales

Los ejemplos anteriores pueden dar pie al planteamiento de algunas de las principales características de los programas lineales, como son:

• En los programas lineales, los espacios de soluciones factibles son polítopos. Es además recomendable, en orden a garantizar la existencia de solución, que dicho espacio sea un conjunto acotado.

• Ya se ha comentado que todo programa lineal es un programa convexo, con lo cual, todo óptimo es global. Pero además, siempre se alcanza el óptimo, o los óptimos, en la frontera del espacio de soluciones factibles. Con la terminología ya conocida, esto significa que en los óptimos siempre alguna restricción está saturada.

• Pero se puede asegurar aún más, en todo programa lineal, si existe óptimo, éste se alcanza, al menos, en un vértice del polítopo que constituye la región admisible.

• No siempre hay unicidad de soluciones, pero al ser programas convexos, si en un programa lineal se alcanza el óptimo en dos puntos diferentes, también se alcanza en cualquier punto que sea combinación lineal convexa de esos dos puntos. Esta propiedad se generaliza para un mayor número de puntos, de forma que si varios puntos son óptimos del problema, también lo es cualquier combinación lineal convexa suya.

Clasificación de las matrices simétricas a partir de los autovalores

Esta clasificación de las matrices simétricas puede llevarse a cabo de una forma más operativa de acuerdo a los siguientes criterios:

Dada una matriz A, sus autovalores son las raíces de su polinomio característico, es decir, las soluciones de la ecuación.

Nota: Los autovalores de una matriz simétrica son siempre números reales.

Una vez calculados los autovalores de una matriz simétrica, se tiene:

• A es definida positiva si y sólo si los autovalores son todos estrictamente positivos.

• A es definida negativa si y sólo si los autovalores son todos estrictamente negativos.

• A es semidefinida positiva si y sólo si los autovalores son todos mayores o iguales a cero.

• A es semidefinida negativa si y sólo si los autovalores son todos menores o iguales a cero.

• A es indefinida si existen dos autovalores de diferentes signos.

Clasificación a partir  de los menores principales de la matriz

Teniendo  en cuenta  los  menores  principales de la matriz A, podemos llegar a las  conclusiones siguientes.

•     A es definida positiva sr y solo si todos los  menores principales son estrictamente  positivos.

•    A es definida  negativa  si  y solo  si los  menores  son todos ellos  no nulos y de signo alterno, siendo siempre  el primero negativo.

•          Si  todos  los  menores  son  estrictamente   positivos,  salvo el  último   que es nulo, entonces  la matriz A es semidifinida positiva.

•   Si  los  menores  son iodos  de no nulos, salvo el último,  y además   de signo alterno, siendo el primero negativo, entonces   la matriz A es semidefinida negativa.

El criterio de  los  menores  principales   para  la clasificación    de matrices  tiene  la  ventaja de  la comodidad  de los  cálculos, pero en contra  puede no decidir  el  tipo de la matriz en algunos  casos.

Convexidad  de conjuntos

Sea $M$  un subconjunto no vacío de ${R}^{n}$; diremos que:

• El subconjunto $M$  es convexo sí y solo si para cualquiera $\overline{X},\overline{Y}\varepsilon M\\$ y para todo $\lambda\epsilon [0,1]$ se verifica que:
 $\overline {Z} =\lambda \overline {X} +(1-\lambda )\overline {Y} \epsilon M$, es decir, el segmento $[\overline{X},\overline{Y}]=\{ \overline {Z}\epsilon {R}^{n}/\overline {Z} =\lambda \overline {X} +(1-\lambda )\overline {Y} ,\quad \lambda \epsilon [0,1]\}$  está contenido en M.

 • El subconjunto M es estrictamente convexo sí y solo sí es convexo y para cualquiera $\overline {X} ,\overline {Y} \epsilon M$, se tiene que el segmento abierto:
 $[\overline {X} ,\overline {Y}]=\{ \overline {Z} \epsilon {R}^{ n }/\overline {Z} =\lambda \overline {X} +(1-\lambda )\overline {Y} ,\lambda \epsilon (0,1)\}$ está contenido en el interior de M.

Concavidad de Funciones