クイックノート

ちょっとした発見・アイデアから知識の発掘を

最適化問題の線形化テクニック

最適化問題とは、
ある関数を最大化(最小化)するような
関数の入力を見つけなさいというものです。

式で書くと次のような形ですね。

 maximize : f(x)
 subject\ to: x \in A

関数fを最大とするような、
x を、x \in Aの中から探しなさいというものです。
A は探す範囲を表しますが、
集合よりも不等式で範囲を指定することが多いです。

(より詳しい説明はこちら↑)

このfAは、当然、解きたい問題によって違ってきますが、
これが、分かりやすい形になっていれば、
解きやすいということになります

一見、変な形をしていても、
テクニックを使って変形すれば、
解きやすい形になることも多いです。

この記事では、
そんな最適化問題の変形のテクニックをまとめていきます。

絶対値の最小化

変形前

ある数字a から xの距離を、
絶対値で測ると|x-a|です。

これを素直に最小化するのであれば、
 minimize: |x-a|
という最適化問題になり、
当然、絶対値が入ってきます。

変形後

これは、次のように変形することができます。
minimize : z
subject\ to: x - a \le z , a - x \le z
式の中から絶対値が消えました。

新しくzという変数が加わっていますが、
これは、絶対値|x -a|の値を表すための変数です。

また、新しく条件が加えられていますが、
これは、zがちゃんと、|x-a|の値であるための条件です。
ただし、正確には、絶対値の値を上側に見積もる条件です。

x \ge a の時は、x -aが正の値になり、この値が絶対値の値で、
a-xは負の値になります。
そのため、新たに加えた条件式は、
 |x-a| \le z, 負の数 \le z
となりますが、後ろの条件は前の条件で上書きされて、
zは絶対値以上の値であるという条件になります。

 x \le a の場合も同様です。

zは最小化されるので、丁度、絶対値と一致する
 z = |x-a|が保証されます。

最大値の最小化

変形前

複数の変数x_1,x_2,x_3,\cdots,x_nの中の最大値を最小化する問題は、

 minimize : \max x_i
 subject\ to: x_i \in A

と書けます。

変形後

これは、次のように変形することができます。

 minimize : z
 subject\ to :z \ge x_i, x_i \in A

新しい変数zが加わっていますが、
これは、[\max x_i]の値を表す変数です。

また、zがちゃんと、最大値を表すように、
新しく条件が加わっています。

条件z \ge x_i によって、
z はどの x_1, x_2, \cdots 以上の値になります。
つまり、最大値以上の値になります。

上の場合と同様に、
zを最小化することで、丁度、最大値と一致することが保証されます。

ReLU 関数の最小化

変形前

0以下の値を0に、
0以上の値をそのままにするReLU関数\psi(x)を使って、

 minimize: \psi(x)
 subject\ to: x \in A

という問題を考えます。

変形後

ややこしそうですが、
\psi(x) = \max(0,x) であることに気をつければ、
最大値の最小化にならって、

 minimize: z
 subject\ to: z \ge 0, z \ge x, x \in A

と変形できます。

2進数の掛け算

変形前

二つの変数x,yの掛け算xyが、
最適化に入りこんでくることがあります。

例えば、
maximize: xy
 subject\ to: x,y \in A
みたいなものです。

この時、xとyが0か1のどちらかを取るのであれば、
掛け算をなくすことができます。

変形後

パターンはつかめてきたと思いますが、
変形したい部分を、別の変数に置き換えます。

maximize: z subject\ to: z \le x, z \le y, x + y \le z + 1, x,y \in A

zx,yと同じく0,1のどちらかを取る変数で、
xyの値を表します。

新たに加えた条件の最初の2つ
z \le x
z \le y
は、x,yのどちらか一方でも0なら、
z \le 0 となり、
zは0になります。
これは、掛け算の結果が0になる条件ですね。

もう一つの条件
 x + y \le z+1
は掛け算の結果が1になる条件を表しています。
x,yが共に1だと、この条件は、
1 \le zとなり、
zは1となります。

プライバシーポリシー