半正定値計画

同義語:半正定値計画法半正定値計画問題semidefinite programmingsemidefinite program

概要

半正定値計画(semidefinite programming)とは、対称行列 $X$ の成分の 1 次式を、1 次の等式と $X$ が半正定値であるという条件のもとで最小化(または最大化)する最適化問題で、線形計画法を行列に広げた凸最適化である。主問題と双対問題の値の差は 2 つの半正定値行列の内積 $\langle X,S\rangle\ge0$ に等しく(弱双対性)、片方が狭義実行可能で最適値が有限なら両者は一致する。半正定値行列はベクトルの内積を並べた行列と同じなので、組合せ最適化の緩和に使える。辺の重みが非負のグラフの最大カット問題では、緩和の最適なベクトルを正規分布で選んだ超平面で分けると、期待値で最適値の $0.878$ 倍以上のカットが得られる(Goemans–Williamson)。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 正定値行列, 線形計画法, 凸最適化

半正定値計画(semidefinite programming、SDP)は、対称行列 $X$ を変数とし、$X$ の成分の 1 次式を目的関数と等式の制約にもち、さらに $X$ が半正定値であることを制約にもつ最適化問題である。成分がすべて対角に並ぶ場合が 線形計画法 で、半正定値の制約は「非負」の制約の行列版にあたる。実行可能な行列の全体は凸集合なので 凸最適化 の問題であり、内点法 で効率よく解ける。
半正定値計画の代表的な使い道は、組合せ最適化の難しい問題の 緩和 である。グラフの頂点を 2 つに分けて、分かれた辺の重みの和を最大にする問題(最大カット問題)は、各頂点に $\pm1$ を割り当てる 2 次の問題に書ける。$\pm1$ を単位ベクトルに置き換えると、ベクトルの内積を並べた行列(Gram 行列)についての半正定値計画になり、多項式時間で解ける。解いたベクトルを無作為な超平面で 2 つに分けると、期待値で最適値の $0.878$ 倍以上の分け方が得られる(Goemans–Williamson)。
この記事では、標準形とその双対問題を定義し、弱双対性と相補性、ベクトルの問題との同値を証明する。強双対性は Slater 条件の下での主張として述べる。主定理として Goemans–Williamson の $0.878$ の評価を、定数の評価も含めて証明する。

定義と使える条件

$\mathbb{S}^n$ を実対称 $n\times n$ 行列の全体とし、$A,B\in\mathbb{S}^n$ の内積を
$$ \langle A,B\rangle=\operatorname{tr}(AB)=\sum_{i,j=1}^nA_{ij}B_{ij} $$
とする。$X\succeq0$ は $X$ が半正定値(すべての $u\in\mathbb{R}^n$ で $u^{\mathsf T}Xu\ge0$)、$X\succ0$ は正定値であることを表す(正定値行列)。

半正定値計画問題

$C,A_1,\dots,A_m\in\mathbb{S}^n$ と $b\in\mathbb{R}^m$ を与える。標準形の半正定値計画問題(主問題)とその 双対問題 を
$$ \text{(P)}\quad\min_{X\in\mathbb{S}^n}\ \langle C,X\rangle\ \ \text{条件 }\langle A_i,X\rangle=b_i\ (i=1,\dots,m),\ X\succeq0, $$
$$ \text{(D)}\quad\max_{y\in\mathbb{R}^m}\ b^{\mathsf T}y\ \ \text{条件 }S:=C-\sum_{i=1}^my_iA_i\succeq0 $$
とする。条件を満たす $X$、$y$ を 実行可能解 という。(P) の下限を $p^\ast$、(D) の上限を $d^\ast$ と書く(実行可能解がなければ $p^\ast=+\infty$、$d^\ast=-\infty$)。$p^\ast$ をとる実行可能解を 最適解 といい、そのとき最適値に 達する という。

狭義実行可能

(P) の実行可能解 $X$ で $X\succ0$ となるものがあるとき (P) は 狭義実行可能、$C-\sum_iy_iA_i\succ0$ となる $y$ があるとき (D) は 狭義実行可能 という。

半正定値行列の全体は凸錐なので($X,Y\succeq0$、$s,t\ge0$ なら $sX+tY\succeq0$)、(P) の実行可能集合は凸集合で、目的関数は 1 次式である。$y\mapsto C-\sum_iy_iA_i$ は 1 次写像なので、(D) の実行可能集合も凸である。(D) の条件の形の不等式を 線形行列不等式 という。
この記事の結論を使える条件をまとめる。

  1. データが対称:$C,A_i\in\mathbb{S}^n$。非対称な $M$ は $\langle M,X\rangle=\langle\tfrac12(M+M^{\mathsf T}),X\rangle$ で対称にしてよい。
  2. 弱双対性 $p^\ast\ge d^\ast$ は無条件に成り立つ(prop-sdp-weak)。
  3. 強双対性 $p^\ast=d^\ast$ と最適値に達することには、片方の問題の狭義実行可能性と最適値の有限性が要る(thm-sdp-strong)。線形計画と違い、両方が実行可能でも $p^\ast>d^\ast$ になりうる(節「使える条件と反例」)。
  4. Goemans–Williamson の評価には、辺の重みが非負であることが要る(thm-sdp-gw)。

公式の表

