Semidefinite programming reformulation for a class of robust optimization problems and its application to robust Nash equilibrium problems

摘要

ロバスト最適化とは，情報に不確実性を持つ数理計画問題を取り扱うための最適化手法のーつである．近年，理論的な研究だけでく，金融工学，生産計画などへ数多くの応用研究がなされており，大きな注目を集めている．特に，ロバスト最適化の考え方を効果的に適用するためには，半正定値計画問題(SDP: SemiDefinite Program) などの効率的なアルゴリズムが存在するクラスの問題へ再定式化することが重要となる．Ben-TalとNemirovski[2]は，不確実性集合が楕円体で表される線形計画問題が，SDPに再定式化できることを示した．しかし，二次錐計画問題(SOCP:Second-Order Cone Program)において不確実集合が楕円体によって表せる場合，SDPに再定式化できるかどうかは，特殊な場合を除き，長い間未解決問題であった[2 ].