logo

ヤンセンの不等式の有限形の証明 📂レンマ

ヤンセンの不等式の有限形の証明

要旨

I⊂RI \subset \mathbb{R} で、凸関数 f:I→Rf : I \to \mathbb{R} と ∑k=1nλk=1,λk>0\displaystyle \sum_{k=1}^{n} \lambda_{k} = 1, \lambda_{k}>0 について

f(λ1x1+λ2x2+⋯+λnxn)≤λ1f(x1)+λ2f(x2)+⋯+λnf(xn)f(∑k=1nλkxk)≤∑k=1nλkf(xk) \begin{align*} f( \lambda_{1} x_{1} + \lambda_{2} x_{2} + \cdots + \lambda_{n} x_{n} ) & \le \lambda_{1} f( x_{1}) + \lambda_{2} f( x_{2}) + \cdots + \lambda_{n} f( x_{n} ) \\ f\left( \sum\limits_{k=1}^{n}\lambda_{k}x_{k} \right) &\le \sum\limits_{k=1}^{n} \lambda_{k} f(x_{k}) \end{align*}

ff が凹関数の場合は、反対の不等式が成り立つ。

f(λ1x1+λ2x2+⋯+λnxn)≥λ1f(x1)+λ2f(x2)+⋯+λnf(xn)f(∑k=1nλkxk)≥∑k=1nλkf(xk) \begin{align*} f( \lambda_{1} x_{1} + \lambda_{2} x_{2} + \cdots + \lambda_{n} x_{n} ) & \ge \lambda_{1} f( x_{1}) + \lambda_{2} f( x_{2}) + \cdots + \lambda_{n} f( x_{n} ) \\ f\left( \sum\limits_{k=1}^{n}\lambda_{k}x_{k} \right) &\ge \sum\limits_{k=1}^{n} \lambda_{k} f(x_{k}) \end{align*}

説明

イェンセンの不等式は、凸関数の代表的な応用として様々な分野で広く使われている。有限フォームは、もともと凸の定義から点の数と重みに関して一般化された形である。

証明

証明方法は同じなので、凸関数についてのみ証明する。

戦略：凸関数の定義を通して関数の内外に項を入れ、数学的帰納法を適用する。

凸関数の定義：区間 I⊂RI \subset \mathbb{R} の任意の2要素 x1,x2x_{1} , x_{2} と関数 f:I→Rf : I \to \mathbb{R} と 0≤t≤10 \le t \le 1 について、f(tx1+(1−t)x2)≤tf(x1)+(1−t)f(x2)f( t x_{1} + (1-t) x_{2}) \le t f(x_{1}) + (1-t) f(x_{2}) ならば、ff を II での凸関数という。

n=1n=1 のとき ff は凸なので

f(λx)≤λf(x) f( \lambda x ) \le \lambda f(x)

n=2n=2 のとき ff は凸なので

f(λ1x1+λ2x2)≤λ1f(x1)+λ2f(x2) f( \lambda_{1} x_{1} + \lambda_{2} x_{2} ) \le \lambda_{1} f( x_{1} ) + \lambda_{2} f( x_{2})

n=N≥3n = N \ge 3 で

f(λ1x1+λ2x2+⋯+λNxN)≤λ1f(x1)+λ2f(x2)+⋯+λNf(xN) f( \lambda_{1} x_{1} + \lambda_{2} x_{2} + \cdots + \lambda_{N} x_{N} ) \le \lambda_{1} f( x_{1}) + \lambda_{2} f( x_{2}) + \cdots + \lambda_{N} f( x_{N} )

これが成立すると仮定して、n=N+1n = N + 1 でも成立することを示せば証明は完了する。

∑k=1N+1λk=1\displaystyle \sum_{k=1}^{N+1} \lambda_{k} = 1 で μi:=λi1−λN+1\displaystyle \mu_{i} := {{\lambda_{i}} \over {1 - \lambda_{N+1}}} を定義すると ∑k=1Nμk=1\displaystyle \sum_{k=1}^{N} \mu_{k} = 1 だから

f(μ1x1+μ2x2+⋯+μNxN)≤μ1f(x1)+μ2f(x2)+⋯+μNf(xN) f( \mu_{1} x_{1} + \mu_{2} x_{2} + \cdots + \mu_{N} x_{N} ) \le \mu_{1} f( x_{1}) + \mu_{2} f( x_{2}) + \cdots + \mu_{N} f( x_{N} )

μi\mu_{i} の定義に従って

f(λ11−λN+1x1+λ21−λN+1x2+⋯+λN1−λN+1xN)≤λ11−λN+1f(x1)+λ21−λN+1f(x2)+⋯+λN1−λN+1f(xN) f( {{\lambda_{1}} \over {1 - \lambda_{N+1}}} x_{1} + {{\lambda_{2}} \over {1 - \lambda_{N+1}}} x_{2} + \cdots + {{\lambda_{N}} \over {1 - \lambda_{N+1}}} x_{N} ) \\ \le {{\lambda_{1}} \over {1 - \lambda_{N+1}}} f( x_{1}) + {{\lambda_{2}} \over {1 - \lambda_{N+1}}} f( x_{2}) + \cdots + {{\lambda_{N}} \over {1 - \lambda_{N+1}}} f( x_{N} )