公式使える条件根拠
$\langle X,S\rangle\ge0$、等号は $XS=0$ のときに限る$X,S\succeq0$lem-sdp-trace
双対ギャップ $\langle C,X\rangle-b^{\mathsf T}y=\langle X,S\rangle\ge0$$X$、$(y,S)$ が実行可能prop-sdp-weak
$p^\ast=d^\ast$ で、(P) が最適値に達する(D) が狭義実行可能で $d^\ast<+\infty$thm-sdp-strong(証明しない)
$p^\ast=d^\ast$ で、(D) が最適値に達する(P) が狭義実行可能で $p^\ast>-\infty$thm-sdp-strong(証明しない)
$X\succeq0\iff X_{ij}=v_i\cdot v_j$ となる $v_1,\dots,v_n\in\mathbb{R}^n$ がある$X\in\mathbb{S}^n$prop-sdp-vector
線形計画は $C,A_i$ が対角の場合—下の計算 1
$\lambda_{\max}(C)=\max\{\langle C,X\rangle\mid\operatorname{tr}X=1,\ X\succeq0\}=\min\{t\mid tI-C\succeq0\}$$C\in\mathbb{S}^n$下の計算 2
$\begin{pmatrix}P&Q\\Q^{\mathsf T}&R\end{pmatrix}\succeq0\iff R-Q^{\mathsf T}P^{-1}Q\succeq0$$P\succ0$$M=\begin{pmatrix}I&P^{-1}Q\\0&I\end{pmatrix}$ で $M^{\mathsf T}\operatorname{diag}(P,\,R-Q^{\mathsf T}P^{-1}Q)\,M$ に等しく、合同変換は半正定値性を保つ
最大カット:$\mathrm{OPT}\le Z_{\mathrm{SDP}}\le\frac n4\lambda_{\max}(L_w)$重み付き Laplace 行列 $L_w$prop-sdp-relax
障壁 $-\log\det X$ の勾配は $-X^{-1}$$X\succ0$BV04 Example 11.7(p. 598)(証明しない)
計算 1・計算 2 を開く

計算 1:$C=\operatorname{diag}(c)$、$A_i=\operatorname{diag}(a_i)$ なら $\langle C,X\rangle=c^{\mathsf T}x$、$\langle A_i,X\rangle=a_i^{\mathsf T}x$($x$ は $X$ の対角)で、非対角成分は目的にも等式の制約にも現れない。半正定値行列の対角成分は非負なので、実行可能な $X$ の非対角成分を $0$ にしても実行可能で値は変わらない。対角行列が半正定値であることは対角成分が非負であることと同じなので、(P) は $\min c^{\mathsf T}x$、$a_i^{\mathsf T}x=b_i$、$x\ge0$ になる。(D) の条件 $\operatorname{diag}(c-\sum_iy_ia_i)\succeq0$ は $\sum_iy_ia_i\le c$ で、線形計画法 の双対問題である。

計算 2:$C=\sum_k\lambda_ku_ku_k^{\mathsf T}$($u_k$ は正規直交な固有ベクトル)と書く。$\operatorname{tr}X=1$、$X\succeq0$ なら $\langle C,X\rangle=\sum_k\lambda_ku_k^{\mathsf T}Xu_k\le\lambda_{\max}\sum_ku_k^{\mathsf T}Xu_k=\lambda_{\max}\operatorname{tr}X=\lambda_{\max}$ で、$X=u_1u_1^{\mathsf T}$($u_1$ は $\lambda_{\max}$ の固有ベクトル)で等号が成り立つ。$tI-C$ の固有値は $t-\lambda_k$ なので、$tI-C\succeq0$ と $t\ge\lambda_{\max}$ は同値である。前者を $\min\langle-C,X\rangle$($m=1$、$A_1=I$、$b_1=1$)の (P) と見ると、その (D) は $\max y$、条件 $-C-yI\succeq0$ で、$t=-y$ とおけば後者になる。2 つの値が等しいことは強双対性の例である。

主定理と証明

弱双対性と相補性

半正定値行列の内積は非負

$X,S\succeq0$ なら $\langle X,S\rangle\ge0$ であり、$\langle X,S\rangle=0$ と $XS=0$ は同値である。

平方根で 2 乗の和に直す

正定値行列 の定理「半正定値な平方根の存在と一意性」により、$X=X^{1/2}X^{1/2}$、$S=S^{1/2}S^{1/2}$ となる半正定値な $X^{1/2},S^{1/2}$ がある。トレースの巡回性から
$$ \langle X,S\rangle=\operatorname{tr}(X^{1/2}X^{1/2}S^{1/2}S^{1/2})=\operatorname{tr}\bigl((S^{1/2}X^{1/2})^{\mathsf T}(S^{1/2}X^{1/2})\bigr)=\sum_{i,j}\bigl((S^{1/2}X^{1/2})_{ij}\bigr)^2\ge0 $$
である。等号は $S^{1/2}X^{1/2}=0$ のときで、そのとき $SX=S^{1/2}(S^{1/2}X^{1/2})X^{1/2}=0$、転置して $XS=0$ である。逆に $XS=0$ なら $\langle X,S\rangle=\operatorname{tr}(XS)=0$ である。$\square$

弱双対性と相補性

$X$ を (P) の、$y$ を (D) の実行可能解とし、$S=C-\sum_iy_iA_i$ とおく。

  1. $\langle C,X\rangle-b^{\mathsf T}y=\langle X,S\rangle\ge0$。とくに $p^\ast\ge d^\ast$ である。
  2. $\langle C,X\rangle=b^{\mathsf T}y$ なら $X$ と $y$ はそれぞれの問題の最適解である。これは $XS=0$(相補性条件)と同値である。

