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

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

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

$R^{4}$ に標準内積とユークリッドノルム $∥ \cdot ∥_{2}$ を入れ、 $∥ x ∥_{1} = \sum_{i = 1}^{4} ∣ x_{i} ∣$ とする。凸関数 $f : R^{4} \to R$ を
$f (x) = 2∥ x ∥_{1} + \frac{1}{2} ∥ x ∥_{2}^{2}$
で定め、その近接写像を
$prox_{f} (v) = x \in R^{4} arg min {f (x) + \frac{1}{2} ∥ x - v ∥_{2}^{2}}$
とする。 $v = (5, - 1, 3, - 4)$ に対して $prox_{f} (v) = (p_{1}, p_{2}, p_{3}, p_{4})$ を求め、組 $(p_{1}, p_{2}, p_{3}, p_{4})$ で答えよ。

この問題で使うもの

近接写像（説明と入口の問題）
劣勾配と劣微分（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

目的関数は座標ごとに分離します。1 変数関数 $2∣ t ∣ + \frac{1}{2} t^{2} + \frac{1}{2} (t - v_{i})^{2}$ の最小化を考えましょう。

ヒント 2

最適性条件は $0 \in \partial h (t)$ です。 $\partial ∣ t ∣$ は $t = 0$ で区間 $[- 1, 1]$ になることに注意すると、 $v_{i} \in 2 t + 2 \partial ∣ t ∣$ が得られます。

ヒント 3

$∣ v_{i} ∣ \leq 2$ なら $t = 0$ 、 $v_{i} > 2$ なら $t = \frac{v _{i} - 2}{2}$ 、 $v_{i} < - 2$ なら $t = \frac{v _{i} + 2}{2}$ となります。これを各成分に当てはめましょう。

答えと解説

答えを見る

(\frac{3}{2}, 0, \frac{1}{2}, - 1)

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

解説を読む

目的関数 $f (x) + \frac{1}{2} ∥ x - v ∥_{2}^{2}$ は強凸なので最小点はただ 1 つで、座標ごとに分離する：
$i = 1 \sum 4 (2∣ x_{i} ∣ + \frac{1}{2} x_{i}^{2} + \frac{1}{2} (x_{i} - v_{i})^{2}) .$
よって各 $i$ について $h (t) = 2∣ t ∣ + \frac{1}{2} t^{2} + \frac{1}{2} (t - v_{i})^{2}$ を最小化すればよい。最適性条件は $0 \in \partial h (t)$ 、すなわち
$0 \in 2 \partial ∣ t ∣ + t + (t - v_{i}) ⟺ v_{i} \in 2 t + 2 \partial ∣ t ∣,$
ここで $\partial ∣ t ∣ = {sign t} (t \neq = 0)$ 、 $\partial ∣0∣ = [- 1, 1]$ 。

$t > 0$ のとき $v_{i} = 2 t + 2$ 、すなわち $t = \frac{v _{i} - 2}{2}$ （ $v_{i} > 2$ のとき）。
$t < 0$ のとき $v_{i} = 2 t - 2$ 、すなわち $t = \frac{v _{i} + 2}{2}$ （ $v_{i} < - 2$ のとき）。
$t = 0$ のとき $v_{i} \in [- 2, 2]$ 。

まとめると $p_{i} = \frac{1}{2} sign (v_{i}) max {∣ v_{i} ∣ - 2, 0}$ （軟しきい値処理を $\frac{1}{2}$ 倍したもの）。

$v = (5, - 1, 3, - 4)$ に適用すると
- $p_{1} = \frac{5 - 2}{2} = \frac{3}{2}$
- $∣ v_{2} ∣ = 1 \leq 2$ より $p_{2} = 0$
- $p_{3} = \frac{3 - 2}{2} = \frac{1}{2}$
- $p_{4} = \frac{- 4 + 2}{2} = - 1$

よって $prox_{f} (v) = (\frac{3}{2}, 0, \frac{1}{2}, - 1)$ 。

別解

目的関数は各座標に分離する。 $g (x) = 2∣ x ∣ + \frac{1}{2} x^{2} + \frac{1}{2} (x - v)^{2}$ を座標ごとに最小化する。 $g$ は強凸なので最小点は一意で、 $0 \in \partial g (x)$ 、すなわち $0 \in 2 \partial ∣ x ∣ + x + (x - v) = 2 \partial ∣ x ∣ + 2 x - v$ で特徴づけられる。\n\n- $x > 0$ のとき $2 + 2 x - v = 0$ より $x = (v - 2) /2$ 。これが正となるのは $v > 2$ 。\n- $x < 0$ のとき $- 2 + 2 x - v = 0$ より $x = (v + 2) /2$ 。これが負となるのは $v < - 2$ 。\n- $∣ v ∣ \leq 2$ のときは $x = 0$ （ $v \in 2 [- 1, 1]$ より $0 \in 2 \partial ∣0∣ - v$ ）。\n\nつまり $p_{i} = \frac{1}{2} sign (v_{i}) max (∣ v_{i} ∣ - 2, 0)$ 。\n\n $v_{1} = 5$ : $p_{1} = (5 - 2) /2 = 3/2$ 。\n $v_{2} = - 1$ : $∣ v_{2} ∣ \leq 2$ より $p_{2} = 0$ 。\n $v_{3} = 3$ : $p_{3} = (3 - 2) /2 = 1/2$ 。\n $v_{4} = - 4$ : $p_{4} = (- 4 + 2) /2 = - 1$ 。\n\n検算: $p_{1} = 3/2$ で $2 c d o t 1 + 2 c d o t f r a c 32 - 5 = 0$ 、 $p_{3} = 1/2$ で $2 + 1 - 3 = 0$ 、 $p_{4} = - 1$ で $- 2 - 2 + 4 = 0$ 、 $p_{2} = 0$ で $- v_{2} = 1 \in [- 2, 2]$ より劣勾配条件を満たす。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題