最適化問題とは、
ある関数を最大化(最小化)するような
関数の入力を見つけなさいというものです。
式で書くと次のような形ですね。
関数を最大とするような、
を、の中から探しなさいというものです。
は探す範囲を表しますが、
集合よりも不等式で範囲を指定することが多いです。
(より詳しい説明はこちら↑)
このやは、当然、解きたい問題によって違ってきますが、
これが、分かりやすい形になっていれば、
解きやすいということになります。
一見、変な形をしていても、
テクニックを使って変形すれば、
解きやすい形になることも多いです。
この記事では、
そんな最適化問題の変形のテクニックをまとめていきます。
絶対値の最小化
変形前
ある数字 から の距離を、
絶対値で測るとです。
これを素直に最小化するのであれば、
という最適化問題になり、
当然、絶対値が入ってきます。
変形後
これは、次のように変形することができます。
式の中から絶対値が消えました。
新しくという変数が加わっていますが、
これは、絶対値の値を表すための変数です。
また、新しく条件が加えられていますが、
これは、がちゃんと、の値であるための条件です。
ただし、正確には、絶対値の値を上側に見積もる条件です。
の時は、が正の値になり、この値が絶対値の値で、
は負の値になります。
そのため、新たに加えた条件式は、
となりますが、後ろの条件は前の条件で上書きされて、
は絶対値以上の値であるという条件になります。
の場合も同様です。
は最小化されるので、丁度、絶対値と一致する
が保証されます。
最大値の最小化
変形前
複数の変数の中の最大値を最小化する問題は、
と書けます。
変形後
これは、次のように変形することができます。
新しい変数が加わっていますが、
これは、[\max x_i]の値を表す変数です。
また、がちゃんと、最大値を表すように、
新しく条件が加わっています。
条件 によって、
はどの 以上の値になります。
つまり、最大値以上の値になります。
上の場合と同様に、
を最小化することで、丁度、最大値と一致することが保証されます。
ReLU 関数の最小化
変形前
0以下の値を0に、
0以上の値をそのままにするReLU関数を使って、
という問題を考えます。
変形後
ややこしそうですが、
であることに気をつければ、
最大値の最小化にならって、
と変形できます。
2進数の掛け算
変形前
二つの変数の掛け算が、
最適化に入りこんでくることがあります。
例えば、
みたいなものです。
この時、xとyが0か1のどちらかを取るのであれば、
掛け算をなくすことができます。
変形後
パターンはつかめてきたと思いますが、
変形したい部分を、別の変数に置き換えます。
はと同じく0,1のどちらかを取る変数で、
の値を表します。
新たに加えた条件の最初の2つ
は、のどちらか一方でも0なら、
となり、
は0になります。
これは、掛け算の結果が0になる条件ですね。
もう一つの条件
は掛け算の結果が1になる条件を表しています。
が共に1だと、この条件は、
となり、
は1となります。