1:$b_i=\langle A_i,X\rangle$ を代入すると
$$ \langle C,X\rangle-b^{\mathsf T}y=\langle C,X\rangle-\sum_iy_i\langle A_i,X\rangle=\Bigl\langle C-\sum_iy_iA_i,\,X\Bigr\rangle=\langle S,X\rangle $$
で、lem-sdp-trace によりこれは $0$ 以上である。左辺の $X$、$y$ について下限・上限をとれば $p^\ast\ge d^\ast$ である。
2:任意の実行可能解 $X'$ について、1 により $\langle C,X'\rangle\ge b^{\mathsf T}y=\langle C,X\rangle$ なので $X$ は最適である。$y$ も同様である。$\langle C,X\rangle=b^{\mathsf T}y$ は 1 により $\langle X,S\rangle=0$ と同じで、lem-sdp-trace によりこれは $XS=0$ と同値である。$\square$

$XS=0$ は、$X$ と $S$ の値域が互いに直交することを意味する。とくに $\operatorname{rank}X+\operatorname{rank}S\le n$ である。線形計画法 の相補性条件 $x_is_i=0$ は、対角の場合のこの条件である。

強双対性(Slater 条件)
  1. (D) が狭義実行可能で $d^\ast<+\infty$ なら、$p^\ast=d^\ast$ であり、(P) は最適値に達する。
  2. (P) が狭義実行可能で $p^\ast>-\infty$ なら、$p^\ast=d^\ast$ であり、(D) は最適値に達する。
出典

この記事では証明しない。一般化された不等式の制約をもつ凸問題の Slater 条件による強双対性(BV04 §5.9.1、p. 265)を、1 は不等式形の半正定値計画(同 Example 5.11、pp. 265–266)に、2 は標準形の錐計画(同 Example 5.12、p. 266)に当てたものである。半正定値行列の錐が自分自身の双対錐であることは lem-sdp-trace の前半と、$u^{\mathsf T}Su=\langle uu^{\mathsf T},S\rangle$ から分かる(同 Example 2.24、p. 52)。スカラーの不等式の場合の証明は 凸最適化 の定理「強双対性(Slater の定理)」にある。

ベクトルの問題との同値

半正定値行列と Gram 行列

$X\in\mathbb{S}^n$ について、$X\succeq0$ であることと、$X_{ij}=v_i\cdot v_j$($1\le i,j\le n$)となるベクトル $v_1,\dots,v_n\in\mathbb{R}^n$ があることは同値である。したがって (P) は、ベクトル $v_1,\dots,v_n\in\mathbb{R}^n$ を変数とする問題
$$ \min\ \sum_{i,j}C_{ij}\,v_i\cdot v_j\ \ \text{条件 }\sum_{i,j}(A_k)_{ij}\,v_i\cdot v_j=b_k\ (k=1,\dots,m) $$
と同じ最適値をもち、実行可能解は $X_{ij}=v_i\cdot v_j$ で 1 対 1 ではないが値を保って対応する。

要点:固有値分解 $X=Q\Lambda Q^{\mathsf T}$ から $X=B^{\mathsf T}B$ と書き、$B$ の列を $v_i$ とする。

詳しい証明を開く

$X\succeq0$ とする。正定値行列 の定理「半正定値行列の特徴づけ」の 2 ⇒ 4 の証明のとおり、$X=Q\Lambda Q^{\mathsf T}$($Q$ は直交行列、$\Lambda=\operatorname{diag}(\lambda_1,\dots,\lambda_n)$、$\lambda_k\ge0$)と書いて $B=\Lambda^{1/2}Q^{\mathsf T}\in\mathbb{R}^{n\times n}$ とおくと $X=B^{\mathsf T}B$ である。$v_i=Be_i$($B$ の第 $i$ 列)とおけば $X_{ij}=e_i^{\mathsf T}B^{\mathsf T}Be_j=v_i\cdot v_j$ である。逆に $X_{ij}=v_i\cdot v_j$ なら、$v_i$ を列に並べた行列 $V$ で $X=V^{\mathsf T}V$ と書けて、$u^{\mathsf T}Xu=(Vu)\cdot(Vu)\ge0$ である。目的関数と制約は $\langle C,X\rangle=\sum_{i,j}C_{ij}X_{ij}$ のように $X$ の成分の 1 次式なので、この対応で値は変わらない。$\square$

数値計算では、得られた $X$ の固有値分解か、ピボット選択つきの Cholesky分解 で $v_i$ を求める。丸めの誤差で $-10^{-12}$ 程度の負の固有値が出たら $0$ に切る。

最大カット問題の緩和

最大カット問題

頂点の集合 $V=\{1,\dots,n\}$ と辺の集合 $E$ をもつ無向グラフで、各辺 $ij\in E$ に重み $w_{ij}$ が与えられているとする。$U\subseteq V$ について、端点の一方だけが $U$ に入る辺の重みの和を
$$ w(\delta(U))=\sum_{\substack{ij\in E\\ \lvert\{i,j\}\cap U\rvert=1}}w_{ij} $$
と書き、$U$ の定める カット の重みという。その最大値 $\mathrm{OPT}=\max_{U\subseteq V}w(\delta(U))$ を求める問題を 最大カット問題 という。

