冷めたコーヒー

Weniger, aber besser

$\sum_{i=1}^{n}\min \{x_i, (Ax+b)_i\}$ の凹性について

tl;dr

この記事では,以下の関数

$$ f(\mathbf{x}) = \sum_{i=1}^{n}\min \left\{x_i, (A\mathbf{x}+\mathbf{b})_i\right\} $$

が凹関数(Wikipedia)であることを見ていく.ここで,$A$ は適当な大きさの実行列であり,$\mathbf{b}$ は適当な大きさの実ベクトルである.また,$x_i$ はベクトル $\mathbf{x}$ の第 $i$ 成分を表す.

お気持ち

関数 $g_i,\, h_i$ を以下のように定義する.

\begin{align} g_i(\mathbf{x}) &:= \mathbf{e}_i^\top \mathbf{x} = \left< \mathbf{e}_i, \mathbf{x}\right>, \\ h_i(\mathbf{x}) &:= \mathbf{e}_i^\top (A\mathbf{x} + \mathbf{b}) = \left<A^\top \mathbf{e}_i, \mathbf{x}\right> + \left< \mathbf{e}_i, \mathbf{b}\right>. \end{align}

ここで,$\mathbf{e}_i$ は $n$ 次元のベクトルであり,その第 $i$ 成分のみ $1$ で他の成分がすべて $0$ であるとする.すなわち,$\mathbf{e}_i = (0,\dots, 0, \underset{i}{1}, 0, \dots, 0)^\top$ である. すると,関数 $f$ は関数 $g_i,\, h_i$ を用いて

$$ f(\mathbf{x}) = \sum_{i=1}^{n}\min \left\{g_i(\mathbf{x}), h_i(\mathbf{x})\right\} $$

と表されることが分かる.

和の部分を無視して,関数 \begin{align} \phi_i(\mathbf{x}) &= \min \left\{g_i(\mathbf{x}), h_i(\mathbf{x})\right\} \\ &= \min \left\{ \mathbf{e}_i^\top \mathbf{x}, \mathbf{e}_i^\top (A\mathbf{x} + \mathbf{b})\right\} \end{align} を観察すると,これは 2 つの線型関数に対して $\min$ をとったものになっているので,気持ちとしては以下のような図として表され,確かに凹関数であるように思える.

f:id:mirucacule:20211124145913j:plain
関数 $\phi_i$ の形状

証明に用いる道具

次の 2 つの命題を用いる:

  • 凹関数の列に対して $\min$ をとった関数もまた凹関数である
  • 凹関数の列に対して和をとった関数もまた凹関数である

まず,一つ目の命題について考える.なお,一般的に数理最適化の分野では凸関数を扱うことが多いため,命題としては凸関数で述べ,その系として凹関数について述べることとする.

補題 凸集合 $S\subset \mathbb{R}^n$ 上で定義された上に有界な実数値関数の列 $\{f_i\}_{i=1}^{n}$ に対して,すべての $f_i$ が $S$ 上の凸関数ならば,実数値関数 $$ f(\mathbf{x}) = \max_{i\in [n]} f_i(\mathbf{x}) $$ は $S$ 上の凸関数である.ここで,$[n]$ は集合$\{1,2,\dots, n\}$ を表す.

