🤖 machine learning

Input convex neural networks as surrogates in mathematical optimisation

Este artículo aboga por el uso de redes neuronales de entrada convexa (ICNN) como sustitutos en la optimización matemática, demostrando que su arquitectura convexa permite relajaciones más ajustadas y algoritmos de rama y cota más eficientes en comparación con las redes de alimentación hacia adelante tradicionales, mejorando así los tiempos de resolución y la escalabilidad para problemas con respuestas subyacentes convexas o cóncavas.

Autores originales: Yu Liu, Jan Kronqvist, Fabricio Oliveira

Publicado 2026-08-11

📖 8 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Yu Liu, Jan Kronqvist, Fabricio Oliveira

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando resolver un rompecabezas masivo y complicado, como planificar la ruta más eficiente para un camión de reparto o mezclar el lote perfecto de vino. A menudo, las reglas del juego están ocultas dentro de una "caja negra" —un programa informático complejo (una red neuronal)— que ha aprendido cómo funciona el mundo observando millones de ejemplos. Sabes qué entra y qué sale, pero no conoces la matemática secreta en su interior. Para encontrar la mejor solución posible, necesitas abrir esa caja negra e integrarla en tu rompecabezas. El problema es que el tipo más común de caja negra es un laberinto dentado y zigzagueante. Intentar encontrar el camino perfecto a través de él es como intentar resolver un cubo de Rubik con los ojos vendados; es tan difícil que las computadoras a menudo se rinden antes de encontrar la respuesta.

Este artículo aborda exactamente ese dolor de cabeza. Introduce un tipo especial de caja negra llamada Red Neuronal de Convexidad de Entrada (ICNN, por sus siglas en inglés). Piensa en esto no como un laberinto dentado, sino como un tobogán suave con forma de cuenco. Debido a que su forma es tan predecible (solo curva en una dirección), las computadoras pueden deslizarse directamente hasta el fondo sin quedarse atascadas. Los autores demuestran que, al usar estos toboganes suaves en lugar de laberintos dentados, podemos resolver estos rompecabezas de optimización mucho más rápido y con mucha menos potencia de cálculo. No solo supusieron que esto funcionaría; construyeron una nueva herramienta matemática para probarlo y lo probaron en problemas del mundo real, como la entrega de ayuda alimentaria o la perforación de pozos de petróleo, encontrando que su método es a menudo mil veces más rápido que el método antiguo.

El Problema: El Laberinto Dentado vs. El Tobogán Suave

En el mundo de la investigación operativa (la ciencia de tomar las mejores decisiones), a menudo utilizamos redes neuronales para actuar como sustitutos. Un sustituto es como un actor de repuesto; imita un proceso complejo y costoso de calcular para que podamos tomar decisiones rápidamente. Durante años, el sustituto estándar ha sido una Red Neuronal de Propagación hacia Adelante (FNN). Imagina una FNN como un paisaje hecho de miles de pequeños escalones y acantilados. Es increíblemente precisa para predecir resultados, pero debido a que es tan dentada, es una pesadilla de optimizar. Para encontrar la mejor solución, las computadoras tienen que convertir el problema en una lista gigante de preguntas de "sí o no" (variables binarias), lo que crea una explosión combinatoria. Es como intentar encontrar el punto más bajo en una cadena montañosa revisando cada roca individualmente; a medida que la red se hace más grande, el tiempo que toma crece tan rápido que la computadora se queda sin tiempo.

Los autores argumentan que, si el proceso del mundo real que estamos modelando es naturalmente suave y curvo (como un cuenco o una colina), no deberíamos forzar a una FNN dentada a hacer el trabajo. En su lugar, deberíamos usar una Red Neuronal de Convexidad de Entrada (ICNN). Una ICNN es una red neuronal con una regla estricta: solo se le permite curvarse en una dirección. Es como un tobogán suave o un cuenco perfecto. Esta restricción estructural hace que la matemática sea mucho más fácil de manejar.

El Descubrimiento: Dos Formas de Ganar

