数理最適化（線形計画問題④）

区分線形凸関数最小化問題の定式についてまとめていきます。

定式

区分線形凸関数最小化問題の定式はこちらです。

$$
min   f(x) = \displaystyle\max_{i=1,2…,m-1} \lbrace{\cfrac{f(a_{i+1}) - f(a_i)}{a_{i+1} - a_i}(x - a_i) + f(a_i)} \rbrace\\
a_1 \leq x \leq a_m
$$

最小化を求める問題なので、「min」はわかりますが、途中にいる「max」がよくわかりません。
なぜ max があるのかをまとめていきます。

max関数

集合の中の最大値を求める関数です。
なので、次の例だと
　max(5, 8, 4, 1) = 8
となります。

なぜmax関数を使うと区分線形凸関数を表現できるのか

凸関数上の点をそれぞれ結んだの線形関数は、以下のようにたくさん引けます。

ある x の位置に対応する線形関数の値 f(x) は、線形関数の数だけ存在します。

その f(x) の中で、最も大きな値のものだけを選択していくと、近似線になります。

凸関数の特徴により、必ず最大値が近似線となります。
そのため、max関数を用いることで、区分線形関数を表すことができます。

図を書いてみるまでよくわかりませんでした。
本を読んでも当たり前のように max が使われており、どのサイトを見ても説明がありません。
おそらく常識的なことなのだと思います。
理解するのに時間がかかりましたが、すっきりしてよかったです。