[TOC]

1. 教科書

• 凸射影定理を図的に解説
• 凸射影定理の証明が載ってる,リンク切れ対策
• 凸体の日本語の教科書(勉強してないが詳しそう)

2. 定義

2.1. 凸集合

凸集合(convex set)

Let $S$ be a vector space over the some ordered field. A set $C$ in $S$ is said to be convex if $(1-t)x+ty\in C\forall x,y\in C,\forall t\in (0,1)$

2.2. 端点

端点(extreme point)

Let $A$ is a convex set in a real vector space. Then $x\in A$ is a extreme point if and only if

$x=\theta y+(1-\theta )z,\theta \in [0,1],y\in A,z\in A\Rightarrow y=x\vee z=x$

2.3. 端点を持つことと直線を含まないことの同値性

2.4. 凸関数

凸関数(convex function)

Let $X$ be a convex set in a real vector space and let $f:X\to R$ be a function.

• $f$ is called convex if $\forall x_1,x_2\in X,\forall t\in [0,1]$:

$f(t{x}_1+(1-t\left)x_2\right)\le tf\left(x_1\right)+(1-t)f\left(x_2\right)$

• $f$ is called strictly convex if $\forall x_1\ne x_2\in X,\forall t\in (0,1)$:

$f(t{x}_1+(1-t\left)x_2\right)<tf\left(x_1\right)+(1-t)f\left(x_2\right)$

• A function $f$ is said to be (strictly) concave if $-f$ is (strictly) convex.

2.5. α-strongly_convex

We say that $f$ is $\alpha$-strongly convex ($\alpha \ge 0$) if it satisfies the following sub gradient inequality:

$$f\left(x\right)-f\left(y\right)\le \nabla f\left(x{)}^T\right(x-y)-\frac{\alpha }{2}\parallel x-y{\parallel }^2(\forall x,y)$$

Since $\nabla f\left(x{)}^T\right(x-y)-\frac{\alpha }{2}\parallel x-y{\parallel }^2\le f(x{)}^T(x-y)$, $f$ is convex(detail)

2.6. リプシッツ連続

リプシッツ連続(Lipschitz continuity)

Given two metric spaces $(X,d_X)$ and $(Y,d_Y)$, a function $f:X\to Y$ is called Lipschitz continuous if there exists a real constant $K\ge 0$ such that

$d_Y\left(f\right(x_1),f(x_2\left)\right)\le K{d}_X(x_1,x_2)\forall x,y\in X$

Any such $K$ is referred to a Lipschitz constant for the function $f$.

2.7. β-smooth

We say that a continuously differentiable function $f$ is $\beta$-smooth $\beta \ge 0$ if the gradient $\nabla f$ is $\beta$-Lipschitz, that is

$$\parallel \nabla f\left(x\right)-\nabla f\left(y\right)\parallel \le \beta \parallel x-y\parallel$$

2.8. エピグラフ

エピグラフ(epigraph)

Let $X\subset R^n$ be a convex set.

Epigraph or supergraph of a function $f:X\to R$ is the set of points lying on or above its graph definied as

$\text{epi}f=\left\{\right(x,t)\mid x\in \text{dom}f,f(x)\le t\}\subset R^{n+1}$

('Epi' means 'above' so epigraph means 'above the graph')

A function is convex(strictly convex) if and only if its epigraph is a (strictly) convex set.

2.9. ヒルベルト空間

ヒルベルト空間(Hilbert space)

A Hilbert space $(H,⟨\cdot ⟩)$ is a real or complex inner product space that is also a complete metric space.

3. 定理

3.1. 凸関数の勾配の単調性

Let $f:R^n\to R$ be class $C^1$. Then $f$ is convex if and only if $\text{dom}f$ is convex and $\nabla f\left(x\right)$ is a monotone operator: $⟨\nabla f\left(x\right)-\nabla f\left(y\right),x-y⟩\ge 0$

Proof p2 Prop1.3,保存用

3.2. 凸関数の２階導関数テスト

Let $K\subset R^n$ be an open convex set, and let $f:K\to R$ be continuous second partial derivatives. If the Hessian of $f$ is positive definite everywhere, then $f$ is convex on $K$.

