Method of Lagrange Multiplier

Lagrange.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Method of Lagrange Multiplier\n",
    "- http://marupeke296.com/oxmath_no2_lagurangemult.html\n",
    "- https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E3%81%AE%E6%9C%AA%E5%AE%9A%E4%B9%97%E6%95%B0%E6%B3%95\n",
    "\n",
    "ラグランジュの未定乗数法について書く。まず、それが何か、ということ。  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "ラグランジュの未定乗数法は、ある制約条件のもとで関数の極値を求める最適化の方法である。\n",
       "つまり、制約条件$$g(x)=0$$が与えられた時の$$f(x)$$の極値を求める。\n",
       "<br><br>\n",
       "具体的な例で考えてみる。二変数関数$$f(x,y) = x + y$$を考える。<br>\n",
       "ここで、この関数の極値の候補を洗い出すために、各変数で偏微分する。<br><br>\n",
       "$$\\frac{\\partial f(x,y)}{\\partial x} = 1$$<br>\n",
       "$$\\frac{\\partial f(x,y)}{\\partial y} = 1$$<br><br>\n",
       "上記のように、この関数の各変数での偏微分は定数なので、この関数は極値を持たない。<br>\n",
       "ここで、以下のような制約条件($$x, y$$を半径1の円上に制約する)を加える。<br><br>\n",
       "$$g(x,y)=x^2+y^2-1=0$$<br><br>\n",
       "ラグランジュの未定乗数法では、元の関数fと、制約条件を表す関数gから以下のような式を作る。<br><br>\n",
       "$$F(\\lambda, x, y) = f(x, y) - \\lambda g(x, y)$$<br><br>\n",
       "\n",
       "そして、この関数Fを全ての変数で偏微分した式が全て0と置く。<br><br>\n",
       "$$\\frac{\\partial F}{\\partial \\lambda} = -g(x,y)\n",
       "= -x^2-y^2+1 = 0$$<br>\n",
       "$$\\frac{\\partial F}{\\partial x} = \\frac{\\partial f}{\\partial x} - \\lambda \\frac{\\partial g}{\\partial x}\n",
       "= 1 - 2\\lambda x = 0$$<br>\n",
       "$$\\frac{\\partial F}{\\partial y} = \\frac{\\partial f}{\\partial y} - \\lambda \\frac{\\partial g}{\\partial y}\n",
       "= 1 - 2\\lambda y = 0$$<br><br>\n",
       "\n",
       "この三つの連立方程式の解が、制約条件gのもとでの関数fの極値である。<br><br>\n",
       "$$x = y = \\frac{1}{2\\lambda}$$<br>\n",
       "$$(\\frac{1}{2\\lambda})^2+(\\frac{1}{2\\lambda})^2-1=0$$<br>\n",
       "より、$$\\lambda=\\pm\\frac{\\sqrt{2}}{2}$$<br>\n",
       "さらに代入して、$$x=y=\\pm\\frac{\\sqrt{2}}{2}$$<br><br>\n",
       "\n",
       "これが制約条件gのもとでの関数fの極値である。"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%latex\n",
    "ラグランジュの未定乗数法は、ある制約条件のもとで関数の極値を求める最適化の方法である。\n",
    "つまり、制約条件$$g(x)=0$$が与えられた時の$$f(x)$$の極値を求める。\n",
    "<br><br>\n",
    "具体的な例で考えてみる。二変数関数$$f(x,y) = x + y$$を考える。<br>\n",
    "ここで、この関数の極値の候補を洗い出すために、各変数で偏微分する。<br><br>\n",
    "$$\\frac{\\partial f(x,y)}{\\partial x} = 1$$<br>\n",
    "$$\\frac{\\partial f(x,y)}{\\partial y} = 1$$<br><br>\n",
    "上記のように、この関数の各変数での偏微分は定数なので、この関数は極値を持たない。<br>\n",
    "ここで、以下のような制約条件($$x, y$$を半径1の円上に制約する)を加える。<br><br>\n",
    "$$g(x,y)=x^2+y^2-1=0$$<br><br>\n",
    "ラグランジュの未定乗数法では、元の関数fと、制約条件を表す関数gから以下のような式を作る。<br><br>\n",
    "$$F(\\lambda, x, y) = f(x, y) - \\lambda g(x, y)$$<br><br>\n",
    "\n",
    "そして、この関数Fを全ての変数で偏微分した式が全て0と置く。<br><br>\n",
    "$$\\frac{\\partial F}{\\partial \\lambda} = -g(x,y)\n",
    "= -x^2-y^2+1 = 0$$<br>\n",
    "$$\\frac{\\partial F}{\\partial x} = \\frac{\\partial f}{\\partial x} - \\lambda \\frac{\\partial g}{\\partial x}\n",
    "= 1 - 2\\lambda x = 0$$<br>\n",
    "$$\\frac{\\partial F}{\\partial y} = \\frac{\\partial f}{\\partial y} - \\lambda \\frac{\\partial g}{\\partial y}\n",
    "= 1 - 2\\lambda y = 0$$<br><br>\n",
    "\n",
    "この三つの連立方程式の解が、制約条件gのもとでの関数fの極値である。<br><br>\n",
    "$$x = y = \\frac{1}{2\\lambda}$$<br>\n",
    "$$(\\frac{1}{2\\lambda})^2+(\\frac{1}{2\\lambda})^2-1=0$$<br>\n",
    "より、$$\\lambda=\\pm\\frac{\\sqrt{2}}{2}$$<br>\n",
    "さらに代入して、$$x=y=\\pm\\frac{\\sqrt{2}}{2}$$<br><br>\n",
    "\n",
    "これが制約条件gのもとでの関数fの極値である。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "一般化して、ラグランジュの未定乗数法はn個の変数を持つ関数fとm個の制約条件gに対しても同様に成り立つ。\n",
       "具体的には以下である。<br><br>\n",
       "n次元空間上の点x=($$x_1,x_2,...,x_n$$)にについて、m個の制約条件の下での関数f(x)の極値を求める。<br>\n",
       "ここで、m個の制約条件は以下のm次元ベクトル値関数で表される。<br><br>\n",
       "$$G(x) = \\left(\n",
       "    \\begin{array}{cccc}\n",
       "      g_1(x_1,x_2,...,x_n) \\\\\n",
       "      g_2(x_1,x_2,...,x_n) \\\\\n",
       "      ... \\\\\n",
       "      g_m(x_1,x_2,...,x_n)\n",
       "    \\end{array}\n",
       "  \\right) = 0$$<br><br>\n",
       "この制約条件Gのもとでの関数fの極値は以下の関数Fを各λ,xで偏微分した連立方程式の解である。<br><br>\n",
       "$$F(\\lambda_1, \\lambda_2, ..., \\lambda_m, x_1, x_2, ..., x_n)\n",
       "= f(x) - \\sum_{i=1}^m \\lambda_i g_i(x)$$"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%latex\n",
    "一般化して、ラグランジュの未定乗数法はn個の変数を持つ関数fとm個の制約条件gに対しても同様に成り立つ。\n",
    "具体的には以下である。<br><br>\n",
    "n次元空間上の点x=($$x_1,x_2,...,x_n$$)にについて、m個の制約条件の下での関数f(x)の極値を求める。<br>\n",
    "ここで、m個の制約条件は以下のm次元ベクトル値関数で表される。<br><br>\n",
    "$$G(x) = \\left(\n",
    "    \\begin{array}{cccc}\n",
    "      g_1(x_1,x_2,...,x_n) \\\\\n",
    "      g_2(x_1,x_2,...,x_n) \\\\\n",
    "      ... \\\\\n",
    "      g_m(x_1,x_2,...,x_n)\n",
    "    \\end{array}\n",
    "  \\right) = 0$$<br><br>\n",
    "この制約条件Gのもとでの関数fの極値は以下の関数Fを各λ,xで偏微分した連立方程式の解である。<br><br>\n",
    "$$F(\\lambda_1, \\lambda_2, ..., \\lambda_m, x_1, x_2, ..., x_n)\n",
    "= f(x) - \\sum_{i=1}^m \\lambda_i g_i(x)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "では、なぜこのラグランジュの未定乗数法で極値が求まるのだろうか？<br>\n",
       "ここ(http://marupeke296.com/oxmath_no2_lagurangemult.html)の説明が非常にわかりやすいが、要約すると、\n",
       "<b>関数$$f(x_1,x_2,...,x_n)$$の勾配ベクトルと制約を表す関数$$g(x_1,x_2,...,x_n)$$\n",
       "の勾配ベクトルが平行になる点が停留点=極値(の候補)である</b>からだ。<br><br>\n",
       "まず勾配ベクトルとは、ある関数(例えば$$f(x)=x^2$$という放物線)の各点において、f(x)の値を大きくする方向のこと。\n",
       "例えば、上記の放物線において、f(1)=1, f(2)=4,...であり、x=1の点においては、xをプラス方向に動かすとf(x)\n",
       "の値が大きくなる。つまりここでの勾配の方向はx軸におけるプラス方向である。また、x=1においてプラス方向に少しxを\n",
       "動かした場合よりも、x=5の時点でプラス方向に同じ大きさだけxを動かした方がf(x)の増加量は大きくなる。勾配ベクトルの\n",
       "長さはこの増加量である。<br><br>\n",
       "\n",
       "複数変数の場合も同様である。例えば、二変数関数$$f(x,y)=x^2+y^2$$の勾配ベクトルはX軸とY軸でその方向を表される。\n",
       "各変数を微小量動かすことでその地点の勾配がわかることから、x,yそれぞれの偏微分が勾配ベクトルの各成分となる。\n",
       "<br><br>\n",
       "\n",
       "ここで、上の\"<b>関数$$f(x_1,x_2,...,x_n)$$の勾配ベクトルと制約を表す関数$$g(x_1,x_2,...,x_n)$$\n",
       "の勾配ベクトルが平行になる点が停留点=極値(の候補)である</b>\"というステートメントに戻る。\n",
       "何を言っているのか？<br>\n",
       "これは、例えば何らかの関数を最小化したい場合、先ほどの勾配ベクトルの考え方(勾配ベクトルは関数の値を大きくする方向)\n",
       "から、勾配ベクトルと反対側に変数を動かしていくことになる。ここで、何の制約もなくf(x)上を動けるとしたら、\n",
       "ただただ勾配の小さい方へ動いていけばよい。が、変数の動ける範囲がある制約g(x)=0に制限されている場合は、その上で\n",
       "しか動くことができない。<br>\n",
       "ここで、f(x)上かつg(x)上のある点xでf(x)の勾配の小さい方向へ動いていこうとすると考える。制約なしならその点に\n",
       "おけるf(x)の勾配ベクトルの正反対方向が動くべき方向である。が、制約があることにより直接その方向へ動けない。\n",
       "いま動ける方向は、点xにおけるg(x)の接線方向のみである。今、点xにおけるf(x)の勾配ベクトル(の正反対方向)と、g(x)\n",
       "の接線方向が完全に垂直ではないとき、接線のどちらかの方向は勾配ベクトル(の正反対方向)のある成分であるので、\n",
       "そちらに動けばf(x)の値は小さくなるはずである。<br>\n",
       "が、もしその点xにおいてg(x)の接線がf(x)の勾配ベクトルと垂直であったなら、その点xからg(x)上に動ける接線方向の\n",
       "いずれに動いてもf(x)の値は小さくならないことになる。つまりそこが停留点である。<br>\n",
       "そして<b>接線は勾配ベクトルに垂直である</b>ということを考えると、\n",
       "g(x)の接線がf(x)の勾配ベクトルに垂直であるということは、f(x)の勾配ベクトルとg(x)の勾配ベクトルが\n",
       "平行であることを意味する。つまりこれが、上のステートメントの意味である。"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%latex\n",
    "では、なぜこのラグランジュの未定乗数法で極値が求まるのだろうか？<br>\n",
    "ここ(http://marupeke296.com/oxmath_no2_lagurangemult.html)の説明が非常にわかりやすいが、要約すると、\n",
    "<b>関数$$f(x_1,x_2,...,x_n)$$の勾配ベクトルと制約を表す関数$$g(x_1,x_2,...,x_n)$$\n",
    "の勾配ベクトルが平行になる点が停留点=極値(の候補)である</b>からだ。<br><br>\n",
    "まず勾配ベクトルとは、ある関数(例えば$$f(x)=x^2$$という放物線)の各点において、f(x)の値を大きくする方向のこと。\n",
    "例えば、上記の放物線において、f(1)=1, f(2)=4,...であり、x=1の点においては、xをプラス方向に動かすとf(x)\n",
    "の値が大きくなる。つまりここでの勾配の方向はx軸におけるプラス方向である。また、x=1においてプラス方向に少しxを\n",
    "動かした場合よりも、x=5の時点でプラス方向に同じ大きさだけxを動かした方がf(x)の増加量は大きくなる。勾配ベクトルの\n",
    "長さはこの増加量である。<br><br>\n",
    "\n",
    "複数変数の場合も同様である。例えば、二変数関数$$f(x,y)=x^2+y^2$$の勾配ベクトルはX軸とY軸でその方向を表される。\n",
    "各変数を微小量動かすことでその地点の勾配がわかることから、x,yそれぞれの偏微分が勾配ベクトルの各成分となる。\n",
    "<br><br>\n",
    "\n",
    "ここで、上の\"<b>関数$$f(x_1,x_2,...,x_n)$$の勾配ベクトルと制約を表す関数$$g(x_1,x_2,...,x_n)$$\n",
    "の勾配ベクトルが平行になる点が停留点=極値(の候補)である</b>\"というステートメントに戻る。\n",
    "何を言っているのか？<br>\n",
    "これは、例えば何らかの関数を最小化したい場合、先ほどの勾配ベクトルの考え方(勾配ベクトルは関数の値を大きくする方向)\n",
    "から、勾配ベクトルと反対側に変数を動かしていくことになる。ここで、何の制約もなくf(x)上を動けるとしたら、\n",
    "ただただ勾配の小さい方へ動いていけばよい。が、変数の動ける範囲がある制約g(x)=0に制限されている場合は、その上で\n",
    "しか動くことができない。<br>\n",
    "ここで、f(x)上かつg(x)上のある点xでf(x)の勾配の小さい方向へ動いていこうとすると考える。制約なしならその点に\n",
    "おけるf(x)の勾配ベクトルの正反対方向が動くべき方向である。が、制約があることにより直接その方向へ動けない。\n",
    "いま動ける方向は、点xにおけるg(x)の接線方向のみである。今、点xにおけるf(x)の勾配ベクトル(の正反対方向)と、g(x)\n",
    "の接線方向が完全に垂直ではないとき、接線のどちらかの方向は勾配ベクトル(の正反対方向)のある成分であるので、\n",
    "そちらに動けばf(x)の値は小さくなるはずである。<br>\n",
    "が、もしその点xにおいてg(x)の接線がf(x)の勾配ベクトルと垂直であったなら、その点xからg(x)上に動ける接線方向の\n",
    "いずれに動いてもf(x)の値は小さくならないことになる。つまりそこが停留点である。<br>\n",
    "そして<b>接線は勾配ベクトルに垂直である</b>ということを考えると、\n",
    "g(x)の接線がf(x)の勾配ベクトルに垂直であるということは、f(x)の勾配ベクトルとg(x)の勾配ベクトルが\n",
    "平行であることを意味する。つまりこれが、上のステートメントの意味である。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "ではこの\"関数$$f(x_1,x_2,...,x_n)$$の勾配ベクトルと制約を表す関数$$g(x_1,x_2,...,x_n)$$\n",
       "の勾配ベクトルが平行になる点が停留点=極値(の候補)である\"というステートメントはどのように\n",
       "ラグランジュの未定乗数法につながるのだろうか。<br><br>\n",
       "\n",
       "わかりやすさのため、f(x,y), g(x,y)の二変数の場合について考える。<br>\n",
       "まず、二つのベクトル$$v_1,v_2$$が平行である、というのは以下のように表される。<br><br>\n",
       "$$v_1=\\lambda v_2$$<br><br>\n",
       "ここで、f(x,y)の勾配ベクトル$$\\nabla f$$とg(x,y)の勾配ベクトル$$\\nabla g$$は、\n",
       "それぞれ偏微分を各成分とした以下のように表される。<br><br>\n",
       "$$\\nabla f = (\\frac{\\partial f}{\\partial x},\\frac{\\partial f}{\\partial y})$$<br>\n",
       "$$\\nabla g = (\\frac{\\partial g}{\\partial x},\\frac{\\partial g}{\\partial y})$$<br><br>\n",
       "\n",
       "停留点でこの二つのベクトルが平行というのは、つまり以下である。<br><br>\n",
       "$$\\nabla f = \\lambda \\nabla g$$<br><br>\n",
       "これを各成分ごとにかくと以下になる。<br><br>\n",
       "$$\\frac{\\partial f}{\\partial x} = \\lambda \\frac{\\partial g}{\\partial x}$$<br>\n",
       "$$\\frac{\\partial f}{\\partial y} = \\lambda \\frac{\\partial g}{\\partial y}$$<br><br>\n",
       "右辺を移行すると以下。<br><br>\n",
       "$$\\frac{\\partial f}{\\partial x} - \\lambda \\frac{\\partial g}{\\partial x} = 0$$<br>\n",
       "$$\\frac{\\partial f}{\\partial y} - \\lambda \\frac{\\partial g}{\\partial y} = 0$$<br><br>\n",
       "上の二式は、もっと上のラグランジュの未定乗数法の説明の偏微分ででてきた式と全く同じ式である。\n",
       "そして、x,yは制約条件g(x,y)=0の範囲でしか動けない、という条件は、\n",
       "以下の関数Fをλで偏微分したその下の式で表されている。<br><br>\n",
       "$$F(\\lambda, x, y) = f(x, y) - \\lambda g(x, y)$$<br>\n",
       "$$\\frac{\\partial F}{\\partial \\lambda} = -g(x,y) = 0$$"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%latex\n",
    "ではこの\"関数$$f(x_1,x_2,...,x_n)$$の勾配ベクトルと制約を表す関数$$g(x_1,x_2,...,x_n)$$\n",
    "の勾配ベクトルが平行になる点が停留点=極値(の候補)である\"というステートメントはどのように\n",
    "ラグランジュの未定乗数法につながるのだろうか。<br><br>\n",
    "\n",
    "わかりやすさのため、f(x,y), g(x,y)の二変数の場合について考える。<br>\n",
    "まず、二つのベクトル$$v_1,v_2$$が平行である、というのは以下のように表される。<br><br>\n",
    "$$v_1=\\lambda v_2$$<br><br>\n",
    "ここで、f(x,y)の勾配ベクトル$$\\nabla f$$とg(x,y)の勾配ベクトル$$\\nabla g$$は、\n",
    "それぞれ偏微分を各成分とした以下のように表される。<br><br>\n",
    "$$\\nabla f = (\\frac{\\partial f}{\\partial x},\\frac{\\partial f}{\\partial y})$$<br>\n",
    "$$\\nabla g = (\\frac{\\partial g}{\\partial x},\\frac{\\partial g}{\\partial y})$$<br><br>\n",
    "\n",
    "停留点でこの二つのベクトルが平行というのは、つまり以下である。<br><br>\n",
    "$$\\nabla f = \\lambda \\nabla g$$<br><br>\n",
    "これを各成分ごとにかくと以下になる。<br><br>\n",
    "$$\\frac{\\partial f}{\\partial x} = \\lambda \\frac{\\partial g}{\\partial x}$$<br>\n",
    "$$\\frac{\\partial f}{\\partial y} = \\lambda \\frac{\\partial g}{\\partial y}$$<br><br>\n",
    "右辺を移行すると以下。<br><br>\n",
    "$$\\frac{\\partial f}{\\partial x} - \\lambda \\frac{\\partial g}{\\partial x} = 0$$<br>\n",
    "$$\\frac{\\partial f}{\\partial y} - \\lambda \\frac{\\partial g}{\\partial y} = 0$$<br><br>\n",
    "上の二式は、もっと上のラグランジュの未定乗数法の説明の偏微分ででてきた式と全く同じ式である。\n",
    "そして、x,yは制約条件g(x,y)=0の範囲でしか動けない、という条件は、\n",
    "以下の関数Fをλで偏微分したその下の式で表されている。<br><br>\n",
    "$$F(\\lambda, x, y) = f(x, y) - \\lambda g(x, y)$$<br>\n",
    "$$\\frac{\\partial F}{\\partial \\lambda} = -g(x,y) = 0$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}