LPゼミ - 研究

内点法のための補題を準備
内点法で以下の不等式を使うようです。テキストに証明のためのヒントが載っています。以下、ヒントにしたがって考えた証明。

Suppose
$x\in R^n,\, x>0,\, \sum_i(1-x_i)=0,\, a:=||1-x||<1$
then, we have
$\log\prod_i x_i \,\geq\, \frac{a^2}{a-1}$

proof: let
$y_i=1-x_i$
then, due to the Jensen's inequality, we obtain
$\left(\prod_i\frac{1}{1-y_i}\right)^{1/n}\leq \frac{1}{n}\sum_i\frac{1}{1-y_i}$ .
Note that
$|y_i|<1$
holds, because of
$a<1$ .
The expression $\sum_i\frac{1}{1-y_i}$ is represented as
$\sum_i\frac{1}{1-y_i}=\sum_{k=0}^\infty\sum_i y_i^k=n+a^2+\sum_iy_i^3+\sum_iy_i^4+\cdots$ .
The summation $\sum_iy_i^k$ is upper bounded as follows:
$\sum_iy_i^k\leq\sum_i|y_i|^{2\cdot k/2}\leq (\sum_i|y_i|^2)^{k/2}=a^k$ .
Therefore, the following inequality holds:
$\left(\prod_i\frac{1}{1-y_i}\right)^{1/n}\leq\frac{1}{n}\sum_i\frac{1}{1-y_i}\leq 1+(a^2+a^3+a^4+\cdots)/n=1+\frac{a^2}{n(1-a)}\leq e^{a^2/(n(1-a))}$ .
Taking the logarithm, we obtain the desired inequality.