Let $H_{(i,j)}$ be an element of Hessian of $f$. Then, $$H_{(i,j)}\equiv \frac{{\partial }^2}{\partial x_i\partial x_j}f$$ ($x_j$で偏微分した後で$x_i$で微分する)

Proof Theorem5,保存用

3.3. 凸関数の接線

Suppose $f:R^n\to R$ be total differentiable convex function over an convex open domain. Then, the following are equivalent

1. $f$ is convex.
2. $f\left(y\right)\ge f\left(x\right)+\nabla f\left(x{)}^T\right(y-x)\forall x,y\in \text{dom}(f)$

pdf5 Theorem2

3.4. 凸関数の同値条件

Suppose $f:R^n\to R$ be class $C^2$ convex function over an convex open domain. Then, the following are equivalent

1. $f$ is convex.
2. $f\left(y\right)\ge f\left(x\right)+\nabla f\left(x{)}^T\right(y-x)\forall x,y\in \text{dom}(f)$
3. ${\nabla }^{2}f\left(x\right)\succ 0\forall x\in \text{dom}\left(f\right)$

pdf5 Theorem2が証明(3)$\Rightarrow$(1)の証明はこちらをを参照

3.5. R上の任意のノルムは凸関数である

Let $\parallel \cdot \parallel :V\to R$ be a norm on a vector space $V$ over $R$. Then $\parallel \cdot \parallel$ is a convex function.

Proof.

任意の$v,w\in V,\lambda \in [0,1]$に対して, $$\parallel \lambda v+(1-\lambda )w\parallel \le \lambda \parallel v\parallel +(1-\lambda )\parallel w\parallel$$

3.6. β-smoothの特徴

Let $f$ be a $\beta$-smooth function on $R^n$. Then for any $x,y\in R^n$, one has

$|f\left(x\right)-f\left(y\right)-\nabla f\left(y{)}^T\right(x-y)|\le \frac{\beta }{2}\parallel x-y{\parallel }^2$

(proof)

多変数の微分積分学の定理を用いると $$f\left(x\right)-f\left(y\right)={\int }_0^1\nabla f(y+t(x-y\left){)}^T\right(x-y)dt$$ が成立することとシュヴァルツの不等式と$\beta$-smoothnessを用いることで、 $$\begin{array}{cc}|f\left(x\right)-f\left(y\right)-\nabla f\left(y{)}^T\right(x-y)|& =\left|{\int }_0^1\nabla f\right(y+t(x-y){)}^T(x-y)dt-\nabla f\left(y{)}^T\right(x-y\left)\right|\\ & \le {\int }_0^1\parallel \nabla f(y-t(x-y\left)\right)-\nabla f\left(y\right)\parallel \cdot \parallel x-y\parallel \\ & \le {\int }_0^1\beta t\parallel x-y{\parallel }^{2}dt\\ & =\frac{\beta }{2}\parallel x-y{\parallel }^2\end{array}$$ Detail of proof lemma3.4

3.7. β-smoothかつconvexと同値な条件

For $f:R^n\to R$ These two statements are equivalent:

1. $f$ Is convex and $\beta$-smooth ($\beta \ge 0$)

2. For any $x,y\in R^n$, one has

   $0\le f\left(x\right)-f\left(y\right)-\nabla f\left(y{)}^T\right(x-y)\le \frac{\beta }{2}\parallel x-y{\parallel }^2$

   where $\beta \ge 0$

(proof)

(1)→(2)は凸性は凸関数の接線とβ-smoothの特徴を用いれば簡単に示せる。

(2)→(1)は凸性は凸関数の接線より示せるので$\beta$-smoothのみを示す。$\beta =0$の時は自明なので、$\beta >0$のみ示す。 $$f\left(x\right)-f\left(y\right)\le \nabla f\left(x{)}^T\right(x-y)-\frac{1}{2\beta }\parallel \nabla f(x)-\nabla f(y\left){\parallel }^2\right(\forall x,y\in R^n)$$ $z=y-\frac{1}{\beta }\left(\nabla f\right(y)-f(x\left)\right)$と定義すると、 $$\begin{array}{cc}f\left(x\right)-f\left(y\right)& =f\left(x\right)-f\left(z\right)+f\left(z\right)-f\left(y\right)\\ & \le \nabla f\left(x{)}^T\right(x-z)+\nabla f(y{)}^T(z-y)+\frac{\beta }{2}\parallel z-y{\parallel }^2\\ & =\nabla f\left(x{)}^T\right(x-y)+(\nabla f\left(x\right)-\nabla f\left(y\right){)}^T(y-z)+\frac{1}{2\beta }\parallel \nabla f\left(x\right)-\nabla f\left(y\right){\parallel }^2\\ & =\nabla f\left(x{)}^T\right(x-y)-\frac{1}{2\beta }\parallel \nabla f(x)-\nabla f(y){\parallel }^2\end{array}$$ これを用いると$\beta$-smoothは簡単に示せる。

