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

目的関数は $C=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 2\\ 1& 2& 0\end{array}\right)$ を用いて $⟨C,X⟩=\mathrm{tr}(CX)=2X_{12}+2X_{13}+4X_{23}$ と書ける。

下界（双対実行可能解）. $y=(y_1,y_2,y_3)=\left(-\frac{1}{2},-2,-2\right)$ とおくと
$$M:=C-\mathrm{diag}(y)=\left(\begin{array}{ccc}\frac{1}{2}& 1& 1\\ 1& 2& 2\\ 1& 2& 2\end{array}\right)=u{u}^{\top },u={\left(\frac{1}{\sqrt{2}},\sqrt{2},\sqrt{2}\right)}^{\top }$$
であり、$M⪰O$ である。$(\mathrm{P})$ の任意の実行可能解 $X$ に対し、$X⪰O,M⪰O$ より $⟨M,X⟩=u^{\top }Xu\ge 0$ なので
$$⟨C,X⟩=⟨M,X⟩+\sum _{i=1}^3{y}_i{X}_{ii}\ge y_1+y_2+y_3=-\frac{1}{2}-2-2=-\frac{9}{2}.$$

上界（主実行可能解）.
$$X^{\ast }=\left(\begin{array}{ccc}1& -\frac{1}{4}& -\frac{1}{4}\\ -\frac{1}{4}& 1& -\frac{7}{8}\\ -\frac{1}{4}& -\frac{7}{8}& 1\end{array}\right)$$
を考える。対角成分はすべて $1$ である。半正定値性を確かめる。$(0,1,-1{)}^{\top }$ は固有値 $1+\frac{7}{8}=\frac{15}{8}>0$ の固有ベクトルである。その直交補空間の正規直交基底 $e_1,\frac{1}{\sqrt{2}}(e_2+e_3)$ に関する $X^{\ast }$ の表現行列は
$$\left(\begin{array}{cc}1& -\frac{\sqrt{2}}{4}\\ -\frac{\sqrt{2}}{4}& \frac{1}{8}\end{array}\right)$$
で、トレースは $\frac{9}{8}>0$、行列式は $\frac{1}{8}-\frac{2}{16}=0$ なので固有値は $\frac{9}{8},0$ である。よって $X^{\ast }⪰O$ で、$X^{\ast }$ は実行可能である。目的関数値は
$$2\left(-\frac{1}{4}\right)+2\left(-\frac{1}{4}\right)+4\left(-\frac{7}{8}\right)=-\frac{1}{2}-\frac{1}{2}-\frac{7}{2}=-\frac{9}{2}.$$
（実際 $X^{\ast }u=0$ となり、相補性 $⟨M,X^{\ast }⟩=0$ が成り立っている。）

下界と上界が一致するので、最適値は $-\frac{9}{2}$ である。

（参考：$X$ を単位ベクトル $v_1,v_2,v_3$ のグラム行列とみると、$v_2\cdot v_3=c$ を固定したとき $v_1=-(v_2+v_3)/\Vert v_2+v_3\Vert$ が最良で、値は $-2\sqrt{2+2c}+4c$。これを $c\in [-1,1]$ で最小化すると $c=-\frac{7}{8}$ で $-\frac{9}{2}$ となり、上の $X^{\ast }$ が得られる。）

目的関数は $⟨C,X⟩$（$C_{12}=C_{13}=1$, $C_{23}=2$, 対角成分 0）と書ける。

【上界（実行可能解）】$X_{12}=X_{13}=-\frac{1}{4}$, $X_{23}=-\frac{7}{8}$, 対角成分 1 とおく。$X=\left(\begin{array}{ccc}1& -1/4& -1/4\\ -1/4& 1& -7/8\\ -1/4& -7/8& 1\end{array}\right)$。これは平面上の単位ベクトル $u_1,u_2,u_3$ で $u_1\cdot u_2=u_1\cdot u_3=-\frac{1}{4}$、$u_2,u_3$ のなす角が $2\pi -2\theta$（$\cos \theta =-\frac{1}{4}$）のもののグラム行列であり、半正定値（$\det X=0$ で階数 2、主小行列式も非負）。目的値は $2(-\frac{1}{4})+2(-\frac{1}{4})+4(-\frac{7}{8})=-\frac{1}{2}-\frac{7}{2}\cdot$ ではなく、$-\frac{1}{2}-\frac{1}{2}-\frac{7}{2}=-\frac{9}{2}$。

【下界（双対実行可能解）】双対問題は $\max y_1+y_2+y_3$ s.t. $C-\mathrm{Diag}(y)⪰O$。$y=(-\frac{1}{2},-2,-2)$ とすると $C-\mathrm{Diag}(y)=\left(\begin{array}{ccc}1/2& 1& 1\\ 1& 2& 2\\ 1& 2& 2\end{array}\right)=\frac{1}{2}w{w}^{\top }$（$w=(1,2,2{)}^{\top }$）は半正定値。任意の実行可能な $X$ について $⟨C,X⟩-\sum y_i=⟨C-\mathrm{Diag}(y),X⟩\ge 0$（$X_{ii}=1$ より $⟨\mathrm{Diag}(y),X⟩=\sum y_i$）。よって $⟨C,X⟩\ge y_1+y_2+y_3=-\frac{9}{2}$。

上界と下界が一致するので最適値は $-\frac{9}{2}$。

検算: $\frac{1}{2}{w}^{\top }Xw=\frac{1}{2}(1,2,2)X(1,2,2{)}^{\top }$。$Xw=(1-\frac{1}{2}-\frac{1}{2},-\frac{1}{4}+2-\frac{7}{4},-\frac{1}{4}-\frac{7}{4}+2)=(0,0,0)$ で相補性条件 $(C-\mathrm{Diag}(y))X=0$ も成り立つ。