発明の詳細な説明【技術分野】 【０００１】 本開示は、最適化装置、最適化方法、及びプログラムに関する。 続きを表示（約 3,000 文字）【背景技術】 【０００２】 一般的な組合せ最適化問題は、所望の目的関数を最適化（最小化又は最大化）する組合せをただ１つ求めることを目的とする。一方で、組合せ最適化問題の中には、最適な組合せのポートフォリオ、すなわちいくつかの組合せのミックスを求めるタイプの問題も存在する。このタイプの問題のうちの一部は凸関数である目的関数を用いて定式化することが可能である。 【０００３】 最適な組合せのポートフォリオを求めるタイプの問題のうち凸関数である目的関数を用いて定式化できる組合せ最適化問題は、選択可能な組合せの個数が少ない場合には、非特許文献１に記載されているＦｒａｎｋ－Ｗｏｌｆｅ法を用いて解くことができる。また、目的関数が強凸関数と呼ばれる良いクラスに属する場合には、非特許文献２に記載されているＦｕｌｌｙ－ｃｏｒｒｅｃｔｉｖｅ Ｆｒａｎｋ－Ｗｏｌｆｅ法やＡｗａｙ－ｓｔｅｐ Ｆｒａｎｋ－Ｗｏｌｆｅ法を用いて解くことができる。ただし、非特許文献１に記載されているＦｒａｎｋ－Ｗｏｌｆｅ法では目的関数の最適値との誤差が反復数の逆数に比例した速度でしか減少せず、また非特許文献２に記載されているＦｕｌｌｙ－ｃｏｒｒｅｃｔｉｖｅ Ｆｒａｎｋ－Ｗｏｌｆｅ法やＡｗａｙ－ｓｔｅｐ Ｆｒａｎｋ－Ｗｏｌｆｅ法では目的関数の最適値との誤差が反復数に対して指数的に減少するものの、目的関数が強凸関数であるという条件を満たす必要がある。これに対して、非特許文献３には、目的関数が強凸よりも緩い条件下でも目的関数の最適値との誤差が反復数に対して指数的に減少するＦｒａｎｋ－Ｗｏｌｆｅ法が記載されている。以下、目的関数の最適値との誤差が反復数に対して指数的に減少することを「線形収束」と呼ぶことにする。 【０００４】 一方で、選択可能な組合せの個数が指数的に多い場合、Ｆｒａｎｋ－Ｗｏｌｆｅの１反復にも指数的な時間が掛かってしまうため現実的な時間で解くことが難しくなる。これに対して、非特許文献４には、選択可能な組合せの集合をコンパクトに表現可能なデータ構造をＦｒａｎｋ－Ｗｏｌｆｅ法内部の計算に用いることにより、選択可能な組合せの個数が指数的に多い場合でも実用上高速に最適化できる手法が記載されている。この非特許文献４に記載されている手法では、目的関数が強凸関数である場合、目的関数の最適値との誤差が線形収束する。 【先行技術文献】 【非特許文献】 【０００５】 Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, Vol. 3, pp. 95-110. Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of Frank--Wolfe optimization variants. In Proceedings of the 28th International Conference on Neural Information Processing Systems, Vol. 1, pp. 496-504, 2015. Dan Garber and Noam Wolf. Frank-Wolfe with a nearest extreme point oracle, In Proceedings of the 34th Annual Conference on Learning Theory, PMLR Vol. 134, pp. 2103-2132, 2021. Kengo Nakamura, Shinsaku Sakaue, and Norihito Yasuda. Practical Frank-Wolfe method with decision diagrams for computing Wardrop equilibrium of combinatorial congestion games. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pp. 2200-2209, 2020. 【発明の概要】 【発明が解決しようとする課題】 【０００６】 しかしながら、非特許文献４に記載されている手法は目的関数の最適値との誤差が線形収束するものの、理論上その速度は非常に遅く、また目的関数が強凸であるという条件は実応用では成り立たないこともある。 【０００７】 本開示は、上記の点に鑑みてなされたもので、目的関数が強凸よりも緩い条件下で目的関数の最適値に対する誤差が線形収束し、選択可能な組合せの個数が指数的に多い場合であっても組合せ最適化問題を高速に解くことができる技術を提供する。 【課題を解決するための手段】 【０００８】 本開示の一態様による最適化装置は、凸関数である目的関数ｆと、アイテム集合Ｘ＝｛ａ １ ，・・・，ａ ｄ ｝に関する選択可能な組合せＣ １ ，・・・，Ｃ ｔ ⊆Ｘの集合を表す組合せ集合ｓｃｒＣとに対して、組合せＣ ｉ が確率ｐ ｉ （ただし、ｐ ｉ ≧０かつｐ １ ＋・・・＋ｐ ｔ ＝１）で含まれることを表すベクトルｘであって、かつ、ｆ（ｘ）を最小化するベクトルｘを求める最適化装置であって、前記目的関数ｆと、前記組合せ集合ｓｃｒＣをゼロサプレス型二分決定グラフで表現したＺＤＤと、前記目的関数ｆの最適値との許容誤差εとを入力する入力部と、前記目的関数ｆと、前記ＺＤＤと、前記許容誤差εに基づいて、Ｆｒａｎｋ－Ｗｏｌｆｅ法の各反復で前回の反復で求めた解ｘ Ｔ から前記ＺＤＤを利用して次の解ｘ Ｔ＋１ を求めることにより、前記目的関数ｆの最適値との誤差が前記許容誤差ε以下であるベクトルｘを求める最適化部と、を有する。 【発明の効果】 【０００９】 目的関数が強凸よりも緩い条件下で目的関数の最適値に対する誤差が線形収束し、選択可能な組合せの個数が指数的に多い場合であっても組合せ最適化問題を高速に解くことができる技術が提供される。 【図面の簡単な説明】 【００１０】 本実施形態に係る最適化装置のハードウェア構成の一例を示す図である。 本実施形態に係る最適化装置の機能構成の一例を示す図である。 組合せ最適化問題の求解処理の一例を示すフローチャートである。 最適化部が実行する処理の流れの一例を示す図である。 ＬｉｎｅａｒＭｉｎ（ｗ）の処理の流れの一例を示す図である。 ＮｅａｒＰｏｉｎｔ（ｘ，ｗ，ρ）の処理の流れの一例を示す図である。 【発明を実施するための形態】 （【００１１】以降は省略されています）
特許ウォッチbot のツイートを見る
この特許をJ-PlatPatで参照する
特許ウォッチ