参考文献 Lemma3.5

3.8. β-smoothかつα-convexの性質

Let $f$ be $\beta$-smooth and $\alpha$-strongly convex on $R^n$. Then $\alpha \le \beta$ and for all $x,y\in R^n$, one has

$${\left(\nabla f\right(x)-\nabla f(y\left)\right)}^T(x-y)\ge \frac{\alpha \beta }{\beta +\alpha }\parallel x-y{\parallel }^2+\frac{1}{\beta +\alpha }\parallel \nabla f\left(x\right)-\nabla f\left(y\right){\parallel }^2$$

(Proof)

$\phi \left(x\right)\equiv f\left(x\right)-\frac{\alpha }{2}\parallel x{\parallel }^2$と定義すると,$f$が$\alpha$-storongly convexityであることを用いることで $$\phi \left(x\right)-\phi \left(y\right)\le \nabla \phi \left(x{)}^T\right(x-y\left)\right(\forall x,y)$$ が成立する.ゆえに$\phi$は凸関数(詳細は以下)

また,$f$が凸であり(α-storongly convexityなら凸集合である)また$\beta$-smoothでもあるので、この定理より $$0\le f\left(x\right)-f\left(y\right)-\nabla f\left(y{)}^T\right(x-y)\le \frac{\beta }{2}\parallel x-y{\parallel }^2(\forall x,y\in R^n)$$ が成立。この不等式に$f\left(x\right)=\phi \left(x\right)+\frac{\alpha }{2}\parallel x{\parallel }^2$を代入することで $$\phi \left(x\right)-\phi \left(y\right)-\nabla \phi \left(y\right)(x-y)\le \frac{\beta -\alpha }{2}\parallel x-y{\parallel }^2(\forall x,y\in R^n)$$ を示すことができる。この時$\beta -\alpha <0$とすると$x\ne y$に対して右辺が負になるので、$\phi$が凸関数であることに矛盾。よって、$\beta -\alpha \ge 0$である。

また$\phi$が凸であることから $$0\le \phi \left(x\right)-\phi \left(y\right)-\nabla \phi \left(y{)}^T\right(x-y\left)\right(\forall x,y\in R^n)$$ が成立する。よって、$\beta -\alpha \ge 0$の時は$\phi$は$(\beta -\alpha )$-smooth

また、$\beta -\alpha >0$であれば、再びこの定理の証明の(2)→(1)の部分を用いると $$\nabla \phi \left(x{)}^T\right(x-y)\ge \phi (x)-\phi (y)+\frac{1}{2(\beta -\alpha )}\parallel \nabla \phi (x)-\nabla \phi (y\left){\parallel }^2\right(\forall x,y\in R^n)$$ が成立する。この不等式と不等式の$x$と$y$を入れ替えた不等式の両辺を足すことによって $$\left(\nabla \phi \right(x)-\nabla \phi (y\left){)}^T\right(x-y)\ge \frac{1}{\beta -\alpha }\parallel \nabla \phi (x)-\nabla \phi (y\left){\parallel }^2\right(\forall x,y\in R^n)$$ が得られる。この不等式に$\nabla \phi \left(x\right)=\nabla f\left(x\right)-\alpha x$を代入してあげると定理が証明できる。

$\beta -\alpha =0$の時は$\phi$が$0$-smoothであるので $$\parallel \phi \left(x\right)-\phi \left(y\right)\parallel =0\Rightarrow \phi \left(x\right)-\phi \left(y\right)=0\Rightarrow \nabla f\left(x\right)-\nabla f\left(y\right)=\alpha (x-y)$$ であり、主張の(左辺)と(右辺)に代入すると(左辺)=(右辺)が成立するのでOK.

