Saltar al contenido
Volver a los resultados

Optimización Convexa

Propuesto por
Stephen Boyd & Lieven Vandenberghe
Año
2004
Tipo
Mathematical optimization framework
Familia
Mathematical programming

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

La optimización convexa es un subcampo de la optimización matemática que estudia el problema de minimizar funciones convexas sobre conjuntos convexos.

Formalizado y popularizado por Stephen Boyd y Lieven Vandenberghe en su influyente libro de texto de 2004, el marco unifica una amplia familia de problemas —incluyendo la programación lineal, la programación cuadrática, la programación semidefinida y la programación de cono de segundo orden— bajo un mismo techo teórico. Su propiedad definitoria es que cualquier solución óptima local es también globalmente óptima, lo que la hace tratable y fiable para la ingeniería, la estadística, el aprendizaje automático y la investigación operativa.

La intuición detrás del método

Imagine un valle en forma de cuenco: no importa dónde empiece a rodar una bola, siempre se asentará en el mismo punto más bajo. La optimización convexa formaliza esta geometría matemáticamente. La función objetivo es el cuenco, la región factible es un terreno de forma convexa y el algoritmo es la bola que sigue la pendiente. Debido a que no hay caídas locales ocultas o crestas engañosas, se garantiza encontrar el verdadero mínimo global, lo que hace que el enfoque sea fundamentalmente diferente y más fiable que la optimización no lineal general.

Historia

Los fundamentos teóricos del análisis convexo se remontan al trabajo de Minkowski y Farkas a principios del siglo XX, con la programación lineal emergiendo en la década de 1940 a través de Dantzig. Los métodos de punto interior, introducidos por Karmarkar en 1984 y refinados a lo largo de la década de 1990, hicieron que los programas convexos generales fueran computacionalmente tratables. El libro de texto de Boyd y Vandenberghe de 2004, publicado por Cambridge University Press y disponible gratuitamente en línea, sintetizó décadas de resultados en un marco coherente y accesible y dio origen al paradigma de programación convexa disciplinada implementado en CVX, CVXPY y herramientas relacionadas.

Cuándo usarlo

Utilice la optimización convexa cuando el objetivo y todas las restricciones puedan expresarse o reformularse como funciones convexas. Es apropiada para la optimización de carteras, la regresión con regularización, el flujo de red, las máquinas de vectores de soporte y el diseño de control. Los supuestos clave son la convexidad del conjunto factible y del objetivo; violar estos elimina la garantía de optimalidad global. Cuando el problema no es convexo, considere relajaciones convexas o solucionadores no lineales locales. Prefiera los solucionadores de programación lineal cuando el problema sea lineal para una eficiencia adicional.

Limitaciones y consideraciones

  • La aplicabilidad depende enteramente de si el problema puede plantearse o aproximarse en forma convexa; muchos problemas del mundo real son inherentemente no convexos.
  • Los métodos de punto interior almacenan y factorizan matrices grandes, lo que hace que los requisitos de memoria y tiempo sean sustanciales para problemas de muy alta dimensión.
  • Las relajaciones convexas de problemas combinatorios o enteros pueden producir soluciones fraccionarias que no son directamente accionables sin heurísticas de redondeo.
  • El modelado del problema requiere experiencia: una afirmación de convexidad incorrecta elimina silenciosamente las garantías teóricas mientras el solucionador aún devuelve una respuesta.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Garantiza una solución globalmente óptima siempre que se pueda lograr una formulación convexa, sin riesgo de convergencia a un mínimo local.
  • Resoluble en tiempo polinomial mediante métodos de punto interior, lo que proporciona eficiencia práctica incluso para problemas a gran escala.
  • La teoría de la dualidad produce certificados de optimalidad, variables duales con interpretaciones económicas y análisis de sensibilidad sin costo adicional.
  • Un rico conjunto de reglas de composición (DCP) permite la verificación sistemática de la convexidad y la transformación automática a una forma lista para el solucionador.

Aplicaciones

  • Optimización de carteras: minimización de la varianza o CVaR sujeta a objetivos de rendimiento y restricciones de asignación en finanzas cuantitativas.
  • Aprendizaje automático: el entrenamiento de máquinas de vectores de soporte, la regresión lasso y ridge, y la regresión logística son programas convexos canónicos.
  • Procesamiento de señales e imágenes: la detección comprimida, la eliminación de ruido por variación total y la recuperación dispersa se formulan como programas convexos.
  • Asignación de redes y recursos: enrutamiento óptimo, control de potencia en redes inalámbricas y asignación de ancho de banda bajo restricciones de capacidad.
  • Sistemas de control: síntesis de controladores H-infinito basada en programación semidefinida y verificación de estabilidad de Lyapunov.

