半正定値計画法

半正定値計画法（SDP）は、半正定値行列の円錐とアフィン空間、すなわちスペクトル面体との交差上で線形目的関数（ユーザーが最小化または最大化したいユーザー指定の関数）の最適化に関係する数学的計画法のサブフィールドです。^[1]

半正定値計画法は、いくつかの理由から関心が高まっている最適化の比較的新しい分野です。オペレーションズリサーチや組み合わせ最適化における多くの実際的な問題は、半正定値計画法の問題としてモデル化または近似できます。自動制御理論では、SDP は線形行列不等式のコンテキストで使用されます。SDP は実際には円錐計画法の特殊なケースであり、内点法によって効率的に解くことができます。すべての線形計画法と (凸) 2 次計画法はSDP として表現でき、SDP の階層を介して多項式最適化問題の解を近似できます。半正定値計画法は、複雑なシステムの最適化に使用されています。近年、一部の量子クエリ複雑性の問題が半正定値計画法の観点から定式化されています。

線形計画問題とは、多面体上の実変数の線形目的関数を最大化または最小化する問題です。半正定値計画では、代わりに実数値ベクトルを使用し、ベクトルのドット積を取ることができます。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{subject to}}&{\displaystyle \sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}}{\text{ for all }}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}}$

行列が半正定値行列であるとは、それが何らかのベクトルのグラム行列である場合（つまり、すべての に対してとなるようなベクトルが存在する場合）、、言われます。この場合、これを と表記します。半正定値行列の同等の定義は他にもいくつかあることに注意してください。たとえば、半正定値行列は、非負の固有値のみを持つ自己随伴行列です。 ${\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}$${\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 のままです。 を確実にするために、すべての に対して 、制約を追加できます。別の例として、任意の半正定値行列に対して、の、エントリが および のスカラー積であるようなベクトルの集合が存在することに注意してください。したがって、SDPは多くの場合、ベクトルのスカラー積に関する線形式として定式化されます。標準形式の SDP の解が与えられれば、ベクトルは時間内に回復できます(たとえば、X の不完全コレスキー分解を使用することによって)。 ${\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}}$${\displaystyle \{v_{i}\}}$${\displaystyle O(n^{3})}$

半正定値行列の空間は凸錐です。したがって、SDP は円錐最適化の特殊なケースであり、円錐最適化は凸最適化の特殊なケースです。

行列Cが対角行列の場合、内積 < C , X > は、 Cの対角要素とXの対角要素のベクトル積に相当します。同様に、行列A _kが対角行列の場合、対応する内積はベクトル積に相当します。これらのベクトル積では、Xの対角要素のみが使用されるため、 Xの非対角要素を0 にするという制約を追加できます。この条件は、 Xのすべての対角要素が非負であるという条件に相当します。その結果得られる SDP は、変数がXの対角要素である線形計画になります。 ${\displaystyle X\succeq 0}$

線形計画法と同様に、次のような一般的な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) が 以下に有界かつ厳密に実行可能であると仮定する（すなわち、 、 となるような問題が存在する） 。すると、 (D-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^{*}}$

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

(ii) 双対問題(D-SDP)が上方に有界であり厳密に実行可能であると仮定する(つまり、 ある に対して)。このとき、(P-SDP)の最適解が存在し、(i)の等式が成り立つ。 ${\displaystyle \sum _{i=1}^{m}(y_{0})_{i}A_{i}\prec C}$${\displaystyle y_{0}\in \mathbb {R} ^{m}}$${\displaystyle X^{*}}$

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}}}$

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

