この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

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

難易度 3大学院入試の専門科目の標準レベル証明問題大学院数学凸最適化・組合せ最適化

$n \geq 2$ を整数、 $k$ を $1 \leq k \leq n - 1$ を満たす整数とする。 $S^{n}$ を $n$ 次実対称行列全体とし、 $X, Y \in S^{n}$ に対して $⟨ X, Y ⟩ = tr (X Y)$ 、 $X ⪰ 0$ は $X$ が半正定値であること、 $X ⪯ Y$ は $Y - X ⪰ 0$ を表す。 $I$ を $n$ 次単位行列とする。

$C \in S^{n}$ の固有値を重複を込めて $λ_{1} \geq λ_{2} \geq \dots \geq λ_{n}$ とし、 $λ_{k} > λ_{k + 1}$ と仮定する。 $W$ を、 $λ_{k}$ 以上の固有値に属する $C$ の固有空間すべての和 $W = \sum_{μ \geq λ_{k}} Ker (C - μ I)$ とし、 $P$ を $R^{n}$ から $W$ への直交射影の行列とする。半正定値計画
$maximize ⟨ C, X ⟩ subject to tr X = k, 0 ⪯ X ⪯ I, X \in S^{n}$
について、その最適解（実行可能解のうち $⟨ C, X ⟩$ が最大となるもの）は $P$ ただ一つであることを証明せよ。

ただし、実対称行列が直交行列で対角化できること、およびこの半正定値計画の最適値が $λ_{1} + λ_{2} + \dots + λ_{k}$ であることは用いてよい。

この問題で使うもの

対称行列の直交対角化（説明と入口の問題）
半正定値制約と小さな半正定値計画（説明と入口の問題）
半正定値計画の双対と最適値の決定（説明と入口の問題）
固有値と固有ベクトル（説明と入口の問題）
内積空間とグラム・シュミットの直交化（説明と入口の問題）

この問題を解けるようになるまで（92 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$C = Q Λ Q^{⊤}$ と対角化して $Y = Q^{⊤} X Q$ に変換すると、目的関数は $\sum_{i} λ_{i} Y_{ii}$ になり、制約は形を保ちます。最適解 $X$ について $Y$ が $D = diag (1, \dots, 1, 0, \dots, 0)$ に一致することを示す方針で考えましょう。

ヒント 2

$λ_{k}$ と $λ_{k + 1}$ の間の数 $μ$ を使い、 $\sum_{i} λ_{i} d_{i} - \sum_{i \leq k} λ_{i}$ を符号が決まる項の和に書き直すと、対角成分 $d_{i} = Y_{ii}$ が決まります。非対角成分には「半正定値行列の対角成分が $0$ ならその行は $0$ 」という補題が効きます。

ヒント 3

$0 \leq d_{i} \leq 1$ 、 $\sum_{i} d_{i} = k$ から $\sum_{i \leq k} (λ_{i} - μ) (d_{i} - 1) + \sum_{i > k} (λ_{i} - μ) d_{i} = 0$ となり、各項が $0$ 以下なので $d_{i} = 1 (i \leq k)$ 、 $d_{i} = 0 (i > k)$ です。次に $i > k$ では $Y$ に、 $i \leq k$ では $I - Y$ に補題を使います。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$C = Q Λ Q^{⊤}$ と対角化し、 $Y = Q^{⊤} X Q$ について $tr Y = k$ 、 $0 ⪯ Y ⪯ I$ 、 $⟨ C, X ⟩ = \sum_{i} λ_{i} Y_{ii}$ を確かめ、 $0 \leq Y_{ii} \leq 1$ を導いている（2 点）
最適解では $\sum_{i} λ_{i} Y_{ii} = \sum_{i \leq k} λ_{i}$ となることと $λ_{k} > λ_{k + 1}$ を使い、 $λ_{k}$ と $λ_{k + 1}$ の間の値との比較などで、 $Y_{ii} = 1 (i \leq k)$ 、 $Y_{ii} = 0 (i > k)$ が強制されることを示している（3 点）
半正定値行列の対角成分が $0$ ならその行（列）が $0$ であることを示し、 $i > k$ では $Y$ に、 $i \leq k$ では $I - Y$ に適用して $Y$ の非対角成分がすべて $0$ 、すなわち $Y = D$ を導いている（3 点）
$\sum_{i \leq k} q_{i} q_{i}^{⊤}$ が $W$ への直交射影 $P$ に等しいこと（ $q_{1}, \dots, q_{k}$ が $W$ を張ることに $λ_{k} > λ_{k + 1}$ を使う）と、 $P$ が実行可能で目的関数値が最適値に等しいことを確かめ、最適解が $P$ ただ一つと結論している（2 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

