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} 의 두 원소 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} )

■

같이보기