El artículo explora dos formas principales de usar estas ICNNs suaves para resolver problemas de optimización, y descubrieron que ambas son superiores a los métodos antiguos.

1. El "Apretón Más Ajustado" (ICNN-MIP)
Primero, los autores analizaron qué sucede si todavía usamos el método estándar de "sí o no" (Programación Entera Mixta, o MIP) pero sustituimos la FNN dentada por una ICNN suave. Demostraron matemáticamente que la "relajación" (una versión simplificada del problema utilizada para adivinar la respuesta) para una ICNN es increíblemente ajustada.

La Analogía: Imagina intentar adivinar el peso de una sandía. El método FNN te da una caja enorme y holgada; la sandía podría estar en cualquier lugar dentro de ella. El método ICNN te da una caja que abraza la sandía perfectamente.
El Resultado: Debido a que la caja de la ICNN es tan ajustada, la computadora no necesita revisar casi tantas posibilidades. En sus pruebas, la versión ICNN resolvió problemas en una fracción de segundo que la versión FNN no pudo resolver incluso después de una hora. En algunos casos, el método ICNN encontró la respuesta perfecta de inmediato sin necesidad de ramificarse en absoluto, mientras que el método FSS se perdió en millones de callejones sin salida.

2. El "Tobogán Resbaladizo" (ICNN-BB)
Segundo, y quizás más emocionante, desarrollaron un algoritmo completamente nuevo llamado ICNN-BB. Este método desecha por completo las preguntas de "sí o no". Debido a que la ICNN es suave y convexa, los autores se dieron cuenta de que podían describir toda la red utilizando solo ecuaciones lineales simples (como una línea recta) sin necesidad de variables binarias.

La Analogía: En lugar de escalar una montaña dentada con una cuerda y ganchos de escalada (variables binarias), simplemente te deslizas por un tobogán suave y sin fricción.
La Trampa: Este tobogán funciona perfectamente si el problema está configurado de una manera específica (minimizar la salida). Si el problema es más complejo, el tobogán podría tener un pequeño espacio donde no es perfectamente ajustado. Para solucionar esto, los autores construyeron una "envolvente cóncava" —una red de seguridad que se asienta sobre el tobogán para atrapar cualquier extremo suelto. Combinaron el tobogán (epígrafo) y la red de seguridad (envolvente cóncava) para crear la descripción matemática más fuerte de la red.
El Resultado: Su nuevo algoritmo, ICNN-BB, realiza la ramificación directamente sobre las variables de entrada (las cosas que estás tratando de decidir) en lugar de las neuronas internas. Esto es una ganancia de eficiencia enorme. En sus pruebas, este método fue a menudo el más rápido, especialmente cuando el problema no era demasiado complejo.

Las Pruebas del Mundo Real

Para demostrar que esto no era solo matemática en papel, los autores probaron sus ideas en tres escenarios muy diferentes del mundo real:

Ayuda Alimentaria Humanitaria: Modelaron un sistema para entregar alimentos a personas necesitadas, tratando de minimizar el costo mientras se cumplen los requisitos nutricionales y de sabor. La parte del "sabor" era la caja negra.
- El Resultado: Los métodos ICNN fueron increíblemente rápidos. El método FNN estándar falló estrepitosamente, tardando más de una hora y no logrando encontrar una solución para redes más grandes. Los métodos ICNN resolvieron los mismos problemas en menos de un segundo. Mejor aún, el método ICNN-BB fue tan preciso que se detuvo inmediatamente en el primer paso, demostrando que el "tobogán" era perfecto para este problema.
Ruteo de Pozos de Petróleo: Esto implicaba decidir cómo rutar el petróleo desde los pozos hasta las instalaciones de procesamiento, un problema lleno de física complicada y elecciones binarias (abrir o cerrar una tubería).
- El Resultado: Aquí, los métodos ICNN también ganaron, pero la carrera estuvo más reñida. El método ICNN-MIP resolvió problemas que la FNN no podía tocar. El método ICCN-BB fue el más rápido en las versiones pequeñas, pero se ralentizó en las más grandes porque la "red de seguridad" (la envolvente cóncava) se volvió demasiado complicada de calcular cuando había demasiadas variables. Esto mostró un límite claro: ICNN-BB es asombroso para complejidad baja a media, pero la "red de seguridad" se vuelve pesada si el problema es demasiado grande.
Mezcla de Vinos: Un vinicultor intentando mezclar uvas de diferentes proveedores para crear el mejor vino al menor costo.
- El Resultado: Similar al problema del petróleo, los métodos ICNN fueron significativamente más rápidos y confiables que el método FNN. El método ICNN-BB fue el campeón para lotes pequeños, pero a medida que aumentaba el número de mezclas, el costo computacional de la "red de seguridad" crecía, haciendo que el método ICNN-MIP estándar fuera una mejor opción eventualmente.