$i\in U$ なら $y_i=1$、そうでなければ $y_i=-1$ とおくと、辺 $ij$ が分かれるのは $y_iy_j=-1$ のとき、すなわち $\frac12(1-y_iy_j)=1$ のときなので
$$ \mathrm{OPT}=\max\Bigl\{\tfrac12\sum_{ij\in E}w_{ij}(1-y_iy_j)\ \Bigm|\ y\in\{-1,1\}^n\Bigr\} $$
である。$y_iy_j$ を $X_{ij}$ に置き換え、$X=yy^{\mathsf T}$ の性質のうち $X_{ii}=1$ と $X\succeq0$ だけを残すと、半正定値計画
$$ Z_{\mathrm{SDP}}=\max\Bigl\{\tfrac12\sum_{ij\in E}w_{ij}(1-X_{ij})\ \Bigm|\ X_{ii}=1\ (i=1,\dots,n),\ X\succeq0\Bigr\} $$
を得る。これを最大カット問題の 半正定値緩和 という。prop-sdp-vector により、これは単位ベクトル $v_1,\dots,v_n\in\mathbb{R}^n$ について $\frac12\sum w_{ij}(1-v_i\cdot v_j)$ を最大にする問題と同じである。重み付き Laplace 行列を $L_w=\sum_{ij\in E}w_{ij}(e_i-e_j)(e_i-e_j)^{\mathsf T}$ とおくと、$X_{ii}=1$ のもとで $\langle(e_i-e_j)(e_i-e_j)^{\mathsf T},X\rangle=2-2X_{ij}$ なので、目的関数は $\frac14\langle L_w,X\rangle$ に等しい。

緩和の上下の評価

重み $w_{ij}$ が実数のとき、$\mathrm{OPT}\le Z_{\mathrm{SDP}}\le\frac n4\lambda_{\max}(L_w)$ である。$Z_{\mathrm{SDP}}$ は最大値として達せられる。

要点:$X=yy^{\mathsf T}$ が実行可能で、上界は $\operatorname{tr}X=n$ と lem-sdp-trace による。

詳しい証明を開く

$y\in\{-1,1\}^n$ について $X=yy^{\mathsf T}$ は $X_{ii}=y_i^2=1$、$u^{\mathsf T}Xu=(y\cdot u)^2\ge0$ を満たし、目的関数の値はカットの重みに等しい。よって $\mathrm{OPT}\le Z_{\mathrm{SDP}}$ である。実行可能な $X$ では $\operatorname{tr}X=n$ で、$\lambda_{\max}(L_w)I-L_w\succeq0$ なので lem-sdp-trace から $\langle\lambda_{\max}(L_w)I-L_w,X\rangle\ge0$、すなわち $\frac14\langle L_w,X\rangle\le\frac n4\lambda_{\max}(L_w)$ である。実行可能集合は $\lvert X_{ij}\rvert\le\sqrt{X_{ii}X_{jj}}=1$($2\times2$ の主小行列式が $0$ 以上)により有界な閉集合なので、連続な目的関数は最大値に達する。$\square$

Goemans–Williamson の方法

緩和の最適なベクトル $v_1,\dots,v_n$ から頂点の分け方を作るには、原点を通る無作為な超平面で単位球面を 2 つに分ける。超平面の法線 $r$ を標準正規分布からとるのが要点で、そうすると $r$ の向きは回転について偏りがなくなる。

無作為な超平面で 2 つのベクトルが分かれる確率

$u,v\in\mathbb{R}^d$ を単位ベクトルとし、$\theta=\arccos(u\cdot v)\in[0,\pi]$ とする。$r=(r_1,\dots,r_d)$ の成分を独立に標準正規分布 $N(0,1)$ からとり、$\operatorname{sgn}(t)=1$($t\ge0$)、$-1$($t<0$)とすると
$$ \Pr\bigl[\operatorname{sgn}(u\cdot r)\ne\operatorname{sgn}(v\cdot r)\bigr]=\frac\theta\pi $$
である。

2 次元に射影すると角度が一様になる

要点:$u,v$ の張る平面への $r$ の射影は 2 次元の標準正規分布に従い、その偏角は一様である。符号が異なるのは、偏角が長さ $\pi$ の 2 つの弧の一方だけに入るときで、その長さは $2\theta$ である。

詳しい証明を開く

$u\cdot r$ は $N(0,1)$ に従うので(多変量正規分布 の定理「1 次変換で多変量正規分布は保たれる」)、$u\cdot r=0$ となる確率は $0$ である。$v$ についても同じなので、以下では内積が $0$ になる場合を無視してよい。

$\theta=0$ なら $u=v$ で、確率は $0=\theta/\pi$ である。$\theta=\pi$ なら $v=-u$ で、$u\cdot r\neq0$ のとき符号は必ず異なるので確率は $1$ である。$0<\theta<\pi$ とする。$e_1=u$ とし、$v-(u\cdot v)u$ を正規化したものを $e_2$ とすると、$e_1,e_2$ は正規直交で $v=\cos\theta\,e_1+\sin\theta\,e_2$ である。$g_1=e_1\cdot r$、$g_2=e_2\cdot r$ とおくと、$(g_1,g_2)$ は $r$ の 1 次変換なので平均 $0$ の 2 次元正規分布に従い、共分散行列は $(e_a\cdot e_b)_{a,b}=I_2$ である(同じ定理)。よって $g_1,g_2$ は独立に $N(0,1)$ に従い(多変量正規分布 の定理「無相関なら独立」)、$(g_1,g_2)$ の密度は $\frac1{2\pi}e^{-(x^2+y^2)/2}$ である。極座標 $(g_1,g_2)=\rho(\cos\varphi,\sin\varphi)$ に直すと、$\{\varphi\in I\}$ の確率は $\int_I\int_0^\infty\frac1{2\pi}e^{-\rho^2/2}\rho\,d\rho\,d\varphi=\frac{\lvert I\rvert}{2\pi}$($I\subseteq[0,2\pi)$ は区間)なので、$\varphi$ は $[0,2\pi)$ の一様分布に従う。

