読者です 読者をやめる 読者になる 読者になる

MyEnigma

とあるエンジニアのブログです。#Robotics #Programing #C++ #Python #MATLAB #Vim #Mathematics #Book #Movie #Traveling #Mac #iPhone

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

ゼロから学ぶ解析力学 (ゼロから学ぶシリーズ)

ゼロから学ぶ解析力学 (ゼロから学ぶシリーズ)

 

目次

はじめに

非線形最適化は、

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

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

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

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

よく使用されるのが、

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

 

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

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

 

今回は、

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

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

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

 

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

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

拘束条件がある中で、

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

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

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

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

 

ここで、

最小化したい評価関数をf(x,y)

拘束条件をg(x,y)=0とすると、

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

下記のような、

拘束条件無しの評価関数F(x,y,λ)に変更することができます。

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

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

一つ乗数を追加します。

 

そして、上記の式において、

下記の式を満たすx,yが停留点の条件になり、

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

f:id:meison_amsl:20160505212550p:plain

 

例題

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

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

評価関数を

とし、

拘束条件を、

とした状態で、

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

具体的な計算は、

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

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

myenigma.hatenablog.com

 

下記が計算結果です。

f:id:meison_amsl:20160505213228p:plain

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

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

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

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

f:id:meison_amsl:20160505213731p:plain

 

参考資料

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

ゼロから学ぶ解析力学 (ゼロから学ぶシリーズ)

ゼロから学ぶ解析力学 (ゼロから学ぶシリーズ)