担当：柳澤 広大

題目：非負半正定値計画問題に対する切除平面法の適用

概要：
　組合せ最適化問題に対する半正定値緩和についてはこれまで多くの研究がなされており，その有効性が示されている．その一方で，近年では多くの組合せ最適化問題が完全正値錐上の最適化問題として同値に定式化できることが示され，完全正値という新たな方向性からの研究も盛んである[1]．ある行列が完全正値であるかどうかの判定は NP 困難であるため依然として緩和手法をとることが考えられているが，その中の一つとして非負半正定値緩和という手法がある．この緩和手法は半正定値緩和よりも高い精度を達成できる反面，計算コストが非常に高いという問題点がある[2]．
　そこで本研究では非負半正定値計画問題に対して切除平面法を用いることで，計算時間を削減することを提案した．また，提案手法の数値実験の結果を元の非負半正定値計画問題と比較することで性能の評価を行った．二次割当問題における非負半正定値緩和に対して提案手法を適用した数値実験結果を通して，非負半正定値緩和の高い精度を失うことなく計算時間が大きく削減されることが確認できた．

参考文献：
[1] S. Burer: On the copositive representation of binary and continuous nonconvex quadratic programs. Mathematical Programming, vol. 120 (2009), pp. 479-495.
[2] A. Yoshise and Y. Matsukawa: On optimization over the doubly nonnegative cone. Proceedings of 2010 IEEE Multi-conference on Systems and Control, Yokohama, September 2010, pp.13-19.