半正定値計画法

線形計画問題とは、多面体上の実変数の線形目的関数を最大化または最小化しようとする問題です。半正定値計画法では、代わりに実数値ベクトルを使用し、ベクトルの内積を取ることができます。線形計画法（LP）における実変数の非負制約は、半正定値計画法（SDP）における行列変数の半正定値制約に置き換えられます。具体的には、一般的な半正定値計画問題は、次の形式の任意の数理計画問題として定義できます。

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n}}}&{\displaystyle \sum _{i,j\in [n]}c_{i,j}(x^{i}\cdot x^{j})}\\{\text{制約条件}}&{\displaystyle \sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}}{\text{すべての }}k について}\\\end{array}}}$

どこで${\displaystyle c_{i,j},a_{i,j,k}}$、そして${\displaystyle b_{k}}$は実数であり、${\displaystyle x^{i}\cdot x^{j}}$はドット積です${\displaystyle x^{i}}$そして ${\displaystyle x^{j}}$。

1${\displaystyle n\times n}$マトリックス${\displaystyle M}$がいくつかのベクトルのグラム行列である場合、正半定値であると言われます（つまり、ベクトルが存在する場合）。${\displaystyle x^{1},\ldots ,x^{n}}$そのため${\displaystyle m_{i,j}=x^{i}\cdot x^{j}}$すべての人々のために${\displaystyle i,j}$) この場合、これを次のように表記します。${\displaystyle M\succeq 0}$。なお、正定値半正定値であることには他にもいくつかの同等の定義があります。例えば、正定値半正定値行列は、非負の固有値のみを持つ自己共役行列です。

で表す$\displaystyle \mathbb {S} ^{n}}$すべての空間${\displaystyle n\times n}$実対称行列。空間には内積（ここで）が備わっています。${\displaystyle {\rm {trace}}}$トレースを表します):

${\displaystyle \langle A,B\rangle$ :={\rm {trace}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}.}

前の節で示した数理計画問題は、以下のように書き換えることができる。

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{k},X\rangle \leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}}$

エントリー${\displaystyle i,j}$で${\displaystyle C}$は${\displaystyle {\frac {c_{i,j}+c_{j,i}}{2}}}$前のセクションから、${\displaystyle A_{k}}$対称的である${\displaystyle n\times n}$行列${\displaystyle i,j}$th エントリ${\displaystyle {\frac {a_{i,j,k}+a_{j,i,k}}{2}}}$前のセクションから。したがって、行列は ${\displaystyle C}$そして${\displaystyle A_{k}}$対称性があり、上記の内積は明確に定義されます。

適切なスラック変数を追加すれば、このSDPは等式形式に変換できることに注意してください。

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{k},X\rangle =b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}}$

便宜上、SDPは若干異なるものの同等の形式で指定されることがあります。例えば、非負のスカラー変数を含む線形式をプログラム仕様に追加することができます。各変数を行列に組み込むことができるため、これは依然としてSDPです。${\displaystyle X}$斜めのエントリーとして（${\displaystyle X_{ii}}$一部の人にとって${\displaystyle i}$)を確実にするために${\displaystyle X_{ii}\geq 0}$制約${\displaystyle X_{ij}=0}$すべてに追加できます${\displaystyle j\neq i}$別の例として、任意の正定値半正定値行列について、${\displaystyle X}$ベクトルの集合が存在する${\displaystyle \{v_{i}\}}$そのため${\displaystyle i}$、${\displaystyle j}$エントリー${\displaystyle X}$は${\displaystyle X_{ij}=(v_{i},v_{j})}$スカラー積​${\displaystyle v_{i}}$そして${\displaystyle v_{j}}$したがって、SDPはベクトルのスカラー積に関する線形式で表されることが多い。標準形式のSDPの解が与えられた場合、ベクトルは${\displaystyle \{v_{i}\}}$回復可能${\displaystyle O(n^{3})}$時間（例えば、Xの不完全なコレスキー分解を使用することによって）。

線形計画法と同様に、次の形式の一般的なSDPが与えられた場合

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{i},X\rangle =b_{i},\quad i=1,\ldots ,m\\&X\succeq 0\end{array}}}$

（主問題またはP-SDP）に対して、双対半正定値計画（D-SDP）を次のように定義する。

${\displaystyle {\begin{array}{rl}{\displaystyle \max _{y\in \mathbb {R} ^{m}}}&b^{T}y\\{\text{subject to}}&{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}}$

任意の2つの行列に対して${\displaystyle P}$そして${\displaystyle Q}$、${\displaystyle P\succeq Q}$手段${\displaystyle P-Q\succeq 0}$。

弱双対性定理によれば、主SDPの値は双対SDPの値以上である。したがって、双対SDPの任意の実行可能解は主SDPの値の下限となり、逆に主SDPの任意の実行可能解は双対SDPの値の上限となる。これは、

${\displaystyle \langle C,X\rangle -b^{T}y=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}b_{i}=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}\langle A_{i},X\rangle =\langle C-\sum _{i=1}^{m}y_{i}A_{i},X\rangle \geq 0,}$