証明.関数 $f$ のエピグラフが凸集合であることを言えばよい.いま,$f_i$ は凸関数であるため,そのエピグラフ $$ \mathrm{epi}\, f_i = \left\{ (\mathbf{x},z)^\top \in \mathbb{R}^{n+1} \mid f_i(\mathbf{x}) \leq z, \, \mathbf{x}\in S,\, z \in \mathbb{R} \right\} $$ は $\mathbb{R}^{n+1}$ 上の凸集合である.また,これらの共通集合 \begin{align} \bigcap_{i \in [n]} \mathrm{epi}\, f_i &= \left\{ (\mathbf{x},z)^\top \in \mathbb{R}^{n+1} \mid f_i(x) \leq z, \, \mathbf{x}\in S,\, z \in \mathbb{R},\, i \in [n] \right\} \\ &= \left\{ (\mathbf{x},z)^\top \in \mathbb{R}^{n+1} \mid \max_{i \in [n]}f_i(\mathbf{x}) \leq z, \, \mathbf{x}\in S,\, z \in \mathbb{R} \right\} \\ &= \left\{ (\mathbf{x},z)^\top \in \mathbb{R}^{n+1} \mid f(\mathbf{x}) \leq z, \, \mathbf{x}\in S,\, z \in \mathbb{R} \right\} \end{align} もまた凸集合である.これは $S$ 上の実数値関数 $f$ のエピグラフである.したがって,$f$ は $S$ 上の凸関数である.(証明終)

この補題の系として,次の命題が成り立つ.

凸集合 $S\subset \mathbb{R}^n$ 上で定義された下に有界な実数値関数の列 $\{f_i\}_{i=1}^{n}$ に対して,すべての $f_i$ が $S$ 上の凹関数ならば,実数値関数 $$ f(\mathbf{x}) = \min_{i\in [n]} f_i(\mathbf{x}) $$ は $S$ 上の凹関数である.ここで,$[n]$ は集合 $\{1,2,\dots, n\}$ を表す.

さて,関数

$$ \phi_i(\mathbf{x}) = \min\{g_i(\mathbf{x}), \,h_i(\mathbf{x})\} = \min\{\mathbf{e}_i^\top \mathbf{x}, \,\mathbf{e}_i^\top (A\mathbf{x} + \mathbf{b})\} $$

について,関数 $g_i,\, h_i$ はそれぞれ $\mathbf{x}$ に関して線型であるため,凸であり,かつ凹である.したがって,系より関数 $\phi_i$ は凹関数であることが分かる.

次に,凹関数の列の和がまた凹関数であることを見ていく.こちらでもまず凸関数の列の和がまた凸関数であることを述べた後,その系として凹関数について述べることとする.

補題 凸集合 $S\subset \mathbb{R}^n$ 上で定義された実数値関数の列 $\{f_i\}_{i=1}^{n}$ に対して,すべての $f_i$ が $S$ 上の凸関数ならば,実数値関数 $$ f(\mathbf{x}) = \sum_{i=1}^{n} f_i(\mathbf{x}) $$ は $S$ 上の凸関数である.

証明.関数 $f$ が凸関数の定義,すなわち,任意の $\mathbf{x},\, \mathbf{y} \in S$ と実数 $\lambda \in [0,1]$ に対して $$ f(\lambda\mathbf{x} + (1-\lambda)\mathbf{y}) \leq \lambda f(\mathbf{x}) + (1-\lambda) f(\mathbf{x}) $$ を満たすことを確認すればよい.容易なので読者に任せる.(証明終)

これについても系として次の命題が成り立つ.

凸集合 $S\subset \mathbb{R}^n$ 上で定義された実数値関数の列 $\{f_i\}_{i=1}^{n}$ に対して,すべての $f_i$ が $S$ 上の凹関数ならば,実数値関数 $$ f(\mathbf{x}) = \sum_{i=1}^{n} f_i(\mathbf{x}) $$ は $S$ 上の凹関数である.

この系を用いると,先の議論より関数 $\phi_i$ はすべての $i\in [n]$ で凹であったから,関数

$$ f(x) = \sum_{i=1}^{n} \phi_i(\mathbf{x}) = \min \left\{x_i, (A\mathbf{x}+\mathbf{b})_i\right\} $$

は凹関数であることが分かる.

結論

以上の議論より,次の命題が成り立つことが確認された.

定理 次の関数 $f\colon\mathbb{R}^n\to\mathbb{R}$ は凹関数である. \begin{align} f(\mathbf{x}) = \sum_{i=1}^{n} \min \left\{x_i, (A\mathbf{x}+\mathbf{b})_i \right\} \end{align}

参考文献