11−λN+1\displaystyle {{1} \over {1 - \lambda_{N+1}}} としてまとめると

f(11−λN+1(λ1x1+λ2x2+⋯+λNxN))≤11−λN+1(λ1f(x1)+λ2f(x2)+⋯+λNf(xN)) f \left( {{1} \over {1 - \lambda_{N+1}}} \left( \lambda_{1} x_{1} + \lambda_{2} x_{2} + \cdots + \lambda_{N} x_{N} \right) \right) \\ \le {{1} \over {1 - \lambda_{N+1}}} \left( \lambda_{1} f( x_{1}) + \lambda_{2} f( x_{2}) + \cdots + \lambda_{N} f( x_{N} ) \right)

両辺に 1−λN+11 - \lambda_{N+1} を掛けると

(1−λN+1)f(11−λN+1(λ1x1+λ2x2+⋯+λNxN))≤λ1f(x1)+λ2f(x2)+⋯+λNf(xN) (1 - \lambda_{N+1}) f \left( {{1} \over {1 - \lambda_{N+1}}} \left( \lambda_{1} x_{1} + \lambda_{2} x_{2} + \cdots + \lambda_{N} x_{N} \right) \right) \\ \le \lambda_{1} f( x_{1}) + \lambda_{2} f( x_{2}) + \cdots + \lambda_{N} f( x_{N} )

両辺に λN+1f(xN+1)\lambda_{N+1} f( x_{N+1} ) を加えると

(1−λN+1)f(11−λN+1(λ1x1+λ2x2+⋯+λNxN))+λN+1f(xN+1)≤λ1f(x1)+λ2f(x2)+⋯+λNf(xN)+λN+1f(xN+1) (1 - \lambda_{N+1}) f \left( {{1} \over {1 - \lambda_{N+1}}} \left( \lambda_{1} x_{1} + \lambda_{2} x_{2} + \cdots + \lambda_{N} x_{N} \right) \right) + \lambda_{N+1} f (x_{N+1}) \\ \le \lambda_{1} f( x_{1}) + \lambda_{2} f( x_{2}) + \cdots + \lambda_{N} f( x_{N} ) + \lambda_{N+1} f( x_{N+1} )

(1−λN+1)+λN+1=1( 1 - \lambda_{N+1} ) + \lambda_{N+1} = 1 であり、ff は凸関数だから

f(1−λN+11−λN+1(λ1x1+λ2x2+⋯+λNxN)+λN+1xN+1)≤(1−λN+1)f(11−λN+1(λ1x1+λ2x2+⋯+λNxN))+λN+1f(xN+1) f \left( {{1 - \lambda_{N+1}} \over {1 - \lambda_{N+1}}} \left( \lambda_{1} x_{1} + \lambda_{2} x_{2} + \cdots + \lambda_{N} x_{N} \right) + \lambda_{N+1} x_{N+1} \right) \\ \le (1 - \lambda_{N+1}) f \left( {{1} \over {1 - \lambda_{N+1}}} \left( \lambda_{1} x_{1} + \lambda_{2} x_{2} + \cdots + \lambda_{N} x_{N} \right) \right) + \lambda_{N+1} f (x_{N+1})

不等式を続けると

f(λ1x1+λ2x2+⋯+λNxN+λN+1xN+1)≤(1−λN+1)f(11−λN+1(λ1x1+λ2x2+⋯+λNxN))+λN+1f(xN+1)≤λ1f(x1)+λ2f(x2)+⋯+λNf(xN)+λN+1f(xN+1) f \left( \lambda_{1} x_{1} + \lambda_{2} x_{2} + \cdots + \lambda_{N} x_{N} + \lambda_{N+1} x_{N+1} \right) \\ \le (1 - \lambda_{N+1}) f \left( {{1} \over {1 - \lambda_{N+1}}} \left( \lambda_{1} x_{1} + \lambda_{2} x_{2} + \cdots + \lambda_{N} x_{N} \right) \right) + \lambda_{N+1} f (x_{N+1}) \\ \le \lambda_{1} f( x_{1}) + \lambda_{2} f( x_{2}) + \cdots + \lambda_{N} f( x_{N} ) + \lambda_{N+1} f( x_{N+1} )

結論として、

f(λ1x1+λ2x2+⋯+λN+1xN+1)≤λ1f(x1)+λ2f(x2)+⋯+λN+1f(xN+1) f( \lambda_{1} x_{1} + \lambda_{2} x_{2} + \cdots + \lambda_{N+1} x_{N+1} ) \le \lambda_{1} f( x_{1}) + \lambda_{2} f( x_{2}) + \cdots + \lambda_{N+1} f( x_{N+1} )

■

関連項目