Repaso: Convexidad y Existencia de Solución

¿Qué es un conjunto convexo?

Un conjunto $C$ es convexo si, al tomar dos puntos cualesquiera de $C$, todo el segmento que los une queda dentro de $C$. No tiene "hoyos" ni "entrantes".

La expresión $\lambda x_1+(1-\lambda )x_2$ se llama combinación convexa de $x_1$ y $x_2$.

Ejemplos y una propiedad clave

Son convexos: los semiespacios $\{x:a^{T}x\le b\}$, las bolas $\{x:\Vert x\Vert \le r\}$, los poliedros (intersección de semiespacios) y todo ${\mathbb{R}}^n$.

Propiedad muy útil: la intersección de conjuntos convexos es convexa. Por eso un poliedro, al ser intersección de semiespacios (convexos), es convexo.

Ejemplo resuelto (Ayudantía 5)

Demostrar que la bola $B=\{x\in {\mathbb{R}}^n:\Vert x\Vert \le r\}$ es convexa. Tomamos $x_1,x_2\in B$ (es decir $\Vert x_1\Vert \le r$, $\Vert x_2\Vert \le r$) y $\lambda \in [0,1]$, y acotamos la norma de la combinación convexa usando desigualdad triangular y homogeneidad:

Como la combinación convexa también cumple $\Vert x\Vert \le r$, pertenece a $B$. Por lo tanto $B$ es convexo. $■$

Definición (desigualdad de Jensen)

Una función $f$ es convexa si, para todo par de puntos, la cuerda que une $(x,f(x))$ con $(y,f(y))$ queda por encima del gráfico de la función:

Si la desigualdad es estricta ($<$) para $x\ne y$ y $\lambda \in (0,1)$, se dice estrictamente convexa.

Dos lecturas equivalentes

• Geométrica: la cuerda nunca pasa por debajo de la curva (la función "se abre hacia arriba").
• Vía epígrafe: $f$ es convexa si y solo si su epígrafe $\{(x,t):t\ge f(x)\}$ es un conjunto convexo.

Cóncava

¿Cómo demostrar convexidad sin usar la definición?

Demostrar convexidad por la desigualdad de Jensen suele ser engorroso. Para funciones diferenciables hay criterios más rápidos.

Caso de una variable

Caso de varias variables: matriz Hessiana

Reglas de composición (atajos)

• Suma: suma de funciones convexas es convexa.
• Máximo: el máximo puntual de funciones convexas es convexo.
• Composición con afín: si $f$ es convexa y $g$ es lineal/afín, entonces $f(g(x))$ es convexa.

Ejemplo resuelto 1 — Composición (Ayudantía 5)

Si $f:{\mathbb{R}}^m\to \mathbb{R}$ es convexa y $g:{\mathbb{R}}^n\to {\mathbb{R}}^m$ es lineal, entonces $h(x)=f(g(x))$ es convexa. Como $g$ es lineal, $g(\lambda x+(1-\lambda )y)=\lambda g(x)+(1-\lambda )g(y)$; aplicando luego la convexidad de $f$:

Ejemplo resuelto 2 — Hessiana de log-sum-exp (Ayudantía 5)

¿Por qué nos importa tanto la convexidad?

Un problema convexo consiste en minimizar una función convexa sobre un dominio convexo (o maximizar una cóncava). Su importancia está en un teorema potentísimo:

Esto significa que no hay que preocuparse por quedar "atrapado" en un óptimo local: cualquier mínimo local que encuentres ya es la mejor solución posible.

Unicidad de la solución

Si además la función objetivo es estrictamente convexa sobre el dominio convexo, entonces la solución óptima (si existe) es única.

¿Existe al menos una solución óptima?

Antes de resolver, conviene saber si el problema tiene óptimo. Hay dos criterios principales.

1. Teorema de Bolzano-Weierstrass (vía compacidad)

Si se cumplen estas cuatro condiciones, el problema admite al menos una solución óptima:

• Continuidad: $f$ es continua (toda función lineal lo es).
• Cerrado: el dominio $D$ está definido por desigualdades no estrictas ($\le ,\ge ,=$).
• Acotado: las variables tienen cotas finitas.
• No vacío: existe al menos un punto factible.

2. Corolario para Programación Lineal

Un LP tiene solución si el dominio es no vacío y la función objetivo está acotada en la dirección de optimización. Una variante es la coercitividad: en un problema de maximización, si una variable sin cota superior aparece con coeficiente negativo (penalización), entonces $f\to -\infty$ cuando esa variable crece, lo que evita el no acotamiento.

Ejemplo resuelto (Ayudantía 5)

Para $\min 7x_1+4x_2-3x_3$ con $x_1+3x_2+9x_3\le 12$, $2x_2-5x_3\le 5$, $3x_1-x_2\le 8$, $x_1,x_2\ge 0$, $x_3\in \mathbb{R}$: la objetivo es lineal (continua); el dominio es cerrado; es no vacío porque $(0,0,0)$ es factible. Para el acotamiento, de las restricciones se acota $x_3$:

Con $x_3\in [-1,\frac{4}{3}]$ acotado, las restricciones (1) y (3) acotan a $x_1,x_2$ (que ya tienen cota inferior 0). El dominio es compacto ⇒ por Bolzano-Weierstrass, existe solución óptima. $■$