定理 以下の線形不等式系のいずれか一方のみが解を持つ。 1. $\lbrace Ax \leq b_1, Bx = b_2 \rbrace$ 2. $\lbrace y_1^{T} A + y_2^{T} B = \boldsymbol{0}, y_1 \ge \boldsymbol{0}, y_1^{T} b_1 + y_2^{T} b_2 < 0\rbrace$ 証明 （1.が成立すると2.が成…

定理 任意の凸関数の集合について、点ごとに上限をとった関数は凸関数である。 証明 凸関数の集合を$\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_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$および任意の$\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(\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$が$\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…

定理 もし$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…