疎性（多項式最適化問題の）

【 そせい（たこうしきさいてきかもんだいの） (sparsity in polynomial optimization problems) 】

多項式最適化問題において，変数の数 $n$, 最大次数 $m$ とした場合， 可能な全ての項の数は $\left({\begin{array}{c}n+m\\m\end{array}}\right)$ である．この数に比べ，ごく少数の項しか用いられていない場合， その多項式最適化問題は疎性を持つと言われる．実際には 多くの多項式最適化問題が疎性を持つと言われている． 多項式最適化問題の疎性を利用して，半正定値緩和問題のサイズを縮小する 様々な方法が提案されている．提案手法によって，疎性の定義も若干異なる．