论文标题
在计算行为不良的二极管问题上，连续且非凸较低级别
On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level
论文作者
论文摘要
众所周知，在理论和实践中很难解决双重优化问题。在本文中，我们强调了在解决连续但非凸较低级别的二聚体问题方面的进一步计算困难。即使将低级问题解决到$ \ VAREPSILON $ - 可行性，即对于任意小但积极的$ \ varepsilon $的非线性约束，所获得的二重性解决方案及其目标值也可能与实际的bilevel解决方案及其实际目标值远距离远。该结果甚至适用于非凸较低级别的唯一问题，为此，严格的互补性条件所保持的，可行的集合是凸的，对于所有可行的高级决策，Slater的约束资格都可以满足其满足。由于在将非凸问题求解到全球最优性时，无法避免考虑$ \ varepsilon $ - 可行性，因此我们的结果表明，需要通过大量护理来完成具有连续和非凸较低级别的计算双杆优化。最后，我们说明较低级别的非线性是观察到的不良行为的关键原因，这表明线性二极管问题至少在可行解决方案的水平上表现更好。
It is well known that bilevel optimization problems are hard to solve both in theory and practice. In this paper, we highlight a further computational difficulty when it comes to solving bilevel problems with continuous but nonconvex lower levels. Even if the lower-level problem is solved to $\varepsilon$-feasibility regarding its nonlinear constraints for an arbitrarily small but positive $\varepsilon$, the obtained bilevel solution as well as its objective value may be arbitrarily far away from the actual bilevel solution and its actual objective value. This result even holds for bilevel problems for which the nonconvex lower level is uniquely solvable, for which the strict complementarity condition holds, for which the feasible set is convex, and for which Slater's constraint qualification is satisfied for all feasible upper-level decisions. Since the consideration of $\varepsilon$-feasibility cannot be avoided when solving nonconvex problems to global optimality, our result shows that computational bilevel optimization with continuous and nonconvex lower levels needs to be done with great care. Finally, we illustrate that the nonlinearities in the lower level are the key reason for the observed bad behavior by showing that linear bilevel problems behave much better at least on the level of feasible solutions.
