脇 隼人情報・通信工学専攻・助教
研究テーマ：半正定値計画問題に対する面的縮小法とその応用
活動の概要
主に, 多項式最適化問題から生じる半正定値計画問題に対する効率的な求解法と, 半正定値計画問題の応用について共同研究を行った. 多項式最適化問題に関しては, いくつか成果があったので, 7で記載することにする.
行列補完問題に対して面的縮小法を適用することを行った. 行列補完問題は, 行列の一部分の値が与えられている状況で, 階数が最小の行列を求める問題である. これは, 半正定値計画問題を利用して凸計画問題として定式化できる. 本来は面的縮小法を適用しても, この半正定値計画問題のサイズを小さくできないのだが, 階数を前もって推定して固定することで, サイズを小さくすることができる. さらにこれにより, 数値的安定性を向上させることが期待できる. ただし, 応用上では, 数十万から数百万のサイズの行列に対する補完問題を考えているので, 更なる工夫が必要であり, 現在の課題となっている.
また, 線形計画問題に対する内点法の初期点に関する研究も行った. 線形計画問題に対する内点法は, 問題と初期点を与える必要ある. 特に, 実用上は, 係数行列や係数ベクトルを摂動した線形計画問題を頻繁に解く必要がある. この際, 適切な初期点を選ぶことで効率よく摂動された線形計画問題を解くことが本研究のテーマである. そのために, 内点法が辿る中心パスの性質を調べる必要があり, 中心パスを定義するパラメータを負にした場合の, 中心パスの性質と解の性質の関係をいくつか求めた. この関係から, 特定の場合は, 元の線形計画問題の最適解から数反復で摂動した線形計画問題の最適解に収束することがわかった. 帰国後もこの共同研究を続けている.
また, 出張を除いて下記の3件の発表を行った.
[1] Hayato Waki, ``On a smaller SDP relaxation for polynomial optimization”, Fields Institute, 2011, September.
[2] Hayato Waki, `` Strange Behaviors of Interior‐point Methods for Solving Semidefinite Programming Problems in Polynomial Optimization”, seminar by Advanced Optimization, McMaster University, 2011, September.
[3] Hayato Waki, ``SDP Relaxation for Polynomial Optimization Problems”, Tutte Seminar, University of Waterloo, 2011, June.
研究成果概要
半正定値計画問題を解く際に, しばしば数値的不安定な状況に陥ることがある. 今回の滞在では, この数値的不安定性を取り除くための手法である, 面的縮小法に関する研究を行った. 特に, 多項式最適化問題から生じる半正定値計画問題を対象にして, 数値的に頑強で効率的なアルゴリズムの提案・実装を行った.これにより, 定式化された半正定値計画問題のサイズを小さくするだけでなく, 数値的安定性も向上した.
また, 等式制約がある多項式最適化問題に対して, 等式制約を利用して生成される半正定値計画問題のサイズを小さくする手法が提案されているが, この手法が面的縮小法として解釈できることがわかった. これにより, 多項式最適化問題から生じる半正定値計画問題には面的縮小法が有効であることがわかった.
共同研究としては, 与えられた多項式最適化問題に対して, よりサイズの小さい半正定値計画問題を与える手法を提案した. これは, 既存の手法を最適化のアプローチで理解することで得られたものであり, この点は理論的な成果である. 実用上はこのままでは不十分だが, これまでに提案された手法を組み合わせることでより, 規模の大きい多項式最適化問題にも適用することできる. 数値実験では, いくつかの多項式最適化問題で有効であることがわかった. また, 双線形行列不等式を含むような最適化問題のクラスにおいても有効であることがわかった. 現在以上の内容をまとめている段階である.
国際化に関する所感及び提言
投稿論文の扱いや, 研究講演の依頼等を通して, 海外の研究者との個人的なネットワークの重要性を実感した. 本来ならば, 欧米の大学・研究機関には人が多いので, そこに所属することでより多くの質の高い研究を遂行できる可能性が高い. しかしながら, 海外の機関に所属することは難しく, このような派遣事業はそういったネットワークを構築するのには有用であると思われる.
作成日：2011年10月 1日 / 更新日：2011年11月18日
