点击上方“Fundamental Research”关注我们
本文研究了从量子多体、多阶段决策等领域中抽象出的一类广义互补约束优化问题。在这类问题中，复杂的广义互补约束可以通过ℓ1罚函数进行处理，但缺乏理论支撑。本文作者在较弱的条件下严格证明了ℓ1罚函数的精确性，成功建立了“惩罚”前后问题的等价性，从而显著降低了求解此类问题的复杂性。本文的研究成果将为量子多体等实际应用中的优化算法设计提供坚实的理论依据。
中文题目：互补约束难摆平，精准惩罚出奇迹
英文原题：The exactness of the ℓ1 penalty function for a class of mathematical programs with generalized complementarity constraints
通讯作者：刘 歆，中国科学院数学与系统科学研究院
第一作者：胡雨宽，中国科学院数学与系统科学研究院
关键词：量子多体；多阶段决策；广义互补约束；罚函数；全局极小解
背景介绍
数学优化研究的是如何在没有限制或有一定限制条件下，选取最优决策方案，使目标达到最优。在现代社会中，数学优化在许多领域发挥着重要作用。广义互补约束优化问题（MPGCC）是一种复杂的优化模型，它通过广义互补约束来描述决策变量之间的互补耦合关系，广泛应用于量子多体、多阶段决策等领域。例如，在处理强关联多电子系统时，这类约束可以用来描述电子之间的库仑排斥效应。
MPGCC的难点
传统的优化理论和方法依赖所谓的约束规范条件，将研究对象从局部或全局极小解这样的拓扑概念转移到显式的代数系统上。然而，由于广义互补约束的存在，在MPGCC中常用的约束规范条件往往不成立。这给MPGCC的理论分析和数值求解带来了巨大挑战。事实上，即使在所有函数均线性的情况下，MPGCC也是NP难的。
消解约束的利器——罚函数
在传统优化中，罚函数法常被用来处理具有复杂约束的问题。它通过在目标函数中引入非负罚项来“惩罚”不符合约束的解，从而构造出所谓的罚函数。随后无需考虑约束，直接使用优化算法求解罚问题。由于罚项的存在，优化算法倾向于搜索到约束违反度较低的区域。随着“惩罚”程度的增加，罚问题的全局最优解的约束违反度将衰减至零。“惩罚”程度通常由罚参数的大小控制。
罚函数的精确性
随着罚参数趋于无穷大，罚问题将变得越来越难以数值求解。因此，一个自然的问题是，是否存在一个有限的最小罚参数，使得罚问题与原问题的全局最优解集完全一致。这就是罚函数的精确性问题，它在理论和实际应用中都具有重要意义。
罚函数的精确性非常依赖于罚项的选择，而这又直接影响优化算法的设计。对于广义互补约束，已有的精确罚理论大多考虑非光滑或不稳定的罚项，这增加了算法设计的复杂度；相比之下，ℓ1罚函数光滑且稳定，但目前还没有实用的精确罚理论。
研究成果
近日，中国科学院数学与系统科学研究院的刘歆研究员和已毕业的博士研究生胡雨宽，针对一类目标函数多仿射的MPGCC，在较弱的条件下严格证明了ℓ1罚函数的精确性。有意思的是，这一结果还表明，当罚参数超过临界值时，此类MPGCC的强稳定解集及其ℓ1罚问题的稳定解集完全一致。由于对于一般的MPGCC，其强稳定解集通常被认为是包含其局部极小解的最小稳定解集，十分难以求得，因此这一发现显著降低了求得此类MPGCC局部极小解的难度。最后，这些结果为量子多体等领域中实际问题的求解奠定了理论基础。这项工作的总结示意图可见图1。
图1 研究问题、研究成果及应用领域示意图
未来方向
这项研究将启发对于ℓ1罚函数在更加一般MPGCC上的理论性质的探讨。另外，还可基于此类MPGCC，构造新的约束规范条件，为强稳定解在更广泛问题上的计算提供理论依据。从实际应用角度看，这些研究成果将推动发展求解量子多体等实际问题的优化算法。
主要作者简介
刘歆 中国科学院数学与系统科学研究院“冯康首席研究员”，国家杰出青年科学基金获得者，Mathematical Programming Computation、Journal of Computational Mathematics等国内外期刊编委。主要研究方向为流形优化、分布式优化及其在材料计算、机器学习等领域的应用。曾获中国工业与应用数学学会应用数学青年科技奖。
胡雨宽 中国科学院数学与系统科学研究院计算数学专业博士毕业。主要研究方向为材料计算中的优化问题、理论与算法。
引用本文
Yukuan Hu, Xin Liu. The exactness of the 𝓁1 penalty function for a class of mathematical programs with generalized complementarity constraints. Fundamental Research, doi.org/10.1016/j.fmre.2023.04.006.
原文链接（复制到浏览器中查看）：
https://www.sciencedirect.com/science/article/pii/S266732582300119X
关于Fundamental Research
Fundamental Research是由国家自然科学基金委员会主管、主办的综合性英文学术期刊。创刊于2021年，期刊立足反映国家自然科学基金资助的优秀成果，全方位报道世界基础研究前沿重要进展和重大创新性成果，提升中国基础研究和中国科学家在国际科学界的显示度和影响力，为中外科学家打造一个高端的国际学术交流平台。内容涵盖数学物理、化学化工、生命科学、地球科学、工程与材料科学、信息科学、管理科学、健康医学、交叉科学等领域，设置Article、Review、Highlight、Perspective、Commentary等栏目。期刊已被ESCI、Scopus、DOAJ、PubMed、CAS（美国化学文摘社）、CSCD（中国科学引文数据库）、CSTPCD（中国科技论文与引文数据库）等国内外知名数据库收录。2023年影响因子5.7，位于综合性期刊Q1区。欢迎广大科研工作者关注、投稿、引用！
扫描或长按识别下方二维码关注我们
期刊主页：
www.keaipublishing.com/en/journals/fundamental-research/
文章阅读：
www.sciencedirect.com/journal/Fundamental-Research
投稿系统：
www.editorialmanager.com/fmre
查看更多本期信息，点击文末“阅读原文”，欢迎阅读、下载及引用！
喜欢本篇内容请给我们点个
在看
点击“阅读原文”了解更多
