Convex Function
定理 関数 $F : \mathbb{R}^{n+m} \to (-\infty, \infty]$ と、次のように定義される関数 $f := \inf_{z \in \mathbb{R}^m} F(x, z) : \mathbb{R}^n \to [-\infty, \infty]$ を考える。このとき、次の２つが成立する。 １. $F$ が凸ならば、$f$ も凸である。…
定理 以下の１, ２のいずれかが成立するとする。 １ １.１ $f(x, \omega)$が$K(\omega)$-リプシッツ連続であり、$\mathbb{E}[K(\omega)]$が有界である。 １.２ $f(x)$が確率1で、$x = x_0$の点で方向微分可能である。 ２ 関数 $f(x)$ が確率 1で凸であるとす…
定理 $C$ を $\mathbb{R}^n$ の凸集合とする。$x \in \text{ri } C$ 及び $y \in \text{cl } C$ とする。このとき、$0 \leq \lambda < 1$ に対して $(1 - \lambda)x + \lambda y$ は $\text{ri } C$（従って特に $C$）に属する。 証明 $B(x, a) = \lbrace x …
定理 $f_1, \dots, f_m$ を $\mathbb{R}^n$上の真凸関数とする。以下も凸関数である。 方針 $f,g,h,k$順に、その関数を定義する錐に対して、$x$、$\lambda, \mu$ 、$\lambda$、$\lambda, x$についてpartial addtionをとれば良い。 証明 錐$K \equiv \lbrace …
定理 $A$を$\mathbb{R}^{n}$から$\mathbb{R}^{m}$への線形変換とする。このとき、$\mathbb{R}^{m}$上の各凸関数$g$に対して、関数$gA$を次のように定義すると、$\mathbb{R}^{n}$上で凸となる。 また、$\mathbb{R}^{n}$上の各凸関数$h$に対して、関数$Ah$を次…
定理 関数$h$ は凸関数とし、Theorem 5.3（Rockafellar 1970）を用いて以下のように関数$f$を定義すると、以下が成立する。 この関数$f$を positively homogeneous convex function generated by $h$と呼ぶ。 証明 $\operatorname{cone}(\operatorname{epi}h…
定理 $g$を凹関数とし、$h(x)=\frac{1}{g(x)}$とする。$h(x)$は$C = \lbrace x \mid g(x) >0 \rbrace$上で凸関数となる。 証明 （解法１） 関数$h$について、$\forall \lambda \in [0.1] \quad x,y \in C$に対して、$z=\lambda x + (1-\lambda)y$とし、 が成…
定理 $\lbrace f_i \mid i \in I \rbrace$ を$\mathbb{R}^{n}$ 上の真凸関数の集合とし $I$は任意の添字集合とする。また、$f$ をその集合の凸包とする。このとき$f$は、 と記述できる。ただし、下限は $x$ を要素 $x_i$ の凸結合として表現するすべての表現…
定理 任意の凸関数の集合について、点ごとに上限をとった関数は凸関数である。 証明 凸関数の集合を$\lbrace f_i(x) \rbrace_{i \in I}$として、題意の関数は以下のように記述される。 このとき、$\operatorname{epi}f = \bigcap_{i \in I} \operatorname{ep…
定理 $f_1, \dots, f_m$を$\mathbb{R}^{n}$上で定義された真凸関数とすると、以下で定義される$f$も$\mathbb{R}^{n}$上で凸関数となる。 証明 $\operatorname{epi}f = \lbrace (x, \mu) \in \mathbb{R}^{n+1} \mid \mu \ge f(x), x = \Sigma_{i=1}^{m} x_i \…
定理 $F$を$\mathbb{R}^{n+1}$内の任意の凸集合とし、次のように定義する： このとき、$f$は$\mathbb{R}^{n}$上の凸関数である。 証明 （解法１） $F$が空集合の場合、定義より$\inf \emptyset = \infty$である。 以下では、$F$が非空であるとする。 $f$が凸…
定理 $f_1$と$f_2$が$\mathbb{R}^{n}$上の真凸関数であるならば、$f_1 + f_2$は凸である。 証明 $f_1, f_2$が真凸関数であることから、$(f_1+f_2)(x)$は$\infty - \infty$のような計算ができない場合は発生しない。$(f_1+f_2)(x) = \infty$ならば、$f_1$また…
定理 $f$を$\mathbb{R}^{n}$から$(-\infty, +\infty]$への凸関数とし、$\varphi$を$\mathbb{R}$から$(-\infty, +\infty]$への凸関数で単調非減少とする。このとき、$h(x) = \varphi(f(x))$は$\mathbb{R}^{n}$上で凸である（$\varphi(+\infty) = +\infty$とす…
定理 正の同次性を持つ真凸関数$f$が部分空間$L$上で線形であるための必要十分条件は、$\forall x \in L$に対して$f(-x) = -f(x)$が成り立つことである。これは、基底$\lbrace b_1, \dots, b_m \rbrace$のすべてのベクトルに対して$f(-b_i) = -f(b_i)$が成り…
定理 $f$が正の斉次性を持つ適切な凸関数であるならば、すべての$x$に対して が成り立つ。 証明 Theorem 4.7（Rockafellar 1970）より、 となる。$f(x+0) \le f(x) + f(0)$となるから、$0 \le f(0)$である。 よって、$f(x) + f(-x) \ge 0$となることから、示…
定理 $f$が正の同次性を持つ真凸関数であるならば、次が成り立つ： ここで、$\lambda_1 > 0, \dots, \lambda_m > 0$である。 証明 Theorem 4.7（Rockafellar 1970）を繰り返し適用することで、 となる。同次性の条件より、$k \in [m] \quad f(\lambda_k x_k)…
定理 $\mathbb{R}^{n}$から$(-\infty, +\infty]$への正の同次関数$f$が凸関数であることは、$f(x + y) \leq f(x) + f(y), \quad x,y \in \mathbb{R}^{n}$ を満たすことと同値である。 証明 $\big(x, f(x) \big) \in \operatorname{epi}f$に対して、$f$が正の…
定理 任意の凸関数$f$および任意の$\alpha \in [-\infty, +\infty]$に対して、レベル集合$\lbrace x \mid f(x) < \alpha \rbrace$および$\lbrace x \mid f(x) \leq \alpha \rbrace$は凸である。 証明 $\lbrace x \mid f(x) < \alpha \rbrace$の場合、Theorem…
定理 $f$が開凸集合$C \subset R^{n}$上の二回連続微分可能な実数値関数であるとする。このとき、$f$が$C$上で凸であるための必要十分条件は、そのヘッセ行列 が$C$内のすべての$x$に対して半正定値であることである。 証明 関数$f$が$C$上で凸であることは…
定理 $f$ が開区間 $(\alpha, \beta)$ 上の二回連続微分可能な実数値関数であるとする。このとき、$f$ が凸であるための必要十分条件は、二次導関数 $f''$ が $(\alpha, \beta)$ 全体で非負であることである。 証明 （$\leftarrow$） $f''$ が $(\alpha, \be…
定理 関数$f$が$\mathbb{R}^{n}$から$[-\infty, +\infty]$への関数であるとする。このとき、$f$ が凸であるための必要十分条件は、$f(x) < \alpha$ および$f(y) < \beta$ のとき、$f \big((1 - \lambda)x + \lambda y \big) < (1 - \lambda)\alpha + \lambda…
定理 関数$f$が$C$から$(-\infty, +\infty]$への関数であり$C$が凸集合（例えば$C = \mathbb{R}^n$）であるとする。このとき、$f$が$C$上で凸であるための必要十分条件は、$\forall x, y \in C$に対して$f\big((1 - \lambda)x + \lambda y\big) \leq (1 - \l…
