「疎性(多項式最適化問題の)」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
("疎性(多項式最適化問題の)" を保護しました。 [edit=sysop:move=sysop])
 
(同じ利用者による、間の1版が非表示)
1行目: 1行目:
'''【 そせい(たこうしきさいてきかもんだいの)  
+
'''【 そせい(たこうしきさいてきかもんだいの) (sparsity in polynomial optimization problems) 】'''
(sparsity in polynomial optimization problems) 】'''
 
  
多項式最適化問題において,変数の数 <math>n</math>, 最大次数 <math>m</math> とした場合,
+
[[多項式最適化問題]]において,
可能な全ての項の数は <math>\left(\begin{array}{c} n+m\\ m \end{array}\right)</math>
+
変数の数<math>n</math>
である.この数に比べ,ごく少数の項しか用いられていない場合,
+
最大次数<math>m</math>とした場合,
その多項式最適化問題は疎性を持つと言われる.実際には
+
可能な全ての項の数は
多くの多項式最適化問題が疎性を持つと言われている.
+
<math>\left(\begin{array}{c} n+m\\ m \end{array}\right)</math>
多項式最適化問題の疎性を利用して,半正定値緩和問題のサイズを縮小する
+
である.
様々な方法が提案されている.提案手法によって,疎性の定義も若干異なる.
+
この数に比べ,ごく少数の項しか用いられていない場合,
 +
その多項式最適化問題は疎性を持つといわれる.
 +
実際には
 +
多くの多項式最適化問題が疎性を持つといわれている.
 +
多項式最適化問題の疎性を利用して,
 +
半正定値緩和問題のサイズを縮小する様々な方法が提案されている.
 +
提案手法によって,疎性の定義も若干異なる.

2007年9月20日 (木) 20:16時点における最新版

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

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