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

${\mathbb{R}}^3$ に標準内積とユークリッドノルム $\Vert \cdot {\Vert }_2$ を入れる。凸関数 $f:{\mathbb{R}}^3\to \mathbb{R}$ を
$$f(x)=2\left(|x_1|+|x_2|+|x_3|\right)$$
で定め、その近接写像を
$${\mathrm{prox}}_f(v)=\arg \underset{x\in {\mathbb{R}}^3}{\min }\left\{f(x)+\frac{1}{2}\Vert x-v{\Vert }_2^2\right\}$$
とする。$v=(5,-1,-3)$ のとき、${\mathrm{prox}}_f(v)=(x_1,x_2,x_3)$ を求め、組 $(x_1,x_2,x_3)$ の形で答えよ。

${\mathbb{R}}^2$ に標準内積とユークリッドノルム $\Vert \cdot {\Vert }_2$ を入れる。凸関数 $f:{\mathbb{R}}^2\to \mathbb{R}$ を
$$f(x)=5\Vert x{\Vert }_{\infty }=5\max \{|x_1|,|x_2|\}(x=(x_1,x_2))$$
で定め、近接写像を
$${\mathrm{prox}}_f(v)=\underset{x\in {\mathbb{R}}^2}{\mathrm{argmin}}\left\{f(x)+\frac{1}{2}\Vert x-v{\Vert }_2^2\right\}$$
とする。$v=(6,3)$ のとき、${\mathrm{prox}}_f(v)$ を成分表示 $(x_1,x_2)$ で求めよ。

実数 $x,y$ を変数とする次の最適化問題を考える。ここで、実対称行列 $A$ について $A⪰O$ は $A$ が半正定値であることを表す。
$$\begin{array}{rl}\text{minimize}& x+4y\\ \text{subject to}& \left(\begin{array}{cc}x& 2\\ 2& y\end{array}\right)⪰O\end{array}$$
この問題の最適値（目的関数の最小値）を求めよ。

実数 $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)$ を求めよ。

頂点集合を $\{1,2,3,4\}$ とする完全グラフ $K_4$ の辺集合を $E$ とし、$M$ を $E$ 上のグラフ的マトロイド（独立集合は森をなす辺集合）、$M^{\ast }$ をその双対マトロイドとする。各辺 $e\in E$ に重み $w(e)$ を
$$w(\{1,2\})=1,w(\{1,3\})=4,w(\{1,4\})=3,w(\{2,3\})=2,w(\{2,4\})=6,w(\{3,4\})=5$$
で与え、辺集合 $B$ の重みを $w(B)={\sum }_{e\in B}w(e)$ と定める。$M^{\ast }$ の基の重みの最大値を求めよ。