A study on practical algorithms for solving DM optimization problems

実用上重要な関数のほとんどは２つの単調関数の差として表記できることが知られているが，このDM(difference of monotonic)関数を目的関数として凸多面体上で大域的に最小化するアルゴリズムをいくつか設計し，計算機上に実装した．計算実験の途中経過を京都大学数理解析研究所の共同利用研究集会で報告した．設計・実装したのはいずれも分枝限定法をベースとするアルゴリズムであり，凸多面体を直方体によって細分する矩形アルゴリズムの亜種である．直方体上における問題の実行可能解の算出には線形計画問題を用い，その最適解ωを使って直方体の細分を行うω細分操作を新たに考案して用いていた．直方体の細分操作に従来からよく使われているのは最長辺を二分割する網羅的方法であるが，これと考案した方法とを比較するため，ランダムに生成したテスト問題を解かせる計算実験を繰り返した．その結果，最適解への手掛かりが極めて少ないこの種の最適化では，実直に二分割を繰り返す方法が意外にも効率のよいことが判明した．この二分割法を凌駕するために様々な工夫を試み，下界値計算に用いる線形計画問題の最適解ωを通る超平面で直方体の最長辺を二分するタイプのω細分操作を構築し，アルゴリズムを計算機上に実装したところ，通常の二分割法と比較しても良好な実験結果を得ることができた．ω細分操作は網羅的な細分法ではないため，アルゴリズムの収束を保障する必要があるが，その証明の目処はすでに立っている．

実用上重要な関数のほとんどは２つの単調関数の差として表記できることが知られているが，このDM(difference of monotonic)関数を目的関数として凸多面体上で大域的に最小化するアルゴリズムをいくつか設計し，計算機上に実装した．計算実験の途中経過を京都大学数理解析研究所の共同利用研究集会で報告した．設計・実装したのはいずれも分枝限定法をベースとするアルゴリズムであり，凸多面体を直方体によって細分する矩形アルゴリズムの亜種である．直方体上における問題の実行可能解の算出には線形計画問題を用い，その最適解ωを使って直方体の細分を行うω細分操作を新たに考案して用いていた．直方体の細分操作に従来からよく使われているのは最長辺を二分割する網羅的方法であるが，これと考案した方法とを比較するため，ランダムに生成したテスト問題を解かせる計算実験を繰り返した．その結果，最適解への手掛かりが極めて少ないこの種の最適化では，実直に二分割を繰り返す方法が意外にも効率のよいことが判明した．この二分割法を凌駕するために様々な工夫を試み，下界値計算に用いる線形計画問題の最適解ωを通る超平面で直方体の最長辺を二分するタイプのω細分操作を構築し，アルゴリズムを計算機上に実装したところ，通常の二分割法と比較しても良好な実験結果を得ることができた．ω細分操作は網羅的な細分法ではないため，アルゴリズムの収束を保障する必要があるが，その証明の目処はすでに立っている．