2019-05-13

ラグランジュの未定乗数法を理解できた気がするのでまとめる

ラグランジュ(ラグランジェ)の未定乗数法は 一つ以上の束縛条件(制約関数)のもとで、目的関数の極値を求めるための最適化手法です。

制約条件が同値の場合にしか使えませんが、 KKT条件を用いることにより不等号を含む制約条件を扱えるようになります。

これについてはまた別の機会に記事にしたいと思います。

info
  • 同僚の Tsutomu Saito さんにレビューしていただきました。 斎藤さんだぞ!(これを言うのも最後かな..
  • ざっとみて違和感はないと言っていただきましたが、細かいところで変なこと書いてたら指摘ください。

手順

目的関数 f と 制約関数 g がある前提で話を進めます。 なお、この記事では考えやすいように 2変数関数の目的関数と制約関数を例に考えます。

この連立方程式をとけば、極値の座標が求められます。

考え方

なぜこのような手順で極値が求められるのかを考えてみましょう。

  • 目的関数 f(x, y) は 単なる2変数関数なので です
  • 制約関数 g(x, y) = 0線(直線または曲線) です
    • (関数の結果を Z軸とすると)制約関数の Z=0のXY平面 と交わっている部分です
    • この線というのが、x, y の定義域ということになります。

基本例題

線を面に沿って描画してみたのが以下です。

図を見ていただいてもうわかったかもしれませんが、 面と線が接している部分の底が今回求めたいポイントです。

info
  • 最後の図は 曲面を 等高線で表示してみました。次のセクションで使います。

式の意味

さて、ここからは式の意味を考えていきましょう。

一言で言うなら、求めるべき極値は 「 等高線接線 (接点)」です。 (もしくは共通の法線を持つ点)

等高線の 交点 は制約条件は満たしていますが 極値ではありません 。(上の図を見てもわかると思います)

info
  • 等高線とは同じ高さの座標(点)をつないだ線のことです。
  • 実は等高線というものは無数に書くことができますが、 それでは非常に見づらいので普通は切りの良い単位で間隔を設定します.
  • 今回は接している位置に等高線がくる感じになりました。(matplotlibが勝手にそのように描画してくれました)

つまり、接線の座標を求めれば良いのですね。では接線とはなんでしょうか?

接線 - Wikipedia より

曲線の接線(せっせん、英: tangent line, tangent)は、平面曲線に対しては、曲線上の一点が与えられたとき、その点において曲線に「ただ触れるだけ」の直線を意味する。ライプニッツは接線を、曲線上の無限に近い二点を通る直線として定義した[1]。 より具体的に解析幾何学において、与えられた直線が曲線 y = f(x) の x = c(あるいは曲線上の点 (c, f(c))における接線であるとは、その直線が曲線上の点 (c, f (c)) を通り、傾きが f の微分係数 f\'(c) に等しいときに言う。 同様の定義は空間曲線やより高次のユークリッド空間内の曲線に対しても適用できる。

曲線と接線が相接する点は接点 (point of tangency) と言い、曲線との接点において接線は曲線と「同じ方向へ」進む。 その意味において接線は、接点における曲線の最適直線近似である。

info
  • 等高線なので当然ですが、XY平面における傾きを指しています。
  • 簡単に言うと今回の3次元空間を上(Z方向)から覗き込んだ図です。

以下の 2条件を満たせば接線であるといえそうです。 それぞれの条件を表す3式も併せて記載します。これらを連立させて導いた座標が求めるべき座標となります。

等高線が平行

もう一方のベクトルのスカラー(λ)倍で表現できているので、これらは平行だと言えます。

未定乗数として定義した λ は目的関数と制約関数の接線倍率だったのですね

制約関数上に共有点を持つ

座標が離れていては接しているとは言えないので、共有点をもつ必要があります。

それぞれの変数で偏微分することでこれらを導くための方程式になるように 接線倍率である未定乗数(λ)を制約関数をかけていたわけです。

応用例題

これらを踏まえ問題を解いてみましょう。

info
  • 以下の問題は別のサイト様からお借りしました。私がごちゃごちゃ解説するよりもわかりやすいと思ったからです。

  • 載せたらまずいのがあったらお手数ですが、 問い合わせTwitterのDM まで連絡ください。

    詳しい解説はリンク先を参照ください。

長径2a,短径2bの楕円に内接する長方形の面積の最大値を求めよ.

引用元リンク

関数 f(x,y,z) = 8xyz の最大値を,条件 g(x,y,z) = x^2+y^2+z^2-1 = 0 のもとで求めよ。

引用元リンク

この例題では 目的関数と制約関数を明示的に与えてくれていますが、 図形的な意味でいうと前の例題と似ていて球体の中に収まる直方体の最大値を求める問題いうことになります。

直径1の円に内接する三角形の中で, その周の長さが最大のものを求めよ.

引用元リンク

なお、「面積」の最大を求める場合は 上記の結果に加えて ヘロンの公式を用いて解けます。 (ラグランジュの未定乗数法は使ってない

ヘロンの公式 - Wikipediahttps://ja.wikipedia.org/wiki/%E3%83%98%E3%83%AD%E3%83%B3%E3%81%AE%E5%85%AC%E5%BC%8F

ヘロンの公式(ヘロンのこうしき、英:Heron's formula)は任意の三角形の3辺a, b, c の長さから面積 S を求める公式。

info

x^2 +y^2 = 1 の条件のもとで,関数f(x,y)=x^3+y^3−3x−3yの最大値最小値を求めよ.

引用元リンク
info
  • ワイヤシュトラスの定理
  • D(空間や平面等)の集合 が R^n 実数からなるベクトル空間に属し、 有界閉集合 のとき、 D上の連続する多変数関数は必ず 最大値・最小値を持つという定理です。
  • ラグランジュの未定乗数法によって求められる値はあくまで極値の候補なので 本来はこれらの定理によって対象の問題が最大値(もしくは最小値)を持つことを保証してあげる必要があります。

おわりに

ふー、ようやく終わった

図形的に理解するのは少し難しかったかもしれませんが、 ラグランジュの未定乗数法を使うこと自体は割と簡単でしたね。

目的関数と制約関数をスムーズに作れるようになるには場数を踏むしかないんでしょう。

以上、おわり!閉廷!

参考