Approximation theory for two-level value functions with applications

两级值函数是参数优化问题的最优值函数，其中可行集由另一个优化问题的最优解集描述。该项目的主要目标是在文献中首次开发两级值函数的显式近似。能够近似这些函数将能够设计简单有效的算法来解决各种优化领域的未解决问题，包括多层，鲁棒和随机优化。由于悲观双层优化代表了两层值函数最突出的应用，因此本项目中开发的近似的效率将通过构建求解悲观双层程序的算法来评估。这是优化领域中最具挑战性的问题之一，因为目标函数没有明确的解析表达式，通常只是上半连续的。悲观双层优化的这些特征使问题脱离了标准优化的框架，在标准优化中，要最小化的目标函数通常是明确给出的，并且要求至少是下半连续的。解决悲观双层规划将释放双层优化的潜力，使其成为最优决策的有力工具。要了解这一点，请注意双层优化问题（也称为Stackelberg博弈）中最基本的规则是领导者（上层玩家）首先通过选择优化其效用函数的决策值进行游戏。随后，追随者（低级玩家）会自私地对领导者的选择做出反应，选择自己的决策值来优化自己的效用函数。这通常会产生两种情况：乐观和悲观的双层方案。在乐观的情况下，人们假设追随者会合作做出有利于领导者的决定。然而，当领导者对追随者的合作不确定时，作为一个风险厌恶者，他/她会解决悲观的双层计划，以最小化追随者的不利选择可能导致的任何潜在损害。因此，很明显，双层优化的大多数实际应用只适用于悲观模型，因为对于领导者来说，假设追随者不会对他/她有利是更现实的。然而，由于求解悲观双层规划非常困难，关于双层优化的文献几乎忽略了这个问题，因此本质上都集中在问题的乐观模型上。该项目将重点从乐观双层优化转向悲观双层优化，同时创建第一个有效解决问题的框架。更广泛地说，由于其固有的数学挑战以及在过去40年中呈指数级增长的广泛应用，双层优化代表了优化领域中最流行的问题之一。这个项目的结果可以帮助解决英国和国际上重要的问题。例如，对于英国目前计划或正在进行的大型交通项目（如横贯铁路、HS2和希思罗机场第三跑道），双层优化为政府（作为上层参与者）提供了一个框架，以最大化其产出，同时确保纳税人（作为下层参与者）也能够实现其预期目标。在这种情况下，可以围绕最优网络设计构建合适的双层优化模型，在必要时建立最优收费政策或对这些设施的需求进行最优估计。

A two-level value function is an optimal value function of a parametric optimization problem where the feasible set is described by the optimal solution set of another optimization problem. The primary goal of this project is to develop, for the first time ever in the literature, explicit approximations of two-level value functions. Being able to approximate these functions will enable the design of simple and efficient algorithms for unsolved problems in various areas of optimization, including multilevel, robust, and stochastic optimization. As pessimistic bilevel optimization represents the most prominent application of two-level value functions, the efficiency of the approximations developed in this project will be evaluated though algorithms to be constructed to solve the pessimistic bilevel program. This is one of the most challenging problems in the field of optimization, as the objective function does not have an explicit analytical expression and is typically only upper semicontinuous. These features of pessimistic bilevel optimizaion place the problem out of the framework of standard optimization, where the objective function to be minimized is usually given explicitly and required to be at least lower semicontinuous. Solving the pessimistic bilevel program will unlock the potential of bilevel optimization as a powerful tool for optimal decision-making. To see this, note that the most basic rule in a bilevel optimization problem (also known as Stackelberg game) is that the leader (upper-level player) plays first by selecting a decision value that optimizes his/her utility function. Subsequently, the follower (lower-level player) selfishly reacts to this choice from the leader by choosing his/her own decision value that optimizes his/her utility function. This generally gives rise to two scenarios: the optimistic and pessimistic bilevel programs. In the optimistic case, one assumes that the follower will cooperate to make decisions that are in favour of the leader. However, if the leader is uncertain about the cooperation of the follower, as a risk-averse player, he/she will solve the pessimistic bilevel program to minimize any potential damage that might result from unfavorable choices from the follower. It is therefore clear that most practical applications of bilevel optimization will only fit into the pessimistic model, as it is more realistic for the leader to assume that the follower will not play in his/her favour. However, because solving the pessimistic bilevel program is very difficult, the literature on bilevel optimization has almost ignored the problem, and is therefore essentially concentrated around the optimistic model of the problem. This project will shift focus from optimistic to pessimistic bilevel optimization, while creating the first framework to efficiently solve the problem. More broadly, bilevel optimization represents one of the most popular problems in the field of optimization thanks to its inherent mathematical challenges, as well as the wide range of applications which have been growing exponentially in the last 40 years. The results from this project can help to solve problems of major importance in the UK and internationally. For instance, for the large transportation projects currently planned or ongoing in the UK (e.g., Crossrail, HS2, and Heathrow 3rd Runway), bilevel optimization offers a framework for the government (as upper-level player) to maximize their outputs while ensuring that taxpayers (as lower-level player) are also able to achieve their expected objectives. Suitable bilevel optimization models in this context can be constructed around the optimal network design, establishing optimal toll policies where necessary or the optimal estimation of the demand for these facilities.