凸最適化・組合せ最適化

凸関数 $f:\mathbb{R}\to \mathbb{R}$ を
$$f(x)=x^2-4x+6|x-1|$$
で定める。凸関数 $f$ の点 $x$ での劣微分を $\partial f(x)=\{g\in \mathbb{R}\mid f(y)\ge f(x)+g(y-x)\text{for all }y\in \mathbb{R}\}$ とする。最適性条件 $0\in \partial f(x)$ を用いて、$f$ を最小にする実数 $x$ を求めよ。

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

実数 $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}$$
この問題の最適値（目的関数の最小値）を求めよ。

${\mathbb{R}}^2$ の多面体
$$P=\{(x,y)\in {\mathbb{R}}^2\mid x\ge 0,y\ge 0,x+y\le 4,x\le 3,y\le 3\}$$
を考える。点 $z\in P$ が $P$ の頂点であるとは、$z$ で等号が成り立つ（活性な）制約の係数ベクトルのうち一次独立なものが $2$ 個あることとする。$P$ の頂点の個数を求めよ。

頂点集合を $V=\{1,2,3,4,5,6\}$ とし、辺集合 $E=\{e_1,e_2,e_3,e_4,e_5,e_6\}$ を
$$e_1=\{1,2\},e_2=\{2,3\},e_3=\{1,3\},e_4=\{4,5\},e_5=\{5,6\},e_6=\{3,4\}$$
とするグラフ $G=(V,E)$ を考える。$M(G)$ を $E$ 上のグラフ的マトロイド（辺の部分集合が独立であるとは、それが閉路を含まないこととする）とし、$r$ をその階数関数とする。$X=\{e_1,e_2,e_3,e_4,e_5\}$ に対して $r(X)$ を求めよ。

関数 $f:\mathbb{R}\to \mathbb{R}$ を $f(x)=2x^2-3x+1$ で定める。$f$ の凸共役（ルジャンドル・フェンシェル変換）
$$f^{\ast }(y)=\underset{x\in \mathbb{R}}{\sup }(xy-f(x))(y\in \mathbb{R})$$
を $y$ の式で表せ。

${\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)$ の形で答えよ。

$x=(x_1,x_2)\in {\mathbb{R}}^2$ を変数とする次の最適化問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}{x}_1^2+x_2^2\text{subject to}5-x_1-2x_2\le 0$$
不等式制約に乗数 $\mu \ge 0$ を対応させたラグランジュ関数を
$$L(x,\mu )=x_1^2+x_2^2+\mu (5-x_1-2x_2)$$
とし、ラグランジュ双対関数を $q(\mu )={\min }_{x\in {\mathbb{R}}^2}L(x,\mu )$ $(\mu \ge 0)$ で定める。$q(\mu )$ を $\mu$ の式で表せ。

頂点集合を $V=\{1,2,3,4,5,6,7\}$、辺集合を
$$E=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,7\},\{7,1\}\}$$
とする閉路グラフ $C_7$ を考える。$C_7$ の最大安定集合問題の整数計画
$$(\mathrm{IP})\text{maximize}\sum _{v=1}^7{x}_v\text{subject to}{x}_u+x_v\le 1(\{u,v\}\in E),x_v\in \{0,1\}(v\in V)$$
の最適値を $z_{\mathrm{IP}}$ とし、$x_v\in \{0,1\}$ を $0\le x_v\le 1$ に置き換えた線形計画緩和 $(\mathrm{LP})$ の最適値を $z_{\mathrm{LP}}$ とする。$z_{\mathrm{LP}}-z_{\mathrm{IP}}$ を求めよ。

$E=\{1,2,3,4,5,6\}$ とし、$E$ 上の一様マトロイド $U_{3,6}$ を考える。すなわち、$E$ の部分集合 $I$ が独立であるとは $|I|\le 3$ であることとする。各要素 $i\in E$ に重み $w(i)$ を
$$w(1)=4,w(2)=7,w(3)=2,w(4)=7,w(5)=5,w(6)=3$$
で与え、基 $B$ の重みを $w(B)={\sum }_{i\in B}w(i)$ と定める。$U_{3,6}$ の基の重みの最大値を求めよ。

