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

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

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