ソフトウェア

数理7研では研究の成果をソフトウェアとして Github で公開しています.

微分代数方程式

DAEPreprocessingToolbox で MATLAB による微分代数方程式 (DAE) の前処理ライブラリを公開しています.
DAE は代数的制約の入った常微分方程式系であり,動的システムのモデリングで自然に現れます.DAE の数値計算にあたっては,高指数 DAE を低指数 DAE に変換する指数減少法が前処理として重要ですが,現在広く用いられている Mattsson–Söderlind の指数減少法(MS 法)[1] はある種の DAE に対しては適用できないことが知られています.
本ライブラリでは,[2] で提案された,MS 法が適用不能な DAE を適用可能な DAE に変換する前処理手法を提供します.

参考文献

  1. S. E. Mattsson and G. Söderlind. Index reduction in differential-algebraic equations using dummy derivatives. SIAM Journal on Scientific Computing, 14(3):677–692, 1993.
  2. T. Oki. Improved structural methods for nonlinear differential-algebraic equations via combinatorial relaxation. In Proceedings of the 44th International Symposium on Symbolic and Algebraic Computation (ISSAC ’19), pp. 315−322, 2019.

劣モジュラ関数最小化

SubmodularFunctionMinimizationで劣モジュラ関数最小化アルゴリズムのライブラリを公開しています.
劣モジュラ関数最小化は,多くの組合せ最適化問題で現れる基本的かつ重要な最適化問題です.近年では,機械学習アルゴリズムの中でも用いられます.
詳しくはサーベイ論文[1]や文献[2][3][4]を参照して下さい.

本ライブラリでは,カット関数・被覆関数などの劣モジュラ関数を,組合せ的な劣モジュラ関数最小化アルゴリズムや藤重・Wolfeアルゴリズムによって最小化することができます.
また,修士論文[5]で提案された,改良版藤重・Wolfeアルゴリズムも使用できます.

参考文献

  1. S. Iwata, “Submodular function minimization,” Math. Program., vol. 112, no. 1, pp. 45–64, 2007.
  2. S. Fujishige, “Submodular Functions and Optimization,” 2nd ed. Elsevier, 2005.
  3. A. Schrijver, “Combinatorial Optimization: Polyhedra and Efficiency,” Springer, 2003.
  4. 室田一雄, 『離散凸解析の考えかた —最適化における離散と連続の数理—』, 共立出版, 2007.
  5. 北村 昌士, “Improving Practical Performance of Submodular Function Minimization” (劣モジュラ関数最小化の実用的高速化), 東京大学, 修士論文, 2015.