概要

ペナルティ法(罰金法)について勉強したので、そのメモとしてここに記載します。

©️ゆるゆり(かわいい...)

定式化

今、変数$x, y$のエネルギー$f(x, y)$が与えられているとします(この$f$はQUBOなどの変換によってすでに2次形式で2値($x, y \in {0, 1}$)の数式になっているものとします)。そのエネルギーが最小になるように$x, y$を取りましょう。これを数式で表現すると

\min_{x, y} f(x, y) \tag{*1}

のようになります。シンプルですね。

制約の導入

ここで

x + y = K \tag{*2}

という制約を導入しましょう。すなわち、この制約を守りつつ(*1)の$f$を最小にしなさい、という問題になりました。

制約ありから制約なしへの変換、ペナルティ法

制約という(*2)を満たしつつ(*1)式を到達する、というと式が2つに分かれていることもあり、複雑さが増しているように感じますね。ではどうするか...答えはそう、制約を制約と思えなくなるような1つの数式にまとめてあげれば良いのです。
そのためにコスト関数を導入しましょう。この制約からズレが生じたときにコストを増加させるような関数を考えればよいとすると、一番簡単な形は以下のようになります。

E 
= f(x, y) + \lambda (x+y-K)^2 \tag{*3}

ここで$\lambda$は制約のズレにかかる重みの定数です。この$E$を最小化すれば、自動的に(*1)式を満たし、かつ制約(*2)も成立するような$x, y$が選択されます。
しかし、気をつけなければならないことは$\lambda$の大きさです。$\lambda \gg 1$を選択すると、せっかく(*1)が満たされていても、$x, y$が制約を少し破っているだけでコスト$E$が大きくなってしまいます。

OpenJijでプログラミングにチャレンジ！

OpenJijというPythonのモジュールを使用することで実際に、最適化問題を解くことが可能です。

$ pip install openjij

で簡単にインストールできます。実際に使用してみると良いでしょう。

結言

今回は最適化問題でよく用いられる基礎的な手法のペナルティ法(罰金法)をご紹介しました。この調子で、他の最適化問題の記事も掲載していく予定です。乞うご期待ください。

アドバンス: 拡張ラグランジュ未定乗数法

詳細は省略(目下、著者が勉強中)させていただきますが、以下のような拡張ラグランジュ未定乗数法を使うことで、より精度よくコストを減らしかつ制約を満たすような$x, y$が見つかることが知られています。

E 
= f(x, y) + \lambda (x+y-K)^2 + \alpha (x+y-K)