La Conclusión

El artículo concluye que las Redes Neuronales de Convexidad de Entrada son la nueva opción predeterminada para problemas de optimización donde la relación subyacente es suave o curva. Ofrecen una ventaja de "dos niveles":

Si las usas con los solucionadores estándar (ICNN-MIP), obtienes una búsqueda mucho más ajustada y eficiente que antes.
Si las usas con su nuevo algoritmo especializado (ICNN-BB), a menudo puedes resolver el problema sin ninguna variable binaria, lo que genera aceleraciones masivas.

Sin embargo, los autores advierten que esto no es una solución mágica para todo. El método ICNN-BB encuentra un muro cuando el número de variables de entrada es demasiado alto (como en la prueba de mezcla de vinos con 55 dimensiones), porque calcular la "red de seguridad" se vuelve demasiado costoso. Pero para una vasta gama de problemas, este enfoque convierte una pesadilla computacionalmente imposible en un deslizamiento rápido y suave. Los autores sugieren que en el futuro podríamos ver formas aún más inteligentes de construir estas redes de seguridad o de mezclar redes convexas y no convexas para obtener lo mejor de ambos mundos.

Resumen Técnico: Redes Neuronales de Convexidad de Entrada como Sustitutos en la Optimización Matemática

Planteamiento del Problema

La incorporación de redes neuronales (NN) entrenadas como sustitutos dentro de problemas de optimización matemática es una práctica estándar en la investigación operativa, particularmente cuando los modelos físicos subyacentes son inaccesibles o computacionalmente prohibitivos. El enfoque predominante utiliza Redes Neuronales de Propagación hacia Adelante (FNN) con activaciones de Unidad Lineal Rectificada (ReLU). Aunque las FNN ofrecen capacidades de aproximación universal, su estructura lineal por tramos requiere una reformulación de Programación Entera Mixta (MIP) exacta para la optimización global. Esta reformulación introduce una variable binaria por cada unidad ReLU, lo que genera una carga computacional que escala linealmente con el tamaño de la red. Además, la relajación de Programación Lineal (LP) continua de las formulaciones FNN-MIP estándar suele ser débil, lo que resulta en árboles de búsqueda extensos y una escalabilidad deficiente para redes más grandes.

Este artículo investiga las Redes Neuronales de Convexidad de Entrada (ICNN) como una arquitectura sustituta alternativa. Las ICNN están restringidas a producir salidas que son convexas con respecto a sus entradas. Los autores abordan dos brechas principales en la literatura:

La falta de un análisis riguroso sobre la validez de la incrustación de epígrafo basada en LP para las ICNN en entornos de optimización general (más allá de la minimización directa).
La ausencia de un análisis comparativo de la densidad de las relajaciones LP entre las formulaciones ICNN-MIP y las formulaciones FNN-MIP estándar.

Metodología

1. Análisis Estructural de ICNN-MIP

Los autores primero derivan una formulación MIP para las ICNN (ICNN-MIP) análoga a las FNN-MIP estándar, pero incorporando las restricciones arquitectónicas específicas de las ICNN (pesos no negativos para las capas ocultas y funciones de activación convexas y no decrecientes).

