Project Details
Funding Scheme : General Research Fund
Project Number : 11211521
Project Title(English) : Towards Scalable Multi-Objective Bilevel Optimization: Foundations, Methodologies and Applications 
Project Title(Chinese) : 针对可扩展的多目标双层优化:理论、方法与应用研究 
Principal Investigator(English) : Prof TAN, Kay Chen 
Principal Investigator(Chinese) :  
Department : Department of Computing
Institution : The Hong Kong Polytechnic University
Co - Investigator(s) :
Dr LI, Ke
Panel : Engineering
Subject Area : Computing Science & Information Technology
Exercise Year : 2021 / 22
Fund Approved : 1,093,580
Project Status : On-going
Completion Date : 31-12-2024
Abstract as per original application
Multi-objective bilevel optimization problem involves two hierarchically nested multi-objective optimization tasks (known as the upper- and lower-level problems) considering the trade-off among several conflicting criteria. It is widely existed in many real-world applications across multiple disciplines from public to private sectors. For example, in a multiuser cooperative mobile edge computing offloading system running under a multiuser interference environment, in which delay-sensitive tasks may be executed on local devices, cooperative devices, or the primary mobile edge computing server, the joint optimization of the offloading decision and computation resource allocation for minimizing the total energy consumption of all mobile users under the delay constraint and maximizing the quality of service essentially has a bilevel structure, where the offloading decision generated in the upper-level is coupled with the optimal allocation of computational resources in the lower-level. Although there have been some research efforts on bilevel optimization, there is a gap between existing methodologies in academia and their further uptake in industry mainly because of its poor scalability: (i) Existing works generally consider small-scale problems, e.g., with up to 10 decision variables and less than 3 objective functions, which are way below the requirement of real-world black-box systems; (ii) Due to the nested structure of two levels of coupling optimization processes, bilevel optimization is known to be strongly NP-hard and highly computationally expensive thus hardly scalable and applicable to large-scale scenarios; (iii) Due to the lack of well-established solution procedures (even for single-objective bilevel optimization), most efforts have been dedicated to simplifying a bilevel optimization problem into a single-level format which incurs inevitable errors and further aggravates the solvability. The aim of this project is to develop a data-driven computational framework for bilevel multi-objective optimization focusing on its scalability to a large number of decision variables and objective functions. It consists of five major tasks: (i) Develop foundations for bilevel multi-objective optimization including extensible benchmark problems mimicking real-world challenges and a performance evaluation platform; (ii) Build surrogate models from a Bayesian perspective to alleviate the high computational cost incurred by the two nested optimization processes; (iii) Develop effecitve transfer optimization techniques to improve the computational efficiency through knowledge transfer; (iv) Develop a multi-space optimization paradigm and GPU-based multi-space algorithms to improve the computational scalability of bilevel multi-objective optimization; (v) Validate the effectiveness of the developed technologies via two real-world complex optimization problems in the domains of software engineering and logistics.
多目标双层优化问题包含两层嵌套的多目标优化任务。其中每层优化任务都需要考虑多个相互冲突的目标函数间的权衡关系。该类问题广泛存在于许多不同领域的实际应用场景。例如,在多用户协作的移动边缘计算中系统卸载环境存在多用户干涉影响。其中对延迟需求高的任务通常于局部设备中运行,而关于卸载决策与计算资源分配的联合优化问题通常具有一个双层优化结构。其中卸载决策是上层优化问题的产物;而对于每一个决策,相应的最优资源分配则由下层优化获得。另外,系统需要同时考虑最小化所有移动端用户能量损耗,并最大化服务质量且应满足延迟约束。 尽管目前在双层优化方面已经引起了研究者广泛兴趣,然而现有计算方法受限于可扩展性差的缺陷无法广泛应用于实际工业场景。主要存在三方面问题:i) 现有方法通常只考虑小规模问题(例如最多考虑10个变量和3个目标函数),远不符合实际黑盒系统情况;ii) 鉴于双层优化问题嵌套结构,它们通常是NP难问题而且计算代价巨大,因此无法满足大规模场景需求;iii) 由于缺少有效求解方法,大部分工作仍试图将双层优化问题简化为单层优化问题,这样无疑带来逼近误差甚至会导致问题无法求解。 本项目主要目的是研究一种数据驱动的计算框架用于求解大规模多目标双层优化问题。它主要包含五个主要任务:i) 研究多目标双层优化问题基础理论,其中包括设计一系列可扩展的测试问题用于模拟实际工程问题中各种挑战,以及一个性能评价平台;ii) 设计基于贝叶斯定理的代理模型用于缓解双层嵌套优化过程高昂计算代价;iii) 设计有效的迁移优化技术用于提高计算效率;iv) 设计多空间优化框架及其GPU实现,用于提高多目标双层优化可扩展性;v) 在软件工程以及物流实际复杂场景下验证方法有效性。
Research Outcome
Layman's Summary of
Completion Report:
Not yet submitted