Lasserre/SOS SDP階層のPrimal/Dual

Sum of
Squares証明とLasserre階層の両方をSDPと表記することができます。これらのSDPが互いに重複しているという証拠なしに、しばしばクレームされていますが、これは明らかではありません。私は、これらが事実上互いにSDPのデュアルであることを証明する助けを得ることを望んでいました。

私は2つのSDPを述べ、その後いくつかの背景情報を述べます。 私たちは$ I subseteq [n]
$に対して複数の変数$ y_I $と$ | I | leq d $。 $ Y $を$ n d + 1 times n ^
d + 1 $次元の行列とし、複数の集合$ I subseteq [n] $、$ | I | leq d $とし、$ Y_
{I、J} = y_ {I cup J} $(複数集合体の下で)とする。 $ A $を対角行列とする。 $ B_I $、$ C_I
$を$ Y $と同じ次元の行列とする。トレースを以下のように定義する。A、B rangle = sum_ {i、j} A_
{i、j} B_ {i、j} $;ベクトルとして扱うと、$ A $と$ B $の間の内積です。原始のラッセルSDPを抽象的に

$$ max langle A、Y rangle \ sum_I y_I B_I succeq 0 \
sum_I y_I C_I succeq 0 \ y_ emptyset = 1 $$

すべての$ I neq emptyset $に対して、$ e_ emptyset = 1 $と$ e_I = 0
$となるベクトルを$ e in mathbb {R} ^ {n ^ d +1} $とする。デュアルは

$$ min lambda \ A_I – lambda e_I = langle Z_1、B_I
rangle + langle Z_2、C_I rangle hspace {3em} forall
subseteq [n]、| I | leq d \ Z_1 succeq 0 \ Z_2 succeq 0
$$

背景:多項式の$ P_0(x)$を超える$ P_1(x) geq 0 $を最適化しようとしているとします。
Lasserre階層はSDP緩和の階層であり、$ d $番目のレベルは次のように定義される。$ Y $を上記のように置き、$
p_0、p_1 in mathbb {R} ^ {n} d + 1} $をそれぞれ$
P_0(x)、P_1(x)$の係数ベクトルとする。つまり、$ p_ {0、I} $は、$ P_0(x)$の単項式$ prod_
{i in I} x_i $の係数です。

行列を定義する$ M(y):= Y $と$ M(y、P_1)_ {| I |、| J | leq d-deg(P_1)/
2}:= sum_ {| K |対角に$ p_0 $が配置された対角行列を$ P $とする。次に、初等度 – $ d $
Lasserre SDPは

$$ max P cdot Y \ M(y) succeq 0 \ M(y、P_1) succeq 0 \
y_ emptyset = 1 $$

We can obtain the primal SDP that I stated originally from the
Lasserre SDP by letting $B_I, C_I$ be such that $M(y) = sum_I B_I
y_I$ and $M(y,P_i) = sum_I C_I y_I$. For more information, I
recommend Chapter 1.7 in “Handbook on Semidefinite, Conic and
Polynomial Optimization” https://link.springer.com/book/10.1007%2F978-1-4614-0769-0#page14

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です