pythonで線形最適化問題を解いてみた



スポンサードリンク

pythonで線形最適化問題を解いたので記録しておきます。

参考にしたサイトはこちら。

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

関数の最適化問題を解くのに知っておかないといけないのは「ラグランジュの未定乗数法」です。

自然言語処理等の機械学習の分野ではこれを知るのと知らないのでは、論文の理解度も全く変わってくるそうです。

こちらの文献にも書いております。

 

条件

  • 目的関数(最適化したい関数)をf(x,y)とする
  • 制約条件(境界条件)をg(x,y)=0とする
  • \(\frac{\partial f}{\partial x}\neq 0\)
  • \(\frac{\partial f}{\partial y}\neq 0\)

の時、未定数\(\lambda\)を考えると以下が成り立つ。
\begin{eqnarray}
\left\{ \begin{array}{ll}
\frac{\partial f}{\partial x}+\lambda\frac{\partial g}{\partial x} = 0 \\
\frac{\partial f}{\partial y}+\lambda\frac{\partial g}{\partial y} = 0 \\
g(x,y) = 0
\end{array} \right.
\end{eqnarray}

以上の三式を満たす(x,y,\(\lambda\))を求める方法が「ラグランジュの未定乗数法」です。

そしてこれが制約条件の元での「最適解」ということです。

別途記事にして書こうと思いますが、この式はナイーブベイズやサポートヴェクターマシン等の最適問題を解く際に必須になる式です。

 

 



スポンサードリンク

pythonを用いて線形最適問題を解く。

pythonで線形計画問題を解く場合、pulpというライブラリを用います。非線形の場合は「open opt」というライブラリを用いるみたいです。今回はpulpの紹介のみで終わりにします。

まずはpulpをpipでインストール

今回の線形最適化問題を示します。

  • 目的関数 \(2x +3 y + 10\)
  • 制約条件 \( x + y = 0.5\)

以上の条件でpulpを用いて計算します。

problem で目的関数と制約条件を定義しています。problem.solve()で解きます。

実行結果

と結果が出ました。x = 0.5 ,y = 0 がどうやら最適解のようです。軽くラグランジュの未定乗数法の復習と、pulpの勉強ができました。
次は非線形問題の最適化についてpythonで勉強していきます。



スポンサードリンク

 

 

 

記事が役に立ったらシェア!

投稿者:

中村 俊

中村 俊

1993/09/04生まれ。機械系大学院を休学し、ベンチャーでインターンしている最中。直近では、デカルトの「方法序説」に感銘を受けた。 趣味:読書、web開発の勉強、異分野の論文読んだり、記事書いたり。 最終的には経営者か研究者になりたい。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA