2次計画法
ラグランジュ乗数の意味
サポートベクトルのマージンを最大化するために、ラグランジュの未定乗数法を等式制約から不等式制約がある場合に拡張する必要があります。
ラグランジュの未定乗数法を不等式制約がある場合に拡張した最適化アルゴリズムを2次計画法(有効制約法)と言います。
不等式制約を考える上でラグランジュ乗数の意味を理解する必要があります。
等式制約で求まった最適解においては、目的関数の勾配と、制約関数の勾配方向が並行になる性質があります。
つまり、適当な定数とおいて以下(1)式が成り立っています。
(1)式の右辺を左辺に移項してやると、
この(2)式はラグランジュ関数を設計変数で微分した値を0とおいた式になります。
ラグランジュの未定乗数法はまさに目的関数と制約関数の勾配が平行になるという性質を利用したアルゴリズムになります。
では、ラグランジュ乗数の意味を考えてみましょう。
ラグランジュ乗数が負の場合は、(1)式より目的関数と制約関数の勾配方向が一致しており、目的関数が減少する方向は、制約関数が減少する方向を意味しています。
反対にラグランジュ乗数が正の場合は、目的関数の勾配は制約関数の勾配と反対方向を向いており、目的関数が減少する方向は、制約関数が増加する方向を意味しています。
ラグランジュ乗数の符号により、目的関数の勾配と制約関数の勾配の向きが一致しているか否かがわかるわけです。
2次計画法のアルゴリズム
不等式制約がある場合に、目的関数を最小化することを考えます。
制約関数と目的関数はそれぞれ、設計変数の1次式、2次式で表されます。
目的関数の純粋な最小値(制約条件がない場合の最小値)が、内にある場合は、制約条件を考える必要はありません。この場合の制約条件を無効制約と呼びます。
しかし反対に外側にある場合は、少なくとも1つの等式制約式 上に最適解が存在し、更にそのラグランジュ乗数は、目的関数が減少する方向と制約関数が増加する方向が一致する様に定まります。
つまりラグランジュ乗数は正の値になります。この場合の制約条件を有効制約と呼びます。
これらの事をまとめると、不等式制約がある場合の目的関数の最小値を与える最適解とラグランジュ乗数は以下4つの条件式を満たすことになります。
添え字のは、制約条件の番号を表しています。制約条件は全部で個あるとします。
(6)、(8)式のは、マトリックスの番目の行を横ベクトルとして表したもので、
は、設計変数の個数です。つまり、
(5)、(6)、(7)、(8)の4つの式はKKT条件(Karush-Kuhn-Tucker条件)と呼ばれています。
(5)式は、目的関数と制約関数の勾配が平行であることを表し、(6)式は不等式制約そのままです。
(7)式は、最適解が無効制約上にある場合はになり、有効制約上にある場合はになることを表しています。
(8)式は、最適解が無効制約上にある場合は、有効制約上にある場合はになるので、とをかけてやると、その値は常に0になることを表しています。
2次計画法では、それぞれのKKT条件を満たすように逐次的にを動かしてやります。
全てのKKT条件が満たされたを発見できた場合はそれが、最適解になります。
以下最適化ルーチンをステップ別で分けていきます。
Step1
先ずは動かしてやる設計変数の初期値を適当に決めてやります。(取りあえずは0ベクトルでいいです。)
その後、を少しずつ動かして、(6)式で表される全ての不等式制約を満たすを見つけてやります。
(6)式を全て満たすを実行可能解といいます。
実行可能解が見つかったら、有効制約となる制約条件があるかどうかを調べます。もし有効制約となる制約条件が見つかったらその制約条件の番号をリストに保存しておきます。
Step2
有効制約となる制約条件が見つかった場合、とから無効制約となる行を取り除き、有効制約のみで作り直してととしてやります。
有効制約で作り直した、及び、より、ラグランジュの未定乗数法を使って一時的な解とラグランジュ乗数を求めてやります。
有効制約となる制約条件が見つからなかった場合は、とを考慮する必要がなく、のみで制約条件がない場合の純粋な目的関数の最小解をとし、ラグランジュ乗数は0にしておきます。
求めたが実行可能解でない場合はStep3へ進み、実行可能解である場合はStep4へ進みます。
Step3
実行可能解の領域外に出てしまったを、有効制約上に乗るように実行可能解に戻してやります。
Step1で求めたは実行可能解であるため、実行可能解領域外に出てしまったとを結ぶ直線上に少なくとも一つは、有効制約となるが存在します。
とを結ぶ直線上の点は、を用いて以下の様に表すことができます。
を少なくとも一つの有効制約上に乗せてやるため、の中で、でかつ一番小さなを見つけてやります。
つまり、個ある制約関数すべてにを入れてやり、その値を0と置いて各式でを求めてやり、0以上でかつ最小になるを一つだけ求めます。
(18)式で求まったを使って、(15)式よりを求めた後、を新しいとして更新します。
この時有効制約が一つ増えているので、その有効制約条件番号をリストに追加してStep2に戻ります。
Step4
Step2で求めたが実行可能解であり、更に同時に求めたの全ての値が(7)式を満たすとき、全てのKKT条件が満たされたことになり、は最適解となっています。
を最適解として出力し、ループを終了します。
<がある場合は、その中で一番小さなの制約条件番号をリストから取り除いてStep2に戻りループを繰り返します。
初期実行可能解の求め方
Step1で適当に決めてやった設計変数の初期値を実行可能解に移動させる方法を考えてみました。
先ず、を制約関数に代入し、>の中で一番大きな値を持つ、を見つけてやります。
今、番目の制約関数値が一番大きかったとして、をの内側に持ってくることを考えます。
点と直線の距離は、
また、が減少する方向は、
(20)式で表される方向に対して、(19)式で表される距離よりも少し長く動かしてやれば、をの内側に持ってくることができます。
1より少し大きい適当な定数をとすると、をアップデートする点は、
になります。
この操作を繰り返していくと、そのうち全ての制約条件を満たす実行可能解を見つけることができます。
ただし、番目の制約関数値が減少する方向は、他の制約関数が減少する方向というわけではないので、この操作をずっと繰り返しても、必ずしも実行可能解が見つかるわけではないです。本来はもっとうまい方法があると思いますが、取りあえずはこの方法を採用しました。
Pythonでコーディング
2次計画法で不等式制約がある場合の目的関数を最小化するコードを書いてみました。
設計変数の個数と制約条件の個数はどちらも2個として、main関数の中で以下4つの簡単なケースにおける最適化結果を出力します。
- 2つある制約条件のうちどちらも無効制約条件の場合
- 2つある制約条件のうち1つが有効制約条件の場合(2番目の制約条件が有効制約)
- 2つある制約条件のうちどちらも有効制約条件の場合
- 目的関数と制約関数を乱数で作成した場合
2つある制約条件のうちどちらも無効制約条件の場合
目的関数と制約条件が以下の場合を考えます。
は以下のようになります。
制約条件、はどちらも無効制約になるので、目的関数の最小値は、制約がない場合の最小値になります。最適解はです。
以下スクリプトの実行結果です。あってますね。
■2つある制約条件のうちどちらも無効制約条件の場合 1回目のイタレーションで最適解が見つかりました。 ・最適解x: [0.0, 0.0] ・目的関数f(x)の最小値: 0.0 ・KKT条件1(∇f+λ∇g=0): True [0.0, 0.0] ・KKT条件2(g<=0): True [-1.0, -1.0] ・KKT条件3(λ>=0): True [0.0, 0.0] ・KKT条件4(λg=0): True [0.0, 0.0]
2つある制約条件のうち1つが有効制約条件の場合(2番目の制約条件が有効制約)
以下、目的関数と制約条件です。
は以下のようになります。
が無効制約、が有効制約になります。グラフから最適解がになるのが直感でわかると思います。
以下スクリプトの実行結果です。まあ、あってます。
■2つある制約条件のうち1つが有効制約条件の場合(2番目の制約条件が有効制約) 2回目のイタレーションで最適解が見つかりました。 ・最適解x: [0.5, -0.5] ・目的関数f(x)の最小値: 0.5 ・KKT条件1(∇f+λ∇g=0): True [0.0, 0.0] ・KKT条件2(g<=0): True [-1.0, 0.0] ・KKT条件3(λ>=0): True [0.0, 1.0] ・KKT条件4(λg=0): True [0.0, 0.0]
2つある制約条件のうちどちらも有効制約条件の場合
以下、目的関数と制約条件です。
は以下のようになります。
、どちらも有効制約になります。こちらもグラフから最適解がになるのが直感でわかると思います。
以下スクリプトの実行結果です。あってますね。
■2つある制約条件のうちどちらも有効制約条件の場合 2回目のイタレーションで最適解が見つかりました。 ・最適解x: [0.0, -1.0] ・目的関数f(x)の最小値: 1.0 ・KKT条件1(∇f+λ∇g=0): True [0.0, 0.0] ・KKT条件2(g<=0): True [0.0, 0.0] ・KKT条件3(λ>=0): True [1.0, 1.0] ・KKT条件4(λg=0): True [0.0, 0.0]
目的関数と制約関数を乱数で作成した場合
最後に、目的関数と制約関数を乱数で作成した場合を試してみました。
を乱数で作成しています。
以下スクリプトの実行結果です。一応KKT条件をすべて満たしているので、最適解は求まっているみたいです。
■目的関数と制約関数を乱数で作成した場合 1回目のイタレーションで最適解が見つかりました。 ・最適解x: [-44.55150263525623, -20.471794551317355] ・目的関数f(x)の最小値: 18.1186729545 ・KKT条件1(∇f+λ∇g=0): True [-3.885780586188048e-16, 2.220446049250313e-16] ・KKT条件2(g<=0): True [-44.92869339177389, -14.731499126102424] ・KKT条件3(λ>=0): True [0.0, 0.0] ・KKT条件4(λg=0): True [0.0, 0.0]
たまに1000回イタレーションループを回しても計算が収束しないときがあります。また、制約条件の数を増やしすぎると初期実行解が見つけられなくなるので、まだ工夫の余地はあるでしょうね。