参考文献 Lemma 3.11

3.9. 中線定理

Let $H$ be a Hilbert space. Then, for any $x,y\in H$, we have

$\parallel x+y{\parallel }^2+\parallel x-y{\parallel }^2=2(\parallel x{\parallel }^2+\parallel y{\parallel }^2)$

parallelogram identity

定義通り計算すれば示せるので略

3.10. 凸射影定理

Suppose $S$ is a nonempty closed convex subset of Hilbert space $H$. Then for every $h\in H$ there is a unique vector $k\in S$ such that

$\parallel h-k\parallel =d(h,S)\equiv {inf}_{\ell \in S}\parallel h-\ell \parallel$

$d\equiv d(h,S)$は下限であるので,任意の自然数$n$に対して,$d\le \parallel h-k_n\parallel <d+\frac{1}{n}$を満たす$\left\{k_n\right\}\subset S$が存在する.この時,明らかに$\parallel h-k_n\parallel \to d(n\to \infty )$である.中線定理より任意の自然数$n,m$に対して, $$\parallel (h-k_n)+(h-k_m){\parallel }^2+\parallel k_m-k_n{\parallel }^2=2(\parallel h-k_n{\parallel }^2+\parallel h-k_m{\parallel }^2)$$ が成立する.$(h-k_n)+(h-k_m)=2(h-\frac{1}{2}(k_m+k_n\left)\right)$であり$S$が凸集合であるので$\frac{1}{2}(k_m+k_n)\in S$であることに注意すると, $$\begin{array}{cc}\parallel k_m-k_n{\parallel }^2& =2(\parallel h-k_n{\parallel }^2+\parallel h-k_m{\parallel }^2)-4\parallel h-\frac{1}{2}(k_m+k_n){\parallel }^2\\ & \le 2(\parallel h-k_n{\parallel }^2+\parallel h-k_m{\parallel }^2)-4d^2\end{array}$$ ゆえに$n,m\to \infty$の時,左辺$\to 2(d^2+d^2)-4d^2=0$となるので$\left\{k_n\right\}$はコーシー列である.また,ヒルベルト空間は完備であり$S$は閉集合であったので$\left\{k_n\right\}$は$S$の元$k$に収束する.また,任意の自然数$n$について, $$|\parallel h-k\parallel -\parallel h-k_n\parallel |\le \parallel (h-k)-(h-k_n)\parallel =\parallel k-k_n\parallel$$ であるので,$\parallel h-k_n\parallel \to \parallel h-k\parallel$である.また,$\parallel h-k_n\parallel \to d$であったので$\parallel h-k\parallel =d$である.

続いて一意性を示す.$\parallel h-\ell \parallel =d$が成立すると仮定する.この時,$S$は凸集合であるので,$\frac{1}{2}(k+\ell )\in S$である.よって$d$の定義より$\parallel h-\frac{1}{2}(k+\ell )\parallel \ge d$である.一方,中線定理より, $$\begin{array}{cc}2(d^2+d^2)& =2(\parallel h-k{\parallel }^2+\parallel h-\ell {\parallel }^2)\\ & =\parallel (h-k)+(h-\ell ){\parallel }^2+\parallel k-\ell {\parallel }^2\\ & ={\Vert 2(h-\frac{1}{2}(k+\ell \left)\right)\Vert }^2+\parallel k-\ell {\parallel }^2\\ & \ge 4d^2+\parallel k-\ell {\parallel }^2\end{array}$$ となるので,ノルムの定義より$k=\ell$.

3.11. 凸射影の幾何学的性質

Suppose $S$ is a nonempty closed convex subset of Hilbert space $(H,⟨\cdot ⟩)$ and $h\in H$.

Then for every $k\in S$,

$\parallel h-k\parallel =d(h,S)\equiv {inf}_{\ell \in S}\parallel h-\ell \parallel \iff \text{Re}(⟨h-k,\ell -k⟩)\le 0\forall \ell \in S$

where $\text{Re}\left(z\right)$ is the real part of $z$.

