Convexidad y por qué importa

Matemática · Lección 15

L2 Derivación Fase F1 Libro MML §7.3 Prereqs Hessiana y Taylor · Formas cuadráticas

Objetivo

Al terminar esta lección se puede:

  1. Definir conjunto convexo y función convexa, y reconocer cuál de las dos condiciones falla en un caso concreto.
  2. Demostrar la caracterización de primer orden: una función convexa diferenciable queda por encima de todos sus planos tangentes.
  3. Demostrar la caracterización de segundo orden: convexidad equivale a que la hessiana sea semidefinida positiva en todo punto.
  4. Demostrar que en una función convexa todo mínimo local es global, y que si es estrictamente convexa el minimizador es único.

De dónde viene

  • Matemática 14: la hessiana y el desarrollo de Taylor con resto. La caracterización de segundo orden es ese desarrollo leído al revés.
  • Matemática 12: el criterio espectral. «Hessiana semidefinida positiva» quiere decir que todos sus eigenvalores son mayores o iguales que cero.
  • Matemática 13: la derivada direccional como límite del cociente de incrementos, que es lo que hace pasar de la desigualdad de la cuerda a la del plano tangente.

Para qué sirve después

  • Matemática 16 y 17: el descenso de gradiente y el método de Newton encuentran mínimos locales. La Proposición 15.5 es lo que convierte ese resultado en la respuesta buscada.
  • Matemática 18: la teoría de multiplicadores de Lagrange y las condiciones KKT se vuelven suficientes, y no solo necesarias, cuando el problema es convexo.
  • Estadística 8 y 13: la log-verosimilitud de la normal y la suma de cuadrados de la regresión son cóncava y convexa respectivamente, y por eso sus puntos críticos son el óptimo y no un óptimo cualquiera.

Notación

Símbolo Se lee Significado
C ce Un conjunto convexo, dominio de f
t te El peso de la combinación, t\in[0,1]
tx+(1-t)y combinación convexa Un punto del segmento entre x e y
H_f(x)\succeq0 hache semidefinida positiva v^\top H_f(x)v\ge0 para todo v
\nabla f(x)\cdot(y-x) — El término lineal del plano tangente en x, evaluado en y
x^\star equis estrella Un minimizador de f

1. Las dos definiciones

Definición 15.1 (conjunto convexo). Un conjunto C\subseteq\mathbb{R}^n es convexo si para todos x,y\in C y todo t\in[0,1] se cumple tx+(1-t)y\in C: el segmento que une dos puntos del conjunto se queda dentro.

Definición 15.2 (función convexa). Una función f definida en un conjunto convexo C es convexa si para todos x,y\in C y todo t\in[0,1], f\big(tx+(1-t)y\big) \;\le\; t\,f(x) + (1-t)\,f(y). Es estrictamente convexa si la desigualdad es estricta siempre que x\ne y y t\in(0,1). Y es cóncava si -f es convexa.

La desigualdad dice que la gráfica queda por debajo de cualquiera de sus cuerdas: el lado izquierdo es la función en un punto del segmento y el derecho es la cuerda sobre ese mismo punto. Sin derivadas de por medio, la definición se puede comprobar sorteando pares de puntos.

Veinte mil pares no demuestran nada, pero uno solo sí refuta: los 2712 casos de la segunda función bastan para descartarla. La convexidad se demuestra con las proposiciones que siguen; se refuta con un contraejemplo.

2. La función queda por encima de sus tangentes

Proposición 15.3 (caracterización de primer orden). Sea f diferenciable en un conjunto convexo abierto C. Entonces f es convexa si y solo si f(y) \;\ge\; f(x) + \nabla f(x)\cdot(y-x) \qquad\text{para todos } x,y\in C.

