Optimización de dos niveles

Problema de programación fraccionaria cuadrática

La optimización de dos niveles es un tipo especial de optimización en el que un problema está integrado (anidado) dentro de otro. La tarea de optimización externa se conoce comúnmente como tarea de optimización de nivel superior, y la tarea de optimización interna se conoce comúnmente como 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] [2] [3]}

Formulación matemática del problema

Una formulación general del problema de optimización de dos niveles se puede escribir de la siguiente manera:

${\displaystyle \min \limits _{x\in X,y\in Y}\;\;F(x,y)}$

sujeto a:

${\displaystyle G_{i}(x,y)\leq 0}$, para ${\displaystyle i\in \{1,2,\ldots ,I\}}$

${\displaystyle y\in \arg \min \limits _{z\in Y}\{f(x,z):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}}$

dónde

${\displaystyle F,f:R^{n_{x}}\times R^{n_{y}}\to R}$

${\displaystyle G_{i},g_{j}:R^{n_{x}}\times R^{n_{y}}\to R}$

${\displaystyle X\subseteq R^{n_{x}}}$

${\displaystyle Y\subseteq R^{n_{y}}.}$

En la formulación anterior, representa la función objetivo de nivel superior y representa la función objetivo de nivel inferior. De manera 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 se debe maximizar alguna función objetivo, es equivalente a minimizar su negativo. 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 lidiar con ellas de manera más eficiente y dedicada; en la representación anterior, se han omitido por brevedad. ${\displaystyle F}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle G_{i}}$ ${\displaystyle g_{j}}$ ${\displaystyle h(x)=0}$ ${\displaystyle \{h(x)\leq 0,\ -h(x)\leq 0\}}$

Competición de Stackelberg

La optimización de dos niveles fue realizada por primera vez en el campo de la teoría de juegos por el economista alemán Heinrich Freiherr von Stackelberg , quien publicó Estructura de mercado y equilibrio (Marktform und Gleichgewicht) en 1934, donde describía este problema jerárquico. El juego estratégico descrito en su libro llegó a conocerse como el juego de Stackelberg, que consta de un líder y un seguidor. El líder se conoce comúnmente como líder de Stackelberg y el seguidor como 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 asimétrico por naturaleza, 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 este contexto, 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, existen dos opciones posibles: se supone 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 de forma cooperativa o de forma agresiva. El problema de dos niveles resultante se denomina problema de programación binivel optimista o problema de programación binivel pesimista, respectivamente.

Aplicaciones

Los problemas de optimización de dos niveles se encuentran comúnmente en una serie de problemas del mundo real. Esto incluye problemas en el ámbito del transporte , la economía , la ciencia de la toma de decisiones , los negocios , la ingeniería , la economía medioambiental , etc. Se analizan brevemente algunos de los problemas prácticos de dos niveles estudiados en la literatura. ^[4]

Problema de configuración de peaje

En el campo del transporte, la optimización de dos niveles aparece comúnmente en el problema de fijación de peajes. Consideremos una red de autopistas operada por el gobierno. El gobierno quiere maximizar sus ingresos eligiendo la configuración óptima de peajes para las autopistas. Sin embargo, el gobierno puede maximizar sus ingresos solo si tiene en cuenta el problema de los usuarios de las autopistas. Para cualquier estructura impositiva dada, los usuarios de las autopistas resuelven su propio problema de optimización, donde minimizan sus costos de viaje al decidir entre utilizar las autopistas o una ruta alternativa. En estas circunstancias, el problema del gobierno debe formularse como un problema de optimización de dos niveles. El nivel superior consta de los objetivos y restricciones del gobierno, y el nivel inferior consta de los objetivos y restricciones de los usuarios de las autopistas para una estructura impositiva dada. Cabe destacar que el gobierno podrá identificar los ingresos generados por una estructura impositiva particular solo si resuelve el problema de nivel inferior que determina en qué medida se utilizan las autopistas.

Optimización estructural

Los problemas de optimización estructural constan de dos niveles de tareas de optimización y se conocen comúnmente como 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 costos o la minimización del peso sujeta a límites en desplazamientos, tensiones y fuerzas de contacto. Las variables de decisión en el nivel superior generalmente son 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 determinar 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 para el problema de nivel superior.

Aplicaciones de defensa

La optimización de dos niveles tiene varias aplicaciones en defensa, como el diseño de la estructura de fuerza estratégica ofensiva y defensiva, la estructura de fuerza de bombarderos estratégicos y la asignación de aeronaves tácticas a 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 puede lograrlo 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.

Aplicaciones de Fuerza Laboral y Recursos Humanos

La optimización de dos niveles puede servir como herramienta de apoyo a las decisiones de las empresas en situaciones de la vida real para mejorar las decisiones sobre la fuerza laboral y los recursos humanos. El primer nivel refleja el objetivo de la empresa de maximizar la rentabilidad. El segundo nivel refleja el objetivo de los empleados de minimizar la brecha entre el salario deseado y un plan de trabajo preferido. El modelo de dos niveles proporciona una solución exacta basada en una formulación de números enteros mixtos y presenta un análisis computacional basado en el cambio de comportamiento de los empleados en respuesta a la estrategia de la empresa, demostrando así cómo los parámetros del problema influyen en la política de decisiones. ^[5]

Metodologías de solución

Los problemas de optimización de dos niveles son difíciles de resolver. Un método de solución es reformular los problemas de optimización de dos niveles para convertirlos en problemas de optimización para los que se dispone de 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 los problemas de optimización de dos niveles. Estas anotaciones facilitan la reformulación automática de los Programas Matemáticos con Restricciones de Equilibrio (MPEC) para los que existe una tecnología de resolución madura. EMP está disponible en GAMS .

