Approximation theory for two-level value functions with applications

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

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.