UMA 2022
El problema de optimización binivel es un problema de minimización con restricciones donde una de las restricciones es a su vez otro problema de minimización. Surge a partir del juego de Stackelberg, donde dos participantes, líder y seguidor, toman decisiones para optimizar sus propias funciones objetivo. El estudio de este problema se centra por lo general en el enfoque optimista, cuya formulación es la siguiente: \[ \min_{x,y} F(x,y)\ \mbox{ s.a. }\ G(x,y)\leq 0,\ y\in S(x)=\mbox{arg}\min_y\{f(x,y)|g(x,y)\leq 0\}. \]
Una de las estrategias para resolver el problema binivel es la reformulación utilizando la función de valor óptimo del nivel inferior (LLVF por sus siglas en inglés), que reemplaza la condición $y\in S(x)$ por las restricciones $g(x,y)\leq 0$ y $f(x,y) - \varphi( x)\leq 0$, donde $\varphi(x):=\mbox{inf}\{f(x,y)|g(x,y)\leq 0\}$. En $1995$, Ye y Zhu [1] derivaron condiciones de optimalidad para este problema utilizando el concepto de calma parcial, permitiendo llevar la restricción con la LLVF al nivel superior con un parámetro de penalización exacta parcial $\lambda$: \[ \min_{x,y} F(x,y)+\lambda(f(x,y)-\varphi(x))\ \mbox{ s.a. }\ G(x,y)\leq 0,\ g(x,y)\leq 0. \]
En los trabajos de Tin et al. [2,3], los autores trabajan con un sistema de ecuaciones no lineales sobredeterminado equivalente al problema binivel, bajo ciertas condiciones, y derivan métodos de segundo órden para resolverlo. Allí encuentran empíricamente que los valores del parámetro $\lambda$ pequeños (menores a $1$) tienen un mejor desempeño que los valores muy grandes (mayores a $10^4$) y que los valores intermedios (entre $10^0$ y $10^4$) tienen bajo rendimiento, lo cual contradice lo esperado para parámetros de penalización.
Estudiamos el comportamiento de este parámetro $\lambda$ para comprender la razón de este funcionamiento anómalo, y derivamos un criterio de rendimiento del parámetro para evaluar cuál valor es mejor en un problema dado.
Trabajo en conjunto con: Andrés A. Barrea (Universidad Nacional de Córdoba, Argentina) y Elvio A. Pilotta (Universidad Nacional de Córdoba, Argentina).
Referencias
[1] Ye, Jane J. and Daoli Zhu. “Optimality conditions for bilevel programming problems.” Optimization 33 (1995): 9-27.
[2] Fliege, Jörg & Tin, Andrey & Zemkoho, Alain. (2021). Gauss–Newton-type methods for bilevel optimization. Computational Optimization and Applications. 10.1007/s10589-020-00254-3.
[3] Tin, Andrey & Zemkoho, Alain. (2021). Levenberg-Marquardt method and partial exact penalty parameter selection in bilevel optimization.