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

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

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

$R^{4}$ に標準内積とユークリッドノルム $∥ \cdot ∥_{2}$ を入れる。凸関数 $f : R^{4} \to R$ を
$f (x) = 3 max {x_{1}, x_{2}, x_{3}, x_{4}}$
で定め、その近接写像を
$prox_{f} (v) = x \in R^{4} argmin {f (x) + \frac{1}{2} ∥ x - v ∥_{2}^{2}}$
とする。 $v = (4, 3, 1, - 2)$ のとき、 $prox_{f} (v)$ を成分の組 $(x_{1}, x_{2}, x_{3}, x_{4})$ の形で求めよ。

この問題で使うもの

近接写像（説明と入口の問題）
劣勾配と劣微分（説明と入口の問題）
モローの分解と凸集合への射影（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$prox_{f} (v) = x^{*}$ は最適性条件 $v - x^{*} \in \partial f (x^{*})$ で特徴づけられる。まず $max {x_{1}, \dots, x_{4}}$ の劣微分を求めよう。

ヒント 2

$\partial f (x) = 3 conv {e_{i} : x_{i} = max_{j} x_{j}}$ 。これから $x_{i}^{*} = min {v_{i}, τ}$ 、 $\sum_{i} (v_{i} - τ)_{+} = 3$ を満たす $τ$ が存在することがわかる。

ヒント 3

$ϕ (τ) = \sum_{i} (v_{i} - τ)_{+}$ は $1 \leq τ \leq 3$ で $7 - 2 τ$ となる。これが $3$ となる $τ$ を求め、 $x_{i}^{*} = min {v_{i}, τ}$ を計算しよう。

答えと解説

答えを見る

(2, 2, 1, - 2)

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

解説を読む

$f$ は実数値の凸関数で、 $\frac{1}{2} ∥ x - v ∥_{2}^{2}$ は強凸なので、最小点 $x^{*} = prox_{f} (v)$ はただ 1 つ存在し、最適性条件
$v - x^{*} \in \partial f (x^{*})$
で特徴づけられる。

$f$ の劣微分. $g (x) = max_{i} x_{i}$ は線形関数 $x \mapsto x_{i}$ の最大値なので、
$\partial g (x) = conv {e_{i} : i \in A (x)}, A (x) = {i : x_{i} = j max x_{j}}$
である。よって $\partial f (x) = 3 conv {e_{i} : i \in A (x)}$ 、すなわち $u \in \partial f (x)$ であることは
$u_{i} \geq 0, i \sum u_{i} = 3, u_{i} = 0 (i \in / A (x))$
と同値である。

最適性条件を解く. $u = v - x^{*}$ とおくと $x^{*} = v - u$ で、 $u \geq 0$ , $\sum u_{i} = 3$ 。最大値をとる添字の集合 $A$ の上でだけ $u_{i} > 0$ になりうるので、ある値 $τ$ （ $= max_{j} x_{j}^{*}$ ）があって
$x_{i}^{*} = min {v_{i}, τ}, u_{i} = (v_{i} - τ)_{+}, i \sum (v_{i} - τ)_{+} = 3$
となる。

$v = (4, 3, 1, - 2)$ で $ϕ (τ) = \sum_{i} (v_{i} - τ)_{+}$ を調べる。
- $3 \leq τ \leq 4$ のとき $ϕ (τ) = 4 - τ \leq 1 < 3$ 。
- $1 \leq τ \leq 3$ のとき $ϕ (τ) = (4 - τ) + (3 - τ) = 7 - 2 τ$ 。 $7 - 2 τ = 3$ より $τ = 2$ で、これは区間内にある。

よって $τ = 2$ 、 $u = (2, 1, 0, 0)$ 、
$x^{*} = v - u = (2, 2, 1, - 2) .$

確認. $x^{*}$ の最大値は $2$ で $A (x^{*}) = {1, 2}$ 。 $v - x^{*} = (2, 1, 0, 0) = 3 (\frac{2}{3} e_{1} + \frac{1}{3} e_{2}) \in 3 conv {e_{1}, e_{2}} = \partial f (x^{*})$ なので最適性条件を満たす。

（別解: $f$ は $3Δ = {y \geq 0, \sum y_{i} = 3}$ の支持関数なので、モローの分解より $prox_{f} (v) = v - P_{3Δ} (v)$ 。 $P_{3Δ} (v) = (v - τ 1)_{+} = (2, 1, 0, 0)$ となり同じ結果を得る。）

したがって $prox_{f} (v) = (2, 2, 1, - 2)$ 。

別解

$f = 3 max_{i} x_{i}$ は $λ = 3$ の $λ max$ で、これはシンプレックス $λ Δ = {y \geq 0, \sum y_{i} = 3}$ 上の支持関数。Moreau の分解より $prox_{f} (v) = v - Π_{3Δ} (v)$ 。

$Π_{3Δ} (v) = max (v - τ, 0)$ （成分ごと）で $\sum = 3$ となる $τ$ を求める。 $v = (4, 3, 1, - 2)$ 。支持を第 1, 2 成分とすると $(4 - τ) + (3 - τ) = 3$ より $τ = 2$ 。このとき $y = (2, 1, max (1 - 2, 0), max (- 2 - 2, 0)) = (2, 1, 0, 0)$ 。和は 3、 $v_{3} - τ = - 1 < 0$ 、 $v_{4} - τ < 0$ 、 $v_{2} - τ = 1 > 0$ で整合。

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

検算: $x = (2, 2, 1, - 2)$ で $max = 2$ を達成する添字は ${1, 2}$ 。最適性条件 $v - x = (2, 1, 0, 0) \in 3 \partial max (x) = 3 conv {e_{1}, e_{2}}$ を確認: $(2, 1, 0, 0) = 3 (\frac{2}{3} e_{1} + \frac{1}{3} e_{2})$ で成立。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題