離散凸最適化のアルゴリズムとソフトウェアの研究
著者 土村 展之
URL http://hdl.handle.net/10236/13884
−1−
連続変数の凸関数に関する最適化問題に対しては、高速なアルゴリズムを用いた高性能なソフトウェアソ ルバが開発され、大規模な問題を解くことができている。一方、現実に現れる問題は、 連続変数ではなく離 散変数の凸関数に関する最適化問題として定式化できることが多い。しかし、この離散凸関数最適化問題に 対しては、 いくつかのアルゴリズムが設計されてはいるが、大規模な問題を解くソフトウェアはいまだ開発 されていなく、効率のよいアルゴリズムや実用的なソフトウェアの開発が求められている。
本論文では、離散凸最適化問題に対して、高速なアルゴリズムを設計し、それらをソフトウェアとして実 装して、実用的ソルバを開発することを目指した。
論 文 内 容 の 要 旨
本論文は計６章で構成されており、 各章の内容は以下のとおりである。
第１章では、離散凸最適化の有用性を明らかにし、 研究目的とともに、 次章以降の課題と構成について述 べている。
第２章では、離散凸解析に関する様々な定義や既知の結果についてまとめている。特に、L 凸関数と M 凸関数の定義を示し、この２つの離散凸関数に対応する離散凸集合を説明するとともに、離散凸関数の例を 挙げている。さらに、２つの離散凸関数を連続変数の関数に拡張したものの性質について述べている。
第３章では、L 凸関数最小化問題を取り上げ、 本論文の主要な成果の一つである連続緩和手法を提案して いる。さらに、 この手法が効率的であることを理論的に裏付ける近接定理を証明するとともに、この手法が 既存アルゴリズムよりも高速であることを計算機実験により実証している。
第４章では、M 凸関数最小化問題を取り上げ、 M 凸関数に対する連続緩和手法を提案し、 その近接定理 を証明し、本手法が既存アルゴリズムよりも高速であることを計算機実験により実証している。さらに、M 凸関数最小化問題の特殊例である資源配分問題に対して、問題固有の特性を利用しながら、提案した連続緩 和手法を適用して解くアルゴリズムを設計し、 その計算量を解析し、従来の手法より計算量が改善されるこ とを示している。
第５章においては、連続緩和手法に基づくアルゴリズムも含め、様々な離散凸最適化アルゴリズムを実装 し、離散凸最適化ソフトウェアソルバを開発したことについて述べている。このソルバにより、大規模な離 散最適化問題を解くことができるようになり、在庫管理問題など様々な現実的な問題も扱えるようになった。
氏 名
学 位 の 専 攻 分 野 の 名 称 学 位 記 番 号 学位授与の要件 学位授与年月日 学 位 論 文 題 目
論 文 審 査 委 員 （主査）
（副査）
土 村 展 之
離散凸最適化のアルゴリズムとソフトウェアの研究 博 士（工 学）
乙理第61号（文部科学省への報告番号乙第359号）
学位規則第４条第２項該当 2014年11月19日
西 関 隆 夫 北 村 泰 彦 巳 波 弘 佳
室 田 一 雄（東京大学大学院教授）
教 授 教 授 教 授
−2−
なお、このソフトウェアはインターネット上で一般に公開されている。
最後に第６章では、結論と今後の課題について述べている。
論 文 審 査 結 果 の 要 旨
本論文は、離散凸最適化問題に対する高速なアルゴリズムの設計とその実用的なソフトウェアへの実装に 関するものである。
離散凸最適化の分野では、離散変数の関数について L 凸関数と M 凸関数という離散凸性が提案され、降 下法や貪欲法のような局所的探索法によって大域的最適解が得られることなど、様々な結果が得られている。
また、降下法とスケーリング技法を組み合わせることにより、多項式時間アルゴリズムも得られている。し かし、実用的な観点からみると、このアルゴリズムの効率は現実的なサイズの問題を扱うにはまだ十分では ないため、より効率的なアルゴリズムを設計することが望まれていた。
本論文は、まず連続緩和手法に基づくアルゴリズムを新たに提案した。これは、元の離散凸関数を連続変 数の凸関数に緩和し、 準ニュートン法などを用いて その関数に関する実数ベクトルの最適解を求め、 それを 整数ベクトルに丸めたものを元の離散凸関数の最小化問題に対する降下法の初期解とするものである。 また、
緩和問題の解と元の離散最小化問題の解が近いことを保証する近接定理を証明することにより、本提案手法 によって高速に解が得られることを理論的に証明している。
さらに、提案手法を含めて、 様々な離散凸最適化アルゴリズムを実装し、 離散凸最適化ソフトウェアソル バを開発している。 また、 そのソルバを用いた計算機実験により、提案手法が既存アルゴリズムよりも高速 であることを実証している。
本論文の重要な貢献は以下のとおりである。
（１）離散 L 凸関数最小化問題および離散 M 凸関数最小化問題に対し、連続緩和手法に基づくアルゴリズ ムを提案するとともに、そのアルゴリズムにより高速に解が得られることを理論的に保証する近接定 理を証明している。
（２）離散 M 凸関数最小化問題の特殊例である資源配分問題に対して、連続緩和手法を適用したアルゴリズ ムの計算量を厳密に解析し、 計算量が先行研究と同等であるか、いくつかの問題に対しては大幅に改 善できることを示している。
（３）提案手法を含む様々な離散凸最適化アルゴリズムを実装して、 離散凸最適化ソフトウェアソルバを開 発し、 一般に公開した。連続凸最適化の分野では高性能なソルバが活発に開発されており、離散最適 化の分野でも整数変数の線形計画問題である整数計画問題など、いくつかの問題に対しては近年のソ ルバの性能向上が著しいが、整数変数の非線形計画問題に対してはソルバの開発が困難な状況にあっ た。これに対して、今回開発したソフトウェアソルバは単純な実装に比べて計算時間で100 〜 1000 倍 速く、問題規模で10 〜 100 倍の大きさのものを解くことができるため、現実規模の問題も十分に扱え るようになった。
本論文の内容は、 既に SIAM Journal on Optimization などに４編の論文として掲載され、国内外の研究 集会や国際会議でも発表されている。
審査委員は、本論文の内容を中心に査問会を開き、また公開の論文発表会を行い、申請者が論文内容及び 関連する分野について十分な理解と学識を有していること、さらに将来の研究遂行について十分な能力を有 していることを確認した。
さらに、著者は本研究に関する査読付き英語論文２編、その他の研究に関する査読付き英語論文を単著１ 編、共著１編を執筆し、英語での口頭発表１件の経験も有しており、十分な英語能力を持つと判断した。
−3−
以上により、審査委員会は、本論文提出者である土村展之氏が博士（工学）の学位を授与されるに足る十 分な資格を有するものと判定する。