${\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=\{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 }$ を求めよ。

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

頂点集合を $\{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 }$ の基の重みの最大値を求めよ。

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

関数 $f:\mathbb{R}\to \mathbb{R}\cup \{+\infty \}$ を
$$f(x)=\{\begin{array}{ll}\frac{1}{x}+4x& (x>0)\\ +\infty & (x\le 0)\end{array}$$
で定める。$f$ の凸共役（ルジャンドル・フェンシェル変換）を
$$f^{\ast }(y)=\underset{x\in \mathbb{R}}{\sup }(xy-f(x))(y\in \mathbb{R})$$
とする。実数 $y$ が $y<4$ を満たすとき、$f^{\ast }(y)$ を $y$ の式で表せ。

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

$E=\{1,2,3,4,5,6,7\}$ とし、各 $i\in E$ に ${\mathbb{R}}^3$ のベクトル $v_i$ を次のように対応させる。
$$v_1=(1,0,0),v_2=(0,1,0),v_3=(1,1,0),v_4=(0,0,1),v_5=(1,0,1),v_6=(2,2,0),v_7=(1,1,1)$$
$M$ を $E$ 上の線形マトロイド（$I\subseteq E$ が独立であるとは、$\{v_i{\}}_{i\in I}$ が $\mathbb{R}$ 上一次独立であること）とし、$M^{\ast }$ をその双対マトロイド（基は $M$ の基の補集合）とする。各要素の重みを
$$w_1=9,w_2=8,w_3=10,w_4=4,w_5=7,w_6=6,w_7=5$$
と定め、部分集合 $B$ の重みを $w(B)={\sum }_{i\in B}{w}_i$ とする。$M^{\ast }$ の基 $B^{\ast }$ にわたる $w(B^{\ast })$ の最大値を求めよ。

${\mathbb{R}}^4$ に標準内積とユークリッドノルム $\Vert \cdot {\Vert }_2$ を入れ、$\Vert x{\Vert }_1={\sum }_{i=1}^4|x_i|$ とする。凸関数 $f:{\mathbb{R}}^4\to \mathbb{R}$ を
$$f(x)=2\Vert x{\Vert }_1+\frac{1}{2}\Vert x{\Vert }_2^2$$
で定め、その近接写像を
$${\mathrm{prox}}_f(v)=\underset{x\in {\mathbb{R}}^4}{\mathrm{argmin}}\left\{f(x)+\frac{1}{2}\Vert x-v{\Vert }_2^2\right\}$$
とする。$v=(5,-1,3,-4)$ に対して ${\mathrm{prox}}_f(v)=(p_1,p_2,p_3,p_4)$ を求め、組 $(p_1,p_2,p_3,p_4)$ で答えよ。

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

$n\ge 2$ を整数、$k$ を $1\le k\le n-1$ を満たす整数とし、
$$P=\left\{x\in {\mathbb{R}}^n:0\le x_i\le 1(i=1,\dots ,n),\sum _{i=1}^n{x}_i=k\right\}$$
とおく。ここで $P$ の頂点とは、$P$ の端点、すなわち「$y,z\in P$ かつ $x=\frac{1}{2}(y+z)$ ならば $y=z=x$」を満たす点 $x\in P$ のことをいう。

$P$ の頂点全体が、成分がすべて $0$ または $1$ で、$1$ の個数がちょうど $k$ 個であるベクトル全体と一致することを示し、特に $P$ の頂点の個数が $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ であることを証明せよ。

${\mathbb{R}}^3$ に標準内積 $⟨\cdot ,\cdot ⟩$ を入れる。関数 $f:{\mathbb{R}}^3\to \mathbb{R}\cup \{+\infty \}$ を
$$f(x)=\{\begin{array}{ll}{x}_1^2+x_2^2+x_3^2+x_1{x}_2+x_2{x}_3& (x_1\ge 0,x_2\ge 0,x_3\ge 0)\\ +\infty & (\text{otherwise})\end{array}$$
で定める。$f$ の凸共役（ルジャンドル・フェンシェル変換）を
$$f^{\ast }(y)=\underset{x\in {\mathbb{R}}^3}{\sup }(⟨y,x⟩-f(x))$$
とするとき、$y=(3,1,3)$ における値 $f^{\ast }(3,1,3)$ を求めよ。

有限集合 $E=\{1,2,3,4,5,6,7,8\}$ の部分集合の族 $(A_1,A_2,A_3,A_4,A_5)$ を次で定める。
$$A_1=\{1,2\},A_2=\{1,2\},A_3=\{1,3,4\},A_4=\{3,4,5\},A_5=\{5,6,7,8\}.$$
部分集合 $I\subseteq E$ が独立であるとは、単射 $\phi :I\to \{1,2,3,4,5\}$ で、すべての $i\in I$ に対して $i\in A_{\phi (i)}$ を満たすものが存在することと定める（$\phi$ は空写像でもよく、$\varnothing$ は独立とする）。このとき独立集合全体は $E$ 上のマトロイド $M$（族 $(A_1,\dots ,A_5)$ の横断マトロイド）をなす。

各要素の重み $w:E\to \mathbb{R}$ を
$$w(1)=6,w(2)=5,w(3)=8,w(4)=7,w(5)=10,w(6)=9,w(7)=4,w(8)=3$$
とし、$B\subseteq E$ に対して $w(B)={\sum }_{i\in B}w(i)$ とおく。$M$ の基 $B$ に対する $w(B)$ の最大値を求めよ。

頂点集合 $V=\{s,a,b,c,t\}$ の有向グラフ $G$ を考える。各有向辺 $e$ には費用 $c_e$ と所要時間 $d_e$ が次のように与えられている（$(c_e,d_e)$ の順に記す）。
$$s\to a:(2,3),s\to b:(5,1),a\to b:(1,1),a\to c:(3,1),$$
$$b\to c:(1,2),a\to t:(1,7),b\to t:(4,2),c\to t:(2,1).$$
グラフにはこれ以外の辺はない。$\mathcal{P}$ を $s$ から $t$ への有向道全体とし、有向道 $P$ の費用と所要時間を $c(P)={\sum }_{e\in P}{c}_e$、$d(P)={\sum }_{e\in P}{d}_e$ と定める。次の制約付き最短路問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}c(P)\text{subject to}d(P)\le 6,P\in \mathcal{P}.$$
$(\mathrm{P})$ の最適値を $p^{\ast }$ とする。時間制約 $d(P)\le 6$ のみを乗数 $\lambda \ge 0$ で緩和したラグランジュ双対関数を
$$\phi (\lambda )=\underset{P\in \mathcal{P}}{\min }\{c(P)+\lambda (d(P)-6)\}(\lambda \ge 0)$$
と定め、双対問題の最適値を $d^{\ast }={\sup }_{\lambda \ge 0}\phi (\lambda )$ とする。$p^{\ast }$ と $d^{\ast }$ をこの順に組 $(p^{\ast },d^{\ast })$ で求めよ。

$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$ の頂点の個数を求めよ。

$2$ 次実正方行列全体 ${\mathbb{R}}^{2\times 2}$ に、フロベニウス内積 $⟨X,Y⟩=\mathrm{tr}(X^{\top }Y)$ とフロベニウスノルム $\Vert X{\Vert }_F=\sqrt{⟨X,X⟩}$ を入れる。$X$ の特異値を ${\sigma }_1(X)\ge {\sigma }_2(X)\ge 0$ とし、核ノルムを $\Vert X{\Vert }_{\ast }={\sigma }_1(X)+{\sigma }_2(X)$ と定める。凸関数 $f:{\mathbb{R}}^{2\times 2}\to \mathbb{R}$ を $f(X)=3\Vert X{\Vert }_{\ast }$ で定め、そのモロー包
$$e(A)=\underset{X\in {\mathbb{R}}^{2\times 2}}{\min }\left\{f(X)+\frac{1}{2}\Vert X-A{\Vert }_F^2\right\}$$
を考える。
$$A=\left(\begin{array}{cc}3& 0\\ 4& 5\end{array}\right)$$
のとき、$e(A)$ の値を求めよ。

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

頂点集合 $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\}$$
の頂点（端点）の個数を求めよ。

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

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

${\mathbb{R}}^2$ に標準内積 $⟨\cdot ,\cdot ⟩$ を入れる。凸関数 $f:{\mathbb{R}}^2\to \mathbb{R}$ を
$$f(x_1,x_2)=\log \left(1+e^{x_1}+e^{x_2}\right)$$
で定め、その凸共役（ルジャンドル・フェンシェル変換）を
$$f^{\ast }(y)=\underset{x\in {\mathbb{R}}^2}{\sup }\{⟨x,y⟩-f(x)\}(y\in {\mathbb{R}}^2)$$
とする。$f^{\ast }\left(\frac{1}{2},\frac{1}{3}\right)$ の値を求めよ。

${\mathbb{R}}^2$ に標準内積とユークリッドノルム $\Vert \cdot {\Vert }_2$ を入れる。凸関数 $f:{\mathbb{R}}^2\to \mathbb{R}$ を
$$f(x_1,x_2)=3|x_1-x_2|+|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\in {\mathbb{R}}^2)$$
とする。$v=(7,-3)$ のとき、${\mathrm{prox}}_f(v)=(p_1,p_2)$ とおく。組 $(p_1,p_2)$ を求めよ。

