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

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

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

$n$ を正の整数、 $λ > 0$ を実数とし、 $f : R^{n} \to R$ を
$f (x) = λ i = 1 \sum n ∣ x_{i} ∣ + \frac{1}{2} i = 1 \sum n x_{i}^{2} (x = (x_{1}, \dots, x_{n}))$
で定める。 $f$ の凸共役 $f^{*} : R^{n} \to (- \infty, \infty]$ を
$f^{*} (y) = x \in R^{n} sup (⟨ y, x ⟩ - f (x))$
で定める（ $⟨ \cdot, \cdot ⟩$ は標準内積）。実数 $a$ に対し $a_{+} = max {a, 0}$ と書く。このとき、すべての $y \in R^{n}$ に対して
$f^{*} (y) = \frac{1}{2} i = 1 \sum n ((∣ y_{i} ∣ - λ)_{+})^{2}$
が成り立ち、特に $f^{*}$ はいたるところ有限であることを証明せよ。

この問題で使うもの

凸共役（ルジャンドル・フェンシェル変換）（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$f$ は座標ごとの関数 $g (t) = λ ∣ t ∣ + \frac{1}{2} t^{2}$ の和です。まず 1 変数の共役 $sup_{t} (s t - g (t))$ を求め、それを座標ごとに足し合わせる方針で考えましょう。

ヒント 2

1 変数の場合は $∣ s ∣ \leq λ$ と $∣ s ∣ > λ$ に分けます。 $∣ s ∣ \leq λ$ なら $s t \leq λ ∣ t ∣$ が使えます。 $s > λ$ なら $t \geq 0$ と $t < 0$ に分け、 $t \geq 0$ では $(s - λ) t - \frac{1}{2} t^{2}$ を平方完成します。 $s < - λ$ は $g$ が偶関数であることから $s > λ$ の場合に帰着できます。

ヒント 3

$s > λ$ のとき $t \geq 0$ では $s t - g (t) = \frac{1}{2} (s - λ)^{2} - \frac{1}{2} (t - (s - λ))^{2}$ 、 $t < 0$ では $s t - g (t) = (s + λ) t - \frac{1}{2} t^{2} < 0$ です。各座標で上限を達成する $t$ が見つかるので、 $n$ 変数では $⟨ y, x ⟩ - f (x) = \sum_{i} (y_{i} x_{i} - g (x_{i}))$ と分けて、上からの評価と達成する点の両方を示します。

採点の観点と模範解答

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

採点の観点を見る

$f (x) = \sum_{i} g (x_{i})$ （ $g (t) = λ ∣ t ∣ + \frac{1}{2} t^{2}$ ）と座標ごとに分解し、 $⟨ y, x ⟩ - f (x)$ が各座標の $y_{i} x_{i} - g (x_{i})$ の和になることを使う方針を立てている（1 点）
$∣ s ∣ \leq λ$ のとき、 $s t \leq λ ∣ t ∣$ から $s t - g (t) \leq 0$ を示し、 $t = 0$ で $0$ が達成されるので 1 変数の上限が $0$ であることを導いている（2 点）
$s > λ$ のとき、 $t \geq 0$ では平方完成で $s t - g (t) \leq \frac{1}{2} (s - λ)^{2}$ （等号は $t = s - λ$ ）、 $t < 0$ では $(s + λ) t - \frac{1}{2} t^{2} < 0$ を示し、上限が $\frac{1}{2} (s - λ)^{2}$ であることを導いている。 $t < 0$ の側を確認せずに微分だけで済ませていない（3 点）
$s < - λ$ の場合を、 $g$ の偶関数性による置き換え $t \mapsto - t$ などで正しく処理し、上限が $\frac{1}{2} (∣ s ∣ - λ)^{2}$ であることを示している（1 点）
$n$ 変数で、すべての $x$ について $⟨ y, x ⟩ - f (x) \leq \sum_{i} h (y_{i})$ を示す上からの評価と、各座標の最大点を並べた点で等号が成り立つことの両方を示し、 $f^{*} (y) = \frac{1}{2} \sum_{i} ((∣ y_{i} ∣ - λ)_{+})^{2}$ と結論している（3 点）

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

模範解答を読む

1 変数関数 $g : R \to R$ を $g (t) = λ ∣ t ∣ + \frac{1}{2} t^{2}$ とおくと、 $f (x) = \sum_{i = 1}^{n} g (x_{i})$ である。また $h (s) = \frac{1}{2} ((∣ s ∣ - λ)_{+})^{2}$ とおく。証明は 2 段階で行う。

