対称錐線形計画に対する内点法に関する研究

点击翻译按钮获取中文摘要

昨年度の終わりに,対称錐上の線形計画に対し,Commutative ClassおよびPower Classの探索方向を用いた内点法アルゴリズムに関して,計算複雑度を計算することができた.このPower Classある実数p>0でパラメタ化されており,これを使ったロングステップ内点法の計算複雑度はpに依存するものになる.既存の有力な方法であるNesterov-Toddの方向およびHRVW/KSH/M方向は,このPower Classの特殊な場合に該当することがわかった.これらの研究を受け継いで,今年度はまず,対称錐上の線形計画の一種である2次錐計画に対する内点法で,Power Classを用いるものを実装し,その効率の研究を行なった.特にNP困難な組合せ最適化問題の一種であるMax-Cut問題に対し,2次錐計画を用いた有効な緩和間題を提案し、これを実装した内点法によって解くことによりその有効性を確認した.これらの結果は,日本応用数理学会年会および統計数理研究所で行なわれた研究集会・最適化において発表された.また,論文"A New SOCP relaxation for MAX-CUT problems"となった.さらに,対称錐上の線形計画の一種である半正定値計画に関して、今回得られた知見から,強多項式で解ける問題のクラスを発見した.これは香港で行われたICOTA (International Conference on Optimization Technique and its Application) 2001において発表され,論文"A unified class of directly solvable semidefinite programming problems"となった.