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

有限集合 $X=\{0,1,3\}\subset \mathbb{R}$ 上の次の最適化問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}{x}^2\text{subject to}2-x\le 0,x\in X$$
$(\mathrm{P})$ の最適値を $p^{\ast }$ とする。不等式制約 $2-x\le 0$ だけを乗数 $\mu \ge 0$ で緩和したラグランジュ関数を $L(x,\mu )=x^2+\mu (2-x)$ とし、双対関数を $q(\mu )={\min }_{x\in X}L(x,\mu )$、双対問題の最適値を $d^{\ast }={\sup }_{\mu \ge 0}q(\mu )$ とする。双対ギャップ $p^{\ast }-d^{\ast }$ を求めよ。

頂点集合を $V=\{0,1,2,3,4,5\}$ とし、辺集合を
$$E=\{\{0,i\}\mid 1\le i\le 5\}\cup \{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,1\}\}$$
とする単純グラフ $G$（車輪グラフ $W_5$。頂点 $0$ が中心、$1,\dots ,5$ が外周の $5$ サイクル）を考える。$G$ の最大安定集合問題の整数計画の線形緩和の実行可能領域
$$P=\left\{x=(x_0,x_1,\dots ,x_5)\in {\mathbb{R}}^6|x_v\ge 0(v\in V),x_u+x_v\le 1(\{u,v\}\in E)\right\}$$
は有界な凸多面体である。$P$ の頂点（端点）の個数を求めよ。

頂点集合 $V=\{1,2,3,4,5,6\}$、辺集合
$$E=\{\{1,2\},\{1,3\},\{2,3\},\{3,4\},\{4,5\},\{4,6\},\{5,6\}\}$$
の単純グラフ $G$ を考える（2 つの三角形 $\{1,2,3\}$, $\{4,5,6\}$ を辺 $\{3,4\}$ でつないだグラフ）。$G$ の安定集合問題の線形計画緩和の実行可能領域
$$P=\left\{x\in {\mathbb{R}}^6|x_v\ge 0(v\in V),x_u+x_v\le 1(\{u,v\}\in E)\right\}$$
の頂点（端点）の個数を求めよ。

$x=(x_1,x_2,x_3,x_4)\in {\mathbb{R}}^4$ とし、整数計画問題（0-1 ナップサック問題）
$$\text{maximize}{c}^{\top }x\text{subject to}2x_1+3x_2+4x_3+5x_4\le 7,x\in \{0,1{\}}^4$$
の線形計画緩和の実行可能領域
$$P=\left\{x\in {\mathbb{R}}^4|2x_1+3x_2+4x_3+5x_4\le 7,0\le x_i\le 1(i=1,2,3,4)\right\}$$
を考える。凸多面体 $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})$ の最適値を求めよ。