$\max$関数の式変形が面白いなーと感じたので勢いで記事にしました!
以下の式が何故成り立つのかを考えます。
最適化したい式の中に$\max$が入っていると、最適化の難易度がぐーんと跳ね上がるのですが、以下の式に置き換えられれば難易度を下げることができます。
\max_{i}x_{i} \fallingdotseq \frac{1}{\beta}\log\sum_{i=1}^{n}\exp(\beta x_{i})
ここで、$i=a$のときに$x$が最大になるとします。つまり、こういうことです。
\max_{i}x_{i} = x_{a}
また、すべての$i$について$x_{i}$が等しいという場合は考えないことにします。
このとき、以下の等式が成り立ちます。
\exp(\beta x_{a}) < \sum_{i=1}^{n}\exp(\beta x_{i}) < n\exp(\beta x_{a})
$x_{i}$は1つの配列の要素です。当然、配列の要素をすべて足し合わせた値と、配列の中で最大となる要素を配列の長さで掛けた値では後者が大きくなります。
次に$\log$をとって、式変形をしていきます。
\begin{align}
\beta x_{a} &< \log\sum_{i=1}^{n}\exp(\beta x_{i}) < \log(n\exp(\beta x_{a})) \\
\beta x_{a} &< \log\sum_{i=1}^{n}\exp(\beta x_{i}) < \log n + \log\exp(\beta x_{a}) \\
\beta x_{a} &< \log\sum_{i=1}^{n}\exp(\beta x_{i}) < \log n + \beta x_{a} \\
x_{a} &< \frac{1}{\beta}\log\sum_{i=1}^{n}\exp(\beta x_{i}) < x_{a} + \frac{1}{\beta}\log n \\
\end{align}
何と、最大値が(多少の誤差はありますが)求まりました!
多少の誤差というのは$\frac{1}{\beta}\log n$のことです。したがって、要素数が増えると誤差も増えるということになりますが、$\beta$の値を大きくすることで誤差の範囲を狭めることができます。
計算機で実行する以上、$\beta$を無限に大きくすることは不可能なので、そこは要素数や$x_{i}$の取りうる範囲に応じて適切に決めていくのでしょう。