閉区間 $X=[0,4]\subset \mathbb{R}$ 上の次の最適化問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}f(x)=-x^2+5x\text{subject to}g(x)=1-x\le 0,x\in X.$$
不等式制約 $g(x)\le 0$ だけに乗数 $\lambda \ge 0$ を付けてラグランジュ関数 $L(x,\lambda )=f(x)+\lambda g(x)$ を作り（$x\in X$ という制約は双対化しない）、双対関数を
$$q(\lambda )=\underset{x\in X}{\min }L(x,\lambda )(\lambda \ge 0)$$
と定める。$(\mathrm{P})$ の最適値を $p^{\ast }$、双対問題 $\underset{\lambda \ge 0}{\max }q(\lambda )$ の最適値を $d^{\ast }$ とする。組 $(p^{\ast },d^{\ast })$ をこの順に求めよ。

$X=[0,2]\times [0,2]\subset {\mathbb{R}}^2$ とし、次の最適化問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}-x_1{x}_2\text{subject to}{x}_1+2x_2\le 2,x=(x_1,x_2)\in X.$$
$(\mathrm{P})$ の最適値を $p^{\ast }$ とする。制約 $x_1+2x_2\le 2$ だけを乗数 $\lambda \ge 0$ で緩和したラグランジュ双対関数
$$g(\lambda )=\underset{x\in X}{\min }\{-x_1{x}_2+\lambda (x_1+2x_2-2)\}$$
を用い、双対問題の最適値を $d^{\ast }={\sup }_{\lambda \ge 0}g(\lambda )$ とする。双対ギャップ $p^{\ast }-d^{\ast }$ を求めよ。

