Approximation theory for two-level value functions with applications

两级值函数的逼近理论及其应用

• 批准号: EP/V049038/1
• 负责人: Alain Zemkoho
• 金额: $ 25.48万
• 依托单位: University of Southampton
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2021
• 资助国家: 英国
• 起止时间: 2021 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FV049038%2F1
• 关键词: Approximation; theory; two; level; value

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.

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

项目成果

Deep learning methods for screening patients' S-ICD implantation eligibility

筛查患者 S-ICD 植入资格的深度学习方法

• DOI: 10.48550/arxiv.2103.06021
• 发表时间: 2021
• 作者: Dunn A

DUALITY THEORY FOR OPTIMISTIC BILEVEL OPTIMIZATION

乐观双水平优化的对偶理论

• 发表时间: 2023
• 期刊: PACIFIC JOURNAL OF OPTIMIZATION
• 影响因子: 0.2
• 作者: En-Naciri Houria

Deep learning and hyperparameter optimization for assessing one's eligibility for a subcutaneous implantable cardioverter-defibrillator

• DOI: 10.1007/s10479-023-05326-1
• 发表时间: 2023-05-24
• 期刊: ANNALS OF OPERATIONS RESEARCH
• 影响因子: 4.8
• 作者: Dunn，Anthony J.;Coniglio，Stefano;Zemkoho，Alain B.
• 通讯作者: Zemkoho，Alain B.

Synthetic Data & the Future of Women's Health: A Synergistic Relationship

综合数据

• DOI: 10.2139/ssrn.4441808
• 发表时间: 2023
• 作者: Delanerolle G

Extension of the value function reformulation to multiobjective bilevel optimization

• DOI: 10.1007/s11590-022-01948-9
• 发表时间: 2021-11
• 期刊: Optimization Letters
• 影响因子: 1.6
• 作者: L. Lafhim;Alain B. Zemkoho