Exactitud de la Relajación: Demuestran que, para cualquier entrada fija, la relajación LP de la formulación ICNN-MIP recupera la salida exacta de la red. En consecuencia, cuando el problema de optimización implica la minimización directa de la salida de la ICNN, la relajación LP es exacta (brecha de integrabilidad cero).
Comparación con FNN: En contraste, las relajaciones FNN-MIP estándar pueden subestimar la salida de la red debido a los signos de los pesos sin restricciones, lo que conduce a una brecha de integridad no nula. Los autores demuestran que las propiedades estructurales de las ICNN producen inherentemente relajaciones LP más densas que sus contrapartes FNN, incluso en escenarios de incrustación general donde la salida no se minimiza directamente.

2. Incrustación de Epígrafo y Validez

El artículo formaliza las condiciones bajo las cuales la incrustación de epígrafo (una reformulación basada en LP que reemplaza las unidades ReLU con desigualdades lineales $y \geq \hat{f}(x)$ ) constituye una reformulación válida del problema original.

Definición de Validez: La incrustación es válida si la solución óptima satisface la restricción de igualdad $y = \hat{f}(x)$ y produce el mismo valor de objetivo que el problema original.
Limitación: La incembedación de epígrafo solo es exacta cuando la estructura del problema penaliza la sobreestimación de la salida del sustituto (por ejemplo, la minimización directa). En casos generales donde la salida del sustituto aparece en restricciones o términos que recompensan valores mayores, la relajación del epígrafo puede admitir soluciones donde $y > \hat{f}(x)$ , lo que la convierte en una reformulación inválida.

3. Relajación Continua Más Fuerte (Envolvente Convexa)

Para abordar los casos donde la incrustación de epígrafo no es válida, los autores construyen la relajación continua más fuerte de la gráfica de la ICNN sobre un dominio de caja.

Envolvente Cóncava: Derivan una envolvente cóncava de la salida de la ICNN mediante el cálculo de combinaciones convexas de los valores de la red en los vértices de la caja de entrada.
Construcción de la Envolvente Convexa: Al combinar el epígrafo (límite inferior) y la envolvente cóncava (límite superior), demuestran que la región factible resultante es exactamente la envolvente convexa de la gráfica de la ICNN. Esta construcción es tratable para las ICNN (requiere $2^n$ evaluaciones de vértices donde $n$ es la dimensión de la entrada) pero es generalmente intratable para las FNN no convexas.

4. Algoritmo ICNN-BB

Basado en la relajación de la envolvente convexa, los autores desarrollan un algoritmo especializado de rama y poda, ICNN-BB:

Estrategia de Ramificación: A diferencia de los enfoques MIP que ramifican sobre variables de activación binarias intermedias, ICNN-BB ramifica directamente sobre las variables de entrada.
Procedimiento: El algoritmo comienza con la incrustación de epígrafo en el nodo raíz. Si la solución no es exacta (la brecha excede la tolerancia), se ramifica sobre la variable de entrada con el intervalo más amplio, estrechando el dominio de la caja y reevaluando la envolvente cóncava en los nuevos vértices.
Terminación: El algoritmo termina en el nodo raíz si la incrustación de epígrafo es válida; de lo contrario, converge al óptimo global a medida que los dominios de las cajas se reducen y la envolvente se estrecha.

Contribuciones Clave

Caracterización Estructural: Demostraron que la relajación LP de las formulaciones ICNN-MIP tiene una brecha de integrabilidad cero para entradas fijas y minimización directa de la salida, ofreciendo una ventaja teórica sobre FNN-MIP.
Condiciones de Validez Formal: Definieron condiciones precisas bajo las cuales la incrustación de epígrafo por LP es una reformulación válida, identificando escenarios en los que falla (por ejemplo, cuando no se penaliza la sobreestimación).
Construcción de la Envolvente Convexa: Demostraron que la envolvente convexa de la gráfica de una ICNN sobre un dominio de caja puede construirse explícitamente mediante la intersección del epígrafo y una envolvente cóncava basada en vértices, una propiedad no disponible para las redes ReLU generales.
Algoritmo Especializado: Desarrollaron ICCN-BB, un método de rama y poda basado en LP que evita las variables binarias por completo, ramificando sobre las entradas y explotando la relajación de la envolvente convexa para la convergencia.
Validación Empírica: Validaron el enfoque a través de tres casos de estudio distintos (ayuda alimentaria humanitaria, rutas de pozos petroleros y mezcla de vinos), comparando ICNN-BB, ICNN-MIP y FNN-MIP.

