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

$2$ 次実対称行列
$$X=\left(\begin{array}{cc}{x}_{11}& x_{12}\\ x_{12}& x_{22}\end{array}\right)$$
を変数とする次の半正定値計画問題 $(\mathrm{P})$ を考える。ここで $X⪰O$ は $X$ が半正定値であることを表す。
$$(\mathrm{P})\text{minimize}4x_{11}+x_{22}\text{subject to}{x}_{12}=3,x_{11}\ge 2,X⪰O.$$
$(\mathrm{P})$ の最適値を求めよ。

${\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})$ の最適値を求めよ。

実数 $x_1,x_2$ についての線形計画問題 (P)
$$\begin{array}{rl}\text{maximize}& 2x_1+3x_2\\ \text{subject to}& x_1+x_2\le 4,\\ & x_1+3x_2\le 6,\\ & x_1\ge 0,x_2\ge 0\end{array}$$
を考える。(P) の最適解は $(x_1,x_2)=(3,1)$ であることがわかっている。(P) の 1 つ目の制約に対応する双対変数を $y_1$、2 つ目の制約に対応する双対変数を $y_2$ として双対問題 (D) を書き、相補性条件を用いて (D) の最適解 $(y_1,y_2)$ を求めよ。

${\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})$ の最適値を求めよ。