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

最適化・線形計画法の問題

難易度 4大学院入試の標準レベル証明問題大学数学最適化・線形計画法

$n$ を正の整数、 $a = (a_{1}, \dots, a_{n}) \in R^{n}$ を任意の実ベクトルとし、
$Δ = {x = (x_{1}, \dots, x_{n}) \in R^{n} x_{i} \geq 0 (i = 1, \dots, n), i = 1 \sum n x_{i} = 1}$
とする。最適化問題
$最小化 f (x) = i = 1 \sum n (x_{i} - a_{i})^{2} 制約 x \in Δ$
について、次を証明せよ。

「方程式 $i = 1 \sum n max (a_{i} - τ, 0) = 1$ を満たす実数 $τ$ がただ 1 つ存在し、その $τ$ を用いて $x_{i}^{*} = max (a_{i} - τ, 0) (i = 1, \dots, n)$ と定めた点 $x^{*} = (x_{1}^{*}, \dots, x_{n}^{*})$ は、この問題のただ 1 つの最適解である。」

ここで最適解とは、 $x^{*} \in Δ$ であって、すべての $x \in Δ$ に対し $f (x^{*}) \leq f (x)$ を満たす点のことである。

この問題で使うもの

KKT 条件（説明と入口の問題）
凸計画と KKT 条件の十分性（説明と入口の問題）
凸集合と凸関数の定義（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

証明は 3 つに分かれる: (i) $φ (τ) = \sum_{i} max (a_{i} - τ, 0)$ について $φ (τ) = 1$ の解がただ 1 つあること、(ii) $x^{*}$ が KKT 条件を満たすこと、(iii) KKT 条件から最適性と一意性を導くこと。

ヒント 2

(i) は $φ$ の連続性・中間値の定理と、 $τ < max_{i} a_{i}$ での狭義単調減少性を使う。(ii) では等式制約の乗数を $ν = 2 τ$ 、非負制約の乗数を $μ_{i} = 2 max (τ - a_{i}, 0)$ と取ってみる。

ヒント 3

(iii) では $f (x) = f (x^{*}) + \nabla f (x^{*}) \cdot (x - x^{*}) + ∥ x - x^{*} ∥^{2}$ と展開し、 $\nabla f (x^{*})$ の成分を KKT 条件で $μ_{i} - ν$ に置き換えると、中央の項が $\sum_{i} μ_{i} x_{i}$ になる。

採点の観点と模範解答

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

採点の観点を見る

$φ (τ) = \sum_{i} max (a_{i} - τ, 0)$ の連続性と $φ (M) = 0$ , $φ (M - 1) \geq 1$ （ $M = max_{i} a_{i}$ ）から中間値の定理で解の存在を示している（2 点）
最大の $a_{i}$ の項に注目して $φ$ が $τ \leq M$ で狭義単調減少であることを示し、解が $τ < M$ にしかないことと合わせて一意性を示している（2 点）
$x^{*} \in Δ$ を確かめ、乗数 $ν = 2 τ$ , $μ_{i} = 2 max (τ - a_{i}, 0)$ などを具体的に与えて、停留条件・ $μ_{i} \geq 0$ ・相補性 $μ_{i} x_{i}^{*} = 0$ をすべて確認している（3 点）
$f (x) - f (x^{*})$ を展開し、KKT 条件と制約を使って $\sum_{i} μ_{i} x_{i} + ∥ x - x^{*} ∥^{2} \geq 0$ の形に変形して最適性を示している（2 点）
上の評価の $∥ x - x^{*} ∥^{2}$ の項（または $f$ の狭義凸性）から最適解の一意性を結論している（1 点）

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

模範解答を読む

第 1 段: $τ$ の存在と一意性

$φ (τ) = \sum_{i = 1}^{n} max (a_{i} - τ, 0)$ とおき、 $M = max_{1 \leq i \leq n} a_{i}$ 、 $M = a_{i_{0}}$ となる添字を $i_{0}$ とする。

各項 $max (a_{i} - τ, 0)$ は $τ$ の連続関数なので、 $φ$ は $R$ 上で連続である。
$τ \geq M$ ならすべての $i$ で $a_{i} - τ \leq 0$ なので $φ (τ) = 0$ 。
$τ = M - 1$ のとき、 $i_{0}$ の項は $max (1, 0) = 1$ で、他の項は $0$ 以上なので $φ (M - 1) \geq 1$ 。

$φ (M - 1) \geq 1 > 0 = φ (M)$ と中間値の定理より、 $φ (τ) = 1$ となる $τ \in [M - 1, M)$ が存在する。