直交対角化により、直交行列 $Q$ と $Λ = diag (λ_{1}, \dots, λ_{n})$ で $C = Q Λ Q^{⊤}$ となるものをとる（固有値は $λ_{1} \geq \dots \geq λ_{n}$ の順に並べる）。 $Q$ の第 $i$ 列を $q_{i}$ とすると $q_{1}, \dots, q_{n}$ は正規直交基底で $C q_{i} = λ_{i} q_{i}$ 。 $D = diag (1, \dots, 1, 0, \dots, 0)$ （ $1$ が $k$ 個）とおく。証明は次の順に行う。(I) 変数の変換、(II) 最適解ならば対角成分が決まること、(III) 最適解ならば $Q^{⊤} X Q = D$ であること、(IV) $Q D Q^{⊤} = P$ であること、(V) $P$ が実際に最適解であること。

(I) 変数の変換。 $X \in S^{n}$ に対し $Y = Q^{⊤} X Q$ とおく（ $Y$ も対称）。任意の $v$ で $v^{⊤} Y v = (Q v)^{⊤} X (Q v)$ なので $X ⪰ 0 \Rightarrow Y ⪰ 0$ 。 $Q^{⊤} Q = I$ より $I - Y = Q^{⊤} (I - X) Q$ なので、同じ理由で $I - X ⪰ 0 \Rightarrow I - Y ⪰ 0$ 。トレースの巡回性より $tr Y = tr (X Q Q^{⊤}) = tr X$ 、また
$⟨ C, X ⟩ = tr (Q Λ Q^{⊤} X) = tr (Λ Q^{⊤} X Q) = tr (Λ Y) = i = 1 \sum n λ_{i} Y_{ii} .$

(II) 対角成分。 $X$ を最適解とし、 $Y = Q^{⊤} X Q$ 、 $d_{i} = Y_{ii}$ とおく。第 $i$ 標準基底ベクトル $e_{i}$ について、 $Y ⪰ 0$ から $d_{i} = e_{i}^{⊤} Y e_{i} \geq 0$ 、 $I - Y ⪰ 0$ から $1 - d_{i} = e_{i}^{⊤} (I - Y) e_{i} \geq 0$ 。また $\sum_{i} d_{i} = tr Y = k$ 。最適値が $λ_{1} + \dots + λ_{k}$ であることから $\sum_{i} λ_{i} d_{i} = \sum_{i \leq k} λ_{i}$ 。

$μ = \frac{1}{2} (λ_{k} + λ_{k + 1})$ とおくと、 $λ_{k} > λ_{k + 1}$ より $λ_{k} > μ > λ_{k + 1}$ 。展開して確かめられる恒等式
$i = 1 \sum n λ_{i} d_{i} - i = 1 \sum k λ_{i} = i = 1 \sum k (λ_{i} - μ) (d_{i} - 1) + i = k + 1 \sum n (λ_{i} - μ) d_{i} + μ (i = 1 \sum n d_{i} - k)$
を考える（右辺を展開すると $- μ \sum_{i \leq k} d_{i} + μ k - μ \sum_{i > k} d_{i} + μ \sum_{i} d_{i} - μ k = 0$ の部分が消えて左辺になる）。左辺は $0$ 、右辺の最後の項も $\sum_{i} d_{i} = k$ より $0$ である。
- $i \leq k$ では $λ_{i} \geq λ_{k} > μ$ かつ $d_{i} - 1 \leq 0$ なので $(λ_{i} - μ) (d_{i} - 1) \leq 0$ 。
- $i > k$ では $λ_{i} \leq λ_{k + 1} < μ$ かつ $d_{i} \geq 0$ なので $(λ_{i} - μ) d_{i} \leq 0$ 。