$u\cdot r=g_1=\rho\cos\varphi$、$v\cdot r=\cos\theta\,g_1+\sin\theta\,g_2=\rho\cos(\varphi-\theta)$ である。$\cos\varphi>0$ となる $\varphi$ は長さ $\pi$ の弧 $(-\frac\pi2,\frac\pi2)$($2\pi$ を法として)、$\cos(\varphi-\theta)>0$ となる $\varphi$ はそれを $\theta$ だけ回した弧である。2 つの弧の共通部分の長さは $\pi-\theta$ なので、どちらか一方だけに入る $\varphi$ の集合の長さは $2(\pi-(\pi-\theta))=2\theta$ である。符号が異なるのは $\varphi$ がこの集合に入るときなので、確率は $\frac{2\theta}{2\pi}=\frac\theta\pi$ である。$\square$

定数 0.878

$-1\le x\le1$ について
$$ \frac1\pi\arccos x\ \ge\ 0.878\cdot\frac{1-x}2 $$
である。

凹の区間と凸の区間に分ける

$x=\cos\theta$($\theta\in[0,\pi]$)とおくと、示すことは $g(\theta)=\dfrac\theta\pi-0.439\,(1-\cos\theta)\ge0$ である。$g(0)=0$、$g'(\theta)=\dfrac1\pi-0.439\sin\theta$、$g''(\theta)=-0.439\cos\theta$ である。
$[0,\frac\pi2]$ の場合。 $g''\le0$ なので $g$ はこの区間で凹関数で、グラフは両端を結ぶ線分より上にある。$g(0)=0$、$g(\frac\pi2)=\frac12-0.439=0.061>0$ なので、この区間で $g\ge0$ である。
$[\frac\pi2,\pi]$ の場合。 $g''\ge0$ なので $g$ は凸関数で、$g'$ は増加する。$g'(\frac\pi2)=\frac1\pi-0.439<0$、$g'(\pi)=\frac1\pi>0$ なので、$g'(\theta^\ast)=0$ となる $\theta^\ast$ がこの区間にただ 1 つあり、$g$ は $\theta^\ast$ で最小になる。$\sin\theta^\ast=s:=\dfrac1{0.439\pi}$ で、$\theta^\ast>\frac\pi2$ から $\cos\theta^\ast=-\sqrt{1-s^2}$、$\theta^\ast=\pi-\arcsin s$ である。数値を計算すると $s=0.7250794\ldots$、$\theta^\ast=2.3304428\ldots$ で
$$ g(\theta^\ast)=\frac{\theta^\ast}\pi-0.439\,\bigl(1+\sqrt{1-s^2}\bigr)=0.0004789\ldots>0 $$
である。よってこの区間でも $g\ge0$ である。$\square$

$\dfrac{2}{\pi}\cdot\dfrac{\theta}{1-\cos\theta}$ の $0<\theta\le\pi$ での最小値を $\alpha_{\mathrm{GW}}$ と書く。数値計算による値は $\alpha_{\mathrm{GW}}=0.8785672\ldots$($\theta=2.3311223\ldots$、$\cos\theta=-0.6891577\ldots$ でとる)で、lem-sdp-alpha は $0.878<\alpha_{\mathrm{GW}}$ を示している。図の左は、$\frac1\pi\arccos x$ が $0.878\cdot\frac{1-x}2$ を上回り、$x\approx-0.689$ で最も近づく様子である。
図: 左は x を -1 から 1 まで動かしたときの、辺が分かれる確率 arccos(x)/π(実線)と、緩和の 1 辺の寄与 (1-x)/2(破線)、その 0.878 倍(点線)。実線は点線より上にあり、x が約 -0.689 のところで最も近づく。右は 5 頂点の閉路 C5 の緩和の最適なベクトル v1 から v5(隣どうしの角が 4π/5)と、法線 r の超平面(直線)の例。この超平面は v2、v4 と v1、v3、v5 を分け、閉路の 5 本の辺のうち v5 と v1 を結ぶ辺以外の 4 本を分ける。 図: 左は x を -1 から 1 まで動かしたときの、辺が分かれる確率 arccos(x)/π(実線)と、緩和の 1 辺の寄与 (1-x)/2(破線)、その 0.878 倍(点線)。実線は点線より上にあり、x が約 -0.689 のところで最も近づく。右は 5 頂点の閉路 C5 の緩和の最適なベクトル v1 から v5(隣どうしの角が 4π/5)と、法線 r の超平面(直線)の例。この超平面は v2、v4 と v1、v3、v5 を分け、閉路の 5 本の辺のうち v5 と v1 を結ぶ辺以外の 4 本を分ける。

Goemans–Williamson の近似

重みがすべて非負($w_{ij}\ge0$)とする。$v_1,\dots,v_n\in\mathbb{R}^n$ を半正定値緩和の最適解の単位ベクトルとし、$r\in\mathbb{R}^n$ の成分を独立に $N(0,1)$ からとって $U=\{i\mid v_i\cdot r\ge0\}$ とおく。このとき
$$ \mathbb{E}\bigl[w(\delta(U))\bigr]\ \ge\ 0.878\,Z_{\mathrm{SDP}}\ \ge\ 0.878\,\mathrm{OPT} $$
である。さらに $0.878\,Z_{\mathrm{SDP}}\le\mathrm{OPT}\le Z_{\mathrm{SDP}}$ である。