(注意)凸射影定理によって,$\parallel h-k\parallel =d(h,S)$となるような$k\in S$は唯一存在することは示せる.

($\Rightarrow$)任意に$\ell \in S$をとると,$S$は凸集合であるので任意の$\lambda \in (0,1]$に対して$m\equiv \lambda \ell +(1-\lambda )k$は$S$の元である.よって,仮定より $$\begin{array}{cc}\parallel h-k\parallel \le \parallel h-m\parallel & \iff \parallel h-k{\parallel }^2\le \parallel h-m{\parallel }^2\\ & \iff 0\le {\lambda }^2\parallel \ell -k{\parallel }^2-2\lambda \text{Re}(⟨h-k,\ell -k⟩)\\ & \iff \text{Re}(⟨h-k,\ell -k⟩)\le \frac{\lambda }{2}\parallel \ell -k{\parallel }^2\end{array}$$ である.任意の$\lambda \in (0,1]$について成立しないといけないので$\text{Re}(⟨h-k,\ell -k⟩)\le 0$

ただし,上記の式中の$\parallel h-m{\parallel }^2$の計算は以下を用いた. $$\begin{array}{cc}\parallel h-m{\parallel }^2& =⟨(h-k)-\lambda (\ell -k),(h-k)-\lambda (\ell -k)⟩\\ & =\parallel h-k{\parallel }^2+{\lambda }^2\parallel \ell -k{\parallel }^2-2\lambda \text{Re}(⟨h-k,\ell -k⟩)\end{array}$$ ($\Leftarrow$)$k\in S$が任意の$\ell \in S$に対して$\text{Re}(⟨h-k,\ell -k⟩)\le 0$を満たしているとする.

この時,$\ell \in S$を任意にとる.$m\equiv 1\cdot \ell +(1-1)k=\ell$の定義すると, $$\text{Re}(⟨h-k,\ell -k⟩)\le \frac{\lambda }{2}\parallel \ell -k{\parallel }^2$$ を満たす.よって上記の逆の議論をすることで,$\parallel h-k\parallel \le \parallel h-m\parallel =\parallel h-\ell \parallel$となる.

3.12. 分離超平面定理supporting_hyperplane

Let $(H,⟨\cdot ⟩)$ be a finite-deimensional Hilber space over a field $R$ ,and $C\subset H$ be a noempty convex set.

Let $x_0$ be such that either $x_0\in bdC$ or $x_0\notin C$

Then, there exists a hyperplane passing throught $x_0$ and containing the set $C$ in one of its half spaces, i.e., there is a vector $a\in H$, $a\ne 0$, such that ${sup}_{z\in C}⟨a,z⟩\le ⟨a,x_0⟩$

• A hyper plane with such property is reffered to as a supporting hyperplane.

(Proof for the case when $C$ is closed)

Let $\left\{x_k\right\}\subset H\setminus C$ sucth that $x_k\to x_0,x_k\ne x_0$.

上記の$\left\{x_k\right\}$の存在性の証明($x_0\in \text{bd}C$の場合)

閉集合の閉包(closure)と閉集合自身は等しいので$x_0\in \text{bd}C=\overline{C}\setminus \text{int}C=C\setminus \text{int}C$となる.

$x_0\notin \text{int}C$より任意の$ϵ>0$に対して中心$x_0$で変形$ϵ$のball$B_{ϵ}\left(x_0\right)⊈C$である.よって,任意の自然数$k$に対してを$x_k\in B_{\frac{1}{k}}\left(x\right)\cap H\setminus C$を満たすように$\{x_k{\}}_k\subset H\setminus C$をとればよい.

上記の$\left\{x_k\right\}$の存在性の証明($x_0\notin C$の場合)

$C$はclosedであったので$H\setminus C$はopen.よって,$r>0$が存在し$B_r\left(x_0\right)\subset H\setminus C$を満たす.また,$H$の任意の元は$H$の孤立点ではないので,$B_r\left(x_0\right)$から$x_0$に収束する点列を取れる.

