Bilevel Optimization with Learning

双层优化涉及描述多个(通常是两个)决策者之间的分层决策过程的数学模型，这些决策者被称为领导者和追随者。一个典型的双层数学规划假定决策者之一，即领导者，知道跟随者问题的参数。然而，在不同的应用中，领导者对追随者所面临的问题没有完整的信息。特别是，这项研究集中在实际环境中，领导者面临着典型的剥削和探索之间的权衡：领导者和追随者在多个时间段进行互动，领导者有机会更新她对追随者问题的知识，并将这些信息纳入决策过程。双层优化是一种广泛应用于执法、经济、交通、医疗、能源等领域的建模和求解工具。然而，标准的双层优化没有解决在许多重要应用程序中出现的这种探索与开发之间的权衡。因此，这项工作的结果将为决策者提供改进的方法。该项目还将通过课程和直接参与研究对研究生和本科生产生教育影响；将鼓励来自代表性不足群体的学生参与，包括通过REU补充方案的本科生。研究将通过结合双层、在线和稳健优化技术，产生一套新的模型和解决方法，用于解决具有不确定性的顺序决策问题和在双层环境下的学习。这些方法之间的接口是一个相当未被探索的话题。此外，将根据半先知的概念制定一类新的基准，以验证不同政策的有效性。最后，决策政策和基准将需要开发复杂的算法。因此，本研究的结果也将提高解决困难类双层和序列优化问题的整体能力，包括不确定性下的优化问题。

Bilevel optimization involves mathematical models that describe hierarchical decision-making processes between multiple, usually two, decision-makers, referred to as a leader and a follower. A typical bilevel mathematical program assumes that one of the decision-makers, namely, the leader, knows the parameters of the follower's problem. Yet, there are various applications where the leader has incomplete information about the problem faced by the follower. In particular, this research is focused on practical settings, where the leader faces a classical exploitation vs. exploration trade-off: the leader and the follower interact during multiple time periods and the leader has an opportunity to update her knowledge of the follower's problem, and to incorporate this information into the decision-making process. Bilevel optimization has been a popular modeling and solution tool applied in different areas such as law enforcement, economics, transportation, health care and energy. However, standard bilevel optimization does not address this exploration vs. exploitation trade-off arising in many important applications. Therefore, the results of this work will provide improved methods for decision-makers. This project will also have educational impacts for graduate and undergraduate students through courses and direct participation in the research; participation of students from the underrepresented groups will be encouraged, including undergraduate via the REU supplement.The research will result in a new set of models and solution methods for sequential decision-making problems with uncertainty and learning in bilevel settings by combining bilevel, online and robust optimization techniques. The interface between these methods is a fairly unexplored topic. In addition, a new class of benchmarks will be developed based on the notion of a semi-oracle for validating the effectiveness of the different policies. Finally, the decision-making policies and benchmarks will require development of sophisticated algorithms. Thus, the results of this research will also enhance the overall ability to solve hard classes of bilevel and sequential optimization problems, including those under uncertainty.