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

頂点集合を $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)$ の最大値を、この順に組で求めよ。

有限集合 $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)$ の最大値を求めよ。

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

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

$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 }$ はいたるところ有限であることを証明せよ。