最後の不等式は、両方の行列が正半定値であるためであり、この関数の結果は双対ギャップと呼ばれることもあります。

主SDPと双対SDPの値が等しい場合、SDPは強双対性を満たすと言われます。線形計画問題では、すべての双対線形計画問題の最適目的関数は主目的関数と等しくなりますが、すべてのSDPが強双対性を満たすわけではありません。一般に、双対SDPの値は主SDPの値より厳密に小さい場合があり、P-SDPとD-SDPは次の性質を満たします。

（i）主問題（P-SDP）が下限を持ち厳密に実行可能であると仮定する（すなわち、 ${\displaystyle X_{0}\in \mathbb {S} ^{n},X_{0}\succ 0}$そのため${\displaystyle \langle A_{i},X_{0}\rangle =b_{i}}$、${\displaystyle i=1,\ldots ,m}$そうすれば最適な解が存在する。${\displaystyle y^{*}}$(D-SDP) および

${\displaystyle \langle C,X^{*}\rangle =b^{T}y^{*}.}$

（ii）双対問題（D-SDP）が上界を持ち、厳密に実行可能であると仮定します（すなわち、 ${\displaystyle \sum _{i=1}^{m}(y_{0})_{i}A_{i}\prec C}$一部の人にとって${\displaystyle y_{0}\in \mathbb {R} ^{m}}$そうすれば最適な解が存在する。${\displaystyle X^{*}}$(P-SDP) となり、(i) の等式が成り立つ。

SDP問題（および一般に任意の凸最適化問題）に対して強双対性が成り立つための十分条件は、スレーター条件です。ラマナによって提案された拡張双対問題を使用することで、追加の正則性条件なしでSDPの強双対性を達成することも可能です。^{[ 2 ] [ 3 ]}

3つの確率変数を考える${\displaystyle A}$、${\displaystyle B}$、 そして${\displaystyle C}$与えられた相関係数のセット${\displaystyle \rho _{AB},\ \rho _{AC},\rho _{BC}}$可能なのは、

${\displaystyle {\begin{pmatrix}1&\rho _{AB}&\rho _{AC}\\\rho _{AB}&1&\rho _{BC}\\\rho _{AC}&\rho _{BC}&1\end{pmatrix}}\succeq 0.}$

この行列は相関行列と呼ばれます。例えば、実験の経験的結果など、何らかの事前知識から次のことがわかっているとします。${\displaystyle -0.2\leq \rho _{AB}\leq -0.1}$そして${\displaystyle 0.4\leq \rho _{BC}\leq 0.5}$最小値と最大値を決定する問題は、${\displaystyle \rho _{AC}\ }$取得できる値は次のように与えられます。