Let $z_k^{\ast }$ be the projection of $x_k$ on the set $C$ for each $k$, i.e. $$\parallel z_k^{\ast }-x_k\parallel =\text{dis}(x_k,C)\equiv \underset{z\in C}{inf}d(x_k,z)$$ The exsistance and uniquness of $z_k^{\ast }$ is proved here. Consider $$a_k\equiv \frac{x_k-z_k^{\ast }}{\parallel x_k-z_k^{\ast }\parallel }\forall k\ge 1$$ This sequence is bounded and, therefore there exists a subsequence of $\left\{a_{{\ell }_k}\right\}$ converging to $a\in R^n$, where $\parallel a\parallel =1$.

収束列$\left\{a_{{\ell }_k}\right\}$ が存在することは以下のように示すことが出来る.$A\equiv \{x\in H\mid \parallel x\parallel =1\}$のような空間を考えるとノルム空間の基本的な性質より閉集合.さらに有界である.よって,コンパクトである.また距離空間においてはコンパクトと点列コンパクトは同値であるので, $A$は点列コンパクトとなるので,収束する部分列$\left\{a_{{\ell }_k}\right\}$ が存在し収束先は$A$の元となるのでノルムは1である.

Since $z_k^{\ast }$ is the projection of $x_k$, by the Property of Projection Theorem, for every $z\in C,k\in N_{>0}$, $$\begin{array}{cc}(z_k^{\ast }-x_k{)}^T(z-z_k^{\ast })\ge 0& \iff a_k^T(z-z_k^{\ast })\le 0\\ & \iff a_k^{T}z\le a_k^T{z}_k^{\ast }\end{array}$$

$$\begin{array}{cc}⟨z_k^{\ast }-x_k,z-z_k^{\ast }⟩\ge 0& \iff ⟨a_k,(z-z_k^{\ast })⟩\le 0\\ & \iff ⟨a_k,z⟩\le ⟨a_k,z_k^{\ast }⟩\end{array}$$

さらに, $$⟨a_k,z_k^{\ast }⟩=⟨a_k,z_k^{\ast }-x_k⟩+⟨a_k,x_k⟩=-⟨a_k,a_k⟩\parallel x_k-z_k^{\ast }\parallel +⟨a_k,x_k⟩<⟨a_k,x_k⟩$$ であるので,$⟨a_k,z⟩<⟨a_k,x_k⟩$であり,$a_k$を収束部分列に限ることによって$⟨a_{{\ell }_k},z⟩<⟨a_{{\ell }_k},x_k⟩$.

ここで任意の$c\in H$に対して,$f:H\to R;x\mapsto ⟨c,x⟩$は連続写像であり,$x_k\to x_0$,$a_{{\ell }_k}\to a$であるので,$⟨a,z⟩\le ⟨a,x_0⟩\forall z\in C$

$f$の連続性は$|⟨c,x⟩-⟨c,y⟩|=|⟨c,x-y⟩\parallel \le \parallel c\parallel \parallel x-y\parallel$より示せる.

3.13. イェンセンの不等式Jensen's_inequality

$X$を確率変数として,$h\left(x\right)$を$X$の値域を含む区間上で凸な関数とする.$X$と$h\left(x\right)$の期待値が有限のとき,$E\left[h\right(X\left)\right]\ge h\left(E\right[X\left]\right)$が成立する.もし,$h\left(x\right)$が狭義の凸関数のとき,等号が成立するのは1点分布の時に限る.

問題文より,$X$の値域を$\text{Im}\left(X\right)$で表すと,仮定より区間$I\supset \text{Im}\left(X\right)$が存在し,$h$は$I$上で凸関数である.

この証明においては,任意の$x_0\in I$に対して,$h\left(x_0\right)=g\left(x_0\right)$と$g\left(x\right)\le h\left(x\right)$を満たす$g\left(x\right)=cx+d$を作成することが肝である.$h$が微分可能であれば,$g\left(x\right)\equiv \nabla h\left(x_0\right)(x-x_0)+h\left(x_0\right)$と定義することで,凸関数の接線の性質より,$h\left(x_0\right)=g\left(x_0\right)$と$g\left(x\right)\le h\left(x\right)$を満たす.以下では,$h$が微分出来ない場合にも対応できる証明になっているが,このような$g\left(x\right)$を認めた上で簡単な証明ならこちらの定理1.11, リンク切れ用を参照

