M凸関数最小化問題に対する高性能近似アルゴリズムの構築

M凸函数最小化问题的高性能逼近算法的构建

基本信息

批准号：
21K21290
负责人：
南川智都
金额：
$ 1.66万
依托单位：
Tokyo Metropolitan University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Research Activity Start-up
财政年份：
2021
资助国家：
日本
起止时间：
2021-08-30 至 2024-03-31
项目状态：
已结题

项目摘要

本研究ではM凸関数最小化問題およびその関連問題について，局所最適解が得られない状況における高性能なアルゴリズムの構築を目指している．本年度は昨年度に引き続き，ジャンプシステム上の分離凸関数最小化問題に対するアルゴリズムの考察を行った．この問題は1995年に安藤らによって提案されたある種の貪欲アルゴリズムによって解けることが知られている．本年度は安藤らのアルゴリズムを精緻化することで，初期解から最適解に遷移できるという測地線性質の証明を進めた．この問題は複雑な離散構造を持つため，従来の離散凸解析において用いられた証明方法とは異なる方法を提案した．この結果について学会発表を行い，専門家と議論を重ねることで，問題に対する理解を深めるとともに，証明の一部に不備があることを発見できた．証明の不備については修正を行い，論文にまとめて投稿中である．また，このジャンプシステム上の分離凸関数最小化問題に対して，以下の問いの答えを検討している．(1)測地線性質を持つ別種の貪欲アルゴリズムや最急降下法が構築可能か(2)局所解について一部の情報が得られない場合について，反復回数を抑えることが可能か(1)について最急降下法の測地線性質を検討したが，未だに分かっていない．限定されたケースでは既に得られた結果から測地線性質をもつことが言えるものの，一般的なケースについては貪欲アルゴリズムで行った証明方法を用いてもうまくいかず，他の証明方法を検討中である．(2)についても一般的な状況において反復回数をうまく抑えられるかは明らかになっていないが，検討を重ねることで問題に対する理解を進めることができている．

在本研究中，我们的目标是在无法获得局部最优解的情况下构建用于 M 凸函数最小化问题和相关问题的高性能算法。继去年之后，今年我们考虑了最小化跳跃系统上的单独凸函数问题的算法。众所周知，这个问题可以使用 Ando 等人于 1995 年提出的一种贪心算法来解决。今年，通过改进 Ando 等人的算法，我们继续证明了测地线性质，即可以从初始解过渡到最优解。由于该问题具有复杂的离散结构，我们提出了一种与传统离散凸分析不同的证明方法。通过在学术会议上展示结果并与专家反复讨论，我们能够加深对问题的理解，并发现证明的某些部分是有缺陷的。我们已经纠正了证明中的缺陷，目前正在将其作为论文提交。此外，我们正在研究以下有关该跳跃系统的分离凸函数最小化问题的答案。（1）是否可以构造另一种具有测地线性质的贪心算法或最速下降法？（2）尽管我们已经研究了测地线性质，但当无法获得有关局部解的某些信息时是否可以减少迭代次数？陡峭下降法的原理目前还不清楚。虽然从已经获得的结果来看，在有限的情况下它具有测地线性质，但在一般情况下，使用贪心算法的证明方法不起作用，正在考虑其他证明方法。对于（2），目前尚不清楚一般情况下是否可以有效抑制迭代次数，但通过反复研究，我们已经能够推进对问题的理解。