制約および目的関数に多項式を用いた最適化問題を多項式最適化問題と言う。この種の最適化問題に対し，近年 Sums of Squares （SOS） 緩和やSDP 緩和と呼ばれる方法が提案され，効率的に大域的最適解が求まる方法として話題を呼んでいる。本講演の前半ではこれらの方法について解説する。後半では，この方法の問題点／改良点／拡張について，講演者が現在行なっている研究を中心に概説する。

（連絡先：コンピュータ科学専攻　今井浩, imai@is.s.u-tokyo.ac.jp）