MyEnigma

とある自律移動システムエンジニアのブログです。#Robotics #Programing #C++ #Python #MATLAB #Vim #Mathematics #Book #Movie #Traveling #Mac #iPhone

ラグランジュの未定乗数法による等式制約付き非線形最適化の概要と例題


数学で考える経済学 いかにして問題を処理するか

 

目次

はじめに

非線形最適化は、

機械学習や、ロボット工学などで

非常に広く利用されますが、

単純な非線形最適化だけでなく、

変数などに制約を与えたい場合に

よく使用されるのが、

ラグランジュの未定乗数法です。

 

機械学習などでよく使用される

SVMなどにも使用されています。

 

今回は、

このラグランジュの未定乗数法の概要と、

具体的にラグランジュの未定乗数法で

最適化問題を解くPythonサンプルコードを紹介したいと思います。

 

ラグランジュの未定乗数法

ラグランジュの未定乗数法は、

拘束条件がある中で、

最適化を実現する手法です。

ラグランジュ乗数という新しい変数を導入することで、

拘束条件付きの最適化の評価関数を、

通常の拘束条件無しの最適化問題にすることができます。

 

ここで、

最小化したい評価関数を

f(x,y)

等式制約条件を

g(x,y)=0

とすると、

局所最適解の候補 x_o, y_oは下記のような2つの条件を満たすことになります。

 

この式は、下の式は元々の等式制約条件、

上の式は、f(x,y)の等高線と、g(x,y)=0の制約条件の線が接するところが

局所最適解であり、その点でのf(x_o, y_o)とg(x_o, y_o)の勾配ベクトルが互いに並行(λで補正すると一致する)

ということを意味しています。

上記を満たすx,yを制約付き停留点と呼び、これらが局所最適な点の候補となります。

 

続いて、下記のような

拘束条件無しの評価関数F(x,y,λ)を導入します。

この式はラグランジュ関数を呼ばれており、

λがラグランジュ乗数という値で、

拘束条件を一つ追加するにつれて、

一つ乗数を追加されるような値です。

 

そして、上記の式F(x,y,λ)において、

下記の式を満たすx,yが、実は前述の制約付き停留点の条件になります。

 

このラグランジュ関数を利用することで、

等式制約付きの最適化問題が、

一つ変数が増えた制約無しの最適化問題に変換することができるため、

通常の勾配法等で最適化を実施することができるようになります。

このように、等式制約付き最適化問題を、

ラグランジュ乗数により、制約無しの最適化問題に変換して解く方法を

ラグランジュの未定乗数法と呼びます。

 

ラグランジュの未定乗数法は等式制約付きの最適化問題用の方法ですが、

不等式制約に拡張すると、KKT条件(Karush-Kuhn-Tucker条件)というより

汎用的で広い範囲の制約付き最適化問題を、

制約無し最適化問題に変換することができます。

このあたりの説明はこちらの動画が

非常にわかりやすく説明しています。

www.youtube.com

 

例題

具体的にラグランジュの未定乗数法で

非線形最適化を実施してみます。

評価関数を

とし、

拘束条件を、

とした状態で、

ラグランジュの未定乗数法を使った最小化の点を計算してみました。

具体的な計算は、

以前紹介したsympyを使って、

微分や連立方程式の解などを実施してもらいました。

myenigma.hatenablog.com

 

下記が計算結果です。

ラグランジュ乗数が0以外で有効な解として(-1,-1)が計算されました。

上記の点と、拘束条件の直線、そして評価関数をグラフにしてみると、

確かに拘束条件を満たした状態で、

評価関数を最小化するパラメータが得られているようにみえます。

 

参考資料

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

MyEnigma Supporters

もしこの記事が参考になり、

ブログをサポートしたいと思われた方は、

こちらからよろしくお願いします。

https://gumroad.com/l/myenigmasupportersgumroad.com