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

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

難易度 2大学院の講義の演習問題レベル大学院数学凸最適化・組合せ最適化

$2$ 次実正方行列全体 $R^{2 \times 2}$ に、フロベニウス内積 $⟨ X, Y ⟩ = tr (X^{⊤} Y)$ とフロベニウスノルム $∥ X ∥_{F} = ⟨ X, X ⟩$ を入れる。 $X$ の特異値を $σ_{1} (X) \geq σ_{2} (X) \geq 0$ とし、核ノルムを $∥ X ∥_{*} = σ_{1} (X) + σ_{2} (X)$ と定める。凸関数 $f : R^{2 \times 2} \to R$ を $f (X) = 3∥ X ∥_{*}$ で定め、そのモロー包
$e (A) = X \in R^{2 \times 2} min {f (X) + \frac{1}{2} ∥ X - A ∥_{F}^{2}}$
を考える。
$A = (3405)$
のとき、 $e (A)$ の値を求めよ。

この問題で使うもの

近接写像（説明と入口の問題）
固有値と固有ベクトル（説明と入口の問題）
行列の和・積と 2 次の逆行列（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

核ノルムはユニタリ不変（特異値だけで決まる）なので、最小化問題を $A$ の特異値ごとのスカラー問題に帰着させましょう。

ヒント 2

フォン・ノイマンのトレース不等式から $∥ X - A ∥_{F}^{2} \geq \sum_{i} (σ_{i} (X) - σ_{i} (A))^{2}$ が成り立ちます。各特異値について $min_{s \geq 0} {3 s + \frac{1}{2} (s - σ)^{2}}$ を解くと、最小点は $s = max {σ - 3, 0}$ です。

ヒント 3

$A^{⊤} A = (25202025)$ の固有値は $45, 5$ なので、特異値は $35$ と $5$ です。 $σ \geq 3$ なら最小値は $3 σ - \frac{9}{2}$ 、 $σ < 3$ なら $\frac{σ ^{2}}{2}$ となります。

答えと解説

答えを見る

95 - 2

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

解説を読む

1. 核ノルムの近接写像（特異値しきい値処理）

$A$ の特異値分解を $A = U diag (σ_{1}, σ_{2}) V^{⊤}$ （ $U, V$ は直交行列）とする。

フォン・ノイマンのトレース不等式 $⟨ X, A ⟩ \leq \sum_{i} σ_{i} (X) σ_{i} (A)$ を使う。 $∥ X ∥_{F}^{2} = \sum_{i} σ_{i} (X)^{2}$ であるから、
$∥ X - A ∥_{F}^{2} = ∥ X ∥_{F}^{2} - 2 ⟨ X, A ⟩ + ∥ A ∥_{F}^{2} \geq i = 1 \sum 2 (σ_{i} (X) - σ_{i} (A))^{2}$
が成り立つ。等号は $X = U diag (s_{1}, s_{2}) V^{⊤}$ （ $A$ と同じ特異ベクトルをもつ）のときに成り立つ。 $f (X) = 3 \sum_{i} σ_{i} (X)$ は特異値だけで決まる。したがって、 $s_{i} = σ_{i} (X)$ とおくと、問題は次のスカラー問題に分かれる。
$e (A) = i = 1 \sum 2 s_{i} \geq 0 min {3 s_{i} + \frac{1}{2} (s_{i} - σ_{i})^{2}} .$

各スカラー問題の最小点は $s_{i} = max {σ_{i} - 3, 0}$ である（ソフトしきい値処理）。最小値は次のとおり。
- $σ_{i} \geq 3$ のとき： $3 (σ_{i} - 3) + \frac{9}{2} = 3 σ_{i} - \frac{9}{2}$
- $σ_{i} < 3$ のとき： $s_{i} = 0$ で $\frac{σ _{i}^{2}}{2}$

（ $s_{i} = max {σ_{i} - 3, 0}$ を並べると得られる $U diag (s_{1}, s_{2}) V^{⊤}$ が近接写像 $prox_{f} (A)$ である。）

2. $A$ の特異値

$A^{⊤} A = (3045) (3405) = (25202025)$
の固有値は $25 \pm 20$ 、すなわち $45$ と $5$ である。よって $σ_{1} = 35 \approx 6.71$ 、 $σ_{2} = 5 \approx 2.24$ となる。

3. モロー包の値

$σ_{1} \geq 3$ 、 $σ_{2} < 3$ であるから、
$e (A) = (3 \cdot 35 - \frac{9}{2}) + \frac{( 5 ) ^{2}}{2} = 95 - \frac{9}{2} + \frac{5}{2} = 95 - 2.$

検算： $P = prox_{f} (A) = (35 - 3) u_{1} v_{1}^{⊤}$ とする。 $f (P) = 95 - 9$ である。 $A - P$ の特異値は $3$ と $5$ なので、 $\frac{1}{2} ∥ A - P ∥_{F}^{2} = \frac{1}{2} (9 + 5) = 7$ となる。合計は $95 - 2$ で、上の結果と一致する。

したがって $e (A) = 95 - 2$ である。

別解

モロー包の最小点は核ノルムのプロキシマル写像で与えられ、 $A$ の特異値に対する閾値 $3$ のソフトしきい値処理になる。

1. $A^{⊤} A = (25202025)$ の固有値は $45, 5$ なので、特異値は $σ_{1} = 35, σ_{2} = 5$ である。検算として、 $σ_{1} σ_{2} = 15 = ∣ det A ∣$ 、 $σ_{1}^{2} + σ_{2}^{2} = 50 = 9 + 16 + 25 = ∥ A ∥_{F}^{2}$ が成り立つ。
2. ソフトしきい値処理により、最小点 $X^{*}$ の特異値は $s_{i} = max (σ_{i} - 3, 0)$ となる。 $s_{1} = 35 - 3$ 、 $σ_{2} = 5 < 3$ より $s_{2} = 0$ 。
3. $f (X^{*}) = 3 (35 - 3) = 95 - 9$ 。
4. $X^{*}$ と $A$ は特異ベクトルを共有するので、 $∥ X^{*} - A ∥_{F}^{2} = (σ_{1} - s_{1})^{2} + (σ_{2} - s_{2})^{2} = 3^{2} + (5)^{2} = 14$ 。よって $\frac{1}{2} ∥ X^{*} - A ∥_{F}^{2} = 7$ 。
5. $e (A) = 95 - 9 + 7 = 95 - 2 \approx 18.12$ 。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題