よって区間$I$に制限した$h$のエピグラフ $$\text{epi}{h|}_I\equiv \left\{\right(x,t)\in R^2\mid x\in I,h(x)\le t\}$$ を考えると,$\text{epi}{h|}_I$は凸関数である.(定義通りやれば示せる)

また,任意の$x_0\in I$に対して$(x,h(x\left)\right)$は$\text{epi}{h|}_I$の境界(boundary)となっている.

実際,任意の$ϵ>0$に対して$(x,h(x)-\frac{ϵ}{2})\subset B_{ϵ}\left(x\right)$かつ$(x,h(x)-\frac{ϵ}{2})\notin \text{epi}{h|}_I$となるので,$(x,h(x\left)\right)$は$\text{epi}{h|}_I$の内部でないので境界

よって,分離超平面定理より,$a=(a_1,a_2{)}^T\ne (0,0)\in R^2$が存在し,任意の$(x,t)$ with $x\in I,t\ge h\left(x_0\right)$に対して, $$\begin{array}{c}⟨a,(x,t)⟩\le ⟨a,(x_0,h(x_0\left)\right)⟩\iff a_{1}x+a_{2}t\le ⟨a,(x_0,h(x_0\left)\right)⟩\end{array}$$ が成立する.ここで右辺は定数であるので,もし$a_2>0$であるなら$t$を十分大きくすることで不等式が成立しなくなるので$a_2\le 0$である.また,$X$が1点分布でないとすると不等式より$a_2\ne 0$となる(1点分布の際は問題文の等号が成立),ゆえに$a_2<0$であり上式の$t$に$h\left(x\right)$を代入することで, $$h\left(x\right)\ge -\frac{a_1}{a_2}x+\frac{1}{a_2}⟨a,(x_0,h(x_0\left)\right)⟩=cx+d\equiv g\left(x\right)$$ と表せる.ただし,$c\equiv -\frac{a_1}{a_2}$,$d\equiv \frac{1}{a_2}⟨a,(x_0,h(x_0\left)\right)⟩$である.ゆえに,$g\left(x_0\right)=h\left(x_0\right)$であることに注意すると, $$\begin{array}{c}E\left[h\right(x\left)\right]\ge E\left[g\right(x\left)\right]=E[cX+d]=cE\left[X\right]+d=c{x}_0+d=g\left(x_0\right)=h\left(x_0\right)=h\left(E\right[x_0\left]\right)\end{array}$$

また,$h$が狭義凸関数であるときを考える.$X$が2点分布の場合は定義通りに問題文の左辺と右辺を計算することで不等式(等号無し)が成立することが分かる.$X$が3点以上の分布の場合.上記の議論より等号成立の場合$E\left[h\right(x\left)\right]=E\left[g\right(x\left)\right]$の時に限るが,$h\left(x\right)\ge g\left(x\right)$であるので任意の$x\in \text{Im}\left(X\right)$に対して$h\left(x\right)=g\left(x\right)$が成立しなけらばならない.ここで,$X$は3点以上であるので$x_1<x_2<x_3\in \text{Im}\left(X\right)$が存在する.よって,$\lambda \in (0,1)$が存在し$x_2=\lambda x_1+(1-\lambda )x_3$が満たされるが,$h$の凸性より $$\begin{array}{cc}h\left(x_2\right)& <\lambda h\left(x_1\right)+(1-\lambda )h\left(x_3\right)\\ & =\lambda (c{x}_1+d)+(1-\lambda )(c{x}_3+d)\\ & =g\left(x_2\right)\end{array}$$ より矛盾.ゆえに問題文の等号成立は1点分布の場合に限る.

3.14. ヘルダーの不等式

$n\in N_{>0},a_i,b_i\ge 0(\forall i=1,\dots ,n),p,q>0$は$\frac{1}{p}+\frac{1}{q}=1$を満たしている時、以下が成立

${\left({\sum }_{i=1}^n{a}_i^p\right)}^{\frac{1}{p}}{\left({\sum }_{i=1}^n{b}_i^q\right)}^{\frac{1}{q}}\ge {\sum }_{i=1}^n{a}_i{b}_i$

特に$p=q=2$の場合はコーシーシュワルツの不等式になっている。つまり、