辺ごとに期待値を比べる

辺 $ij$ が分かれるのは $v_i\cdot r$ と $v_j\cdot r$ の符号が異なるときなので、lem-sdp-hyperplane によりその確率は $\frac1\pi\arccos(v_i\cdot v_j)$ である。期待値の線形性 により
$$ \mathbb{E}\bigl[w(\delta(U))\bigr]=\sum_{ij\in E}w_{ij}\cdot\frac1\pi\arccos(v_i\cdot v_j) $$
である。$w_{ij}\ge0$ なので、各項に lem-sdp-alpha を $x=v_i\cdot v_j$ で使って
$$ \mathbb{E}\bigl[w(\delta(U))\bigr]\ge\sum_{ij\in E}w_{ij}\cdot0.878\cdot\frac{1-v_i\cdot v_j}2=0.878\,Z_{\mathrm{SDP}} $$
を得る。prop-sdp-relax により $Z_{\mathrm{SDP}}\ge\mathrm{OPT}$ である。後半:確率変数 $w(\delta(U))$ はある結果で期待値以上の値をとるので、$\mathrm{OPT}\ge\mathbb{E}[w(\delta(U))]\ge0.878\,Z_{\mathrm{SDP}}$ である。$\square$

計算時間と、より良い比の難しさ

半正定値計画は、技術的な条件のもとで、加法的な誤差 $\varepsilon$ 以内の解を入力の大きさと $\log(1/\varepsilon)$ の多項式の時間で求められる(WS11 §6.1、p. 142)。誤差 $\varepsilon$ の解を使うと、同じ証明で期待値は $0.878\,(Z_{\mathrm{SDP}}-\varepsilon)$ 以上になる。次の 2 つはこの記事では証明しない(WS11 Theorem 6.10・6.11、p. 147):$\alpha>\frac{16}{17}\approx0.941$ の $\alpha$-近似アルゴリズムがあれば P $=$ NP である。一意ゲーム予想を仮定すると、$\alpha_{\mathrm{GW}}$ より大きい定数 $\alpha$ の $\alpha$-近似アルゴリズムがあれば P $=$ NP である。乱数を使わない形にもでき、比の損失はいくらでも小さくできる(同 p. 147)。

計算の手順

  1. 形を整える:問題を (P) か (D) の形に書き、行列を対称にする。最大カットなら $C=-\frac14L_w$、$A_i=e_ie_i^{\mathsf T}$、$b_i=1$ の (P)(最小化に直した形)である。
  2. 狭義実行可能性を確かめる(thm-sdp-strong)。最大カットの緩和では $X=I$ が (P) の、$t<-\frac14\lambda_{\max}(L_w)$ の $y=(t,\dots,t)$ が (D) の狭義実行可能解なので、強双対性が成り立ち両方とも最適値に達する。
  3. 内点法で解く:障壁 $-\log\det X$ を使う(内点法、BV04 §11.6.1、pp. 597–598)。双対ギャップ $\langle X,S\rangle$(prop-sdp-weak)が許容誤差 $\varepsilon$ 以下になったら止める。
  4. ベクトルに直す:$X=Q\Lambda Q^{\mathsf T}$ と固有値分解し、負の微小な固有値を $0$ に切って $v_i=\Lambda^{1/2}Q^{\mathsf T}e_i$ とする(prop-sdp-vector)。
  5. 丸める:$r\sim N(0,I_n)$ をとり、$U=\{i\mid v_i\cdot r\ge0\}$ とする(thm-sdp-gw)。
  6. 繰り返す:独立に $k$ 回丸めて最もよいカットを残す。比 $w(\delta(U))/Z_{\mathrm{SDP}}$ は、その入力で保証できる比として毎回分かる。
    6 の回数の目安:$W=w(\delta(U))$ は $\mathrm{OPT}\le Z_{\mathrm{SDP}}$ 以下なので $Z_{\mathrm{SDP}}-W\ge0$ で、thm-sdp-gw から $\mathbb{E}[Z_{\mathrm{SDP}}-W]\le0.122\,Z_{\mathrm{SDP}}$ である。$Z_{\mathrm{SDP}}>0$ なら Markovの不等式 により $\Pr[W<(0.878-\delta)Z_{\mathrm{SDP}}]\le\frac{0.122}{0.122+\delta}$($\delta>0$)なので、$k$ 回とも失敗する確率は $\bigl(\frac{0.122}{0.122+\delta}\bigr)^k$ 以下である。$\delta=0.01$ なら $k=176$ で $10^{-6}$ 以下になる。

例題

2 × 2 の半正定値計画

$\min X_{11}+X_{22}$、条件 $2X_{12}=2$、$X\succeq0$ を解く($C=I$、$A_1=\begin{pmatrix}0&1\\1&0\end{pmatrix}$、$b_1=2$)。
答え:$p^\ast=d^\ast=2$。最適解 $X=\begin{pmatrix}1&1\\1&1\end{pmatrix}$、双対の最適解 $y=1$、$S=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$ で $XS=0$。

途中の計算を開く

