微分不可能な凸計画問題に対する実用的に高速なアルゴリズムの開発

工学上の重要な問題の多くは凸計画問題に定式化できる.とくに組合せ計画問題の緩和問題や制御系の安定化問題などに見られる半正定値計画問題は,近年内点法に基づいた解法が効果的に適用できることがわかると,盛んに研究されるようになった.話題の中心は,アルゴリズムの収束性はもちろんのこと,その理論的な速さや,実際的な応用性についてである.特に後者に対しそは,現実的な問題に対する数値実験を行うことが重要である.これまで,半正定値計画問題に対する解法は内点法が中心で多くの文献が見られるが,ここではこの問題がある分離性をもった凸計画問題に再定式化できることに注目して,交互方向乗数法を適用することを考えている.この方法は分解法に分類される解法の1つであり,その理論的な部分はDouglas-Rachford法や近接点法などに基づいている.この場合の交互方向乗数法の収束性も同様に考えることができることがわかった.また,組合せ計画問題の例である最大クリーク問題などに対して実際に計算機実験を試みた.その結果,交互方向乗数法の欠点である反復回数の多いことは改善できなかったが,1回の反復に要する計算時間は少ないので,トータルで見ると希望の持てる解法であった.また,最近制御の問題を最適化問題として考えることが盛んで,内点法などの最適化の手法がどんどん適用されている.したがって,今後LMI,BMIなどを解くために提案するアルゴリズムを適用することを考えている.

工学上の重要な問題の多くは凸計画問題に定式化できる.とくに組合せ計画問題の緩和問題や制御系の安定化問題などに見られる半正定値計画問題は,近年内点法に基づいた解法が効果的に適用できることがわかると,盛んに研究されるようになった.話題の中心は,アルゴリズムの収束性はもちろんのこと,その理論的な速さや,実際的な応用性についてである.特に後者に対しそは,現実的な問題に対する数値実験を行うことが重要である.これまで,半正定値計画問題に対する解法は内点法が中心で多くの文献が見られるが,ここではこの問題がある分離性をもった凸計画問題に再定式化できることに注目して,交互方向乗数法を適用することを考えている.この方法は分解法に分類される解法の1つであり,その理論的な部分はDouglas-Rachford法や近接点法などに基づいている.この場合の交互方向乗数法の収束性も同様に考えることができることがわかった.また,組合せ計画問題の例である最大クリーク問題などに対して実際に計算機実験を試みた.その結果,交互方向乗数法の欠点である反復回数の多いことは改善できなかったが,1回の反復に要する計算時間は少ないので,トータルで見ると希望の持てる解法であった.また,最近制御の問題を最適化問題として考えることが盛んで,内点法などの最適化の手法がどんどん適用されている.したがって,今後LMI,BMIなどを解くために提案するアルゴリズムを適用することを考えている.