凸最適化・組合せ最適化の問題

手順 1：双対問題を作る 制約 $X_{ii}=1$ に乗数 $y_i$ をつけると、$(\mathrm{P})$ の双対問題は
$$(\mathrm{D})\text{maximize}{y}_1+y_2+y_3+y_4\text{subject to}C-\mathrm{Diag}(y)⪰O$$
である。弱双対性：$(\mathrm{P})$ の実行可能解 $X$ と $(\mathrm{D})$ の実行可能解 $y$ に対し、$C-\mathrm{Diag}(y)⪰O$，$X⪰O$ より $⟨C-\mathrm{Diag}(y),X⟩\ge 0$ なので
$$⟨C,X⟩\ge ⟨\mathrm{Diag}(y),X⟩=\sum _i{y}_i{X}_{ii}=\sum _i{y}_i.$$

手順 2：固有値による下界（双対の実行可能解） $y=(t,t,t,t)$ とおくと、制約は $C-tE⪰O$，すなわち $t\le {\lambda }_{\min }(C)$ である。$C$ は $4$ 頂点の閉路 $1-2-3-4-1$ の隣接行列で、任意の $x\in {\mathbb{R}}^4$ に対して
$$x^{\top }(C+2E)x=2\sum _{i=1}^4{x}_i^2+2(x_1{x}_2+x_2{x}_3+x_3{x}_4+x_4{x}_1)=(x_1+x_2{)}^2+(x_2+x_3{)}^2+(x_3+x_4{)}^2+(x_4+x_1{)}^2\ge 0$$
が成り立つ。よって $C+2E⪰O$，すなわち $y=(-2,-2,-2,-2)$ は $(\mathrm{D})$ の実行可能解で、目的関数値は $-8$。弱双対性から、$(\mathrm{P})$ の任意の実行可能解について $⟨C,X⟩\ge -8$ である。（実際 ${\lambda }_{\min }(C)=-2$ で、固有ベクトルは $v=(1,-1,1,-1{)}^{\top }$。）

手順 3：下界を達成する主問題の実行可能解 最小固有値の固有ベクトル $v=(1,-1,1,-1{)}^{\top }$ を用いて $X^{\circ }=v{v}^{\top }$ とおくと
$$X^{\circ }=\left(\begin{array}{cccc}1& -1& 1& -1\\ -1& 1& -1& 1\\ 1& -1& 1& -1\\ -1& 1& -1& 1\end{array}\right)$$
である。$X^{\circ }=v{v}^{\top }⪰O$ で、対角成分はすべて $1$ なので実行可能である。目的関数値は、$C$ の $1$ が立つ $8$ か所 $(1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(4,1),(1,4)$ での $X^{\circ }$ の成分がすべて $-1$ なので
$$⟨C,X^{\circ }⟩=8\times (-1)=-8.$$

手順 4：結論 下界 $-8$ が主問題の実行可能解で達成されたので、$(\mathrm{P})$ の最適値は $-8$ である（双対問題の最適値も $-8$ で、双対ギャップはない）。

$C$ の非零成分は $C_{12}=C_{14}=C_{23}=C_{34}=1$ とその対称成分で、$⟨C,X⟩=2(X_{12}+X_{14}+X_{23}+X_{34})$。

下界: $X⪰O$, $X_{ii}=1$ なので、2 次主小行列式 $X_{ii}{X}_{jj}-X_{ij}^2\ge 0$ より $|X_{ij}|\le 1$。よって $X_{12},X_{14},X_{23},X_{34}\ge -1$ で、$⟨C,X⟩\ge 2\cdot (-4)=-8$。

達成: $v=(1,-1,1,-1{)}^T$ として $X=v{v}^T$ とおくと $X⪰O$（階数 1）, $X_{ii}=1$。$X_{12}=X_{14}=X_{23}=X_{34}=-1$ となり $⟨C,X⟩=-8$。

よって最適値は $-8$。検算: $v^{T}Cv=2(v_1{v}_2+v_1{v}_4+v_2{v}_3+v_3{v}_4)=2(-1-1-1-1)=-8$。