La optimización binivel es un tipo especial de optimización donde un problema está incrustado (anidado) dentro de otro. La tarea de optimización externa se denomina comúnmente tarea de optimización de nivel superior y la tarea de optimización interna se denomina comúnmente tarea de optimización de nivel inferior. Estos problemas involucran dos tipos de variables, denominadas variables de nivel superior y variables de nivel inferior. [1]
Formulación matemática del problema
Una formulación general del problema de optimización binivel se puede escribir de la siguiente manera:
sujeto a: , por
dónde
En la formulación anterior, representa la función objetivo de nivel superior y representa la función objetivo de nivel inferior. similar representa el vector de decisión de nivel superior y representa el vector de decisión de nivel inferior. y representan las funciones de restricción de desigualdad en los niveles superior e inferior, respectivamente. Si alguna función objetivo debe maximizarse, es equivalente a minimizar su negativa. La formulación anterior también es capaz de representar restricciones de igualdad, ya que estas se pueden reescribir fácilmente en términos de restricciones de desigualdad: por ejemplo, se puede traducir como . Sin embargo, generalmente vale la pena tratar las restricciones de igualdad por separado, para abordarlas de manera más eficiente de una manera dedicada; en la representación anterior, se han omitido por brevedad.
Competencia Stackelberg
La optimización binivel se realizó por primera vez en el campo de la teoría de juegos por un economista alemán Heinrich Freiherr von Stackelberg que publicó Market Structure and Equilibrium (Marktform und Gleichgewicht) en 1934 que describía este problema jerárquico. El juego estratégico descrito en su libro llegó a conocerse como el juego Stackelberg que consiste en un líder y un seguidor. El líder se conoce comúnmente como un líder de Stackelberg y el seguidor se conoce comúnmente como un seguidor de Stackelberg. En un juego de Stackelberg, los jugadores del juego compiten entre sí, de modo que el líder hace el primer movimiento y luego el seguidor reacciona de manera óptima a la acción del líder. Este tipo de juego jerárquico es de naturaleza asimétrica, donde el líder y el seguidor no pueden intercambiarse. El líder sabe ex ante que el seguidor observa sus acciones antes de responder de manera óptima. Por lo tanto, si el líder quiere optimizar su objetivo, entonces necesita anticipar la respuesta óptima del seguidor. En esta configuración, el problema de optimización del líder contiene una tarea de optimización anidada que corresponde al problema de optimización del seguidor. En los juegos de Stackelberg, el problema de optimización de nivel superior se conoce comúnmente como el problema del líder y el problema de optimización de nivel inferior se conoce comúnmente como el problema del seguidor.
Si el seguidor tiene más de una respuesta óptima a una determinada selección del líder, hay dos opciones posibles: se asume la mejor o la peor solución del seguidor con respecto a la función objetivo del líder, es decir, se supone que el seguidor actúa en de forma cooperativa o agresiva. El problema binivel resultante se denomina problema de programación binivel optimista o problema de programación binivel pesimista, respectivamente.
Aplicaciones
Los problemas de optimización binivel se encuentran comúnmente en una serie de problemas del mundo real. Esto incluye problemas en el dominio del transporte , economía , ciencia de decisiones , negocios , ingeniería , economía ambiental , etc. Se discuten brevemente algunos de los problemas prácticos de dos niveles estudiados en la literatura. [2]
Problema de configuración de peaje
En el campo del transporte, la optimización binivel aparece comúnmente en el problema del establecimiento de peajes. Considere una red de carreteras operada por el gobierno. El gobierno quiere maximizar sus ingresos eligiendo la configuración de peaje óptima para las carreteras. Sin embargo, el gobierno puede maximizar sus ingresos solo si toma en cuenta el problema de los usuarios de la carretera. Para cualquier estructura impositiva dada, los usuarios de las carreteras resuelven su propio problema de optimización, donde minimizan sus costos de viaje al decidir entre utilizar las carreteras o una ruta alternativa. En estas circunstancias, el problema del gobierno debe formularse como un problema de optimización binivel. El nivel superior consiste en los objetivos y restricciones del gobierno, y el nivel inferior consiste en los objetivos y restricciones de los usuarios de la carretera para una estructura tributaria determinada. Es de destacar que el gobierno podrá identificar los ingresos generados por una estructura tributaria en particular solo resolviendo el problema de nivel inferior que determina en qué medida se utilizan las carreteras.
Optimización estructural
Los problemas de optimización estructural constan de dos niveles de tareas de optimización y se denominan comúnmente problemas de programación matemática con restricciones de equilibrio ( MPEC ). El objetivo de nivel superior en tales problemas puede implicar la minimización de costes o la minimización de peso sujeto a límites en los desplazamientos, tensiones y fuerzas de contacto. Las variables de decisión en el nivel superior suelen ser la forma de la estructura, la elección de materiales, la cantidad de material, etc. Sin embargo, para cualquier conjunto dado de variables de nivel superior, las variables de estado (desplazamiento, tensiones y fuerzas de contacto) solo se pueden calcular resolviendo el problema de minimización de energía potencial que aparece como una restricción de satisfacción de equilibrio o una tarea de minimización de nivel inferior al problema de nivel superior.
Aplicaciones de defensa
La optimización binivel tiene una serie de aplicaciones en defensa, como el diseño de la estructura de la fuerza estratégica ofensiva y defensiva, la estructura de la fuerza del bombardero estratégico y la asignación de aviones tácticos a las misiones. La entidad ofensiva en este caso puede considerarse un líder y la entidad defensiva en este caso puede considerarse un seguidor. Si el líder quiere maximizar el daño causado al oponente, entonces solo se puede lograr si el líder tiene en cuenta las reacciones del seguidor. Un seguidor racional siempre reaccionará de manera óptima a la ofensiva del líder. Por lo tanto, el problema del líder aparece como una tarea de optimización de nivel superior, y la respuesta óptima del seguidor a las acciones del líder se determina resolviendo la tarea de optimización de nivel inferior.
Metodologías de solución
Los problemas de optimización binivel son difíciles de resolver. Un método de solución es reformular problemas de optimización binivel a problemas de optimización para los que se encuentran disponibles algoritmos de solución robustos. La Programación Matemática Extendida (EMP) es una extensión de los lenguajes de programación matemática que proporciona varias palabras clave para problemas de optimización binivel. Estas anotaciones facilitan la reformulación automática de programas matemáticos con restricciones de equilibrio (MPEC) para los que existe tecnología de resolución madura. EMP está disponible dentro de GAMS .
Reformulación de KKT
Ciertos programas de dos niveles, en particular los que tienen un nivel inferior convexo y satisfacen una condición de regularidad (por ejemplo, la condición de Slater ), pueden reformularse a un solo nivel reemplazando el problema de nivel inferior por sus condiciones de Karush-Kuhn-Tucker . Esto produce un programa matemático de un solo nivel con restricciones de complementariedad, es decir, MPEC. Si el problema del nivel inferior no es convexo, con este enfoque el conjunto factible del problema de optimización binivel se amplía mediante soluciones óptimas locales y puntos estacionarios del nivel inferior, lo que significa que el problema de un solo nivel obtenido es una relajación del binivel original. problema.
Reformulación de valor óptimo
Denotando por
la llamada función de valor óptimo , una posible reformulación de un solo nivel del problema binivel es
sujeto a: , por
Este es un problema de optimización no uniforme ya que la función de valor óptimo en general no es diferenciable, incluso si todas las funciones de restricción y la función objetivo en el problema de nivel inferior son suaves. [3]
Optimización evolutiva binivel
Para problemas complejos de dos niveles, los métodos clásicos fallan debido a dificultades como no linealidad , discreción , no diferenciabilidad , no convexidad, etc. En tales situaciones, los métodos evolutivos, aunque computacionalmente exigentes, podrían ser una herramienta alternativa para compensar algunas de estas dificultades y conducir a una solución óptima aproximada. [4]
Optimización binivel multiobjetivo
Un problema de optimización binivel puede generalizarse a un problema de optimización binivel multiobjetivo con múltiples objetivos en uno o ambos niveles. Un problema general de optimización de dos niveles multiobjetivo se puede formular de la siguiente manera:
En los juegos de Stackelberg: problema de líder
sujeto a: , por ;
En los juegos de Stackelberg: problema del seguidor
dónde
En la formulación anterior, representa el vector objetivo de nivel superior con objetivos y representa el vector objetivo de nivel inferior con objetivos. Similar, representa el vector de decisión de nivel superior y representa el vector de decisión de nivel inferior. y representan las funciones de restricción de desigualdad en los niveles superior e inferior, respectivamente. Las restricciones de igualdad también pueden estar presentes en un programa binivel, pero se han omitido por brevedad.
Referencias
- ^ * Dempe, Stephan (2002). Fundamentos de la programación binivel . Springer, Boston, MA. doi : 10.1007 / b101970 .
- Vicente, LN; Calamai, PH (1994). "Programación binivel y multinivel: una revisión bibliográfica". Revista de optimización global . 5 (3): 291-306. doi : 10.1007 / BF01096458 .
- Colson, Benoit; Marcotte, Patrice; Savard, Gilles (2005). "Programación binivel: una encuesta". 4OR . 3 (2): 87–107. doi : 10.1007 / s10288-005-0071-0 .
- ^ "Alcance: optimización evolutiva binivel" . www.bilevel.org . Consultado el 6 de octubre de 2013 .
- ^ Dempe, Stephan; Kalashnikov, Vyacheslav; Prez-Valds, Gerardo A .; Kalashnykova, Nataliya (2015). Problemas de programación binivel: teoría, algoritmos y aplicaciones a redes energéticas . Springer-Verlag Berlín Heidelberg. ISBN 978-3-662-45827-3.
- ^ Sinha, A .; Malo, P .; Deb, K. Una revisión sobre optimización binivel: de enfoques y aplicaciones clásicos a evolutivos . Transacciones IEEE sobre Computación Evolutiva, Volumen: 22, Edición: 2, abril de 2018