Reformulación de KKT

Ciertos programas de dos niveles, en particular aquellos que tienen un nivel inferior convexo y satisfacen una condición de regularidad (por ejemplo, la condición de Slater ), se pueden reformular 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 de nivel inferior no es convexo, con este enfoque el conjunto factible del problema de optimización de dos niveles se amplía con 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 problema de dos niveles original.

Reformulación del valor óptimo

Denotando por

${\displaystyle \phi (x)=\min \limits _{z\in Y}\{f(x,z):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}}$

la llamada función de valor óptimo , una posible reformulación de un solo nivel del problema de dos niveles es

${\displaystyle \min \limits _{x\in X,y\in Y}\;\;F(x,y)}$

sujeto a:

${\displaystyle G_{i}(x,y)\leq 0}$, para ${\displaystyle i\in \{1,2,\ldots ,I\}}$

${\displaystyle g_{j}(x,y)\leq 0,j\in \{1,2,\ldots ,J\}}$

${\displaystyle f(x,y)\leq \phi (x).}$

Este es un problema de optimización no suave 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. ^[6]

Métodos heurísticos

En el caso de problemas complejos de dos niveles, los métodos clásicos pueden fallar debido a dificultades como la no linealidad , la discreción , la no diferenciabilidad , la no convexidad , etc. En tales situaciones, se pueden utilizar métodos heurísticos. Entre ellos, los métodos evolutivos, aunque exigentes desde el punto de vista computacional, a menudo constituyen una herramienta alternativa para compensar algunas de estas dificultades encontradas por los métodos exactos, aunque sin ofrecer ninguna garantía de optimalidad en las soluciones que producen. ^[7]

Optimización binivel multiobjetivo

Un problema de optimización de dos niveles se puede generalizar a un problema de optimización de dos niveles con múltiples objetivos en uno o ambos niveles. Un problema general de optimización de dos niveles con múltiples objetivos se puede formular de la siguiente manera:

${\displaystyle \min \limits _{x\in X,y\in Y}\;\;F(x,y)=(F_{1}(x,y),F_{2}(x,y),\ldots ,F_{p}(x,y))}$ En los juegos de Stackelberg: Problema del líder

sujeto a:

${\displaystyle G_{i}(x,y)\leq 0}$, para ; ${\displaystyle i\in \{1,2,\ldots ,I\}}$

${\displaystyle y\in \arg \min \limits _{z\in Y}\{f(x,z)=(f_{1}(x,z),f_{2}(x,z),\ldots ,f_{q}(x,z)):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}}$ En los juegos de Stackelberg: Problema del seguidor

dónde

${\displaystyle F:R^{n_{x}}\times R^{n_{y}}\to R^{p}}$

${\displaystyle f:R^{n_{x}}\times R^{n_{y}}\to R^{q}}$

${\displaystyle G_{i},g_{j}:R^{n_{x}}\times R^{n_{y}}\to R}$

${\displaystyle X\subseteq R^{n_{x}}}$

${\displaystyle Y\subseteq R^{n_{y}}.}$

En la formulación anterior, representa el vector objetivo de nivel superior con objetivos y representa el vector objetivo de nivel inferior con objetivos. De manera 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 de dos niveles, pero se han omitido por brevedad. ${\displaystyle F}$ ${\displaystyle p}$ ${\displaystyle f}$ ${\displaystyle q}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle G_{i}}$ ${\displaystyle g_{j}}$

Referencias

1. Dempe, Stephan (2002). "Prefacio". Fundamentos de la programación binivel . Optimización no convexa y sus aplicaciones. Vol. 61. Springer, Boston, MA. págs. vii–viii. doi :10.1007/b101970. ISBN. 1-4020-0631-4.
2. Vicente, LN ; Calamai, PH (1994). "Programación binivel y multinivel: una revisión bibliográfica". Journal of Global Optimization . 5 (3): 291–306. doi :10.1007/BF01096458. S2CID  26639305.
3. Colson, Benoit; Marcotte, Patrice; Savard, Gilles (2005). "Programación binivel: una encuesta". 4OR . 3 (2): 87–107. doi :10.1007/s10288-005-0071-0. S2CID  15686735.
4. "Alcance: Optimización evolutiva de dos niveles". www.bilevel.org . Consultado el 6 de octubre de 2013 .
5. Ben-Gal, Hila Chalutz; Forma, Iris A.; Singer, Gonen (marzo de 2022). "Un modelo flexible de contratación y compensación de empleados: un enfoque de optimización de dos niveles". Computers & Industrial Engineering . 165 : 107916. doi :10.1016/j.cie.2021.107916. PMC 9758963 . PMID  36568877. S2CID  245625445. 
6. Dempe, Stephan; Kalashnikov, Vyacheslav ; Prez-Valds, Gerardo A.; Kalashnykova, Nataliya (2015). "3.6 La transformación del valor óptimo". Problemas de programación de dos niveles: teoría, algoritmos y aplicaciones a redes de energía . Springer-Verlag Berlin Heidelberg. págs. 84–85. doi :10.1007/978-3-662-45827-3. ISBN . 978-3-662-45827-3.
7. Sinha, Ankur; Malo, Pekka; Deb, Kalyanmoy (abril de 2018). "Una revisión sobre optimización de dos niveles: de enfoques y aplicaciones clásicos a evolutivos". IEEE Transactions on Evolutionary Computation . 22 (2): 276–295. arXiv : 1705.06270 . doi :10.1109/TEVC.2017.2712906. S2CID  4626744.

Enlaces externos

• Glosario de programación matemática