半正定値計画の双対と最適値の決定

${\mathcal{S}}^4$ を $4$ 次実対称行列全体とし、$A,B\in {\mathcal{S}}^4$ に対して $⟨A,B⟩=\mathrm{tr}(AB)={\sum }_{i,j}{A}_{ij}{B}_{ij}$ と定める。$X⪰O$ は $X$ が半正定値であることを表す。行列 $C\in {\mathcal{S}}^4$ を
$$C=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right)$$
とし、$X=(X_{ij})\in {\mathcal{S}}^4$ を変数とする次の半正定値計画問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}⟨C,X⟩\text{subject to}{X}_{ii}=1(i=1,2,3,4),X⪰O$$
$(\mathrm{P})$ の最適値を求めよ。

${\mathcal{S}}^3$ を $3$ 次実対称行列全体とし、$X⪰O$ は $X$ が半正定値であることを表す。$X=(X_{ij})\in {\mathcal{S}}^3$ を変数とする次の半正定値計画問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}2X_{12}+2X_{13}+4X_{23}\text{subject to}{X}_{11}=X_{22}=X_{33}=1,X⪰O.$$
$(\mathrm{P})$ の最適値を求めよ。

${\mathcal{S}}^3$ を $3$ 次実対称行列全体とし、$A,B\in {\mathcal{S}}^3$ に対して $⟨A,B⟩=\mathrm{tr}(AB)$ と定める。$X⪰O$ は $X$ が半正定値であることを表す。
$$C=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 2\\ 1& 2& 0\end{array}\right)$$
として、次の半正定値計画問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}⟨C,X⟩\text{subject to}{X}_{11}=X_{22}=X_{33}=1,X\in {\mathcal{S}}^3,X⪰O$$
$(\mathrm{P})$ の最適値を求めよ。

$n\ge 2$ を整数、$k$ を $1\le k\le n-1$ を満たす整数とする。${\mathbb{S}}^n$ を $n$ 次実対称行列全体とし、$X,Y\in {\mathbb{S}}^n$ に対して $⟨X,Y⟩=\mathrm{tr}(XY)$、$X⪰0$ は $X$ が半正定値であること、$X⪯Y$ は $Y-X⪰0$ を表す。$I$ を $n$ 次単位行列とする。

$C\in {\mathbb{S}}^n$ の固有値を重複を込めて ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$ とし、${\lambda }_k>{\lambda }_{k+1}$ と仮定する。$W$ を、${\lambda }_k$ 以上の固有値に属する $C$ の固有空間すべての和 $W={\sum }_{\mu \ge {\lambda }_k}\mathrm{Ker}(C-\mu I)$ とし、$P$ を ${\mathbb{R}}^n$ から $W$ への直交射影の行列とする。半正定値計画
$$\text{maximize}⟨C,X⟩\text{subject to}\mathrm{tr}X=k,0⪯X⪯I,X\in {\mathbb{S}}^n$$
について、その最適解（実行可能解のうち $⟨C,X⟩$ が最大となるもの）は $P$ ただ一つであることを証明せよ。

ただし、実対称行列が直交行列で対角化できること、およびこの半正定値計画の最適値が ${\lambda }_1+{\lambda }_2+\cdots +{\lambda }_k$ であることは用いてよい。

${\mathcal{S}}^5$ を $5$ 次実対称行列全体とし、$X⪰O$ は $X$ が半正定値であることを表す。$X=(X_{ij})\in {\mathcal{S}}^5$ を変数とする次の半正定値計画問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}f(X)=(X_{12}+X_{23}+X_{34}+X_{45}+X_{15})+\frac{1}{2}(X_{13}+X_{24}+X_{35}+X_{14}+X_{25})$$
$$\text{subject to}{X}_{ii}=1(i=1,2,3,4,5),X⪰O.$$
$(\mathrm{P})$ の最適値（$f(X)$ の最小値）を求めよ。

$x=(x_1,\dots ,x_5)\in {\mathbb{R}}^5$ を変数とする次の最適化問題 $(\mathrm{P})$ を考える（添字は $\mathrm{mod}5$ で考え、$x_6=x_1$ とする）。
$$(\mathrm{P})\text{minimize}f(x)=2\sum _{i=1}^5{x}_i{x}_{i+1}\text{subject to}{x}_i^2-1=0(i=1,\dots ,5).$$
その最適値を $p^{\ast }$ とする。等式制約に乗数 $\nu =({\nu }_1,\dots ,{\nu }_5)\in {\mathbb{R}}^5$ を対応させたラグランジュ関数
$$L(x,\nu )=f(x)+\sum _{i=1}^5{\nu }_i(x_i^2-1)$$
に対し、双対関数を $q(\nu )={\inf }_{x\in {\mathbb{R}}^5}L(x,\nu )$（値 $-\infty$ を許す）、ラグランジュ双対問題の最適値を $d^{\ast }={\sup }_{\nu \in {\mathbb{R}}^5}q(\nu )$ とする。双対ギャップ $p^{\ast }-d^{\ast }$ を求めよ。

$n\ge 2$ を整数とし、$J$ を成分がすべて $1$ の $n$ 次正方行列、$I$ を $n$ 次単位行列、$W=J-I$ とする。$x\in {\mathbb{R}}^n$ を変数とする最適化問題
$$(\mathrm{P})\text{minimize}{x}^{\top }Wx\text{subject to}{x}_i^2-1=0(i=1,\dots ,n)$$
を考え、その最適値を $p^{\ast }$ とする。$\nu \in {\mathbb{R}}^n$ に対しラグランジュ関数を
$$L(x,\nu )=x^{\top }Wx+\sum _{i=1}^n{\nu }_i(x_i^2-1)$$
と定め、双対関数を $g(\nu )={\inf }_{x\in {\mathbb{R}}^n}L(x,\nu )\in [-\infty ,\infty )$、双対問題の最適値を $d^{\ast }={\sup }_{\nu \in {\mathbb{R}}^n}g(\nu )$ とする。

双対ギャップ $p^{\ast }-d^{\ast }$ が、$n$ が奇数のとき $1$、$n$ が偶数のとき $0$ であることを証明せよ。