定理 まず以下の変数や記法を定義する。 ・通し番号の集合を分割する２種類の集合$\lbrace M_{i} \rbrace_{i=1}^{p}, \lbrace N_{j} \rbrace_{j=1}^{q}$： ・行列$A \in \mathbb{R}^{m \times n}$、その$(i,j)$要素を$a_{i,j}$とする。またブロック行列を$A_…

定理 以下の線形不等式系のいずれか一方のみが解を持つ。 $A_i$は行列を指しており、$i$は通し番号である。また$\gneq$は、両辺が一致することはないが要素ごとに見ると$\ge$が成立する不等式である。 $\lbrace A_1 x_1 + A_2 x_2 + A_3 x_3 + \sum_{j=4}^{q…

定理 以下の線形不等式系のいずれか一方のみが解を持つ。 $A_i$は行列を指しており、$i$は通し番号である。また$\gneq$は、両辺が一致することはないが要素ごとに見ると$\ge$が成立する不等式である。 $\lbrace A_1 x_1 + A_2 x_2 + A_3 x_3 + \sum_{j=4}^{q…

定理 以下の線形不等式系のいずれか一方のみが解を持つ。 1. $\lbrace Ax + Bv + Cz = \boldsymbol{0}, v \ge \boldsymbol{0}, z > \boldsymbol{0} \rbrace$ 2. $\lbrace y^{T} A = \boldsymbol{0}, y^{T} B \ge \boldsymbol{0}, y^{T} C \gneq \boldsymbol{…

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

定理 $\lbrace f_i \mid i \in I \rbrace$ を$\mathbb{R}^{n}$ 上の真凸関数の集合とし $I$は任意の添字集合とする。また、$f$ をその集合の凸包とする。このとき$f$は、 と記述できる。ただし、下限は $x$ を要素 $x_i$ の凸結合として表現するすべての表現…

定理 以下の線形不等式系のいずれか一方のみが解を持つ。 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…

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