0 以下の項の和が $0$ だから各項が $0$ で、 $λ_{i} - μ \neq = 0$ なので
$d_{i} = 1 (i \leq k), d_{i} = 0 (i > k) .$

(III) 非対角成分。 補題: $A \in S^{n}$ 、 $A ⪰ 0$ 、 $A_{ii} = 0$ ならば、すべての $j$ で $A_{ij} = 0$ 。
（証明） $j \neq = i$ とし、実数 $t$ に対し $v = t e_{i} + e_{j}$ とおくと $0 \leq v^{⊤} A v = t^{2} A_{ii} + 2 t A_{ij} + A_{j j} = 2 t A_{ij} + A_{j j}$ 。もし $A_{ij} \neq = 0$ なら $t = - (A_{j j} + 1) / (2 A_{ij})$ で右辺が $- 1 < 0$ となり矛盾。よって $A_{ij} = 0$ 。 $j = i$ のときは仮定そのもの。

$i \neq = j$ を任意にとる。
- $i > k$ のとき: $Y ⪰ 0$ 、 $Y_{ii} = 0$ に補題を使って $Y_{ij} = 0$ 。
- $i \leq k$ のとき: $I - Y ⪰ 0$ 、 $(I - Y)_{ii} = 1 - d_{i} = 0$ に補題を使って $(I - Y)_{ij} = - Y_{ij} = 0$ 。

よって $Y$ の非対角成分はすべて $0$ で、(II) と合わせて $Y = D$ 、すなわち $X = Q D Q^{⊤} = \sum_{i = 1}^{k} q_{i} q_{i}^{⊤}$ 。

(IV) $Q D Q^{⊤} = P$ 。 $U = span {q_{1}, \dots, q_{k}}$ とおき、 $U = W$ を示す。 $i \leq k$ では $λ_{i} \geq λ_{k}$ で $q_{i} \in Ker (C - λ_{i} I)$ なので $q_{i} \in W$ 、よって $U \subset W$ 。逆に $μ^{'} \geq λ_{k}$ 、 $w \in Ker (C - μ^{'} I)$ とし、 $w = \sum_{j} c_{j} q_{j}$ と展開すると $0 = (C - μ^{'} I) w = \sum_{j} c_{j} (λ_{j} - μ^{'}) q_{j}$ 。 $q_{j}$ は一次独立なので $c_{j} (λ_{j} - μ^{'}) = 0$ 。 $j > k$ では $λ_{j} \leq λ_{k + 1} < λ_{k} \leq μ^{'}$ なので $c_{j} = 0$ 、よって $w \in U$ 。 $W$ はこのような $w$ の和だから $W \subset U$ 。したがって $U = W$ 。

$q_{1}, \dots, q_{k}$ は $W$ の正規直交基底なので、任意の $v$ に対し $R v = \sum_{i \leq k} q_{i} (q_{i}^{⊤} v)$ （ $R = \sum_{i \leq k} q_{i} q_{i}^{⊤}$ ）は $W$ に属し、各 $j \leq k$ で $q_{j}^{⊤} (v - R v) = q_{j}^{⊤} v - q_{j}^{⊤} v = 0$ だから $v - R v ⊥ W$ 。よって $R$ は $W$ への直交射影で、 $R = P$ 。

(V) $P$ は最適解。 $P = Q D Q^{⊤}$ は対称で固有値は $1$ （ $k$ 個）と $0$ （ $n - k$ 個）だから、 $P$ と $I - P = Q (I - D) Q^{⊤}$ はともに固有値がすべて $0$ 以上で半正定値、すなわち $0 ⪯ P ⪯ I$ 。 $tr P = tr D = k$ 。(I) より $⟨ C, P ⟩ = tr (Λ D) = λ_{1} + \dots + λ_{k}$ で、これは最適値に等しいから $P$ は最適解である。

(II)〜(IV) より最適解は $P$ 以外にあり得ず、(V) より $P$ は最適解である。以上で、最適解が $P$ ただ一つであることが証明された。

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

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題