${\mathbb{R}}^2$ に標準内積 $⟨\cdot ,\cdot ⟩$ とユークリッドノルム $\Vert \cdot {\Vert }_2$ を入れ、$\Vert x{\Vert }_1=|x_1|+|x_2|$ とする。凸関数 $f:{\mathbb{R}}^2\to \mathbb{R}$ を
$$f(x)=\frac{1}{3}\Vert x{\Vert }_2^3+2\Vert x{\Vert }_1$$
で定め、その凸共役（ルジャンドル・フェンシェル変換）を
$$f^{\ast }(y)=\underset{x\in {\mathbb{R}}^2}{\sup }(⟨x,y⟩-f(x))(y\in {\mathbb{R}}^2)$$
とする。$f^{\ast }(5,6)$ の値を求めよ。

$n$ を正の整数、$\lambda >0$ を実数とし、$f:{\mathbb{R}}^n\to \mathbb{R}$ を
$$f(x)=\lambda \sum _{i=1}^n|x_i|+\frac{1}{2}\sum _{i=1}^n{x}_i^2(x=(x_1,\dots ,x_n))$$
で定める。$f$ の凸共役 $f^{\ast }:{\mathbb{R}}^n\to (-\infty ,\infty ]$ を
$$f^{\ast }(y)=\underset{x\in {\mathbb{R}}^n}{\sup }\left(⟨y,x⟩-f(x)\right)$$
で定める（$⟨\cdot ,\cdot ⟩$ は標準内積）。実数 $a$ に対し $a_{+}=\max \{a,0\}$ と書く。このとき、すべての $y\in {\mathbb{R}}^n$ に対して
$$f^{\ast }(y)=\frac{1}{2}\sum _{i=1}^n{\left((|y_i|-\lambda {)}_{+}\right)}^2$$
が成り立ち、特に $f^{\ast }$ はいたるところ有限であることを証明せよ。

$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$ であることは用いてよい。