${\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 に緩和します。
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 を解くと、 の単位ベクトルのセットが得られます。ベクトルは共線である必要がないため、この緩和されたプログラムの値は、元の 2 次整数プログラムの値よりも高くなるだけです。最後に、パーティションを取得するには丸め手順が必要です。Goemans と Williamson は、原点を通る一様ランダムな超平面を選択し、対応するベクトルが超平面のどちら側にあるかに応じて頂点を分割します。簡単な分析により、この手順で予想される近似比(パフォーマンス保証) 0.87856 - ε が達成されることがわかります。 （カットの期待値は、エッジがカットされる確率のエッジ全体にわたる合計であり、これは、エッジの端点のベクトル間の角度に比例します。この確率を と比較すると、期待値では、比率は常に少なくとも 0.87856 になります。）ユニーク ゲーム予想を仮定すると、この近似比率が本質的に最適であることが示されます。 ${\displaystyle \mathbf {R^{n}} }$${\displaystyle \cos ^{-1}\langle v_{i},v_{j}\rangle }$${\displaystyle \pi }$${\displaystyle (1-\langle v_{i},v_{j}\rangle )/{2}}$

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

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

半正定値実行可能性問題( SDF) は、次のような決定問題です。SDP が与えられた場合、少なくとも 1 つの実行可能な解が存在するかどうかを判断します。この問題の正確な実行時複雑度は不明です (1997 年現在)。ただし、ラマナは次のことを証明しました。^[2]

• チューリング マシンモデルでは、SDF が NP に属する場合と、SDF が co-NP に属する場合とで同じです。したがって、NP = coNP でない限り、SDF は NP 完全ではありません。
• Blum-Shub-Smale マシンモデルでは、SDF は NP と co-NP の交差点にあります。

SDP を解決するためのアルゴリズムにはいくつかの種類があります。これらのアルゴリズムは、プログラム記述のサイズと多項式である時間の加算誤差までの SDP の値を出力します。 ${\displaystyle \epsilon }$${\displaystyle \log(1/\epsilon )}$

楕円体法は凸計画法の一般的な方法であり、特にSDPを解くために使用できます。SDPのコンテキストでは、楕円体法は次の保証を提供します。^{[1] ：Thm.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 は次のように記述できます。 。SDP のすべての係数が有理数であるとします。R を、実行可能解の最大フロベニウス ノルムの明示的に与えられた上限とし、ε> 0 を定数とします。 S ^{n内の行列}X は、 Xからのフロベニウス距離が最大でεであるL内のすべての行列Y が実行可能性条件 を満たす場合、 ε 深であると呼ばれます。と表記します。楕円体は、次のいずれかの出力を返します。 ${\displaystyle \max _{X\in L}\langle C,X\rangle {\text{ subject to }}X\succeq 0}$${\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]}はこのアプローチに基づいています。

円錐最適化のための一次法は、大きなヘッセ行列の計算、保存、因数分解を回避し、精度が多少犠牲になるものの、内点法よりもはるかに大きな問題に拡張できます。一次法は、分割円錐ソルバー (SCS) に実装されています。^[9]もう 1 つの一次法は、交互方向乗数法(ADMM) です。^[10]この方法では、各ステップで半正定値行列の円錐への投影が必要です。

コード ConicBundle は、SDP 問題を非滑らかな最適化問題として定式化し、非滑らかな最適化のスペクトル バンドル法によって解決します。このアプローチは、特殊なクラスの線形 SDP 問題に非常に効率的です。

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

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

顔縮小アルゴリズムは、問題の制約を検査することでSDP問題を前処理するために使用されるアルゴリズムです。これらは、

• 厳密な実現可能性の欠如を検出します。
• 冗長な行と列を削除します。
• 変数行列のサイズを縮小する。^[14]

• 平方根和問題- SDP 実現可能性問題の特殊なケース。

• Lieven Vandenberghe、Stephen Boyd、「半定値プログラミング」、SIAM Review 38、1996 年 3 月、pp. 49–95。pdf
• Monique Laurent、Franz Rendl、「半正定値計画法と整数計画法」、レポート PNA-R0210、CWI、アムステルダム、2002 年 4 月。optimization-online
• E. de Klerk、「半正定値計画法の側面: 内点アルゴリズムと選択されたアプリケーション」、Kluwer Academic Publishers、2002 年 3 月、ISBN 1-4020-0547-4。 
• Robert M. Freund、「半正定値計画法 (SDP) 入門」、SDP 入門

• 分野別の紹介やイベントへのリンク
• László Lovászによる半正定計画法に関する講義ノート