Convex Set
定理 $C$ を $\mathbb{R}^{n}$ 内の凸集合とする。このとき、$z \in \operatorname{int}C$ であるための必要十分条件は、任意の $y \in \mathbb{R}^{n}$ に対して、$\epsilon > 0$ が存在して、$z + \epsilon y \in C$ となることである。 証明 （$\Rightarr…
定理 $C$ を $R^{n}$ 内の非空の凸集合とする。このとき、$z \in \operatorname{ri} C$ であるための必要十分条件は、任意の $x \in C$ に対して、$(1 - \mu)x + \mu z$ が $C$ に属する、$\mu > 1$ となる $\mu$ が存在することである。 不明点 （$\Leftarr…
定理 もし $C$ が $\mathbb{R}^n$ の凸集合であるならば、$\operatorname{cl}C$ と交わる任意の開集合は、$\operatorname{ri}C$ とも交わる。 証明 任意の開集合を$A$として、$\operatorname{cl} C \cap A \neq \emptyset \Rightarrow \operatorname{ri}C \c…
定理 $\mathbb{R}^n$ 内の凸集合 $C_1$ と $C_2$ に対して、$\operatorname{cl} C_1 = \operatorname{cl} C_2$ であることは $\operatorname{ri} C_1 = \operatorname{ri} C_2$ であることと同値である。これらの条件は $\operatorname{ri} C_1 \subset C_2 …
定理 $\mathbb{R}^n$ 内の任意の凸集合 $C$ に対して、$\text{cl} (\text{ri} C) = \text{cl } C$ かつ $\text{ri} (\text{cl } C) = \text{ri } C$ が成り立つ。 証明 ($\text{cl} (\text{ri } C) = \text{cl} C$ の証明) $\text{ri } C \subset C$より$\te…
定理 任意の凸集合 $C \subset \mathbb{R}^n$ に対し、$\operatorname{cl} C$ および $\operatorname{ri} C$ は同じアフィン包を持ち、それぞれ$C$と同じ次元を持つ。（特に、$C \neq \emptyset$ ならば $\operatorname{ri} C \neq \emptyset$ である。） 証…
定理 非空の凸集合$C$に対して以下が成立する。 (a) $\operatorname{ri}C$ は非空の凸集合であり、$C$と同じアフィン包を持つ。 (b) $m$が $\operatorname{aff}C$ の次元であり、$m > 0$ であれば、ベクトル $x_0, x_1, \dots, x_m \in \operatorname{ri}C$ …
定理 関数$h$ は凸関数とし、Theorem 5.3（Rockafellar 1970）を用いて以下のように関数$f$を定義すると、以下が成立する。 この関数$f$を positively homogeneous convex function generated by $h$と呼ぶ。 証明 $\operatorname{cone}(\operatorname{epi}h…
定理 $f_i$が$\mathbb{R}^{n}$上の凸関数であり、$z_i$が任意の添字集合$I$の各$i \in I$に対して実数であるとする。このとき、$C = \lbrace x \mid f_i(x) \leq z_i, \forall i \in I \rbrace$ は凸集合である。 証明 $f_i$は$\mathbb{R}$の値を持つ関数で…
定理 関数 $f$ が $\mathbb{R}^{n}$ から $(-\infty, +\infty]$ への関数であるとする。このとき、$f$ が凸であるための必要十分条件は、$f(\lambda_1 x_1 + \cdots + \lambda_m x_m) \leq \lambda_1 f(x_1) + \cdots + \lambda_m f(x_m)$が $\lambda_1 \geq…
定理 関数$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…
定理 もし$K_1$と$K_2$が原点を含む凸錐であれば、$K_1 + K_2 = \text{conv} (K_1 \cup K_2)$、$K_1 \# K_2 = K_1 \cap K_2$が成立する。 証明 （$K_1 + K_2 = \text{conv} (K_1 \cup K_2)$について） Theorem 3.3（Rockafellar 1970）より、$K_1 + K_2 = \b…
定理 もし $C_1$ および $C_2$ が $\mathbb{R}^{n}$ の凸集合なら、そのinverse addition $C_1 \# C_2 = \bigcup \Big\lbrace \big((1 - \lambda)C_1 \cap \lambda C_2 \big) \mid 0 \leq \lambda \leq 1 \Big\rbrace$ もまた凸集合である。 証明 本証明では…
定理 $C_1$ と $C_2$ は $\mathbb{R}^{m+p}$ の凸集合とする。また、$C$ をベクトルの集合 $x = (y, z)$（ここで $y \in \mathbb{R}^m$ および $z \in \mathbb{R}^{p}$）とし、$(y, z_1) \in C_1$、$(y, z_2) \in C_2$、および $z_1 + z_2 = z$ となるような…
定理 $C$と$D$がそれぞれ$R^{m}$と$R^{p}$の凸集合であるとする。このとき、$C \oplus D = \lbrace x = (y, z) \mid y \in C, z \in D \rbrace$は$R^{m+p}$の凸集合である。 証明 $0 \le \lambda \le 1$に対して、$y_1, y_2 \in C, z_1, z_2 \in D$を考える…
定理 凸集合$C$を部分空間$L$へ直交射影して得られる集合は凸集合である。 方針 直行射影が線形変換であることを証明し、Theorem 3.4（Rockafellar 1970）を適用する。 ただし、証明が長くなるため直行射影定理や直行分解の性質は既知として進める。 証明 $L…
定理 $A$を$\mathbb{R}^{n}$から$\mathbb{R}^{m}$への線形変換とする。このとき、任意の凸集合$C \subset \mathbb{R}^{n}$に対して$AC = \lbrace Ax \mid x \in C \rbrace$は凸集合である。また任意の凸集合$D \subset \mathbb{R}^{m}$に対して $A^{-1}D = \…
定理 ${C_i | i \in I }$ を $\mathbb{R}^{n}$内の非空の凸集合の任意の集合とする。このとき、$\lbrace \lbrace \lambda_i \rbrace_{i \in I} \mid \Sigma_{i \in I} \lambda_i = 1, \quad \lambda_i \in \mathbb{R}_{+} \quad i \in I \rbrace$とすると、 …
定理 $C$ が凸集合であり、$\lambda_1 \geq 0$, $\lambda_2 \geq 0$ ならば、$(\lambda_1 + \lambda_2)C = \lambda_1 C + \lambda_2 C$となる。 証明 （$\Rightarrow$） $x \in C$とすれば、$(\lambda_1 + \lambda_2)x = \lambda_1 x + \lambda_2 x$より明ら…
定理 もし $C_1$ と $C_2$ が $\mathbb{R}^{n}$ 内の凸集合であれば、それらの和 $C_1 + C_2 = \lbrace x_1 + x_2 \mid x_1 \in C_1, x_2 \in C_2 \rbrace$ も凸である。 証明 $x, y \in C_1 + C_2$ とすると、$x_1, y_1 \in C_1 \quad x_2, y_2 \in C_2$ を…
定理 $K$ を$0$を含む凸錐とする。このとき、$K$ を含む最小の部分空間は$K - K = \lbrace x - y \mid x \in K, y \in K \rbrace = \mathrm{aff}\ K$であり、$K$ 内に含まれる最大の部分空間は$(-K) \cap K$である。 証明 （Kを含む最小の部分空間） Theorem…
定理 凸集合$C$に対して、$K = \lbrace \lambda x \mid \lambda > 0, x \in C \rbrace$とする。$K$ は $C$ を含む最小の凸錐である。 証明 Corollary 2.6.2（Rockafellar 1970）より、Cの全ての線形結合が$K$に含まれることを示せば良い。Theorem 2.2（Rocka…
定理 任意の $\mathbb{R}^{n}$ の部分集合 $S$ と、$S$ の全ての正の線形結合の集合 $K$ を考える。このとき、$K$ は $S$ を含む最小の凸錐である。 証明 題意より明らかに$K \supseteq S$となる。また、Corollary 2.6.1（Rockafellar 1970）より$K$は凸錐と…
定理 ある $\mathbb{R}^n$ の部分集合が凸錐であるための必要十分条件は、その部分集合がその要素の全ての正の線形結合を含むことである。 方針 必要条件はTheorem 2.6（Rockafellar 1970）の内容を加算個に拡張したものであるため、数学的帰納法で証明する…
定理 ある$\mathbb{R}^{n}$の部分集合が凸錐であるための必要十分条件は、それが加法と正のスカラー倍に対して閉じていることである。 証明 （$\Rightarrow$） $K$ を凸錐とし、$x,y \in K$ とする。$K$ が凸であることより、$z = \frac{1}{2}(x + y) \in K$…
定理 任意の添字集合 $I$ に対して、$b_i \in \mathbb{R}^n$ とするとき、$K = \lbrace x \in \mathbb{R}^n \mid \langle x, b_i \rangle \leq 0, i \in I \rbrace$は凸錐である。 方針 Corollary 2.1.1（Rockafellar 1970）と同様に証明する。 証明 $K_i = …
定理 任意の凸錐の集合の交わりは凸錐である。 方針 Theorem 2.1（Rockafellar 1970）と同様に証明する。 証明 凸錐の族を$\lbrace K_\lambda \rbrace_{\lambda \in \Lambda}$とし、その積集合を$K = \bigcap_{\lambda \in \Lambda} K_\lambda$とする。 $\fo…
定理 任意の $S \subset R^{n}$ に対して、$\operatorname{conv} S$ は $S$ の要素のすべての凸結合から成ります。 証明 （Sの凸結合$\rightarrow \operatorname{conv} S$） $S \subseteq \operatorname{conv}S$であり、その凸結合は全てTheorem 2.2（Rockaf…
定理 $\mathbb{R}^{n}$ の部分集合$C$が凸集合であることと、$C$がその元についてのすべての凸結合を含むことと同値である。 証明 帰納法を用いて証明する。 1. $m=2$のとき 凸集合の定義より、$\forall x_1, x_2 \in C$に対して、$\lambda_1 + \lambda_2 = …
定理 任意の添字集合 $I$ に対して、$i \in I$ のとき $b_i \in \mathbb{R}^n$ かつ $\beta_i \in \mathbb{R}$ とする。このとき集合$C = \lbrace x \in \mathbb{R}^n \mid \langle x, b_i \rangle \leq \beta_i, \forall i \in I \rbrace$は凸である。 証明…