$E$ を有限集合、$\mathcal{I}$ を $E$ の部分集合の族とし、$M=(E,\mathcal{I})$ は次の 3 条件を満たすマトロイドとする。
- (I1) $\varnothing \in \mathcal{I}$
- (I2) $J\in \mathcal{I}$ かつ $J^{\prime }\subseteq J$ ならば $J^{\prime }\in \mathcal{I}$
- (I3) $J,K\in \mathcal{I}$ かつ $|J|<|K|$ ならば、ある $x\in K\setminus J$ が存在して $J\cup \{x\}\in \mathcal{I}$

$\mathcal{I}$ の元を独立集合、包含関係について極大な独立集合を基という。すべての基の要素数は等しい（これを $M$ の階数 $r$ とする）ことは用いてよい。

重み $w:E\to \mathbb{R}$ が単射である（相異なる要素の重みは相異なる）とし、基 $B$ の重みを $w(B)={\sum }_{x\in B}w(x)$ と定める。このとき、重み $w(B)$ を最大にする基はただ 1 つであることを証明せよ。

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

${\mathbb{R}}^2$ に標準内積 $⟨\cdot ,\cdot ⟩$ を入れ、凸関数 $f:{\mathbb{R}}^2\to \mathbb{R}$ を
$$f(x_1,x_2)=\log \left(e^{x_1}+e^{x_2}\right)+\frac{1}{2}(x_1-x_2{)}^2$$
で定める。$f$ の凸共役（ルジャンドル・フェンシェル変換）を
$$f^{\ast }(y)=\underset{x\in {\mathbb{R}}^2}{\sup }\left\{⟨y,x⟩-f(x)\right\}(y\in {\mathbb{R}}^2)$$
とする。
$$y^{\circ }=\left(\frac{3}{4}+\log 3,\frac{1}{4}-\log 3\right)$$
に対して、$f^{\ast }(y^{\circ })$ の値を求めよ。

頂点集合を $V=\{1,2,3,4,5,6,7\}$ とする単純グラフ $G$ を考える。$G$ の辺集合 $E$ は、$\{1,2,3,4,5\}$ の異なる $2$ 頂点を結ぶ $10$ 本の辺すべてと、$4$ 本の辺 $\{1,6\},\{2,6\},\{3,6\},\{6,7\}$ からなる（$|E|=14$）。辺 $\{i,j\}$ を $ij$ と書く。各辺の重み $w$ は次のとおりである。
$$\begin{array}{ccccccccccccccc}e& 16& 26& 45& 35& 67& 12& 13& 14& 15& 23& 24& 25& 34& 36\\ w(e)& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14\end{array}$$
閉路を含まない辺集合を森とよぶ（空集合も森とする）。$E$ の部分集合 $I$ が独立であることを「森 $F_1,F_2\subseteq E$ を用いて $I=F_1\cup F_2$ と書けること」と定めると、これは $E$ 上のマトロイド $M$（$G$ のグラフ的マトロイド $M(G)$ とそれ自身との合併 $M(G)\vee M(G)$）を定める。$M$ の階数 $r_M(E)$ と、$M$ の基 $B$ の重み $w(B)={\sum }_{e\in B}w(e)$ の最大値を、この順に組で求めよ。

