Convexidad

La idea

Un conjunto C es convexo si el segmento que une dos puntos cualesquiera de C queda íntegramente dentro de C: nada de agujeros ni entrantes. Una función f es convexa si su gráfica queda por debajo de cualquiera de sus cuerdas, es decir, si para todo λ ∈ [0, 1] se cumple f(λa + (1 − λ)b) ≤ λ f(a) + (1 − λ) f(b). Geométricamente, la función «abre hacia arriba»; el conjunto de puntos por encima de la gráfica (el epigrafo) es un conjunto convexo.

Para funciones derivables dos veces hay criterios cómodos: en una variable, f es convexa si f″(x) ≥ 0 en todo el dominio; en varias variables, si la matriz hessiana es semidefinida positiva (todos sus valores propios ≥ 0). También es convexa la función que queda siempre por encima de sus rectas tangentes: f(y) ≥ f(x) + f′(x)(y − x). Las operaciones habituales preservan la convexidad: sumas con coeficientes positivos, máximos de funciones convexas y composiciones con funciones afines.

La consecuencia práctica es enorme: en un problema convexo (minimizar una función convexa sobre un conjunto convexo) todo mínimo local es global y basta con encontrar un punto donde el gradiente se anule. Se acaban las trampas de los mínimos locales y existen algoritmos con garantías de convergencia. La desigualdad de Jensen generaliza la definición a promedios y esperanzas: f(E[X]) ≤ E[f(X)] para f convexa, resultado que explica, por ejemplo, por qué la media aritmética domina a la geométrica y por qué la diversificación reduce el riesgo. Distinguir si un modelo es convexo o no es la primera pregunta que se hace cualquier persona que optimiza.

Fórmulas clave

• Conjunto convexox, y ∈ C ⇒ λx + (1 − λ)y ∈ C ∀λ ∈ [0, 1]
• Función convexaf(λa + (1 − λ)b) ≤ λ f(a) + (1 − λ) f(b)
• Criterio de segunda derivadaf convexa ⇔ f″(x) ≥ 0 (una variable)
• Criterio hessianof convexa ⇔ H(f) semidefinida positiva
• Desigualdad tangentef(y) ≥ f(x) + f′(x)(y − x)
• Desigualdad de Jensenf(E[X]) ≤ E[f(X)]

Dónde se aplica

En finanzas, el modelo de Markowitz minimiza una varianza (función convexa cuadrática) sujeta a restricciones lineales: por eso se resuelve al instante y con solución única. En ingeniería eléctrica, el diseño de filtros y el control predictivo se reformulan como programas convexos para poder garantizar tiempos de respuesta. En estadística y aprendizaje automático, la regresión con penalización de norma (ridge, lasso) y la máquina de vectores soporte son convexas, lo que asegura que dos personas que ajusten el mismo modelo con los mismos datos obtendrán idéntico resultado, algo que no ocurre con las redes neuronales profundas.

Con programación (Python)

import math

def es_convexa(f, a, b, n=400):
    """Comprueba f'' >= 0 con diferencias centradas"""
    h = (b - a) / n
    peor = (0.0, None)
    for i in range(1, n):
        x = a + i * h
        segunda = (f(x - h) - 2 * f(x) + f(x + h)) / (h * h)
        if segunda < peor[0]:
            peor = (segunda, x)
    return peor[0] > -1e-4, peor

pruebas = [("x^2", lambda x: x * x),
           ("e^x", lambda x: math.exp(x)),
           ("|x|", lambda x: abs(x)),
           ("x^4 - 3x^2", lambda x: x ** 4 - 3 * x * x)]
for nombre, g in pruebas:
    ok, peor = es_convexa(g, -2, 2)
    print("%-12s convexa: %-5s   min f'' = %8.3f" % (nombre, str(ok), peor[0]))

# Prueba de la cuerda (Jensen) para la funcion no convexa
h = lambda x: x ** 4 - 3 * x * x
a, b = -1.5, 1.5
for lam in (0.25, 0.5, 0.75):
    izq = h(lam * a + (1 - lam) * b)
    der = lam * h(a) + (1 - lam) * h(b)
    print("lambda = %.2f   f(mezcla) = %7.4f   cuerda = %7.4f   cumple: %s" % (lam, izq, der, izq <= der))

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Máximos, mínimos y optimización · Programación lineal · Descenso del gradiente