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

添字を $\mathrm{mod}5$ で考え、$A_1$ を $5$-サイクル $1\text{-}2\text{-}3\text{-}4\text{-}5\text{-}1$ の隣接行列、$A_2$ を $i$ と $i+2$ を結ぶ（五芒星の）グラフの隣接行列とし、$C=A_1+\frac{1}{2}{A}_2$ とおく。$\mathrm{tr}(A_{1}X)=2{\sum }_i{X}_{i,i+1}$、$\mathrm{tr}(A_{2}X)=2{\sum }_i{X}_{i,i+2}$ なので
$$f(X)=\frac{1}{2}\mathrm{tr}(CX).$$

$C$ の固有値. $C$ は巡回行列なので、$\omega =e^{2\pi i/5}$、$v_k=({\omega }^{kj}{)}_{j=1}^5$ $(k=0,\dots ,4)$ が固有ベクトルで、固有値は
$${\mu }_k=2\cos \frac{2\pi k}{5}+\cos \frac{4\pi k}{5}.$$
$\cos \frac{2\pi }{5}=\frac{\sqrt{5}-1}{4}$、$\cos \frac{4\pi }{5}=-\frac{1+\sqrt{5}}{4}$ を用いると
$${\mu }_0=3,{\mu }_1={\mu }_4=\frac{\sqrt{5}-1}{2}-\frac{1+\sqrt{5}}{4}=\frac{\sqrt{5}-3}{4},{\mu }_2={\mu }_3=-\frac{1+\sqrt{5}}{2}+\frac{\sqrt{5}-1}{4}=-\frac{3+\sqrt{5}}{4}.$$
よって最小固有値は $\lambda =-\frac{3+\sqrt{5}}{4}$ である。

下界. $C-\lambda I⪰O$ であり、実行可能な $X⪰O$ に対して半正定値行列どうしのトレース内積は非負だから
$$\mathrm{tr}((C-\lambda I)X)\ge 0⟹\mathrm{tr}(CX)\ge \lambda \mathrm{tr}X=5\lambda .$$
したがって $f(X)\ge \frac{5\lambda }{2}=-\frac{5(3+\sqrt{5})}{8}$。（これは双対問題 $\max \frac{1}{2}{\sum }_i{y}_i$ s.t. $C-\mathrm{diag}(y)⪰O$ の実行可能解 $y=(\lambda ,\dots ,\lambda )$ による弱双対性に当たる。）

下界の達成. $u_j=\cos \frac{4\pi j}{5}$、$w_j=\sin \frac{4\pi j}{5}$ として $X^{\ast }=u{u}^{\top }+w{w}^{\top }$ とおくと $X^{\ast }⪰O$ で
$$X_{jl}^{\ast }=\cos \frac{4\pi (j-l)}{5},X_{jj}^{\ast }=1$$
より実行可能である。$X_{j,j\pm 1}^{\ast }=\cos \frac{4\pi }{5}=-\frac{1+\sqrt{5}}{4}$、$X_{j,j\pm 2}^{\ast }=\cos \frac{8\pi }{5}=\cos \frac{2\pi }{5}=\frac{\sqrt{5}-1}{4}$ だから
$$f(X^{\ast })=5\cdot \left(-\frac{1+\sqrt{5}}{4}\right)+\frac{5}{2}\cdot \frac{\sqrt{5}-1}{4}=\frac{-10-10\sqrt{5}+5\sqrt{5}-5}{8}=-\frac{15+5\sqrt{5}}{8}.$$
これは下界に一致する。

よって最適値は $-\frac{5(3+\sqrt{5})}{8}$ である。

$f(X)=\frac{1}{2}⟨W,X⟩$ と書く。ここで $W$ は、$|i-j|\equiv \pm 1(\mathrm{mod}5)$ の成分が $1$、$|i-j|\equiv \pm 2(\mathrm{mod}5)$ の成分が $1/2$、対角成分が $0$ の巡回行列である。

$W$ の固有値は ${\mu }_k=2\cos \frac{2\pi k}{5}+\cos \frac{4\pi k}{5}$ $(k=0,\dots ,4)$ である。
- ${\mu }_0=3$
- ${\mu }_1={\mu }_4=2\cos 72^{\circ }+\cos 144^{\circ }=\frac{\sqrt{5}-1}{2}-\frac{1+\sqrt{5}}{4}\cdot \frac{}{}$ を計算すると約 $-0.191$
- ${\mu }_2={\mu }_3=2\cos 144^{\circ }+\cos 288^{\circ }=-\frac{1+\sqrt{5}}{2}+\frac{\sqrt{5}-1}{4}=-\frac{3+\sqrt{5}}{4}\approx -1.309$

最小固有値は ${\mu }_{\min }=-\frac{3+\sqrt{5}}{4}$ である。

下界: $X⪰O$ かつ $\mathrm{tr}X=5$ なので $⟨W,X⟩\ge {\mu }_{\min }\mathrm{tr}X=5{\mu }_{\min }$ となる。よって $f(X)\ge \frac{5}{2}{\mu }_{\min }=-\frac{5(3+\sqrt{5})}{8}$。

達成: ${\mu }_{\min }$ に対応する固有空間 $E=\mathrm{span}\{{\mathbf{c}}_2,{\mathbf{s}}_2\}$（${\mathbf{c}}_2,{\mathbf{s}}_2$ は $k=2$ の実固有ベクトル、$\cos \frac{4\pi j}{5}$ と $\sin \frac{4\pi j}{5}$ を並べたもの）への直交射影を $P$ とし、$X=\frac{5}{2}P$ とおく。$P$ は巡回行列で、その対角成分は $2/5$ である。したがって $X_{ii}=1$ かつ $X⪰O$ を満たし、$X$ は実行可能である。このとき $⟨W,X⟩=\frac{5}{2}{\mu }_{\min }\cdot 2=5{\mu }_{\min }$ となり、下界が達成される。

最適値は $\frac{5}{2}{\mu }_{\min }=-\frac{5(3+\sqrt{5})}{8}=-\frac{15+5\sqrt{5}}{8}\approx -3.2725$。