一意性を示す。 $φ (τ) = 1$ なら $φ (τ) \neq = 0$ なので $τ < M$ である。 $τ < τ^{'} \leq M$ とすると、各 $i$ で $max (a_{i} - τ, 0) \geq max (a_{i} - τ^{'}, 0)$ （ $max (\cdot, 0)$ は単調非減少で $a_{i} - τ > a_{i} - τ^{'}$ ）であり、 $i_{0}$ については $a_{i_{0}} - τ = M - τ > M - τ^{'} \geq 0$ より $max (a_{i_{0}} - τ, 0) = M - τ > M - τ^{'} = max (a_{i_{0}} - τ^{'}, 0)$ 。よって $φ (τ) > φ (τ^{'})$ であり、 $φ$ は $(- \infty, M]$ で狭義単調減少である。 $φ (τ) = 1$ の解はすべて $(- \infty, M)$ にあるので、解は 1 つしかない。

第 2 段: $x^{*} \in Δ$ と KKT 条件

第 1 段の $τ$ で $x_{i}^{*} = max (a_{i} - τ, 0)$ とおく。 $x_{i}^{*} \geq 0$ かつ $\sum_{i} x_{i}^{*} = φ (τ) = 1$ なので $x^{*} \in Δ$ 。

制約を $g_{i} (x) = - x_{i} \leq 0$ 、 $h (x) = \sum_{i} x_{i} - 1 = 0$ と書くと、KKT 条件は「 $μ_{i} \geq 0$ , $ν \in R$ があって $\frac{\partial f}{\partial x _{i}} (x^{*}) - μ_{i} + ν = 0$ 、 $μ_{i} x_{i}^{*} = 0$ 」である。 $\frac{\partial f}{\partial x _{i}} = 2 (x_{i} - a_{i})$ なので、
$ν = 2 τ, μ_{i} = 2 (x_{i}^{*} - a_{i}) + ν = 2 (max (a_{i} - τ, 0) - (a_{i} - τ)) = 2 max (τ - a_{i}, 0)$
と取る（最後の等号は、 $a_{i} \geq τ$ と $a_{i} < τ$ に分けて確かめられる）。すると
- $μ_{i} \geq 0$ ;
- $x_{i}^{*} > 0$ なら $a_{i} > τ$ なので $μ_{i} = 0$ 、 $x_{i}^{*} = 0$ なら $μ_{i} x_{i}^{*} = 0$ 。いずれの場合も $μ_{i} x_{i}^{*} = 0$ ;
- 定義から $2 (x_{i}^{*} - a_{i}) = μ_{i} - ν$ 。

となり、KKT 条件が成り立つ。

第 3 段: 最適性と一意性

任意の $x \in Δ$ をとる。 $x - a = (x^{*} - a) + (x - x^{*})$ と分けて展開すると
$f (x) = f (x^{*}) + i = 1 \sum n 2 (x_{i}^{*} - a_{i}) (x_{i} - x_{i}^{*}) + i = 1 \sum n (x_{i} - x_{i}^{*})^{2} .$
第 2 項に $2 (x_{i}^{*} - a_{i}) = μ_{i} - ν$ を代入すると
$i \sum (μ_{i} - ν) (x_{i} - x_{i}^{*}) = i \sum μ_{i} x_{i} - i \sum μ_{i} x_{i}^{*} - ν (i \sum x_{i} - i \sum x_{i}^{*}) = i \sum μ_{i} x_{i} - 0 - ν (1 - 1) = i \sum μ_{i} x_{i} .$
ここで相補性 $μ_{i} x_{i}^{*} = 0$ と、 $x, x^{*} \in Δ$ より成分の和がともに $1$ であることを使った。 $μ_{i} \geq 0, x_{i} \geq 0$ なので $\sum_{i} μ_{i} x_{i} \geq 0$ 。したがって
$f (x) \geq f (x^{*}) + ∥ x - x^{*} ∥^{2} \geq f (x^{*}) .$
よって $x^{*}$ は最適解である。さらに $x \in Δ$ も最適解なら $f (x) = f (x^{*})$ なので、上の不等式から $∥ x - x^{*} ∥^{2} \leq 0$ 、すなわち $x = x^{*}$ 。

以上より、 $\sum_{i} max (a_{i} - τ, 0) = 1$ を満たす $τ$ はただ 1 つ存在し、 $x_{i}^{*} = max (a_{i} - τ, 0)$ で定まる $x^{*}$ はこの問題のただ 1 つの最適解である。

最適化・線形計画法の問題

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題