Demostración. (\Rightarrow) Sea f convexa y t\in(0,1]. Escribiendo x+t(y-x) = (1-t)x+ty, la Definición 15.2 da f\big(x+t(y-x)\big) \le (1-t)f(x)+t\,f(y), y restando f(x) y dividiendo entre t>0, \frac{f\big(x+t(y-x)\big)-f(x)}{t} \;\le\; f(y)-f(x). El lado izquierdo es el cociente de incrementos en la dirección v=y-x. El mismo cálculo de la Proposición 13.8 —tomando allí h=tv— muestra que tiende a \nabla f(x)\cdot v cuando t\to0^+, sin que haga falta que v sea unitario. Pasando al límite, \nabla f(x)\cdot(y-x) \le f(y)-f(x), que es la desigualdad buscada.

(\Leftarrow) Supóngase la desigualdad para todos los pares, y sean x,y\in C, t\in[0,1] y z=tx+(1-t)y, que está en C por la Definición 15.1. Aplicándola dos veces desde z, f(x)\ge f(z)+\nabla f(z)\cdot(x-z), \qquad f(y)\ge f(z)+\nabla f(z)\cdot(y-z). Multiplicando la primera por t\ge0, la segunda por 1-t\ge0 y sumando, t\,f(x)+(1-t)f(y) \;\ge\; f(z) + \nabla f(z)\cdot\big[t(x-z)+(1-t)(y-z)\big]. El corchete vale tx+(1-t)y-z = 0 por la definición de z, así que el término lineal desaparece y queda t\,f(x)+(1-t)f(y)\ge f(z), que es la Definición 15.2. ∎

Esa equivalencia es la que hace útil la convexidad: el plano tangente deja de ser una aproximación local y pasa a ser una cota inferior válida en todo el dominio. Sabiendo el valor y el gradiente en un punto, se sabe algo cierto sobre todos los demás.

3. El criterio que se puede calcular

Proposición 15.4 (caracterización de segundo orden). Sea f con segundas parciales continuas en un conjunto convexo abierto C. Entonces f es convexa si y solo si H_f(x) es semidefinida positiva para todo x\in C.

Demostración. La demostración de la Proposición 14.5 da, para x,y\in C y algún \xi del segmento que los une —que está en C porque C es convexo—, f(y) = f(x) + \nabla f(x)\cdot(y-x) + \tfrac12\,(y-x)^\top H_f(\xi)\,(y-x). \tag{$\dagger$}

(\Leftarrow) Si toda hessiana es semidefinida positiva, el último término de (\dagger) es mayor o igual que cero, luego f(y)\ge f(x)+\nabla f(x)\cdot(y-x) para todos x,y, y la Proposición 15.3 da la convexidad.

(\Rightarrow) Por contrarrecíproco. Supóngase que existen x_0\in C y v con v^\top H_f(x_0)v<0. Como las segundas parciales son continuas, la función \xi\mapsto v^\top H_f(\xi)v también lo es, así que sigue siendo negativa en toda una bola alrededor de x_0. Tomando y=x_0+tv con t>0 lo bastante pequeño para que el segmento entero quede en esa bola, (\dagger) da f(y) = f(x_0) + \nabla f(x_0)\cdot(y-x_0) + \tfrac{t^2}{2}\,v^\top H_f(\xi)\,v \;<\; f(x_0)+\nabla f(x_0)\cdot(y-x_0), que contradice la Proposición 15.3. Luego f no es convexa. ∎

Por el criterio espectral de la Proposición 12.4, «semidefinida positiva» quiere decir que el menor eigenvalor no es negativo. Eso convierte la convexidad en algo que una máquina puede comprobar punto por punto.

En la primera función el menor eigenvalor vale 2 en todo punto —la hessiana es \operatorname{diag}(e^x+2,\,2)— y nunca baja de ahí. En la segunda, 1709 de los 4000 puntos tienen un eigenvalor negativo, y uno solo ya habría bastado.

4. Por qué importa

Proposición 15.5 (todo mínimo local es global). Sea f convexa en un conjunto convexo C. Si a\in C es un mínimo local de f, entonces f(a)\le f(y) para todo y\in C.

