凸最適化のサブフィールド

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

半正定値計画法は、いくつかの理由から関心が高まっている最適化の比較的新しい分野です。オペレーションズリサーチや組み合わせ最適化における多くの実際的な問題は、半正定値計画法問題としてモデル化または近似できます。自動制御理論では、SDPは線形行列不等式のコンテキストで使用されます。SDPは実際には円錐計画法の特殊なケースであり、内点法によって効率的に解くことができます。すべての線形計画法と（凸）二次計画法は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 ]}

例

[編集]

例1

[編集]

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

例2

[編集]

問題を考えてみましょう

最小化 ${\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}$

例3（Goemans-Williamson最大カット近似アルゴリズム）

[編集]

半正定値計画法は、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でない限り、この最大化問題を効率的に解くことはできません。しかし、ゴーマンスとウィリアムソンは、この種の問題に取り組むための一般的な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を解くと、 における単位ベクトルの集合が得られます。ベクトルは共線的である必要がないため、この緩和された計画の値は、元の二次整数計画の値よりも高くなるだけです。最後に、分割を得るために丸め手順が必要です。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が与えられたとき、それが少なくとも一つの実行可能解を持つかどうかを判定する。この問題の正確な実行時計算量は不明である（1997年時点）。しかし、ラマナは次のことを証明した。^{[ 2 ]}

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

SDPを解くアルゴリズム

[編集]

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 をS ^{n内の行列の}m 個の等式制約を満たすアフィン部分空間とすると、SDP は次のように表すことができます。SDP のすべての係数が有理数であるとします。Rを、実行可能解の最大フロベニウスノルムの明示的に与えられた上限とし、ε> 0 を定数とします。S ⁿ内の行列X がε 深であるとは、 L内のXからのフロベニウス距離が最大εであるすべての行列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 ]}もう一つの一次法は、交互方向乗数法（ADMM）です。^{[ 10 ]}この方法では、各ステップで半正定値行列の円錐への射影が必要です。

バンドル法

[編集]

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

その他の解決方法

[編集]

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

近似法

[編集]

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

前処理アルゴリズム

[編集]

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

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

参照

[編集]

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

参考文献

[編集]

1. ゲルトナー、ベルント; Matoušek、Jiří (2012)、Gärtner、Bernd。 Matousek、Jiri (編)、「半正定計画法」、近似アルゴリズムと半正定計画法、ベルリン、ハイデルベルク: Springer、pp.  15–25、doi : 10.1007/978-3-642-22015-9_2、ISBN 978-3-642-22015-9、 2023年12月31日取得
2. Ramana, Motakuri V. (1997). 「半正定値計画法の正確な双対性理論とその計算量への影響」 .数理計画. 77 (1): 129– 162. doi : 10.1007/BF02614433 . ISSN 0025-5610 . S2CID 12886462 .  
3. Vandenberghe, Lieven; Boyd, Stephen (1996). 「半正定値計画法」 . SIAM Review . 38 (1): 49– 95. doi : 10.1137/1038003 . ISSN 0036-1445 . 
4. Raghavendra, Prasad (2008). 「あらゆるCSPに対する最適アルゴリズムと近似不可能性？」 .第40回ACMコンピューティング理論シンポジウム議事録. pp.  245– 254. doi : 10.1145/1374376.1374414 . ISBN 9781605580470. S2CID  15075197 .
5. Harrach, Bastian (2021)、「凸非線形半正定値計画法による逆楕円係数問題の解法」、Optimization Letters、16 (5): 1599– 1609、arXiv : 2105.11440、doi : 10.1007/s11590-021-01802-4、S2CID 235166806 
6. Simmons-Duffin, David (2015-02-06). 「共形ブートストラップのための半正定値計画法ソルバー」. Journal of High Energy Physics . 2015 (6) 174. arXiv : 1502.02033 . Bibcode : 2015JHEP...06..174S . doi : 10.1007/JHEP06(2015)174 . S2CID 256009551 . 
7. ジャン・ハオティアン;カトゥリア、タルン;リー、イン・タット。パドマナーバン、スワティ。宋、趙（2020年11月）。 「半正定計画法のためのより高速な内点法」。2020 IEEE 第 61 回コンピュータ サイエンスの基礎に関する年次シンポジウム (FOCS)。米国ノースカロライナ州ダーラム: IEEE。ページ 910–918。arXiv : 2009.10217。​​土井: 10.1109/FOCS46700.2020.00089。ISBN 978-1-7281-9621-3. S2CID  221836388 .
8. 黄、白河;江春華。宋、趙。タオ、蘭州。張瑞哲（2021-11-18）。 「SDP の迅速な解決: 堅牢な IPM フレームワークと効率的な実装」。arXiv : 2101.08208 [ math.OC ]。
9. Brendan O'Donoghue、Eric Chu、Neal Parikh、Stephen Boyd、「Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding」、Journal of Optimization Theory and Applications、2016年、1042～1068ページ、 https://web.stanford.edu/~boyd/papers/pdf/scs.pdf。
10. Wen, Zaiwen, Donald Goldfarb, Wotao Yin. 「半正定値計画法のための交互方向拡張ラグランジュ法」『数理計画計算』2.3-4 (2010): 203-230.
11. Burer, Samuel; Monteiro, Renato DC (2003), 「低ランク因数分解による半正定値計画法を解くための非線形計画アルゴリズム」, Mathematical Programming , 95 (2): 329– 357, CiteSeerX 10.1.1.682.1520 , doi : 10.1007/s10107-002-0352-8 , ISSN 1436-4646 , S2CID 7691228   
12. Castañeda, O.; Goldstein, T.; Studer, C. (2016年12月). 「近似半正定値緩和法による大規模マルチアンテナ無線システムにおけるデータ検出」 . IEEE Transactions on Circuits and Systems I: Regular Papers . 63 (12): 2334– 2346. arXiv : 1609.01797 . Bibcode : 2016ITCSR..63.2334C . doi : 10.1109/TCSI.2016.2607198 . hdl : 20.500.11850/448631 . ISSN 1558-0806 . 
13. Hazan, Elad (2008). 「半正定値計画に対するスパース近似解」 . Laber, Eduardo Sany; Bornstein, Claudson; Nogueira, Loana Tito; Faria, Luerbio (編). LATIN 2008: Theoretical Informatics . Lecture Notes in Computer Science. Vol. 4957. ベルリン、ハイデルベルク: Springer. pp.  306– 316. doi : 10.1007/978-3-540-78773-0_27 . ISBN 978-3-540-78773-0。
14. Zhu, Yuzixuan; Pataki, Gábor; Tran-Dinh, Quoc (2019)、「Sieve-SDP：半正定値プログラムを前処理するための単純な顔面縮小アルゴリズム」、数学計画計算、11 (3): 503– 586、arXiv : 1710.08954、doi : 10.1007/s12532-019-00164-4、ISSN 1867-2949、S2CID 53645581  

• Lieven Vandenberghe, Stephen Boyd, "Semidefinite Programming", SIAM Review 38, 1996年3月, pp. 49–95. pdf
• Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming", Report PNA-R0210, CWI, Amsterdam, April 2002.最適化オンライン
• E. de Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications", Kluwer Academic Publishers, 2002年3月, ISBN 1-4020-0547-4。
• Robert M. Freund、「半正定値計画法（SDP）入門」、SDP入門

外部リンク

[編集]

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Semidefinite_programming&oldid=1308068424"