主問題:$X\succeq0$ から $X_{11}X_{22}\ge X_{12}^2=1$ で、相加相乗平均により $X_{11}+X_{22}\ge2\sqrt{X_{11}X_{22}}\ge2$。上の $X$ で $2$ になる。双対問題:$\max2y$、条件 $C-yA_1=\begin{pmatrix}1&-y\\-y&1\end{pmatrix}\succeq0$。固有値は $1\pm y$ なので条件は $\lvert y\rvert\le1$ で、$d^\ast=2$。値が一致するので prop-sdp-weak の 2 により両方とも最適で、$XS=\begin{pmatrix}1-1&-1+1\\1-1&-1+1\end{pmatrix}=0$。

三角形の最大カット

3 頂点の完全グラフ $K_3$(重み $1$)で、$\mathrm{OPT}$、$Z_{\mathrm{SDP}}$ と丸めの期待値を求める。
答え:$\mathrm{OPT}=2$、$Z_{\mathrm{SDP}}=\frac94=2.25$、期待値 $2$。比 $\mathrm{OPT}/Z_{\mathrm{SDP}}=\frac89\approx0.8889$。

途中の計算を開く

どの分け方でも分かれる辺は $0$ 本か $2$ 本なので $\mathrm{OPT}=2$。平面の単位ベクトルを $120^\circ$ ずつずらしてとると $v_i\cdot v_j=-\frac12$ で、値は $3\cdot\frac12(1+\frac12)=\frac94$。$L_w$ の固有値は $0,3,3$ なので prop-sdp-relax の上界も $\frac34\cdot3=\frac94$ で、$Z_{\mathrm{SDP}}=\frac94$。各辺が分かれる確率は $\frac1\pi\cdot\frac{2\pi}3=\frac23$ なので、期待値は $3\cdot\frac23=2$(平面の直線はこの 3 本のベクトルを必ず 1 本と 2 本に分けるので、毎回 $2$)。

5 頂点の閉路

閉路 $C_5$(重み $1$)で同じものを求める。
答え:$\mathrm{OPT}=4$、$Z_{\mathrm{SDP}}=\frac{25+5\sqrt5}8\approx4.522542$、期待値 $4$。比 $\mathrm{OPT}/Z_{\mathrm{SDP}}=\frac{32}{25+5\sqrt5}\approx0.884458$。

途中の計算を開く

辺の数は奇数なので全部は分けられず、4 本は分けられるから $\mathrm{OPT}=4$。$v_k=(\cos\frac{4\pi k}5,\sin\frac{4\pi k}5)$($k=0,\dots,4$)とすると隣どうしの内積は $\cos\frac{4\pi}5=-\frac{1+\sqrt5}4$ で、値は $5\cdot\frac12\bigl(1+\frac{1+\sqrt5}4\bigr)=\frac{25+5\sqrt5}8$。$L_w$ の固有値は $2-2\cos\frac{2\pi k}5$ で、最大は $2-2\cos\frac{4\pi}5=\frac{5+\sqrt5}2$。prop-sdp-relax の上界 $\frac54\cdot\frac{5+\sqrt5}2$ は下界と一致するので $Z_{\mathrm{SDP}}=\frac{25+5\sqrt5}8$。これは $y_i=\frac14\lambda_{\max}(L_w)$ が $\operatorname{diag}(y)-\frac14L_w\succeq0$ と $\sum_iy_i=Z_{\mathrm{SDP}}$ を満たすことと同じで、双対の側からの最適性の証明になっている。各辺が分かれる確率は $\frac45$ なので期待値は $4$。

使える条件と反例

外す条件反例成り立たなくなること
thm-sdp-strong の 1 の「(D) が狭義実行可能」ex-sdp-gap$p^\ast=1>d^\ast=0$ で強双対性が成り立たない
thm-sdp-strong の 2 の「(P) が狭義実行可能」ex-sdp-attain$p^\ast=d^\ast=0$ だが (D) は最適値に達しない
thm-sdp-gw の「重みが非負」ex-sdp-negative期待値 $\frac2\pi\arccos\frac14\approx0.8391$ が $0.878\,\mathrm{OPT}=0.878$ を下回る
lem-sdp-hyperplane の「$r$ が正規分布」$r$ を $\pm e_1,\pm e_2$ から一様に選ぶ。$u=e_1$、$v=(\frac12,\frac{\sqrt3}2)$分かれる確率は $\frac14$ で、$\frac\theta\pi=\frac13$ にならない
緩和で落とした「$X$ の階数が 1」ex-sdp-c5$Z_{\mathrm{SDP}}\approx4.5225>\mathrm{OPT}=4$ で、緩和の値は最適値に一致しない
双対ギャップのある問題

(D):$\max\,-y_1$、条件 $\begin{pmatrix}0&y_1&0\\y_1&y_2&0\\0&0&y_1+1\end{pmatrix}\succeq0$。これは $C=\operatorname{diag}(0,0,1)$、$A_1=-(E_{12}+E_{21}+E_{33})$、$A_2=-E_{22}$、$b=(-1,0)$ の (D) である($E_{ij}$ は $(i,j)$ 成分だけ $1$ の行列)。
答え:$d^\ast=0$、$p^\ast=1$。どちらも最適値に達するが、どちらも狭義実行可能でない。

確認を開く

(D):$(1,1)$ 成分が $0$ の半正定値行列は第 1 行が $0$ なので($2\times2$ の主小行列式 $-y_1^2\ge0$)、$y_1=0$。$y_2\ge0$ なら実行可能で、$d^\ast=0$。(P):$\min X_{33}$、条件 $-2X_{12}-X_{33}=-1$、$-X_{22}=0$、$X\succeq0$。$X_{22}=0$ から同じ理由で $X_{12}=0$、よって $X_{33}=1$ で $p^\ast=1$($X=\operatorname{diag}(1,0,1)$)。(D) の行列も (P) の $X$ も対角成分に必ず $0$ があるので、正定値にはならない。