Demostración. Sea y\in C cualquiera y t\in(0,1]. El punto (1-t)a+ty está en C y, cuando t\to0^+, tiende a a; así que para t suficientemente pequeño cae dentro del entorno donde a es mínimo local, y por tanto f(a) \;\le\; f\big((1-t)a+ty\big). Acotando el lado derecho con la Definición 15.2, f(a) \;\le\; (1-t)f(a) + t\,f(y). Restando (1-t)f(a) queda t\,f(a)\le t\,f(y), y dividiendo entre t>0, f(a)\le f(y). Como y era arbitrario, a es mínimo global. ∎

La demostración no usa derivadas en ningún paso: la convexidad sola ya prohíbe que exista un valle separado del fondo verdadero. Esa es la razón de fondo por la que se persigue la convexidad al plantear un problema.

Proposición 15.6 (unicidad del minimizador). Si f es estrictamente convexa en C convexo, entonces tiene a lo sumo un minimizador.

Demostración. Supóngase que a\ne b son dos minimizadores, con f(a)=f(b)=m. El punto medio \tfrac12a+\tfrac12b está en C, y por convexidad estricta —con t=\tfrac12 y a\ne b—, f\big(\tfrac12a+\tfrac12b\big) \;<\; \tfrac12 f(a)+\tfrac12 f(b) = m, lo que contradice que m sea el valor mínimo. Luego no puede haber dos. ∎

Cuarenta puntos de partida al azar y un solo destino en la función convexa; dos destinos distintos en la que no lo es. Eso es la Proposición 15.5 en la práctica: con convexidad, dónde se empiece a buscar deja de importar.

Ejercicios

Ejercicio 1 — Qué operaciones conservan la convexidad

Demostrar, directamente desde la Definición 15.2, que si f y g son convexas entonces también lo son f+g, \alpha f con \alpha\ge0, y \max\{f,g\}. Comprobar con un contraejemplo que el producto fg no la conserva.

Ejercicio 2 — La suma de cuadrados es convexa

Demostrar que S(b)=\|y-Xb\|^2 es convexa en b calculando su hessiana, y que es estrictamente convexa si y solo si X tiene rango columna completo. Relacionarlo con la unicidad de la solución de mínimos cuadrados de la lección 6.

Sin rango completo la función sigue siendo convexa —la hessiana no deja de ser semidefinida positiva—, pero pierde la convexidad estricta, y con ella la unicidad: hay una dirección entera en la que S no cambia, que es exactamente el núcleo de X.

Reto

En proyectos/notebooks/F1-retos.ipynb, sección Mat 15:

  1. Escribir es_convexa(f, grad, hess, caja, n=5000) que muestree la caja y devuelva el menor eigenvalor hallado junto con el punto donde ocurre. Probarla con cinco funciones de convexidad conocida y anotar cuántas muestras hicieron falta para encontrar el punto malo en la que menos lo enseña.
  2. Comprobar la Proposición 15.3 en la práctica: para una función convexa, tomar el plano tangente en un punto y verificar que acota por debajo a la función en toda una rejilla, no solo cerca. Repetirlo con una no convexa y medir a qué distancia empieza a fallar la cota.
  3. Demostrar que la composición g(f(x)) con f convexa y g convexa creciente es convexa, y construir un contraejemplo donde g sea convexa pero decreciente. Anotarlo en 50-Errores/.

Del libro

Mathematics for Machine Learning dedica §7.3 Convex Optimization a este material, dentro del capítulo 7 sobre optimización continua. El libro tiene copyright y no es descargable desde el entorno en que se escribió esta página, así que se cita número y título y no se le atribuye ninguna frase.

Preguntas para leer §7.3 con lápiz:

  1. La sección trata problemas de optimización convexa, donde tanto la función objetivo como el conjunto factible son convexos. Con la Definición 15.1 y la Proposición 15.5, ¿por qué hacen falta las dos condiciones, y qué puede salir mal si el conjunto factible no es convexo aunque la función sí lo sea?
  2. §7.3 llega a la dualidad y al problema dual. Antes de leerla: con la Proposición 15.3, ¿por qué el plano tangente en cualquier punto da una cota inferior del mínimo global, y en qué se parece eso a una función dual?
  3. La programación lineal es el caso donde la función y las restricciones son afines. ¿Qué dice la Proposición 15.4 sobre la hessiana de una función afín, y por qué entonces toda función afín es a la vez convexa y cóncava?

