连续DR次模最大化问题的理论与算法综述  

A survey on theory and algorithms for continuous DR-submodular maximization

作　　者：剧嘉琛 杨瑞琪 张真宁 堵丁柱 Jiachen Ju;Ruiqi Yang;Zhenning Zhang;Ding-Zhu Du

机构地区：[1]北京工业大学运筹学与信息工程研究所,北京100124 [2]Department of Computer Science,University of Texas at Dallas,Richardson,Texas 75080,USA

出　　处：《中国科学:数学》2025年第2期501-516,共16页Scientia Sinica:Mathematica

基　　金：国家自然科学基金(批准号:12131003和12101587)资助项目。

摘　　要：收益递减(diminishing returns,DR)次模最大化问题是研究具有边际收益递减性质的函数的优化问题.在连续优化领域中,DR次模函数不仅在理论上具有深远的研究价值,而且在应用上也展现了广泛的实用意义,特别是在资源分配、广告预算优化、传感器网络和能量管理等实际应用场景中发挥了关键作用.本文主要阐述连续域上DR次模最大化问题的经典算法及其相关变形问题的算法,涵盖Frank-Wolfe型算法、双贪婪算法、随机算法和在线算法等,并回顾近年来有关连续DR次模最大化问题的主要研究进展,为进一步探索该领域的前沿问题提供了有益参考.The diminishing returns property defines an optimization challenge known as the DR-submodular maximization problem.In the continuous domain,the DR-submodular function holds significant theoretical research value and demonstrates extensive practical relevance across various applications.This type of problem is commonly abstracted from practical scenarios including resource allocation,advertising budget optimization,sensor network,and energy management.In this paper,we discuss classic algorithms for continuous DR-submodular maximization and their variants,covering Frank-Wolfe algorithms,double greedy algorithms,stochastic algorithms,and online algorithms.We also review recent research progress on continuous DR-submodular maximization,providing useful references for further exploration of frontier issues in this field.

关 键 词：DR次模最大化 非凸优化 近似算法 

分 类 号：O224[理学—运筹学与控制论]