$\left({\sum }_{i=1}^n{a}_i^2\right)\left({\sum }_{i=1}^n{b}_i^2\right)\ge {\left({\sum }_{i=1}^n{a}_i{b}_i\right)}^2$

(proof)

$A\equiv {\sum }_{i=1}^n{a}_i^p,B\equiv {\sum }_{i=1}^n{b}_i^q$と定義すると、$A$もしくは$B$が$0$の時は等号が成立するので、$A$と$B$のどちらも正であるときのみ考える。

$f\left(x\right)=\log x$とすると$f^{\prime \prime }\left(x\right)<0$であるので$f$は上に凸(詳細は凸関数の２階導関数テストを参照)。ゆえに、$s,t>0$に対して $$\frac{1}{p}f\left(s\right)+\frac{1}{q}f\left(t\right)\le f(\frac{1}{p}s+\frac{1}{q}t)\iff \frac{1}{p}\log s+\frac{1}{q}\log t\le \log (\frac{s}{p}+\frac{t}{q})\iff s^{\frac{1}{p}}{t}^{\frac{1}{q}}\le \frac{s}{p}+\frac{t}{q}$$ ここで、上式において$s=\frac{a_i^p}{A},t=\frac{b_i^q}{B}$として$i$に関して和をとると、 $$\begin{array}{cc}& \sum _{i=1}^n{\left(\frac{a_i^p}{A}\right)}^{\frac{1}{p}}{\left(\frac{b_i^q}{B}\right)}^{\frac{1}{q}}\le \sum _{i=1}^n(\frac{a_i^p}{A}+\frac{b_i^q}{B})\\ \iff & \frac{1}{A^{\frac{1}{p}}{B}^{\frac{1}{q}}}\sum _{i=1}^n{a}_i{b}_i\le \frac{1}{pA}\sum _{i=1}^n\frac{a_i^p}{A}+\sum _{i=1}^n\frac{b_i^q}{B}=1\\ \Rightarrow & \sum _{i=1}^n{a}_i{b}_i\le A^{\frac{1}{p}}{B}^{\frac{1}{q}}\end{array}$$ 参考資料

4. Backup

4.1. 閉集合と点の距離

Let $(V,\parallel \cdot \parallel )$ be a finite-dimensional normed space over a field $R$, $C$ be a nonempty closed convex set, and $a\in V$. Then, $d(a,C)=inf\{\parallel x-a\parallel \mid x\in C\}$ is reached at a unique point $c\in C$. $c$ is said projection of $a$ on the set $C$.i.e.

There exists unique $c\in C$ such that $\parallel x-c\parallel \le \parallel x-a\parallel (\forall x\in V)$

$C$は空集合でないので,元$c\in C$が取れるので1つ固定する.$S\equiv \{x\in C\mid \parallel a-x\parallel \le \parallel a-c\parallel \}$を定義すると,$S$の任意の元$x$に対して,$\parallel x\parallel \le \parallel x-a\parallel +\parallel a\parallel \le \parallel a-c\parallel +\parallel a\parallel$となるので$S$は有界である.また,$f:V\to R;x\mapsto \parallel a-x\parallel$と定義すると$f$は連続関数であり$D\equiv f^{-1}\left(\right[0,a-c\left]\right)$と定義すると$S=D\cap C$となる.$[0,a-c]$は閉集合で$f$が連続写像であるので$D$も閉集合である.よって,$S$は閉集合である.また,$S$は有界であったので,$S$は有界閉集合である.よって,体$K$の条件より$S$はコンパクト.また定義域を$S$に制限した写像$f$を考えると,$f$は全射になるので$f\left(S\right)$はコンパクトであるので有界閉集合.$S$の定義より,$d(a,C)=inff\left(S\right)$であるので$d(a,C)=inff\left(S\right)=minf\left(S\right)$.よって,$c\in C$で$d(a,C)=\parallel a-c\parallel$となるものが存在する.次に固有性を示す. $c_1,c_2\in C$が$d(a,C)=\parallel a-c_1\parallel =\parallel a-c_2\parallel$を満たすとする.この時$C$がconvexであるので$c=\frac{c_1+c_2}{2}\in C$である.よって,$d(a,C)$の定義より$\parallel a-c_1\parallel \le \parallel a-c\parallel$であるが,