Discrete convex approximation on non-linear discrete optimization

非线性离散优化的离散凸逼近

基本信息

批准号：
21K04533
负责人：
森口聡子
金额：
$ 1.91万
依托单位：
Tokyo Metropolitan University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2025-03-31
项目状态：
未结题

项目摘要

本研究の大きな目標として，連続最適化と離散凸解析の融合により，最適化の理論とアルゴリズムの効率化の方法論を構築し，個別の実問題，応用先への成功にとどまらず，広く適用できるようにすることをまず掲げる．それを達成するための技術的なアプローチとして「離散凸緩和」を取り上げる．「離散凸解析」の理論は，連続と離散を繋ぐパラダイムとして，国際的に認知されており，さらに最近では，「離散中点凸性」など，離散凸解析の理論体系に基づく方法論が新しい離散関数のクラスへと展開されている．今年度，従前の研究で扱われていた範囲より，さらに広い対象範囲での「離散凸性の利用」が期待できるようになった状況を受け，Ｍ凸関数，Ｌ凸関数，整凸関数，マルチモジュラ関数など，離散凸関数の理論研究において考察される種々の関数クラスに対して，それらの間の包含関係や，そのうちの２つのクラスの共通部分がどのようなものになるのかを網羅的に整理する研究を継続した．これによって，様々な分野の研究者が離散凸関数の概念を容易に理解できるようになると期待される．また，連続最適化との融合に貢献する，離散凸構造を不等式系で表現する多面体的表現にも取り組んだ．まず，上述の複数の離散凸構造の間の包含関係や，そのうちの２つのクラスの共通部分の理解に，多面体的表現は有用であった．多面体的表現により，整数計画の理論の応用やソルバーの利用がしやすくなるという今後の展開も開ける．

这项研究的主要目的是通过结合连续优化和离散凸分析来构建优化理论和算法效率方法，从而可以广泛应用它，而不仅仅是将其应用于单个实际问题和个人应用程序。我们将专注于“离散凸放松”，作为实现这一目标的技术方法。 “离散凸分析”的理论在国际上被认为是连续和离散的范式，并且最近，基于离散凸的理论系统（例如“离散的中点凸度”）已发展为新的离散功能类别。 In response to the situation in which "using discrete convexity" can be expected to be expected in a wider range than previously covered in research, we have continued our research to comprehensively organize the inclusion relationships between these classes, such as M-convex, L-convex, symmetric convex, and multimodular functions, for various function classes considered in theoretical research on discrete convex functions, such as M-convex, L-convex, symmetric凸和多模块化函数，以及这两个类别的共同部分。这有望使各个领域的研究人员轻松理解离散凸功能的概念。我们还研究了在不平等系统中表达离散凸结构的多面体表示，这有助于通过连续优化的整合。首先，多面部表达对于理解上述多个离散凸结构与两个类别的相交之间的包含关系很有用。多面体表示还将开辟未来的发展，在这种发展中，应用整数编程理论更容易使用求解器。