Resultados Experimentales

Caso 1: Ayuda Alimentaria Humanitaria

Configuración: Optimización de la adquisición de cestas de alimentos con un sustituto de palatabilidad.
Hallazgos: Las ICNN igualaron la precisión de las FNN. FNN-MIP falló al resolver instancias más grandes dentro del límite de tiempo debido a relajaciones débiles. ICNN-MIP resolvió todas las instancias en el nodo raíz (cero ramificación) tanto para HiGHS como para Gurobi. ICCN-BB fue el más rápido, resolviendo todas las instancias en menos de 0.1 segundos en el nodo raíz, confirmando que la incrustación de epígrafo era válida para este problema.

Caso 2: Rutas de Pozos Petroleros

Configuración: Maximización del flujo de petróleo con sustitutos para el rendimiento del pozo y la caída de presión del riser, involucrando decisiones de ruta combinatorias.
Hallazgos: ICCN-MIP requirió consistentemente menos nodos y resolvió más rápido que FNN-MIP en todos los solvers. ICCN-BB superó significativamente a ICCN-MIP cuando se utilizó el solver de código abierto HiGHS (3–8 veces menos nodos, 3–4 veces más rápido). Sin embargo, con el solver comercial Gurobi, la sobrecarga de actualizar la envolvente cóncava en ICCN-BB a veces superó el beneficio de un árbol de búsqueda más pequeño, haciendo que ICCN-MIP fuera más rápido para instancias grandes. Esto resalta un compromiso dependiente del solver.

Caso 3: Mezcla de Vinos

Configuración: Minimización del costo de mezclas de uva con sustitutos para la predicción de calidad, variando el número de mezclas y las dimensiones de entrada.
Hallazgos: ICCN-MIP mostró una escalabilidad superior sobre FNN-MIP en términos de conteo de nodos. ICCN-BB fue altamente eficiente para dimensiones de entrada pequeñas a moderadas (resolviendo en fracciones de segundo). Sin embargo, para dimensiones de entrada altas (55 dimensiones en la instancia más grande), el crecimiento exponencial del conjunto de vértices ( $2^n$ ) en la construcción de la envolvente cóncava abrumó al algoritmo, causando que ICCN-BB fallara en encontrar una solución factible dentro del límite de tiempo, mientras que las formulaciones MIP permanecieron tratables.

Significado y Reivindicaciones

El artículo afirma que las ICNN ofrecen una alternativa estructuralmente superior a las FNN para problemas de optimización donde la respuesta subyacente es aproximadamente convexa o cóncava.

Relajaciones Más Densas: La arquitectura convexa proporciona inherentemente relajaciones LP más densas, reduciendo la necesidad de ramificación en las formulaciones MIP.
Reformulación LP Exacta: Cuando la estructura del problema lo permite, las ICNN admiten reformulaciones LP exactas sin variables binarias, permitiendo el uso de solvers de LP eficientes.
Frontera de Escalabilidad: Los autores identifican la dimensionalidad de la entrada como la frontera de escalabilidad práctica para el algoritmo propuesto ICCN-BB. Si bien ofrece mejoras significativas de velocidad para dimensiones bajas a moderadas al eliminar las variables binarias, el costo exponencial de la enumeración de vértices limita su aplicabilidad a problemas de alta dimensión sin técnicas de aproximación adicionales.

El trabajo sugiere que las ICNN deben ser la elección de sustituto por defecto cuando la función subyacente exhibe convexidad o concavidad, siempre que la dimensión de entrada sea manejable para el enfoque de rama y poda propuesto o la estructura del problema permita una incrustación de epígrafo válida.