${\displaystyle {\begin{array}{rl}{\displaystyle \min /\max }&x_{13}\\{\text{subject to}}&-0.2\leq x_{12}\leq -0.1\\&0.4\leq x_{23}\leq 0.5\\&{\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0\end{array}}}$

私たちは設定しました${\displaystyle \rho _{AB}=x_{12},\ \rho _{AC}=x_{13},\ \rho _{BC}=x_{23}}$答えを得るために。これはSDPで定式化できます。不等式制約は、変数行列を拡張し、スラック変数を導入することで処理します。例えば、

${\displaystyle \mathrm {tr} \left(\left({\begin{array}{cccccc}0&1&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&1&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right)\cdot \left({\begin{array}{cccccc}1&x_{12}&x_{13}&0&0&0\\x_{12}&1&x_{23}&0&0&0\\x_{13}&x_{23}&1&0&0&0\\0&0&0&s_{1}&0&0\\0&0&0&0&s_{2}&0\\0&0&0&0&0&s_{3}\end{array}}\right)\right)=x_{12}+s_{1}=-0.1}$

このSDPを解くと、以下の最小値と最大値が得られます。${\displaystyle \rho _{AC}=x_{13}\ }$として${\displaystyle -0.978}$そして${\displaystyle 0.872}$それぞれ。

問題を考察する

最小限に抑える${\displaystyle {\frac {(c^{T}x)^{2}}{d^{T}x}}}$

対象${\displaystyle Ax+b\geq 0}$

ここで我々は、${\displaystyle d^{T}x>0}$いつでも${\displaystyle Ax+b\geq 0}$。

補助変数の導入${\displaystyle t}$この問題は次のように言い換えることができる。

最小限に抑える${\displaystyle t}$

対象${\displaystyle Ax+b\geq 0,\,{\frac {(c^{T}x)^{2}}{d^{T}x}}\leq t}$

この定式化では、目的は変数の線形関数である。${\displaystyle x,t}$。

最初の制約は次のように書ける。

${\displaystyle {\textbf {diag}}(Ax+b)\geq 0}$

行列${\displaystyle {\textbf {diag}}(Ax+b)}$対角要素の値がベクトルの要素と等しい正方行列${\displaystyle Ax+b}$。

2番目の制約は次のように書ける。

${\displaystyle td^{T}x-(c^{T}x)^{2}\geq 0}$

定義する${\displaystyle D}$次のように

${\displaystyle D=\left[{\begin{array}{cc}t&c^{T}x\\c^{T}x&d^{T}x\end{array}}\right]}$

シュール補元理論を用いると、

${\displaystyle D\succeq 0}$

（ボイドとヴァンデンベルゲ、1996年）

この問題に関連する半正定値計画問題は

最小限に抑える${\displaystyle t}$

対象${\displaystyle \left[{\begin{array}{ccc}{\textbf {diag}}(Ax+b)&0&0\\0&t&c^{T}x\\0&c^{T}x&d^{T}x\end{array}}\right]\succeq 0}$

半正定値計画法は、NP困難な最大化問題の近似アルゴリズムを開発するための重要なツールです。SDPに基づく最初の近似アルゴリズムは、Michel GoemansとDavid P. Williamsonによるものです（JACM、1995年）。^{[ 1 ]：第1章} 彼らは最大カット問題を研究しました。グラフG = ( V、E )が与えられたとき、一方の側から他方の側へ交差するエッジの数を最大化するように頂点Vの分割を出力します。この問題は、整数二次計画法として表現できます。

最大化する${\displaystyle \sum _{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2}},}$それぞれ${\displaystyle v_{i}\in \{1,-1\}}$。

P = NPでない限り、この最大化問題を効率的に解くことはできません。しかし、GoemansとWilliamsonは、この種の問題に取り組むための一般的な3段階の手順を発見しました。

1. 整数二次計画問題をSDPに緩和する。（これは、平方和階層の第1レベルを使用しても導出できる。）
2. SDPを解く（任意に小さな加法誤差の範囲内で）${\displaystyle \epsilon }$)
3. SDPの解を丸めて、元の整数二次計画問題の近似解を得る。

最大限のカット効果を得るには、最も自然なリラックス法は

${\displaystyle \max \sum _{(i,j)\in E}{\frac {1-\langle v_{i},v_{j}\rangle }{2}},}$そのため${\displaystyle \lVert v_{i}\rVert ^{2}=1}$ここで、最大化はベクトルに対して行われる。${\displaystyle \{v_{i}\}}$整数スカラーの代わりに。

これは、目的関数と制約条件がすべてベクトル内積の線形関数であるため、SDPです。SDPを解くと、次の単位ベクトルのセットが得られます。${\displaystyle \mathbf {R^{n}} }$ベクトルは共線である必要がないため、この緩和されたプログラムの値は、元の二次整数計画の値よりも高くなるだけです。最後に、分割を得るために丸め手順が必要です。GoemansとWilliamsonは、原点を通る一様ランダムな超平面を選択し、対応するベクトルが超平面のどちら側にあるかに応じて頂点を分割します。簡単な分析により、この手順で期待近似比（性能保証）が0.87856 - εに達することが示されています。（カットの期待値は、エッジがカットされる確率のエッジごとの合計であり、これは角度に比例します。）${\displaystyle \cos ^{-1}\langle v_{i},v_{j}\rangle }$エッジの端点のベクトル間の${\displaystyle \pi }$この確率を${\displaystyle (1-\langle v_{i},v_{j}\rangle )/{2}}$期待値として、この比率は常に少なくとも 0.87856 である。）ユニークゲーム予想を仮定すると、この近似比率が本質的に最適であることが示される。

GoemansとWilliamsonの最初の論文以来、SDPは数多くの近似アルゴリズムの開発に応用されてきた。その後、Prasad Raghavendraは、ユニークゲーム予想に基づいて制約充足問題の一般的なフレームワークを開発した。^{[ 4 ]}

半正定値計画法は、最大カット問題の解法のように、組み合わせ最適化問題の近似解を求めるために適用されており、その近似比は 0.87856 です。SDP は、幾何学ではテンセグリティ グラフを決定するためにも使用され、制御理論ではLMIとして、逆楕円係数問題では凸非線形半正定値制約として現れます。^{[ 5 ]}また、共形ブートストラップを使用して共形場理論を制約するために物理学で広く使用されています。^{[ 6 ]}