Para el Cerebro

Nota nueva en 10-Conceptos/convexidad.md, enlazada a [[hessiana]], [[descenso-de-gradiente]] y [[minimos-cuadrados]]. Conviene rehacer a mano la Proposición 15.5: son cuatro líneas, no usa derivadas, y es la razón por la que toda esta lección existe.

¿Qué es un conjunto convexo?::Uno donde el segmento entre dos puntos cualesquiera se queda dentro
¿Qué es una función convexa?::f(tx+(1−t)y) ≤ t f(x) + (1−t) f(y): la gráfica queda bajo sus cuerdas
¿Qué dice la caracterización de primer orden?::f(y) ≥ f(x) + ∇f(x)·(y−x): la función queda por encima de sus tangentes
¿Para qué sirve esa desigualdad?::El plano tangente pasa de aproximación local a cota inferior válida en todo el dominio
¿Cuál es el criterio de segundo orden?::Convexa ⟺ hessiana semidefinida positiva en todo punto
¿Cómo se comprueba ese criterio?::Mirando que el menor eigenvalor de la hessiana no sea negativo (Prop 12.4)
¿Qué gana uno con la convexidad?::Todo mínimo local es global (Proposición 15.5)
¿Esa demostración usa derivadas?::No: sale solo de la desigualdad de la definición, en cuatro líneas
¿Cuándo es único el minimizador?::Cuando la función es estrictamente convexa
¿Qué operaciones conservan la convexidad?::Suma, producto por escalar no negativo, y máximo; el producto no
¿Es convexa la suma de cuadrados ‖y−Xb‖²?::Sí, con hessiana 2XᵀX; estrictamente si X tiene rango columna completo

Fuentes

Lo que esta página demuestra sola. Las Proposiciones 15.3, 15.4, 15.5 y 15.6 se demuestran aquí a partir de las Definiciones 15.1 y 15.2 y del desarrollo de Taylor de la lección 14. Se comprueban además numéricamente: la desigualdad de la Definición 15.2 en 20 000 pares sorteados, con cero violaciones en la función convexa y 2712 en la que no lo es; el menor eigenvalor de la hessiana sobre 4000 puntos, constante en 2 en un caso y negativo en 1709 puntos en el otro; y que 40 descensos desde arranques al azar llegan a un solo destino en la convexa y a dos en la otra. Los dos visuales se contrastaron antes de publicarse contra las fórmulas en todo el rango de sus controles.

Lo que se usa de otras lecciones sin repetir. El desarrollo de Taylor con resto de Lagrange, en la forma (\dagger), es la demostración de la Proposición 14.5. Que el cociente de incrementos tiende a \nabla f(x)\cdot v también para v no unitario es el cálculo de la Proposición 13.8. El criterio espectral que traduce «semidefinida positiva» a «ningún eigenvalor negativo» es la Proposición 12.4.

Lo que se enuncia sin demostrar. En la Proposición 15.4, dirección (\Rightarrow), se usa que si una función continua es negativa en un punto lo sigue siendo en un entorno; es la definición de continuidad aplicada con \varepsilon igual a la mitad del valor, y no se detalla. El Ejercicio 1 pide la demostración de que suma, escalado no negativo y máximo conservan la convexidad, que no se hace en el cuerpo de la lección.

Lo que viene de los libros.

  • Mathematics for Machine Learning (Deisenroth, Faisal & Ong, Cambridge University Press, 2020), §7.3 Convex Optimization — citada por número y título, sin transcribir texto.

Lo que es mío, no del libro. La organización en tres caracterizaciones equivalentes —cuerda, tangente y hessiana— con la demostración de ida y vuelta de cada una, y el orden que deja la Proposición 15.5 al final como la razón de todo lo anterior. El segundo visual, que muestra doce descensos simultáneos con un control de pasos en lugar de un solo camino: el reparto en dos destinos solo se ve cuando se miran varios a la vez.

Índices verificados el 12-09-2026 contra el índice publicado del PDF oficial.

→ Siguiente: Descenso de gradiente y sus variantes