$x=(x_1,x_2,x_3,x_4)\in \{0,1{\}}^4$ を変数とする次の 0-1 ナップサック問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{maximize}7x_1+5x_2+4x_3+3x_4\text{subject to}5x_1+4x_2+3x_3+2x_4\le 9,x\in \{0,1{\}}^4.$$
$(\mathrm{P})$ の最適値を $p^{\ast }$ とする。不等式制約だけに乗数 $\lambda \ge 0$ を導入してラグランジュ関数
$$L(x,\lambda )=7x_1+5x_2+4x_3+3x_4+\lambda (9-5x_1-4x_2-3x_3-2x_4)$$
を定め、双対関数を $g(\lambda )={\max }_{x\in \{0,1{\}}^4}L(x,\lambda )$、双対問題の最適値を $d^{\ast }={\min }_{\lambda \ge 0}g(\lambda )$ とする。双対ギャップ $d^{\ast }-p^{\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$ の頂点（端点）の個数を求めよ。

頂点集合を $\{1,2,3,4,5\}$ とする完全グラフ $K_5$ の辺集合を $E$ とし、$M(K_5)$ を $E$ 上のグラフ的マトロイド（独立集合は森をなす辺集合）、$M^{\ast }$ をその双対マトロイドとする。さらに $M^{\ast }$ の階数 $5$ への切り詰め $T$ を
$$\mathcal{I}(T)=\{I\subseteq E:I\text{ は }{M}^{\ast }\text{ で独立},|I|\le 5\}$$
で定める（$T$ はマトロイドである）。

辺 $ij$（$1\le i<j\le 5$）に重み $w(ij)=2^i+2^j$ を与える。$T$ の基 $B$ のうち、重みの和 $w(B)={\sum }_{e\in B}w(e)$ が最大となるものについて、その最大値を求めよ。

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

$B=[-1,2]\times [-1,2]\subset {\mathbb{R}}^2$ とし、次の最適化問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}f(x)=-x_1{x}_2\text{subject to}{x}_1+x_2=1,x=(x_1,x_2)\in B$$
等式制約 $x_1+x_2=1$ だけを乗数 $\mu \in \mathbb{R}$ で緩和し、集合制約 $x\in B$ は残したラグランジュ関数
$$L(x,\mu )=-x_1{x}_2+\mu (x_1+x_2-1)$$
から双対関数 $q(\mu )=\underset{x\in B}{\min }L(x,\mu )$ を定め、双対問題 $(\mathrm{D})$: $\underset{\mu \in \mathbb{R}}{\max }q(\mu )$ を考える。$(\mathrm{P})$ の最適値を $p^{\ast }$、$(\mathrm{D})$ の最適値を $d^{\ast }$ とするとき、双対ギャップ $p^{\ast }-d^{\ast }$ を求めよ。

${\mathbb{F}}_2=\{0,1\}$ を 2 元体とし、$E={\mathbb{F}}_2^4\setminus \{0\}$（15 個のベクトルからなる集合）とする。$E$ 上のマトロイド $M$ を、部分集合 $I\subseteq E$ が ${\mathbb{F}}_2$ 上 1 次独立であるとき、かつそのときに限り独立集合であるものとして定める（$M$ の階数は $4$）。$M^{\ast }$ を $M$ の双対マトロイド、すなわち $M$ の基の補集合 $E\setminus B$ 全体を基の族とするマトロイドとする。

ベクトル $v\in E$ の成分のうち $1$ であるものの個数を $\mathrm{hw}(v)$ と書き、重み $w:E\to \mathbb{Z}$ を
$$w(v)=\{\begin{array}{ll}1& (\mathrm{hw}(v)=2,4)\\ 2& (\mathrm{hw}(v)=1)\\ 3& (\mathrm{hw}(v)=3)\end{array}$$
で定める。$M^{\ast }$ の基 $B^{\ast }$ の重みを $w(B^{\ast })={\sum }_{v\in B^{\ast }}w(v)$ とするとき、$w(B^{\ast })$ が最大となる $M^{\ast }$ の基 $B^{\ast }$ の個数を求めよ。

頂点集合を $V=\{1,2,3,4,5\}$ とする完全グラフ $K_5$ の辺集合を $E$（$|E|=10$）とする。頂点 $v$ に接続する辺の集合を $\delta (v)$ と書く。$K_5$ の最大マッチング問題の整数計画の線形緩和として、${\mathbb{R}}^E$ の多面体
$$P=\left\{x\in {\mathbb{R}}^E|x_e\ge 0(e\in E),\sum _{e\in \delta (v)}{x}_e\le 1(v\in V)\right\}$$
を考える。$P$ の頂点のうち、整数ベクトルでない（少なくとも 1 つの成分が整数でない）ものの個数を求めよ。

${\mathbb{R}}^3$ に標準内積 $⟨\cdot ,\cdot ⟩$ を入れ、
$$C=\left\{x\in {\mathbb{R}}^3|x_1+x_2+x_3=1,0\le x_i\le \frac{1}{2}(i=1,2,3)\right\}$$
とする。関数 $f:{\mathbb{R}}^3\to \mathbb{R}\cup \{+\infty \}$ を
$$f(x)=\{\begin{array}{ll}\sum _{i=1}^3{x}_i\log x_i& (x\in C)\\ +\infty & (x\notin C)\end{array}$$
で定める。ただし $0\log 0=0$ とする。$f$ の凸共役 $f^{\ast }(y)={\sup }_{x\in {\mathbb{R}}^3}\{⟨x,y⟩-f(x)\}$ について、$y=(2\log 3,\log 3,0)$ における値 $f^{\ast }(y)$ を求めよ。