修士論文 要旨

多項式計画問題とその緩和法に関する研究
数理情報学専攻 48096210
指導教員

1 多項式計画問題と半正定値計画緩和

勝見佑平
室田一雄 教授

2 研究内容多 項 式 計 画 問 題 と は ，多 変 数 の 実 係 数 多 項 式

本研究では，Lasserre [2] によって示された SDP 緩

g1 , . . . , gm ∈ R[x] によって記述される制約条件を満和による手法が理論的に優れているものであることをたす x ∈ R のうち，目的関数 p ∈ R[x] を最小にする保証する二つの定理

nような解 x∗ ，及び最小値 p∗ を求める問題である:∗p = inf n p(x)x∈Rs.t. g1 (x) ≥ 0, . . . , gm (x) ≥ 0.

• R[x] における「非負多項式の特徴を与える定理(1)（Positivstellensatz）」• その双対空間 (R[x])∗ における，「ある測度が存在ここで，x(= (x1 , . . . , xn )) は n 個の変数であり，R[x] =R[x1 , . . . , xn ] は実係数多項式の環である．

して，積分の形で書けるような線形汎関数の特徴を与える定理」

多項式計画問題は記述力が高く，例えば，複数の多項に注目する．前者の定理は 1900 年に Hilbert によって式の共通の実零点を求める問題や 0-1 線形計画問題が提唱された非負多項式と SOS（Sums Of Squares）多(1) の形で表現できる．このことから多項式計画問題は項式の関係を問う Hilbert の第 17 番目の問題に端を発一般に変数の次元 n と制約条件の数 m の多項式に比例し，また後者の定理も 20 世紀初頭から研究が続くモーする時間で解くことは難しいと考えられている．このメント問題として知られる関数解析学の一分野が起源問題 (1) に対する統一的なアプローチとして，半正定値である．

計画緩和によって近似する手法が Lasserre [2] によって

本研究では多項式システムが空である証拠を解とし確立され，以後，様々な利点が明らかになっている．てもつ SDP の実行可能性判定問題を与える定理とし半正定値計画緩和（以下，SDP 緩和）とは，元の問て，Farkas の補題を始めとする一連の二者択一定理，非題を近似するような半正定値計画問題（SemiDefinite

負多項式の特徴を与える定理，零点定理を整理する．まProgram，以下 SDP）を構成し，元の問題の近似的なた，それらの定理の最適化問題への応用として，多項式解を得る手法である．n × n 対称行列の空間を S n と書計画問題の最適値が入力の多項式サイズの SDP を解くくことにする．行列 A ∈ S n , C ∈ S n , ベクトル b ∈ Rn

ことで得られる場合の例を示す．例えば，目的関数 f がが与えられたとき，SDP は次のように定式化される:

4 次の凸関数，4 次以下の凸関数 g1 , . . . , gm から定まる

minn C • X

X∈S(2)

s.t. Ai • X = bi (i = 1, . . . , m)
X ≽ O.
ここで，演算 • は 2 つの対称行列に関して A • B :=Tr(AB) と定義される．SDP には内点法と呼ばれる，任意の精度の解を n, m の多項式時間で計算するアルゴリズムが存在し，現在様々なソルバに実装されている．

m 個の制約条件 gi (x) ≤ 0 (i = 1, . . . , m) からなる凸4 次計画問題は凸集合の分離定理から示される基本的な二者択一定理を用いて双対問題を構成し，多項式の非負多項式計画問題とその緩和法に関する研究 (勝見佑平)

制約を緩和することで次の SDP 緩和問題が得られる:

supCurto–Fialkow [1] の定理が証明できることがわかる．
なお，このロジックによる定理の証明の核となる道具ρρ∈R, y∈Rmは，Laurent [3]，Laurent and Rostalski [4] によってs.t. [f − ρ]α +m∑

yi gα = A • Bα

i=1

すでに言及されている定理である．

3 結果と今後の課題∀α : |α| ≤ 2,A ≽ O,
yi ≥ 0 (i = 1, . . . , m).

本論文では以下の 3 点を扱った．

• 凸解析の分野の二者択一定理や非負多項式の特徴

ここで，Bα は各 α ∈ Zn+ に対して定義される定数行列を与える定理，零点定理などを整理した．また，S-である．2 変数 (n = 2) の場合はスレーター条件の仮定補題や凸関数に関する二者択一定理を応用して簡の下，この SDP 緩和問題の最適値と元の問題の最適値単な緩和問題を構成し，多項式時間で最適値が計算は等しくなる．この問題のサイズは O(m + n2 ) であり，できる多項式計画問題の問題例を示した．

n と m の多項式に比例する時間で最適値を計算するこ• モーメント問題における Curto–Fialkow [1] によとができる．元の問題の制約条件の最大次数が 4 のとる定理に対して，モーメント行列の半正定値性のき，Lasserre [2] の SDP 緩和の階層の一番簡単な問題

意味をとらえるために，半正定値とは限らない一に一致し，制約条件の最大次数が 2 以下のとき，その一般のモーメント行列の分解 [4] を利用して別証を与番簡単な問題よりさらに簡単な緩和問題となっている．

えた．

∗

一方，双対空間 (R[x])に関する定理の研究として，モーメント行列の半正定値性に関する考察を行う．

• Lasserre [2] による SDP 緩和の手法と，その利点についてまとめた．

(R[x])∗ の各元は，対応する実数列 y ∈ RZ+ と同一視nすることができる．この y に関して α 行 β 列の要素がyα+β であるような可算無限のサイズの行列 M (y) は多項式計画問題の最適値がサイズの小さな緩和問題の最適値として計算できる例が多く報告されている．

モーメント行列と呼ばれる．実数列 y ∈ RZ+ が与えら本研究で扱った特殊ケースを足がかりに，なぜ最適値がれたとき，それをモーメントとしてもつ Rn 上のボレル得られるのか考察することが今後の課題である．

測度 µ が存在する（y は表現測度 µ をもつ，という）た

参考文献

nめの条件を問う問題はモーメント問題と呼ばれる重要な問題である．モーメント行列の半正定値性は，y が表現測度 µ をもつための必要条件であり，n = 1 の場合は十分でもあること，n ≥ 2 の場合は一般に十分でないことなどがわかっている．本研究では，Curto–Fialkow[1] による「モーメント行列のランクが有限ならば，モーメント行列の半正定値性は y が表現測度 µ をもつための必要十分条件である」という定理の証明を，半正定値とは限らない一般の複素数値モーメント行列の性質だ
けでどこまで議論が進むのかを調査することで，半正定値性が何において重要かを明らかにする．結果として，

C[x] のイデアルである ker M (y) の共通の零点の集合
V (ker M (y)) に注目したとき，M (y) が実対称半正定値ならば，V (ker M (y)) の元が全て実かつ単根である，という事実のみに半正定値性を利用することで上述の[1] R. E. Curto and L. A. Fialkow. Solution of truncatedcomplex moment problem for flat data. Memoirs of
the American Mathematical Society, Vol. 119, No. 568,
1996.
[2] J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on
Optimization, Vol. 11, pp. 796–817, 2001.
[3] M. Laurent. Revisiting two theorems of Curto and Fialkow on moment matrices. Proceedings of the American Mathematical Society, Vol. 133, pp. 2965–2976,
2005.
[4] M. Laurent and P. Rostalski. The approach of moments for polynomial equations. In Handbook on
Semidefinite, Cone and Polynomial Optimization. toappear.