段階 A: 各 $s \in R$ について、すべての $t \in R$ で $s t - g (t) \leq h (s)$ が成り立ち、さらに等号を成り立たせる $t = τ (s)$ が存在する。
段階 B: 段階 A を各座標に使い、 $f^{*} (y) = \sum_{i} h (y_{i})$ を導く。

段階 A（1 変数の場合）。 $s$ を固定し、 $ψ_{s} (t) = s t - g (t)$ とおく。 $s$ の範囲で 3 つに場合分けする（ $∣ s ∣ \leq λ$ 、 $s > λ$ 、 $s < - λ$ で実数全体が尽くされる）。

場合 1: $∣ s ∣ \leq λ$ 。 このとき $h (s) = 0$ 。任意の $t$ に対し $s t \leq ∣ s ∣∣ t ∣ \leq λ ∣ t ∣$ なので
$ψ_{s} (t) = s t - λ ∣ t ∣ - \frac{1}{2} t^{2} \leq - \frac{1}{2} t^{2} \leq 0 = h (s) .$
また $ψ_{s} (0) = 0$ なので、 $τ (s) = 0$ で等号が成り立つ。

場合 2: $s > λ$ 。 このとき $h (s) = \frac{1}{2} (s - λ)^{2}$ 。
- $t \geq 0$ のとき、 $∣ t ∣ = t$ より平方完成して
$ψ_{s} (t) = (s - λ) t - \frac{1}{2} t^{2} = \frac{1}{2} (s - λ)^{2} - \frac{1}{2} (t - (s - λ))^{2} \leq \frac{1}{2} (s - λ)^{2} .$
- $t < 0$ のとき、 $∣ t ∣ = - t$ より $ψ_{s} (t) = (s + λ) t - \frac{1}{2} t^{2}$ 。 $s + λ > 0$ 、 $t < 0$ なので $(s + λ) t < 0$ 、よって $ψ_{s} (t) < 0 \leq \frac{1}{2} (s - λ)^{2}$ 。

したがってすべての $t$ で $ψ_{s} (t) \leq h (s)$ 。さらに $τ (s) = s - λ > 0$ は $t \geq 0$ の範囲にあり、上の平方完成の式で第 2 項が $0$ になるので $ψ_{s} (τ (s)) = h (s)$ 。

場合 3: $s < - λ$ 。 $g$ は偶関数（ $g (- t) = g (t)$ ）なので、 $u = - t$ とおくと $ψ_{s} (t) = (- s) u - g (u) = ψ_{- s} (u)$ である。 $- s > λ$ だから場合 2 を $- s$ に使えて、すべての $u$ で $ψ_{- s} (u) \leq \frac{1}{2} (- s - λ)^{2}$ 、等号は $u = - s - λ$ で成り立つ。 $- s - λ = ∣ s ∣ - λ > 0$ より右辺は $h (s)$ に等しい。よってすべての $t$ で $ψ_{s} (t) \leq h (s)$ であり、 $τ (s) = - (- s - λ) = s + λ$ で等号が成り立つ。

以上で段階 A が示された。

段階 B（ $n$ 変数の場合）。 $y \in R^{n}$ を固定する。

(上からの評価) 任意の $x \in R^{n}$ に対し、 $⟨ y, x ⟩ = \sum_{i} y_{i} x_{i}$ と $f (x) = \sum_{i} g (x_{i})$ より
$⟨ y, x ⟩ - f (x) = i = 1 \sum n (y_{i} x_{i} - g (x_{i})) = i = 1 \sum n ψ_{y_{i}} (x_{i}) \leq i = 1 \sum n h (y_{i}) .$
最後の不等号は、段階 A を $s = y_{i}$ 、 $t = x_{i}$ に各 $i$ で使った。 $x$ は任意なので $f^{*} (y) \leq \sum_{i} h (y_{i})$ 。

(上限の達成) $x ˉ = (τ (y_{1}), \dots, τ (y_{n}))$ とおくと、段階 A の等号条件から各 $i$ で $ψ_{y_{i}} (τ (y_{i})) = h (y_{i})$ なので
$⟨ y, x ˉ ⟩ - f (x ˉ) = i = 1 \sum n ψ_{y_{i}} (τ (y_{i})) = i = 1 \sum n h (y_{i}) .$
よって $f^{*} (y) \geq \sum_{i} h (y_{i})$ 。

両方を合わせて
$f^{*} (y) = i = 1 \sum n h (y_{i}) = \frac{1}{2} i = 1 \sum n ((∣ y_{i} ∣ - λ)_{+})^{2} .$
右辺は有限の実数なので、 $f^{*}$ はいたるところ有限である。 $y$ は任意であったから、これで命題が証明された。

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

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題