Cómo funciona

Cómo funciona

1

El analista plantea el problema de decisión como un programa convexo en forma estándar: minimizar una función objetivo convexa f0(x) sujeta a restricciones de desigualdad convexas fi(x) ≤ 0 y restricciones de igualdad afines Ax = b. Acertar con la formulación —elegir la representación de variables adecuada y expresar todas las restricciones en forma convexa— es el primer paso crítico que determina si se aplican las potentes garantías.

Fórmula
\min_{x \in \mathcal{C}} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0,\; i=1,\ldots,m,\; Ax = b
2

Antes de resolver, se verifica que cada función del problema sea convexa, lo que significa que su epígrafe es un conjunto convexo o, equivalentemente, que satisface la desigualdad del punto medio. El conjunto de reglas de programación convexa disciplinada (DCP, por sus siglas en inglés) de Boyd y Vandenberghe proporciona una forma sistemática de confirmar la convexidad mediante reglas de composición, de modo que los analistas no necesitan probar la convexidad desde cero para cada problema.

Fórmula
f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y), \quad \forall x,y \in \text{dom}\,f,\; \theta \in [0,1]
3

El Lagrangiano L(x, λ, ν) se forma relajando las restricciones con multiplicadores duales. Bajo la condición de calificación de restricciones de Slater, se cumple la dualidad fuerte: los óptimos primal y dual coinciden y las condiciones KKT —estacionariedad, factibilidad primal/dual y holgura complementaria— son necesarias y suficientes para la optimalidad global. La dualidad también produce certificados de optimalidad e información de sensibilidad sobre cómo cambia el óptimo con los datos del problema.

Fórmula
L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \nu^T(Ax-b), \quad \lambda_i \geq 0
4

Los métodos de punto interior, las variantes de descenso de gradiente o los algoritmos proximales se mueven iterativamente a través del conjunto factible hacia el óptimo. Para problemas suaves no restringidos, los pasos de gradiente con tamaños de paso adecuados convergen a tasas conocidas. Para problemas restringidos o estructurados, los métodos de punto interior logran una convergencia en tiempo polinomial con alta precisión, y los métodos de primer orden como ADMM escalan a instancias muy grandes.

Fórmula
x^{(k+1)} = x^{(k)} - t_k \nabla f_0(x^{(k)}), \quad t_k > 0

Errores comunes

  • Asumir que un problema es convexo sin verificación formal; las reglas de composición deben comprobarse rigurosamente, no por inspección visual del objetivo.
  • Descuidar el condicionamiento numérico: los problemas mal escalados hacen que los solucionadores informen soluciones inexactas o inviables a pesar de la factibilidad teórica.
  • Ignorar las brechas de dualidad en solucionadores no estándar o en configuraciones donde la condición de Slater falla, lo que puede invalidar las afirmaciones de optimalidad basadas en KKT.
  • Tratar la solución de relajación convexa como la solución del problema original cuando se eliminaron restricciones enteras o combinatorias durante la reformulación.

Preguntas frecuentes

¿Cómo sé si mi problema es convexo?

Compruebe si la función objetivo y cada función de restricción satisfacen la desigualdad de convexidad del punto medio, o verifique la convexidad utilizando el conjunto de reglas de programación convexa disciplinada. Si cada función se construye a partir de primitivas convexas conocidas combinadas de acuerdo con reglas de composición que preservan la convexidad (función externa convexa no decreciente, funciones internas convexas, etc.), el problema es convexo. El Capítulo 3 de Boyd y Vandenberghe proporciona un extenso catálogo de funciones convexas.

¿Cuál es la diferencia entre la optimización convexa y la programación lineal?

La programación lineal es un caso especial de optimización convexa donde tanto el objetivo como todas las restricciones son funciones afines (lineales). La optimización convexa es mucho más general, abarcando programas cuadráticos, de cono de segundo orden y semidefinidos. Mientras que los métodos simplex y de punto interior resuelven programas lineales, solo los métodos de punto interior se extienden directamente a la clase convexa completa.

¿Puede la optimización convexa manejar variables enteras o binarias?

No directamente; las restricciones enteras hacen que un problema sea combinatoriamente difícil y generalmente no convexo. Un enfoque común es resolver la relajación convexa (eliminando la integralidad) para obtener una cota inferior, luego aplicar ramificación y acotación o redondeo. Los solucionadores de programación entera mixta convexa combinan estas ideas, pero la garantía de óptimo global de la optimización convexa pura ya no se aplica en plena generalidad.

Métodos relacionados

Fuentes

  1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.

    ISBN: 978-0-521-83378-3
    Copiado.