Bilevel Optimization with Learning

点击翻译按钮获取中文摘要

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.