楕円体法は凸計画法の一般的な方法であり、特にSDPを解くために使用できます。SDPの文脈では、楕円体法は次の保証を提供します。^{[ 1 ]：定理2.6.1}次の等式形式のSDPを考えます。

${\displaystyle {\begin{array}{rl}{\displaystyle \max _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{k},X\rangle =b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}}$

L を、 m 個の等式制約を満たすS ⁿ内の行列のアフィン部分空間とします。したがって、SDP は次のように記述できます。${\displaystyle \max _{X\in L}\langle C,X\rangle {\text{ subject to }}X\succeq 0}$SDP のすべての係数が有理数であると仮定します。実行可能解の最大フロベニウスノルムの上限を明示的にRとし、 ε> 0 を定数とします。S ⁿの行列Xは、 Lの任意の行列Y がXからフロベニウス距離が最大εであり、かつ実行可能性条件を満たす場合、 ε-ディープと呼ばれます。${\displaystyle Y\succeq 0}$. 表記する${\displaystyle v_{deep}:=\sup\{\langle C,X\rangle :X{\text{ is }}\epsilon {\text{-deep}}\}}$楕円体は、以下のいずれかの出力を返します。

• L 内の行列 X* (すなわち、すべての線形等式制約を厳密に満たす) であって、X* と何らかの実行可能解との間のフロベニウス距離が最大でε (すなわち、不等式制約を近似的に満たす) である。${\displaystyle X\succeq 0}$）、 そして${\displaystyle \langle C,X^{*}\rangle \geq v_{deep}-\epsilon }$（つまり、ほぼ最適な目的値）。
• その問題にはε深解が存在しない（つまり、その問題は近似的に実行不可能である）ことを証明する証明書。

実行時間は、入力のバイナリ符号化と、チューリングマシンモデルにおける log(R/ ε )に関して多項式になります。

一般に、R はnに対して二重指数関数的になる可能性があることに注意してください。その場合、楕円体法の実行時間保証はnに対して指数関数的になります。しかし、ほとんどのアプリケーションでは、Rはそれほど大きくありません。このような場合、楕円体法は、チューリングマシンモデルで多項式実行時間を保証する唯一の既知の方法です。^{[ 1 ] : 23}しかし、実際には、そのパフォーマンスはそれほど良くありません。

ほとんどのコードは内点法（CSDP、MOSEK、SeDuMi、SDPT3 、DSDP、SDPA）に基づいています。これらは一般的な線形SDP問題に対して堅牢かつ効率的ですが、アルゴリズムが2次法であり、大きな（そして多くの場合密な）行列を保存して因数分解する必要があるという事実によって制限されます。理論的には、最先端の高精度SDPアルゴリズム^{[ 7 ] [ 8 ]}はこのアプローチに基づいています。

円錐最適化の一次法は、大きなヘッセ行列の計算、保存、因数分解を回避し、精度を多少犠牲にする代わりに、内点法よりもはるかに大きな問題に対応できます。一次法は、Splitting Cone Solver (SCS) に実装されています。^{[ 9 ]}もう 1 つの一次法は、交互方向乗数法(ADMM) です。^{[ 10 ]}この方法は、各ステップで半正定値行列の円錐への射影を必要とします。

ConicBundleというコードは、SDP問題を非平滑最適化問題として定式化し、非平滑最適化のスペクトルバンドル法を用いて解きます。この手法は、特定の種類の線形SDP問題に対して非常に効率的です。

拡張ラグランジュ法に基づくアルゴリズム（PENSDP）は、内点法と同様の挙動を示し、非常に大規模な問題に特化することができます。他のアルゴリズムは、低ランク情報を使用し、SDPを非線形計画問題として再定式化します（SDPLR、ManiSDP）。^{[ 11 ]}

SDP を近似的に解くアルゴリズムも提案されています。このような方法の主な目的は、近似解で十分であり、複雑さを最小限に抑える必要があるアプリケーションで、より低い複雑さを実現することです。多入力多出力 (MIMO) 無線システムでのデータ検出に使用されている著名な方法は、半正定値行列ではなく半正定値行列のコレスキー分解因子に基づいて動作する Triangular Approximate SEmidefinite Relaxation (TASER) [ 12 ] です。^{この方法は}、最大カットのような問題の近似解を計算し、多くの場合、正確な解法による解に匹敵しますが、アルゴリズムの反復回数はわずか 10 ～ 20 回です。Hazan ^{[ 13 ]}は、変数行列のトレースが 1 でなければならないという追加の制約を持つ SDP を解くための近似アルゴリズムを開発しました。