最適値に達しない問題

(D):$\max\,-y_1$、条件 $\begin{pmatrix}y_1&1\\1&y_2\end{pmatrix}\succeq0$($C=E_{12}+E_{21}$、$A_1=-E_{11}$、$A_2=-E_{22}$、$b=(-1,0)$)。
答え:$d^\ast=0$ だが (D) は最適値に達しない。(D) は狭義実行可能で($y=(2,2)$)、thm-sdp-strong の 1 のとおり $p^\ast=0$ で (P) は $X=\operatorname{diag}(1,0)$ で最適値に達する。(P) は狭義実行可能でない。

確認を開く

条件は $y_1>0$、$y_1y_2\ge1$ なので $-y_1<0$ で、$y=(t,1/t)$($t\to+0$)で $-y_1\to0$。(P):$\min2X_{12}$、条件 $X_{11}=1$、$X_{22}=0$、$X\succeq0$。$X_{22}=0$ から $X_{12}=0$ で値は $0$。$X_{22}=0$ なので $X\succ0$ にはならない。

負の重みで比の保証が成り立たない例

3 頂点で $w_{12}=w_{13}=-1$、$w_{23}=2$ とする。
答え:$\mathrm{OPT}=1$、$Z_{\mathrm{SDP}}=\frac98$。最適な $X$ はただ 1 つで $X_{12}=X_{13}=\frac14$、$X_{23}=-\frac78$。丸めの期待値は $\frac2\pi\arccos\frac14\approx0.839139<0.878$。

確認を開く

カットの重みは $U=\{2\}$ か $\{3\}$ で $-1+2=1$、$U=\{1\}$ で $-2$、空集合で $0$ なので $\mathrm{OPT}=1$。上の $X$ は $\det X=(1-X_{23})(1+X_{23}-2X_{12}^2)=0$ で、ほかの主小行列式も非負なので半正定値であり、値は $\frac12(X_{12}+X_{13}-2X_{23})=\frac98$。双対:$y=(-\frac38,\frac34,\frac34)$ とすると $\operatorname{diag}(y)-\frac14L_w=2uu^{\mathsf T}$($u=(-\frac14,\frac12,\frac12)$)$\succeq0$ で、$\sum y_i=\frac98$。実行可能な $X$ について lem-sdp-trace から $\langle\operatorname{diag}(y)-\frac14L_w,X\rangle\ge0$、すなわち $\frac14\langle L_w,X\rangle\le\sum_iy_iX_{ii}=\sum_iy_i$ なので、値が一致する上の $X$ は最適で、最適な $X$ は相補性 $Xu=0$ と $X_{ii}=1$ から上の値に決まる。期待値は $\frac1\pi(-2\arccos\frac14+2\arccos(-\frac78))$ で、$\cos(2\arccos\frac14)=2\cdot\frac1{16}-1=-\frac78$ から $\arccos(-\frac78)=2\arccos\frac14$ なので $\frac2\pi\arccos\frac14$。負の重みの項では lem-sdp-alpha を掛けると不等号の向きが逆になる。

反例の表の 4 行目の確認:$r=e_1,-e_1,e_2$ では $u\cdot r$ と $v\cdot r$ の符号が同じで、$r=-e_2$ では $u\cdot r=0$(符号 $+$)、$v\cdot r=-\frac{\sqrt3}2$ で異なる。

よくある誤り

誤り正しくはなぜ
両方が実行可能なら $p^\ast=d^\ast$ とする狭義実行可能性などの条件が要るex-sdp-gap
双対の条件を $\sum_iy_iA_i-C\succeq0$ と書く(P) が最小化なら $C-\sum_iy_iA_i\succeq0$prop-sdp-weak の計算
緩和の値 $Z_{\mathrm{SDP}}$ を最大カットの値とする$Z_{\mathrm{SDP}}$ は上界で、一般に $\mathrm{OPT}< Z_{\mathrm{SDP}}$ex-sdp-c5
1 回の丸めで $0.878$ 倍が保証されるとする保証は期待値。繰り返して最良を残す節「計算の手順」
負の重みでも $0.878$ を使う非負の重みが条件ex-sdp-negative

補足

半正定値計画は、行列の最大固有値の最小化、制御の線形行列不等式、多項式が 2 乗の和で書けるかの判定などにも現れる。線形計画の内点法の考え方は、対数障壁を $-\log\det X$ に替えてそのまま半正定値計画に移る(BV04 §11.6)。最大カット以外にも、ベクトルの問題に緩和して無作為な超平面で丸める方法は、2 次計画、相関クラスタリング、3 彩色可能なグラフの彩色などに使われる(WS11 第 6 章)。

関連項目

参考文献

[1]
Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004, Example 2.24(p. 52)、§4.6.2(pp. 168–169)、§5.2.3(p. 226)、§5.9.1 と Example 5.11(pp. 265–266)、Example 5.12(p. 266)、§11.6.1 と Example 11.7(pp. 597–598)
[2]
David P. Williamson; David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, 頁は著者公開の電子版(2011)のもの:§6.1(pp. 141–142)、§6.2:Lemma 6.3(p. 143)、Lemma 6.7(pp. 144–145)、Lemma 6.8 と Theorem 6.9(p. 145)、Theorems 6.10・6.11(p. 147)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する