Method to solve constrained optimization problems
数学的最適化 において 、 ラグランジュ乗数法は 、 方程式の制約（つまり、 変数 の選択された値が 1つ以上の 方程式 を正確に満たす必要があるという条件）のもとで 関数の 極大値と極小値 を見つける戦略である。 [1]この 法 は数学者 ジョゼフ＝ルイ・ラグランジュ にちなんで名付けられている。
要約と根拠 基本的な考え方は、制約付き問題を、制約なしの問題の微分検定が 適用できる形に変換することである 。関数の勾配と制約の勾配の関係は、むしろ自然に元の問題の再定式化を導き、 ラグランジアン関数 またはラグランジアンとして知られる。 [2] 一般的な場合、ラグランジアンは次のように定義される。
L ( x , λ ) ≡ f ( x ) + ⟨ λ , g ( x ) ⟩ {\displaystyle {\mathcal {L}}(x,\lambda )\equiv f(x)+\langle \lambda ,g(x)\rangle }
関数の場合 、表記は 内積 を表します 。この値は ラグランジュ乗数 と呼ばれます 。 f , g {\displaystyle f,g} ⟨ ⋅ , ⋅ ⟩ {\displaystyle \langle \cdot ,\cdot \rangle } λ {\displaystyle \lambda }
単純なケースでは、内積は ドット積 として定義され、ラグランジアンは
L ( x , λ ) ≡ f ( x ) + λ ⋅ g ( x ) {\displaystyle {\mathcal {L}}(x,\lambda )\equiv f(x)+\lambda \cdot g(x)}
この方法は次のように要約できる。等式制約 に従う 関数の最大値または最小値を求めるには 、 とラグランジュ乗数 の 関数として考えた場合 の の 停留点を 求める。これは、 に関する偏微分を含め、すべての 偏微分が ゼロになることを意味する 。 [3] f {\displaystyle f} g ( x ) = 0 {\displaystyle g(x)=0} L {\displaystyle {\mathcal {L}}} x {\displaystyle x} λ {\displaystyle \lambda ~} λ {\displaystyle \lambda ~}
∂ L ∂ x = 0 {\displaystyle {\frac {\partial {\mathcal {L}}}{\partial x}}=0} そして ∂ L ∂ λ = 0 ; {\displaystyle {\frac {\ \partial {\mathcal {L}}\ }{\partial \lambda }}=0\ ;} または同等
∂ f ( x ) ∂ x + λ ⋅ ∂ g ( x ) ∂ x = 0 {\displaystyle {\frac {\partial f(x)}{\partial x}}+\lambda \cdot {\frac {\partial g(x)}{\partial x}}=0} そして g ( x ) = 0 . {\displaystyle g(x)=0~.} 元の制約付き最適化 に対応する解は 常に ラグランジュ関数の 鞍点であり、 [4] [5] 境界付きヘッセ行列 の 定常性 から定常点の中で識別することができる 。 [6]
この手法の大きな利点は、制約条件を明示的に パラメータ化する ことなく最適化を解くことができることです。そのため、ラグランジュ乗数法は、制約条件付きの困難な最適化問題を解く際に広く用いられています。さらに、ラグランジュ乗数法は、 Karush–Kuhn–Tucker条件 によって一般化されており、与えられた定数 に対して の形の不等式制約も考慮に入れることができます 。 h ( x ) ≤ c {\displaystyle h(\mathbf {x} )\leq c} c {\displaystyle c}
声明 以下はラグランジュの乗数定理として知られています。 [7]
を目的 関数 、を 制約関数とします。これらは両方とも に属します （ つまり、連続した1次導関数を持ちます）。 を 次の最適化問題に対する最適解とし、偏導関数行列 に対して となるものとします 。 f : R n → R {\displaystyle f\colon \mathbb {R} ^{n}\to \mathbb {R} } g : R n → R c {\displaystyle g\colon \mathbb {R} ^{n}\to \mathbb {R} ^{c}} C 1 {\displaystyle C^{1}} x ⋆ {\displaystyle x_{\star }} [ D g ( x ⋆ ) ] j , k = ∂ g j ∂ x k {\displaystyle {\Bigl [}\operatorname {D} g(x_{\star }){\Bigr ]}_{j,k}={\frac {\ \partial g_{j}\ }{\partial x_{k}}}} rank ( D g ( x ⋆ ) ) = c ≤ n {\displaystyle \operatorname {rank} (\operatorname {D} g(x_{\star }))=c\leq n}
maximize f ( x ) subject to: g ( x ) = 0 {\displaystyle {\begin{aligned}&{\text{maximize }}f(x)\\&{\text{subject to: }}g(x)=0\end{aligned}}}
すると、次のよう な一意のラグランジュ乗数が存在します （この式では、 は列ベクトルなので、その転置は行 ベクトルです。あるいは、ラグランジュ乗数を行ベクトルとして直接再定義し、転置を回避することもできます）。 λ ⋆ ∈ R c {\displaystyle \lambda _{\star }\in \mathbb {R} ^{c}} D f ( x ⋆ ) = λ ⋆ T D g ( x ⋆ ) . {\displaystyle \operatorname {D} f(x_{\star })=\lambda _{\star }^{\mathsf {T}}\operatorname {D} g(x_{\star })~.} λ ⋆ {\displaystyle \lambda _{\star }} λ ⋆ T {\displaystyle \lambda _{\star }^{\mathsf {T}}}
ラグランジュの乗数定理は、等式制約の下で評価される関数の任意の局所的最大値（または最小値）において、制約条件が適用される場合（後述）、 関数の 勾配（その点）は、ラグランジュの乗数が 係数 として作用する制約（その点）の勾配の 線形結合 として表すことができることを述べています。 [8] これは、制約のすべての勾配に垂直な任意の方向は、関数の勾配にも垂直であると言うことと同等です。あるいは、関数の 方向微分はすべての実行可能な方向で 0 であると言うことに相当します 。
単一の制約 図1：赤い曲線は制約 g ( x , y ) = c を示しています。青い曲線は f ( x , y )の等高線です。赤い制約が青い等高線に接する点は、 d 1 > d 2 であるため、制約に沿った f ( x , y ) の最大値です 。 制約が 1 つだけ、選択変数が 2 つだけの場合 (図 1 に例示)、 最適化問題 を考えます
(加法定数は に含まれるのではなく 、別々に示されることがあります。その場合、制約は 図 1 のように記述されます)。 と は両方 とも 連続した第 1 偏導関数を持つと仮定します。 ラグランジュ乗数 (または ラグランジュ未定乗数 )と呼ばれる 新しい変数 ( )を導入し、 項 を加算または減算できる、によって定義される ラグランジュ関数 (または ラグランジュ式 、 ラグランジュ式 )
を調べます。 が元の制約付き問題に対して の最大値である場合、 が存在するので、 ( ) はラグランジュ関数 の 停留点 です(停留点とは、 の第 1 偏導関数が 0 である点です)。 この仮定は制約条件の適格性と呼ばれます。 ただし、ラグランジュ乗数の方法は、制約付き問題における最適性に対する 必要条件 のみをもたらすため、すべての停留点で元の問題の解が得られるわけではありません 。 [9] [10] [11] [12] [13] 最小値または最大値を得るための十分条件 も存在する が、特定の 候補解が十分条件を満たす場合、その解が 局所的に 最良であること 、つまり近傍の許容される点よりも優れていることが保証されるだけである。 大域的 最適値は、必要条件と局所的十分条件を満たす点における元の目的関数の値を比較することによって見つけることができる。 maximize x , y f ( x , y ) subject to g ( x , y ) = 0. {\displaystyle {\begin{aligned}{\underset {x,y}{\text{maximize}}}\quad &f(x,y)\\{\text{subject to}}\quad &g(x,y)=0.\end{aligned}}} g {\displaystyle g} g ( x , y ) = c , {\displaystyle g(x,y)=c,} f {\displaystyle f} g {\displaystyle g} λ {\displaystyle \lambda } L ( x , y , λ ) = f ( x , y ) + λ ⋅ g ( x , y ) , {\displaystyle {\mathcal {L}}(x,y,\lambda )=f(x,y)+\lambda \cdot g(x,y),} λ {\displaystyle \lambda } f ( x 0 , y 0 ) {\displaystyle f(x_{0},y_{0})} f ( x , y ) {\displaystyle f(x,y)} ∇ g ( x 0 , y 0 ) ≠ 0 , {\displaystyle \nabla g(x_{0},y_{0})\neq 0,} λ 0 {\displaystyle \lambda _{0}} x 0 , y 0 , λ 0 {\displaystyle x_{0},y_{0},\lambda _{0}} L {\displaystyle {\mathcal {L}}} ∇ g ≠ 0 {\displaystyle \nabla g\neq 0}
ラグランジュ乗数法は、最大値において、 f ( x , y )は g = 0 となる隣接点の方向には増加しないという直感に基づいています。もし増加するとすれば、 g = 0 に沿ってさらに増加していくことになり、開始点が実際には最大値ではなかったことになります。このように考えると、これは制約のない関数の微分が 0 か どうかをテストすることと全く同じです。 つまり、関連する（実行可能な）方向において方向微分が 0 であることを確認していることになります。
さまざまなd の値に対して f ( x , y ) = d で与えられる f の 輪郭と、 g ( x , y ) = c で与えられる g の輪郭 を視覚化できます 。
g = c の等高線に沿って歩くと仮定します 。 歩行中に f がほとんど変化しない点を見つけることに興味があります。これらの点は最大値となる可能性があるからです。
これが起こる原因は 2 つあります。
定義により、 f はその等高線に沿って歩いても変化しないので、 f の等高線に触れることができます。これは、 f と g の等高線への接線が ここで平行であることを意味します。 f の「レベル」部分に到達しました 。つまり、 f は どの方向にも変化しません。 最初の可能性（ f の等高線に触れる ）を確認するには、関数の 勾配が 等高線に垂直であるため、 f と gの等高線への接線が平行になるのは、 f と g の勾配が平行で
ある 場合のみであることに 留意
してください。したがって、 g ( x , y ) = c と なる点 （ x , y ） を求めます 。また、 はそれぞれの勾配です。2つの勾配ベクトルは平行ですが、勾配ベクトルの大きさは一般に等しくないため、定数 が必要です。この定数はラグランジュ乗数と呼ばれます（慣例によっては、 の 前にマイナス記号が付きます）。 ∇ x , y f = λ ∇ x , y g , {\displaystyle \nabla _{x,y}f=\lambda \,\nabla _{x,y}g,} λ {\displaystyle \lambda } ∇ x , y f = ( ∂ f ∂ x , ∂ f ∂ y ) , ∇ x , y g = ( ∂ g ∂ x , ∂ g ∂ y ) {\displaystyle \nabla _{x,y}f=\left({\frac {\partial f}{\partial x}},{\frac {\partial f}{\partial y}}\right),\qquad \nabla _{x,y}g=\left({\frac {\partial g}{\partial x}},{\frac {\partial g}{\partial y}}\right)} λ {\displaystyle \lambda } λ {\displaystyle \lambda }
この方法は、が レベルであるという 2 番目の可能性も解決することに注意してください 。 f がレベルの場合、その勾配はゼロであり、 に関係なく設定は解になります 。 λ = 0 {\displaystyle \lambda =0} ∇ x , y g {\displaystyle \nabla _{x,y}g}
これらの条件を一つの方程式に組み込むために、補助関数を導入し 、次の式を解きます 。これは、3つの未知数を持つ3つの方程式を解くことになることに注意してください。これがラグランジュ乗数法です。 L ( x , y , λ ) ≡ f ( x , y ) + λ ⋅ g ( x , y ) , {\displaystyle {\mathcal {L}}(x,y,\lambda )\equiv f(x,y)+\lambda \cdot g(x,y)\,,} ∇ x , y , λ L ( x , y , λ ) = 0 . {\displaystyle \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0~.}
の 偏 微分 は ∇ λ L ( x , y , λ ) = 0 {\displaystyle \ \nabla _{\lambda }{\mathcal {L}}(x,y,\lambda )=0\ } g ( x , y ) = 0 , {\displaystyle \ g(x,y)=0\ ,} L {\displaystyle {\mathcal {L}}} λ {\displaystyle \lambda } g ( x , y ) . {\displaystyle \ g(x,y)~.}
要約すると、
この方法は 変数の 関数に簡単に一般化でき、 n + 1 個の未知数を持つ n + 1 個の 方程式 を解くことになります 。 ∇ x , y , λ L ( x , y , λ ) = 0 ⟺ { ∇ x , y f ( x , y ) = − λ ∇ x , y g ( x , y ) g ( x , y ) = 0 {\displaystyle \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0\iff {\begin{cases}\nabla _{x,y}f(x,y)=-\lambda \,\nabla _{x,y}g(x,y)\\g(x,y)=0\end{cases}}} n {\displaystyle n} ∇ x 1 , … , x n , λ L ( x 1 , … , x n , λ ) = 0 {\displaystyle \nabla _{x_{1},\dots ,x_{n},\lambda }{\mathcal {L}}(x_{1},\dots ,x_{n},\lambda )=0}
f の制約付き極値は ラグランジアン の 臨界点 ですが、必ずしも の 局所的極値 ではありません (以下の § 例 2 を参照)。 L {\displaystyle {\mathcal {L}}} L {\displaystyle {\mathcal {L}}}
ラグランジアンを ハミルトニアン として再定式化する と 、解はハミルトニアンの局所最小値となる。これは 最適制御理論において、 ポンチャギンの最大値原理 の形で行われる 。
ラグランジュ乗数法の解が必ずしもラグランジアンの極値とは限らないという事実は、数値最適化において困難をもたらします。これは、ラグランジアンの勾配の 絶対値を 最小化することで解決できます。これらの最小値は、例5：数値最適化に示すように、絶対値の零点と同じだからです。
複数の制約 図 2: 交差する 2 本の線に沿って制約された放物面。 図3: 図2の等高線図。 ラグランジュの乗数法は、同様の議論を用いて、複数の制約条件を伴う問題を解くように拡張することができます。2 つの直線制約が 1 点で交差する 放物面を考えてみましょう。唯一の実行可能な解として、この点は明らかに制約付きの極値です。しかし、 の 水準集合 は 、交差点においてどちらの制約条件にも明らかに平行ではありません (図 3 を参照)。その代わりに、2 つの制約条件の勾配の線形結合になります。制約条件が複数ある場合、それが一般に私たちが求めるものになります。ラグランジュ法では、 の勾配が 必ずしもいずれかの単一の制約条件の勾配の倍数になる点ではなく、 の勾配がすべての制約条件の勾配の線形結合になる点を求めます。 f {\displaystyle f} f {\displaystyle f}
具体的には、制約条件があり 、 を満たす点の集合に沿って歩いているとします。 与えられた制約関数の輪郭上の すべての点 には、許容される方向の空間、 すなわち に垂直なベクトルの空間があります。すべての制約によって許容される方向の集合は、すべての制約の勾配に垂直な方向の空間です。この許容される移動の空間を で表し 、制約の勾配の範囲を で表します。 すると、 のすべての要素に垂直なベクトルの空間は M {\displaystyle M} g i ( x ) = 0 , i = 1 , … , M . {\displaystyle g_{i}(\mathbf {x} )=0,i=1,\dots ,M\,.} x {\displaystyle \mathbf {x} } g i {\displaystyle g_{i}} ∇ g i ( x ) . {\displaystyle \nabla g_{i}(\mathbf {x} )\,.} A {\displaystyle \ A\ } S . {\displaystyle S\,.} A = S ⊥ , {\displaystyle A=S^{\perp }\,,} S . {\displaystyle S\,.}
我々は依然として、歩行中に変化しない 点を見つけることに興味を持っています。なぜなら、これらの点は（制約された）極値である可能性があるからです。したがって、 から遠ざかるあらゆる許容方向が に垂直である ような点を探します （そうでなければ 、その許容方向に沿って移動することで が増加する可能性があります）。言い換えれば、と なる スカラーが存在するのです。 f {\displaystyle f} x {\displaystyle \mathbf {x} } x {\displaystyle \mathbf {x} } ∇ f ( x ) {\displaystyle \nabla f(\mathbf {x} )} f {\displaystyle f} ∇ f ( x ) ∈ A ⊥ = S . {\displaystyle \nabla f(\mathbf {x} )\in A^{\perp }=S\,.} λ 1 , λ 2 , … , λ M {\displaystyle \lambda _{1},\lambda _{2},\ \dots ,\lambda _{M}} ∇ f ( x ) = ∑ k = 1 M λ k ∇ g k ( x ) ⟺ ∇ f ( x ) − ∑ k = 1 M λ k ∇ g k ( x ) = 0 . {\displaystyle \nabla f(\mathbf {x} )=\sum _{k=1}^{M}\lambda _{k}\,\nabla g_{k}(\mathbf {x} )\quad \iff \quad \nabla f(\mathbf {x} )-\sum _{k=1}^{M}{\lambda _{k}\nabla g_{k}(\mathbf {x} )}=0~.}
これらのスカラーはラグランジュ乗数です。これで 、制約条件ごとに1つずつ、ラグランジュ乗数ができました。 M {\displaystyle M}
前と同様に、補助関数を導入して 、
未知数 を含む方程式 を解くことを解決します 。 L ( x 1 , … , x n , λ 1 , … , λ M ) = f ( x 1 , … , x n ) − ∑ k = 1 M λ k g k ( x 1 , … , x n ) {\displaystyle {\mathcal {L}}\left(x_{1},\ldots ,x_{n},\lambda _{1},\ldots ,\lambda _{M}\right)=f\left(x_{1},\ldots ,x_{n}\right)-\sum \limits _{k=1}^{M}{\lambda _{k}g_{k}\left(x_{1},\ldots ,x_{n}\right)}\ } ∇ x 1 , … , x n , λ 1 , … , λ M L ( x 1 , … , x n , λ 1 , … , λ M ) = 0 ⟺ { ∇ f ( x ) − ∑ k = 1 M λ k ∇ g k ( x ) = 0 g 1 ( x ) = ⋯ = g M ( x ) = 0 {\displaystyle \nabla _{x_{1},\ldots ,x_{n},\lambda _{1},\ldots ,\lambda _{M}}{\mathcal {L}}(x_{1},\ldots ,x_{n},\lambda _{1},\ldots ,\lambda _{M})=0\iff {\begin{cases}\nabla f(\mathbf {x} )-\sum _{k=1}^{M}{\lambda _{k}\,\nabla g_{k}(\mathbf {x} )}=0\\g_{1}(\mathbf {x} )=\cdots =g_{M}(\mathbf {x} )=0\end{cases}}} n + M {\displaystyle n+M} n + M {\displaystyle \ n+M\ }
複数の制約がある場合の制約適格性の仮定は、関連するポイントでの制約勾配が線形に独立していることです。
制約条件の下で極大値と極小値を求める問題は、微分 可能多様体 [14] 上の極大値と極小値を求める問題に一般化できる。以下では、多様体 がユークリッド空間である必要はなく、 リーマン多様体 である必要もない。勾配 （リーマン計量の選択に依存する）の出現はすべて、 外微分に置き換えることができる。 M . {\displaystyle \ M~.} M {\displaystyle M} ∇ {\displaystyle \ \nabla \ } d . {\displaystyle \ \operatorname {d} ~.}
単一の制約 を 次元の 滑らかな多様体 とします。 が 0 が正規 の値 である滑らかな関数で ある によって定義される 部分多様体に制限されたときに、 滑らかな関数の 停留点を見つけたいとします 。 M {\displaystyle \ M\ } m . {\displaystyle \ m~.} x {\displaystyle \ x\ } f : M → R {\displaystyle \ f:M\to \mathbb {R} \ } N {\displaystyle \ N\ } g ( x ) = 0 , {\displaystyle \ g(x)=0\ ,} g : M → R {\displaystyle \ g:M\to \mathbb {R} \ }
と を、 および の 外微分 とする。 における 制約の定常性は、を意味する。 同値 に、核は を含む。 言い換えれば、 およびは 比例1形式である。そのためには、以下の 連立方程式が成立することが必要かつ十分である。 ここで、は 外積 を表す 。定常点 は、上記の連立方程式の解に制約を加えたものである。 方程式の左辺は、 分解可能な要素 からなるの部分多様体 に属するため、これらの方程式は独立ではない ことに注意されたい 。 d f {\displaystyle \ \operatorname {d} f\ } d g {\displaystyle \ \operatorname {d} g\ } f {\displaystyle \ f\ } g {\displaystyle \ g\ } f | N {\displaystyle \ f|_{N}\ } x ∈ N {\displaystyle \ x\in N\ } d ( f | N ) x = 0 . {\displaystyle \ \operatorname {d} (f|_{N})_{x}=0~.} ker ( d f x ) {\displaystyle \ \ker(\operatorname {d} f_{x})\ } T x N = ker ( d g x ) . {\displaystyle \ T_{x}N=\ker(\operatorname {d} g_{x})~.} d f x {\displaystyle \ \operatorname {d} f_{x}\ } d g x {\displaystyle \ \operatorname {d} g_{x}\ } 1 2 m ( m − 1 ) {\displaystyle \ {\tfrac {1}{2}}m(m-1)\ } d f x ∧ d g x = 0 ∈ Λ 2 ( T x ∗ M ) {\displaystyle \operatorname {d} f_{x}\wedge \operatorname {d} g_{x}=0\in \Lambda ^{2}(T_{x}^{\ast }M)} ∧ {\displaystyle \ \wedge \ } x {\displaystyle \ x\ } g ( x ) = 0 . {\displaystyle \ g(x)=0~.} 1 2 m ( m − 1 ) {\displaystyle \ {\tfrac {1}{2}}m(m-1)\ } Λ 2 ( T x ∗ M ) {\displaystyle \ \Lambda ^{2}(T_{x}^{\ast }M)\ }
この定式化では、ラグランジュ乗数、 つまり λ {\displaystyle \ \lambda \ } d f x = λ ⋅ d g x . {\displaystyle \ \operatorname {d} f_{x}=\lambda \cdot \operatorname {d} g_{x}~.}
複数の制約 と を、 上記の単一制約の場合のセクションと同様にします。そこで説明した関数ではなく、 が 正規値 である ような 成分関数を持つ 滑らかな関数を考えます 。 を の部分多様体 とします。 M {\displaystyle \ M\ } f {\displaystyle \ f\ } g {\displaystyle g} G : M → R p ( p > 1 ) , {\displaystyle \ G:M\to \mathbb {R} ^{p}(p>1)\ ,} g i : M → R , {\displaystyle \ g_{i}:M\to \mathbb {R} \ ,} 0 ∈ R p {\displaystyle 0\in \mathbb {R} ^{p}} N {\displaystyle N} M {\displaystyle \ M\ } G ( x ) = 0 . {\displaystyle \ G(x)=0~.}
x {\displaystyle \ x\ } が の停留点である場合、かつ が含まれる 場合に限る。 便宜上、 ととする。 ここで は 接写像またはヤコビアンを表す （は と 正準に同一視できる ）。 部分空間の 次元は の次元よりも小さく 、すなわち が に属し 、 かつ が の像に属する場合に限る 。 計算的に言えば、条件は が の行列の行空間、 あるいはそれと同値な の行列の列空間 （転置行列）に属することである。 が の行列の列の外積を表す場合 、 における の 停留条件は となる 。ここでも、この定式化では、ラグランジュ乗数、 すなわち f | N {\displaystyle f|_{N}} ker ( d f x ) {\displaystyle \ \ker(\operatorname {d} f_{x})\ } ker ( d G x ) . {\displaystyle \ \ker(\operatorname {d} G_{x})~.} L x = d f x {\displaystyle \ L_{x}=\operatorname {d} f_{x}\ } K x = d G x , {\displaystyle \ K_{x}=\operatorname {d} G_{x}\ ,} d G {\displaystyle \ \operatorname {d} G} T M → T R p {\displaystyle \ TM\to T\mathbb {R} ^{p}~} T x R p {\displaystyle \ T_{x}\mathbb {R} ^{p}} R p {\displaystyle \ \mathbb {R} ^{p}} ker ( K x ) {\displaystyle \ker(K_{x})} ker ( L x ) {\displaystyle \ker(L_{x})} dim ( ker ( L x ) ) = n − 1 {\displaystyle \ \dim(\ker(L_{x}))=n-1\ } dim ( ker ( K x ) ) = n − p . {\displaystyle \ \dim(\ker(K_{x}))=n-p~.} ker ( K x ) {\displaystyle \ker(K_{x})} ker ( L x ) {\displaystyle \ \ker(L_{x})\ } L x ∈ T x ∗ M {\displaystyle L_{x}\in T_{x}^{\ast }M} K x ∗ : R p ∗ → T x ∗ M . {\displaystyle \ K_{x}^{\ast }:\mathbb {R} ^{p\ast }\to T_{x}^{\ast }M~.} L x {\displaystyle L_{x}} K x , {\displaystyle \ K_{x}\ ,} K x ∗ {\displaystyle K_{x}^{\ast }} ω x ∈ Λ p ( T x ∗ M ) {\displaystyle \ \omega _{x}\in \Lambda ^{p}(T_{x}^{\ast }M)\ } K x ∗ , {\displaystyle \ K_{x}^{\ast }\ ,} f | N {\displaystyle \ f|_{N}\ } x {\displaystyle \ x\ } L x ∧ ω x = 0 ∈ Λ p + 1 ( T x ∗ M ) {\displaystyle L_{x}\wedge \omega _{x}=0\in \Lambda ^{p+1}\left(T_{x}^{\ast }M\right)} λ 1 , … , λ p {\displaystyle \ \lambda _{1},\ldots ,\lambda _{p}\ } d f x = ∑ i = 1 p λ i d ( g i ) x . {\displaystyle \ \operatorname {d} f_{x}=\sum _{i=1}^{p}\lambda _{i}\operatorname {d} (g_{i})_{x}~.}
ラグランジュ乗数の解釈 このセクションでは、制約方程式を 形式から 形式に変更します。 ここで、 は m 個の実定数であり 、ラグランジアン表現 の追加引数として考えられます 。 g i ( x ) = 0 {\displaystyle g_{i}({\bf {x}})=0} g i ( x ) = c i , {\displaystyle \ g_{i}({\bf {x}})=c_{i}\ ,} c i {\displaystyle \ c_{i}\ } L {\displaystyle {\mathcal {L}}}
ラグランジュ乗数は、しばしば何らかの興味深い量として解釈されます。例えば、制約条件の等高線をパラメータ化することにより、つまりラグランジュ表現 が L ( x 1 , x 2 , … ; λ 1 , λ 2 , … ; c 1 , c 2 , … ) = f ( x 1 , x 2 , … ) + λ 1 ( c 1 − g 1 ( x 1 , x 2 , … ) ) + λ 2 ( c 2 − g 2 ( x 1 , x 2 , … ) ) + ⋯ {\displaystyle {\begin{aligned}&{\mathcal {L}}(x_{1},x_{2},\ldots ;\lambda _{1},\lambda _{2},\ldots ;c_{1},c_{2},\ldots )\\[4pt]={}&f(x_{1},x_{2},\ldots )+\lambda _{1}(c_{1}-g_{1}(x_{1},x_{2},\ldots ))+\lambda _{2}(c_{2}-g_{2}(x_{1},x_{2},\dots ))+\cdots \end{aligned}}} ∂ L ∂ c k = λ k . {\displaystyle \ {\frac {\partial {\mathcal {L}}}{\partial c_{k}}}=\lambda _{k}~.}
したがって、 λ k は、制約パラメータの関数として最適化される量の変化率です。例えば、 ラグランジュ力学 では、運動方程式は、 作用 （運動エネルギーと位置エネルギーの差の時間積分）の停留点を見つけることによって導出されます。したがって、スカラーポテンシャルによる粒子への力 F = −∇ V は、粒子の制約軌道の変化に伴う作用（位置エネルギーから運動エネルギーへの変換）の変化を決定するラグランジュ乗数として解釈できます。制御理論では、これは代わりに 共線方程式 として定式化されます。
さらに、 包絡線定理 によれば、ラグランジュ乗数の最適値は、対応する制約定数が元の目的関数の最適到達値に及ぼす限界効果として解釈できる。最適値における値を星印（ ）で表すと、次のようになる。 ⋆ {\displaystyle \star } d f ( x 1 ⋆ ( c 1 , c 2 , … ) , x 2 ⋆ ( c 1 , c 2 , … ) , … ) d c k = λ ⋆ k . {\displaystyle {\frac {\ \operatorname {d} f\left(\ x_{1\star }(c_{1},c_{2},\dots ),\ x_{2\star }(c_{1},c_{2},\dots ),\ \dots \ \right)\ }{\operatorname {d} c_{k}}}=\lambda _{\star k}~.}
例えば、経済学では、プレイヤーの最適利益は行動の制約空間を前提として計算されます。ここで、ラグランジュ乗数は、与えられた制約の緩和（例えば、所得の変化を通じて）による目的関数（利益）の最適値の変化です。このような文脈では、制約の 限界 費用は 影の価格 と呼ばれます 。 [15] λ ⋆ k {\displaystyle \ \lambda _{\star k}\ }
十分な条件 制約付き局所的最大値または最小値に対する十分条件は、ラグランジュ表現の2次導関数の境界付き ヘッセ行列 の主小行列式（左上揃えの小行列式の行列式）の列によって述べることができる。 [6] [16]
例
例1 制約付き最適化問題の図解 1 制約の下で 最大化したいとします。 実行 可能集合 は単位円であり、 f の 水準集合 は対角線（傾き-1）であるため、最大値はで発生し 、最小値はで発生することがグラフ上でわかります。 f ( x , y ) = x + y {\displaystyle \ f(x,y)=x+y\ } x 2 + y 2 = 1 . {\displaystyle \ x^{2}+y^{2}=1~.} ( 1 2 , 1 2 ) , {\displaystyle \ \left({\tfrac {1}{\sqrt {2}}},{\tfrac {1}{\sqrt {2}}}\right)\ ,} ( − 1 2 , − 1 2 ) . {\displaystyle \ \left(-{\tfrac {1}{\sqrt {2}}},-{\tfrac {1}{\sqrt {2}}}\right)~.}
ラグランジュ乗数法の場合、制約は ラグランジュ関数であり、
が 0 に設定されている 場合 と同等の関数です 。 g ( x , y ) = x 2 + y 2 − 1 = 0 , {\displaystyle g(x,y)=x^{2}+y^{2}-1=0\ ,} L ( x , y , λ ) = f ( x , y ) + λ ⋅ g ( x , y ) = x + y + λ ( x 2 + y 2 − 1 ) , {\displaystyle {\begin{aligned}{\mathcal {L}}(x,y,\lambda )&=f(x,y)+\lambda \cdot g(x,y)\\[4pt]&=x+y+\lambda (x^{2}+y^{2}-1)\ ,\end{aligned}}} f ( x , y ) {\displaystyle \ f(x,y)\ } g ( x , y ) {\displaystyle \ g(x,y)\ }
これで勾配を計算できます。 したがって、次のようになります。 ∇ x , y , λ L ( x , y , λ ) = ( ∂ L ∂ x , ∂ L ∂ y , ∂ L ∂ λ ) = ( 1 + 2 λ x , 1 + 2 λ y , x 2 + y 2 − 1 ) , {\displaystyle {\begin{aligned}\nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )&=\left({\frac {\partial {\mathcal {L}}}{\partial x}},{\frac {\partial {\mathcal {L}}}{\partial y}},{\frac {\partial {\mathcal {L}}}{\partial \lambda }}\right)\\[4pt]&=\left(1+2\lambda x,1+2\lambda y,x^{2}+y^{2}-1\right)\ \color {gray}{,}\end{aligned}}} ∇ x , y , λ L ( x , y , λ ) = 0 ⇔ { 1 + 2 λ x = 0 1 + 2 λ y = 0 x 2 + y 2 − 1 = 0 {\displaystyle \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0\quad \Leftrightarrow \quad {\begin{cases}1+2\lambda x=0\\1+2\lambda y=0\\x^{2}+y^{2}-1=0\end{cases}}}
最後の方程式が元の制約であることに注意してください。
最初の2つの式は、 最後の式に代入すると次の式が得られる。 つまり 、の停留点 は x = y = − 1 2 λ , λ ≠ 0 . {\displaystyle x=y=-{\frac {1}{2\lambda }},\qquad \lambda \neq 0~.} 1 4 λ 2 + 1 4 λ 2 − 1 = 0 , {\displaystyle {\frac {1}{4\lambda ^{2}}}+{\frac {1}{4\lambda ^{2}}}-1=0\ ,} λ = ± 1 2 , {\displaystyle \lambda =\pm {\frac {1}{\sqrt {2\ }}}\ ,} L {\displaystyle {\mathcal {L}}} ( 2 2 , 2 2 , − 1 2 ) , ( − 2 2 , − 2 2 , 1 2 ) . {\displaystyle \left({\tfrac {\sqrt {2\ }}{2}},{\tfrac {\sqrt {2\ }}{2}},-{\tfrac {1}{\sqrt {2\ }}}\right),\qquad \left(-{\tfrac {\sqrt {2\ }}{2}},-{\tfrac {\sqrt {2\ }}{2}},{\tfrac {1}{\sqrt {2\ }}}\right)~.}
これらの点における 目的関数 fを評価すると、次の式が得られる。 f ( 2 2 , 2 2 ) = 2 , f ( − 2 2 , − 2 2 ) = − 2 . {\displaystyle f\left({\tfrac {\sqrt {2\ }}{2}},{\tfrac {\sqrt {2\ }}{2}}\right)={\sqrt {2\ }}\ ,\qquad f\left(-{\tfrac {\sqrt {2\ }}{2}},-{\tfrac {\sqrt {2\ }}{2}}\right)=-{\sqrt {2\ }}~.}
したがって、制約付き最大値は であり、制約付き最小値は です 。 2 {\displaystyle \ {\sqrt {2\ }}\ } − 2 {\displaystyle -{\sqrt {2}}}
例2 制約付き最適化問題の図解 2 ここで例1 の目的関数を修正して 、 再び円に沿って を最小化する のではなく を最小化するようにします。 ここで の水準集合は 依然として傾きが-1の直線であり、これらの水準集合に接する円上の点は再び および です 。 これらの接点は の最大値です。 f ( x , y ) = ( x + y ) 2 {\displaystyle \ f(x,y)=(x+y)^{2}\ } f ( x , y ) = x + y , {\displaystyle \ f(x,y)=x+y\ ,} g ( x , y ) = x 2 + y 2 − 1 = 0 . {\displaystyle \ g(x,y)=x^{2}+y^{2}-1=0~.} f {\displaystyle f} ( 2 / 2 , 2 / 2 ) {\displaystyle \ ({\sqrt {2}}/2,{\sqrt {2}}/2)\ } ( − 2 / 2 , − 2 / 2 ) . {\displaystyle \ (-{\sqrt {2}}/2,-{\sqrt {2}}/2)~.} f . {\displaystyle \ f~.}
一方、最小値は、 （その構成上、 負の値をとることができないため）の水準で、 および の水準曲線が 制約に接しないところで発生します。4点すべてを正しく極値として特定する条件は、最小値は で 、最大値は で 特徴付けられるというものです。 f = 0 {\displaystyle \ f=0\ } f {\displaystyle \ f\ } ( 2 / 2 , − 2 / 2 ) {\displaystyle \ ({\sqrt {2}}/2,-{\sqrt {2}}/2)\ } ( − 2 / 2 , 2 / 2 ) , {\displaystyle \ (-{\sqrt {2}}/2,{\sqrt {2}}/2)\ ,} f {\displaystyle \ f\ } ∇ x , y , λ ( f ( x , y ) + λ ⋅ g ( x , y ) ) = 0 {\displaystyle \ \nabla _{x,y,\lambda }\left(f(x,y)+\lambda \cdot g(x,y)\right)=0\ } λ = 0 {\displaystyle \ \lambda =0\ } λ = − 2 . {\displaystyle \ \lambda =-2~.}
例3 制約付き最適化問題3 の図解 。 この例では、より複雑な計算を扱っていますが、それでも単一の制約の問題です。
の最大値を求める場合、 - 座標と - 座標が原点を中心とする半径 の円上にあると仮定する 。 つまり 、 制約 f ( x , y ) = x 2 y {\displaystyle f(x,y)=x^{2}y} x {\displaystyle \ x\ } y {\displaystyle \ y\ } 3 . {\displaystyle \ {\sqrt {3\ }}~.} g ( x , y ) = x 2 + y 2 − 3 = 0 . {\displaystyle g(x,y)=x^{2}+y^{2}-3=0~.}
制約は1つだけなので、乗数も1つだけあります。 λ . {\displaystyle \ \lambda ~.}
制約は 、半径の円上ではゼロです。 の任意の倍数 を追加しても、 関心領域（元の制約が満たされている円上）では変更されません 。 g ( x , y ) {\displaystyle \ g(x,y)\ } 3 . {\displaystyle \ {\sqrt {3\ }}~.} g ( x , y ) {\displaystyle \ g(x,y)\ } g ( x , y ) {\displaystyle \ g(x,y)\ } g ( x , y ) {\displaystyle \ g(x,y)\ }
通常のラグランジュ乗数法を適用すると、 勾配を計算するための式が得られます。 したがって、 (iii)は元の制約式と同じです。(i)は 、またはを 意味します。 そして、 (iii)により、 (ii)から、この式が得られます。 これを(ii)に代入すると、次の式が得られます。 これを(iii)に代入して解くと、 次 の式が得られます。したがって、6つの臨界点があります。 L ( x , y , λ ) = f ( x , y ) + λ ⋅ g ( x , y ) = x 2 y + λ ( x 2 + y 2 − 3 ) , {\displaystyle {\begin{aligned}{\mathcal {L}}(x,y,\lambda )&=f(x,y)+\lambda \cdot g(x,y)\\&=x^{2}y+\lambda (x^{2}+y^{2}-3)\ ,\end{aligned}}} ∇ x , y , λ L ( x , y , λ ) = ( ∂ L ∂ x , ∂ L ∂ y , ∂ L ∂ λ ) = ( 2 x y + 2 λ x , x 2 + 2 λ y , x 2 + y 2 − 3 ) . {\displaystyle {\begin{aligned}\nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )&=\left({\frac {\partial {\mathcal {L}}}{\partial x}},{\frac {\partial {\mathcal {L}}}{\partial y}},{\frac {\partial {\mathcal {L}}}{\partial \lambda }}\right)\\&=\left(2xy+2\lambda x,x^{2}+2\lambda y,x^{2}+y^{2}-3\right)~.\end{aligned}}} ∇ x , y , λ L ( x , y , λ ) = 0 ⟺ { 2 x y + 2 λ x = 0 x 2 + 2 λ y = 0 x 2 + y 2 − 3 = 0 ⟺ { x ( y + λ ) = 0 (i) x 2 = − 2 λ y (ii) x 2 + y 2 = 3 (iii) {\displaystyle \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0\quad \iff \quad {\begin{cases}2xy+2\lambda x=0\\x^{2}+2\lambda y=0\\x^{2}+y^{2}-3=0\end{cases}}\quad \iff \quad {\begin{cases}x(y+\lambda )=0&{\text{(i)}}\\x^{2}=-2\lambda y&{\text{(ii)}}\\x^{2}+y^{2}=3&{\text{(iii)}}\end{cases}}} x = 0 {\displaystyle \ x=0\ } λ = − y . {\displaystyle \ \lambda =-y~.} x = 0 {\displaystyle x=0} y = ± 3 {\displaystyle \ y=\pm {\sqrt {3\ }}\ } λ = 0 {\displaystyle \ \lambda =0\ } λ = − y , {\displaystyle \ \lambda =-y\ ,} x 2 = 2 y 2 . {\displaystyle \ x^{2}=2y^{2}~.} y {\displaystyle \ y\ } y = ± 1 . {\displaystyle \ y=\pm 1~.} L : {\displaystyle \ {\mathcal {L}}\ :} ( 2 , 1 , − 1 ) ; ( − 2 , 1 , − 1 ) ; ( 2 , − 1 , 1 ) ; ( − 2 , − 1 , 1 ) ; ( 0 , 3 , 0 ) ; ( 0 , − 3 , 0 ) . {\displaystyle ({\sqrt {2\ }},1,-1);\quad (-{\sqrt {2\ }},1,-1);\quad ({\sqrt {2\ }},-1,1);\quad (-{\sqrt {2\ }},-1,1);\quad (0,{\sqrt {3\ }},0);\quad (0,-{\sqrt {3\ }},0)~.}
これらの点において目的を評価すると、 f ( ± 2 , 1 ) = 2 ; f ( ± 2 , − 1 ) = − 2 ; f ( 0 , ± 3 ) = 0 . {\displaystyle f(\pm {\sqrt {2\ }},1)=2;\quad f(\pm {\sqrt {2\ }},-1)=-2;\quad f(0,\pm {\sqrt {3\ }})=0~.}
したがって、目的関数は （制約条件の下で）で 大域的 最大値に達し、 大域的最小値 はで達する。 この 点はの 極小 値 であり、 はの極大値 で ある。これは 、ヘッセ行列 の考察によって決定される 。 ( ± 2 , 1 ) {\displaystyle \ (\pm {\sqrt {2\ }},1\ )} ( ± 2 , − 1 ) . {\displaystyle \ (\pm {\sqrt {2\ }},-1)~.} ( 0 , 3 ) {\displaystyle \ (0,{\sqrt {3\ }})\ } f {\displaystyle \ f\ } ( 0 , − 3 ) {\displaystyle \ (0,-{\sqrt {3\ }})\ } f , {\displaystyle \ f\ ,} L ( x , y , 0 ) . {\displaystyle \ {\mathcal {L}}(x,y,0)~.}
は臨界点であるが、 は 極値ではないこと に注意すること。 ( 2 , 1 , − 1 ) {\displaystyle \ ({\sqrt {2\ }},1,-1)\ } L , {\displaystyle \ {\mathcal {L}}\ ,} L . {\displaystyle \ {\mathcal {L}}~.} L ( 2 + ε , 1 , − 1 + δ ) = 2 + δ ( ε 2 + ( 2 2 ) ε ) . {\displaystyle {\mathcal {L}}\left({\sqrt {2\ }}+\varepsilon ,1,-1+\delta \right)=2+\delta \left(\varepsilon ^{2}+\left(2{\sqrt {2\ }}\right)\varepsilon \right)~.}
の任意の近傍が与えられたとき、 正の小さな値と、 どちらかの符号の 小さな値を選択して 、より大きい値とより小さい値の両方を得ることができる。これ は、この点（あるいは任意の臨界点）で評価された のヘッセ行列からもわかるように、これは 不定行列 である。 の各臨界点は [4] の 鞍点 である。 ( 2 , 1 , − 1 ) , {\displaystyle \ ({\sqrt {2\ }},1,-1)\ ,} ε {\displaystyle \ \varepsilon \ } δ {\displaystyle \ \delta \ } L {\displaystyle \ {\mathcal {L}}} 2 . {\displaystyle \ 2~.} L {\displaystyle \ {\mathcal {L}}\ } L {\displaystyle \ {\mathcal {L}}\ } L . {\displaystyle \ {\mathcal {L}}~.}
例4 – エントロピー 情報エントロピーが 最大となる 点上の 離散確率分布を 求めたいとします。これは 、点上の 最も構造化されていない 確率分布を求めたいということと同じです。 言い換えれば、 シャノンエントロピー 方程式を最大化したいのです。 { p 1 , p 2 , … , p n } {\displaystyle \ \{p_{1},p_{2},\ldots ,p_{n}\}\ } { p 1 , p 2 , ⋯ , p n } . {\displaystyle \ \{p_{1},p_{2},\cdots ,p_{n}\}~.} f ( p 1 , p 2 , … , p n ) = − ∑ j = 1 n p j log 2 p j . {\displaystyle f(p_{1},p_{2},\ldots ,p_{n})=-\sum _{j=1}^{n}p_{j}\log _{2}p_{j}~.}
これが確率分布であるためには、各点における 確率の合計が 1 に等しくなければなりません。したがって、制約は次のようになります。 p i {\displaystyle \ p_{i}\ } x i {\displaystyle \ x_{i}\ } g ( p 1 , p 2 , … , p n ) = ∑ j = 1 n p j = 1 . {\displaystyle g(p_{1},p_{2},\ldots ,p_{n})=\sum _{j=1}^{n}p_{j}=1~.}
ラグランジュ乗数を使用して、すべての離散確率分布にわたって 最大 エントロピー点を見つけます。 次の式が必要です。 これにより
、次 のn 個の方程式 のシステムが得られます。 p → ∗ , {\displaystyle \ {\vec {p}}^{\,*}\ ,} p → {\displaystyle \ {\vec {p}}\ } { x 1 , x 2 , … , x n } . {\displaystyle \ \{x_{1},x_{2},\ldots ,x_{n}\}~.} ∂ ∂ p → ( f + λ ( g − 1 ) ) | p → = p → ∗ = 0 , {\displaystyle \left.{\frac {\partial }{\partial {\vec {p}}}}(f+\lambda (g-1))\right|_{{\vec {p}}={\vec {p}}^{\,*}}=0\ ,} k = 1 , … , n , {\displaystyle \ k=1,\ \ldots ,n\ ,} ∂ ∂ p k { − ( ∑ j = 1 n p j log 2 p j ) + λ ( ∑ j = 1 n p j − 1 ) } | p k = p ⋆ k = 0 . {\displaystyle \left.{\frac {\partial }{\partial p_{k}}}\left\{-\left(\sum _{j=1}^{n}p_{j}\log _{2}p_{j}\right)+\lambda \left(\sum _{j=1}^{n}p_{j}-1\right)\right\}\right|_{p_{k}=p_{\star k}}=0~.}
これらのn 方程式 を微分すると、次の式が得られます。 − ( 1 ln 2 + log 2 p ⋆ k ) + λ = 0 . {\displaystyle -\left({\frac {1}{\ln 2}}+\log _{2}p_{\star k}\right)+\lambda =0~.}
これはすべてが等しいことを示しています（ λ のみに依存するため ）。制約条件を用いると 、 p ⋆ k {\displaystyle \ p_{\star k}\ } ∑ j p j = 1 , {\displaystyle \sum _{j}p_{j}=1\ ,} p ⋆ k = 1 n . {\displaystyle p_{\star k}={\frac {1}{n}}~.}
したがって、均一分布は、 n 点の分布の中でエントロピーが最大となる分布です 。
例5 – 数値最適化 ラグランジュ乗数により、臨界点は鞍点に発生します（例 5 ）。 勾配の大きさを使用して、臨界点が局所最小値で発生するように強制することができます (例 5 )。 ラグランジアンの臨界点は 、極大値（または極小値）ではなく、 鞍点で発生します。 [4] [17] 残念ながら、 山登り法 、 勾配降下法 、一部の 準ニュートン法 など、多くの数値最適化手法は、鞍点ではなく、極大値（または極小値）を見つけるように設計されています。このため、定式化を修正して最小化問題になるようにするか（たとえば、以下のようにラグランジアンの 勾配の2乗を極値化する）、または必ずしも極値ではなく、 停留点 を見つける最適化手法（極値探索 直線探索を行わない ニュートン法 など ） を使用する必要があります。
簡単な例として、制約 を最小化する x の値を見つける問題を考えてみましょう (この問題は、この制約を満たす値は 2 つしかないため、やや非典型的ですが、対応する制約のない関数を 3 次元で視覚化できるため、説明には役立ちます)。 f ( x ) = x 2 , {\displaystyle \ f(x)=x^{2}\ ,} x 2 = 1 . {\displaystyle \ x^{2}=1~.}
ラグランジュ乗数を使用すると、この問題は制約のない最適化問題に変換できます。 L ( x , λ ) = x 2 + λ ( x 2 − 1 ) . {\displaystyle {\mathcal {L}}(x,\lambda )=x^{2}+\lambda (x^{2}-1)~.}
2つの臨界点は、 x = 1 および x = −1 の鞍点で発生します 。
この問題を数値最適化手法で解くには、まず、臨界点が局所最小値に現れるように問題を変換する必要があります。これは、制約なし最適化問題の勾配の大きさを計算することで行われます。
まず、制約のない問題の偏微分を各変数に関して計算します。 ∂ L ∂ x = 2 x + 2 x λ ∂ L ∂ λ = x 2 − 1 . {\displaystyle {\begin{aligned}&{\frac {\partial {\mathcal {L}}}{\partial x}}=2x+2x\lambda \\[5pt]&{\frac {\partial {\mathcal {L}}}{\partial \lambda }}=x^{2}-1~.\end{aligned}}}
対象関数が簡単に微分可能でない場合は、各変数に関する微分は次のように近似できます
。 ただし、 は小さな値です。 ∂ L ∂ x ≈ L ( x + ε , λ ) − L ( x , λ ) ε , ∂ L ∂ λ ≈ L ( x , λ + ε ) − L ( x , λ ) ε , {\displaystyle {\begin{aligned}{\frac {\ \partial {\mathcal {L}}\ }{\partial x}}\approx {\frac {{\mathcal {L}}(x+\varepsilon ,\lambda )-{\mathcal {L}}(x,\lambda )}{\varepsilon }},\\[5pt]{\frac {\ \partial {\mathcal {L}}\ }{\partial \lambda }}\approx {\frac {{\mathcal {L}}(x,\lambda +\varepsilon )-{\mathcal {L}}(x,\lambda )}{\varepsilon }},\end{aligned}}} ε {\displaystyle \varepsilon }
次に、偏導関数の二乗の合計の平方根である勾配の大きさを計算します。 h ( x , λ ) = ( 2 x + 2 x λ ) 2 + ( x 2 − 1 ) 2 ≈ ( L ( x + ε , λ ) − L ( x , λ ) ε ) 2 + ( L ( x , λ + ε ) − L ( x , λ ) ε ) 2 . {\displaystyle {\begin{aligned}h(x,\lambda )&={\sqrt {(2x+2x\lambda )^{2}+(x^{2}-1)^{2}\ }}\\[4pt]&\approx {\sqrt {\left({\frac {\ {\mathcal {L}}(x+\varepsilon ,\lambda )-{\mathcal {L}}(x,\lambda )\ }{\varepsilon }}\right)^{2}+\left({\frac {\ {\mathcal {L}}(x,\lambda +\varepsilon )-{\mathcal {L}}(x,\lambda )\ }{\varepsilon }}\right)^{2}\ }}~.\end{aligned}}}
(大きさは常に非負なので、大きさの二乗を最適化することは大きさ自体を最適化することと同等です。したがって、これらの式から「平方根」を省略しても、最適化の結果に違いは生じません。)
h の臨界点は、の 場合と同様に、 x = 1 および x = −1 で発生します。ただし、 の臨界点とは異なり、 h の臨界点は 局所的最小値で発生するため、数値最適化手法を使用してその点を見つけることができます。 L . {\displaystyle {\mathcal {L}}~.} L , {\displaystyle {\mathcal {L}}\,,}
アプリケーション
ラグランジアン力学 ラグランジュ力学 では 、オイラー・ラグランジュ方程式にラグランジュ乗数を加えて、系に物理的な制約を課す手法が提案されている。 [18] この手法は一般には必須ではない。代替手法として、制約が暗黙的に課されるように線形独立な一般化座標系を選択する手法があるからである。
ラグランジュ乗数を用いる場合、制約方程式はオイラー-ラグランジュ方程式と同時に解く必要がある。したがって、方程式は（ 常微分方程式 系ではなく） 微分代数 方程式系となる。 [19]
ラグランジュ乗数法は、ラグランジアンを線形独立な一般化座標系で記述することが困難な場合に有用である。例えば、プログラムによる動的システムのモデリングアルゴリズムや、閉運動連鎖を持つシステムのモデリングに用いられる。 [20] また、非ホロノミック制約を課す場合にも有用である。 [18] [20]
ホロノミック制約方程式の集合が与えられたとき 、ラグランジュ乗数を持つオイラー・ラグランジュ方程式は次のように表される [18] [19] f j ( q , t ) = 0 {\displaystyle f_{j}(\mathbf {q} ,t)=0}
d d t ∂ L ∂ q ˙ i − ∂ L ∂ q i + ∑ j = 1 C λ j ∂ f j ∂ q i ⏟ − τ i , constraint = τ i {\displaystyle {\frac {\mathrm {d} }{\mathrm {d} t}}{\frac {\partial L}{\partial {\dot {q}}_{i}}}-{\frac {\partial L}{\partial q_{i}}}+\underbrace {\sum _{j=1}^{C}\lambda _{j}{\frac {\partial f_{j}}{\partial q_{i}}}} _{-\tau _{i,{\text{constraint}}}}=\tau _{i}}
の意味は、 それを方程式の反対側に移し、一般化された力の項に吸収することで解釈できる 。この解釈では、系には 追加の自由度がいくつかあり、追加的に課される制約はないが、制約力が たまたま適切な値を持ち、制約が成立する。 [18] [19] τ i , constraint {\displaystyle \tau _{i,{\text{constraint}}}} τ i {\displaystyle \tau _{i}} C {\displaystyle C} τ i , constraint {\displaystyle \tau _{i,{\text{constraint}}}}
制御理論 最適制御 理論では 、ラグランジュ乗数は 共存 変数として解釈され、ラグランジュ乗数は ポンチャギンの最大値原理 における ハミルトニアン の最小化として再定式化されます。
非線形計画法 ラグランジュ乗数法にはいくつかの一般化があります。 非線形計画法 には、不等式制約に対するカラテオドリ・ジョン乗数法や凸乗数法など、いくつかの乗数規則があります。 [21]
経済 一般均衡モデル などの 数理経済学 の多くのモデルでは 、消費者行動は 効用最大化 、企業行動は 利潤最大化として実装されており、どちらの行動も 予算制約 や 生産制約 といった制約条件に左右される 。最適解を求める一般的な方法は、ラグランジュ乗数を用いて制約条件を強制する関数を最大化することで達成される。 [22] [23] [24] [25]
電力システム ラグランジュ乗数に基づく手法は 、分散型エネルギー資源（DER）の配置や負荷制限などの 電力システムに応用されている。 [26]
安全な強化学習 ラグランジュ乗数法は制約付き マルコフ決定過程 に適用される。 [27]
これにより、安全な強化学習において勾配ベースのプライマルデュアルアルゴリズムが自然に生成される。 [28]
制約付きの PDE 問題、つまり正規化された解の特性の研究を考えると、ラグランジュ乗数は重要な役割を果たします。
参照
参考文献 ^ ホフマン, ローレンス・D.; ブラッドリー, ジェラルド・L. (2004). 『ビジネス・経済・社会・生命科学のための微積分』 （第8版）. マグロウヒル高等教育. pp. 575– 588. ISBN 0-07-242432-X 。 ^ ブライアン・ビービス、イアン・M・ドブス（1990年）「静的最適化」『 経済分析のための最適化と安定性理論 』ニューヨーク：ケンブリッジ大学出版局、p. 40. ISBN 0-521-33605-8 。 ^ Protter, Murray H. ; Morrey, Charles B. Jr. (1985). Intermediate Calculus (第2版). New York, NY: Springer. p. 267. ISBN 0-387-96058-9 。 ^ abc Walsh, GR (1975). 「ラグランジュ関数の鞍点特性」. 最適化手法 . ニューヨーク: John Wiley & Sons. pp. 39– 44. ISBN 0-471-91922-5 。 ^ カルマン、ダン (2009). 「ラグランジュによるレベリング：制約付き最適化の新たな視点」. 数学マガジン . 82 (3): 186– 196. doi :10.1080/0025570X.2009.11953617. JSTOR 27765899. S2CID 121070192. ^ ab シルバーバーグ, ユージン; スエン, ウィング (2001). 『経済学の構造：数学的分析 （第3版）』 ボストン: アーウィン・マグロウヒル. pp. 134– 141. ISBN 0-07-234352-4 。 ^ de la Fuente , Angel (2000). 『経済学者のための数学的手法とモデル』 ケンブリッジ: ケンブリッジ大学出版局. p. 285. doi :10.1017/CBO9780511810756. ISBN 978-0-521-58512-5 。 ^ Luenberger, David G. (1969). ベクトル空間法による最適化 . ニューヨーク: John Wiley & Sons. pp. 188– 189. ^ Bertsekas, Dimitri P. (1999). 非線形計画法 （第2版）. Cambridge, MA: Athena Scientific. ISBN 1-886529-00-0 。 ^ Vapnyarskii, IB (2001) [1994]、「ラグランジュ乗数」、 数学百科事典 、 EMSプレス 。 ^ ラスドン、レオン・S. (2002) [1970]. 大規模システムのための最適化理論 （復刻版）. ミネオラ、ニューヨーク、NY: ドーバー. ISBN 0-486-41999-1 . MR 1888251。 ^ Hiriart-Uruty、ジャン-バティスト; ルマレシャル、クロード (1993)。 「第 XII 章: 実践者のための抽象的な二元性」。 凸解析および最小化アルゴリズム 。 Grundlehren der Mathematischen Wissenschaften [数学科学の基本原理]。 Vol. 306. デラウェア州ベルリン: Springer-Verlag。 pp. 136–193 (および参考文献コメント pp. 334–335)。 ISBN 3-540-56852-2 MR 1295240。 第2巻：高度な理論とバンドル法。 ^ ルマレシャル、クロード (2000 年 5 月 15 日 - 19 日)。 「ラグランジュ緩和」。ユンガーでは、マイケル。ナデフ、デニス (編)。 計算による組み合わせ最適化: ダグシュトゥール城で開催されたスプリング スクールの論文 。 2000 年 5 月 15 日から 19 日まで、 ダグシュトゥール城で春の学校が開催されました 。コンピューターサイエンスの講義ノート。 Vol. 2241. デラウェア州ベルリン: Springer-Verlag (2001 年発行)。 pp. 112–156 。 土井 :10.1007/3-540-45586-8_4。 ISBN 3-540-42877-1 . MR 1900016. S2CID 9048698. ^ ラフォンテーヌ、ジャック (2015). 微分多様体入門. シュプリンガー. p. 70. ISBN 978-3-319-20735-3 。 ^ ディキシット、アビナッシュ・K. (1990). 「影の価格」. 『経済理論における最適化』 （第2版）. ニューヨーク: オックスフォード大学出版局. pp. 40– 54. ISBN 0-19-877210-6 。 ^ Chiang, Alpha C. (1984). 『数理経済学の基礎的手法 （第3版）』McGraw-Hill. p. 386. ISBN 0-07-010813-7 。 ^ Heath, Michael T. (2005). 『科学計算入門』 McGraw-Hill. p. 203. ISBN 978-0-07-124489-3 。 ^ abcd ゴールドスタイン, ハーバート ; プール, チャールズ P. Jr.; サフコ, ジョン L. (2002). 古典力学（第3版）. サンフランシスコ, カリフォルニア州: アディソン・ウェスレー. pp. 45– 51. ISBN 0-201-65702-3 。 ^ abc Brenan, KE; Campbell, SL; Petzold, LR (1995). 微分代数方程式における初期値問題の数値解法 . Society for Industrial and Applied Mathematics. pp. 4– 5. doi :10.1137/1.9781611971224. ^ ab Roy, Featherstone (2008). 剛体ダイナミクスアルゴリズム . Springer New York. pp. 42– 45, 141– 143. doi :10.1007/978-1-4899-7560-7. ^ Pourciau, Bruce H. (1980). 「現代の乗数ルール」 . American Mathematical Monthly . 87 (6): 433– 452. doi :10.2307/2320250. JSTOR 2320250. ^ Kamien, MI ; Schwartz, NL (1991). Dynamic Optimization: The Calculus of Variations and Optimal Control in Economics and Management (Second ed.). New York: Elsevier. ISBN 0-444-01609-0 。 ^ Glötzl, Erhard; Glötzl, Florentin; Richters, Oliver (2019). 「制約付き最適化から制約付きダイナミクスへ：経済学と力学のアナロジーの拡張」 Journal of Economic Interaction and Coordination . 14 (3): 623– 642. doi :10.1007/s11403-019-00252-7. hdl : 10419/171974 . ^ Baxley, John V.; Moorhouse, John C. (1984). 「経済学におけるラグランジュ乗数問題」 アメリカ数学月刊誌 . 91 (7): 404– 412. doi :10.1080/00029890.1984.11971446. 。 ^ Janová, Jitka (2011). 「制約付き力学手法の経済学への応用」. European Journal of Physics . 32 (6): 1443– 1463. arXiv : 1106.3455 . Bibcode :2011EJPh...32.1443J. doi :10.1088/0143-0807/32/6/001. ^ Gautam, Mukesh; Bhusal, Narayan; Benidris, Mohammed (2020). 感度に基づく適応型低周波数負荷遮断アプローチ . 2020 IEEE Texas Power and Energy Conference (TPEC). 米国電子電気学会 . pp. 1– 5. doi :10.1109/TPEC48276.2020.9042569. ^ Altman, Eitan (2021). 制約付きマルコフ決定過程 . Routledge . ^ Ding, Dongsheng; Zhang, Kaiqing; Jovanovic, Mihailo; Basar, Tamer (2020). 制約付きマルコフ決定過程のための自然方策勾配プライマル・デュアル法 . ニューラル情報処理システムの進歩.
さらに読む ブライアン・ビービス、イアン・M・ドブス (1990). 「静的最適化」. 経済分析のための最適化と安定性理論 . ニューヨーク：ケンブリッジ大学出版局. pp. 32– 72. ISBN 0-521-33605-8 。 ベルツェカス, ディミトリ・P. (1982). 制約付き最適化とラグランジュ乗数法 . ニューヨーク: アカデミック・プレス. ISBN 0-12-093480-9 。 ベヴァリッジ、ゴードンSG; シェクター、ロバートS. (1970). 「ラグランジュ乗数」. 最適化：理論と実践 . ニューヨーク：マグロウヒル. pp. 244– 259. ISBN 0-07-005128-3 。 ブライアン・R・ビンガー、エリザベス・ホフマン (1998). 「制約付き最適化」. ミクロ経済学と微積分 （第2版）. 参考文献: Addison-Wesley. pp. 56– 91. ISBN 0-321-01225-9 。 カーター、マイケル (2001). 「等式制約」. 数理経済学の基礎 . ケンブリッジ, マサチューセッツ州: MIT 出版. pp. 516– 549. ISBN 0-262-53192-5 。 ヘステネス、マグナス・R. (1966). 「等式制約条件下の関数の最小値」 変分法と最適制御理論 . ニューヨーク: Wiley. pp. 29– 34. ワイリー, C. レイ; バレット, ルイス C. (1995). 「制約条件下の積分の極値」. 先端工学数学 (第6版). ニューヨーク: マグロウヒル. pp. 1096– 1103. ISBN 0-07-072206-4 。
外部リンク ウィキブックの 微積分最適化法には、 ラグランジュ乗数 に関するページがあります。
博覧会 Steuard. 「概念紹介」. slimy.com . — さらに、物理学で使用される 変分法 におけるラグランジュ乗数についても簡単に説明します。 カーペンター、ケネス H.「線形制約付き二次形式のラグランジュ乗数」 （PDF） 。 カンザス州立大学 。
追加のテキストとインタラクティブなアプレット レスニック「税金を ラグランジュ乗数として用いる政府の例による簡単な説明」 umiacs.umd.edu メリーランド大学 2015年9月4日時点のオリジナルよりアーカイブ。 2007年 2月28日 閲覧 。 ダン・クライン. 「永久的な傷跡を残さないラグランジュ乗数] 直感を重視した説明」 (PDF) . nlp.cs.berkeley.edu . カリフォルニア大学バークレー校 . Sathyanarayana, Shashi. 「ラグランジュ乗数法の幾何学的表現」. wolfram.com ( Mathematicaの デモ). Wolfram Research . Internet Explorer / Firefox / Safariが必要です。 — 最小化点では、最急降下の方向はその点における制約曲線の接線に対して垂直でなければならないという説得力のある洞察を 2 次元で提供します。 「ラグランジュ乗数 - 2変数」。MIT オープンコースウェア（ocw.mit.edu） （アプレット）。 マサチューセッツ工科大学 。 「ラグランジュ乗数」。MIT オープンコースウェア（ocw.mit.edu） （ビデオ講義）。数学18-02：多変数微分積分。 マサチューセッツ工科大学 。2007年秋。 Bertsekas. 「ラグランジュ乗数の詳細」 （PDF） . athenasc.com （スライド／講義）。非線形計画法。 — 非線形最適化に関するテキストに付随するコーススライド ワイアット、ジョン (2004年4月7日) [2002年11月19日]. 「ルグランジュ乗数、制約付き最適化、そして最大エントロピー原理」 (PDF) . www-mtl.mit.edu . Elec E & CS / Mech E 6.050 – 情報、エントロピー、そして計算. — ラグランジュ乗数の背後にある幾何学的考え方 「最適化におけるラグランジュ乗数の使用」 matlab.cheme.cmu.edu （MATLABの例）。ペンシルベニア州ピッツバーグ：カーネギーメロン大学。2011年12月24日。
![{\displaystyle {\Bigl [}\operatorname {D} g(x_{\star }){\Bigr ]}_{j,k}={\frac {\ \partial g_{j}\ }{\partial x_{k}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e64847aaf74c536fcbdd35ff935281fda73117f3)
![{\displaystyle {\begin{aligned}&{\mathcal {L}}(x_{1},x_{2},\ldots ;\lambda _{1},\lambda _{2},\ldots ;c_{1},c_{2},\ldots )\\[4pt]={}&f(x_{1},x_{2},\ldots )+\lambda _{1}(c_{1}-g_{1}(x_{1},x_{2},\ldots ))+\lambda _{2}(c_{2}-g_{2}(x_{1},x_{2},\dots ))+\cdots \end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1867ddf9118c757c322a3d5c0c94965c64a65d0a)
![{\displaystyle {\begin{aligned}{\mathcal {L}}(x,y,\lambda )&=f(x,y)+\lambda \cdot g(x,y)\\[4pt]&=x+y+\lambda (x^{2}+y^{2}-1)\ ,\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/69623e2b0ffebabe351b9e7ed58a76751601bf66)
![{\displaystyle {\begin{aligned}\nabla_{x,y,\lambda}{\mathcal{L}}(x,y,\lambda)&=\left({\frac{\partial{\mathcal{L}}}{\partial x}},{\frac{\partial{\mathcal{L}}}{\partial y}},{\frac{\partial{\mathcal{L}}}{\partial \lambda}}\right)\\[4pt]&=\left(1+2\lambda x,1+2\lambda y,x^{2}+y^{2}-1\right)\\color{gray}{,}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdf9c05227cba7a2024d2ef806cf55712c1a3073)
![{\displaystyle {\begin{aligned}&{\frac {\partial {\mathcal {L}}}{\partial x}}=2x+2x\lambda \\[5pt]&{\frac {\partial {\mathcal {L}}}{\partial \lambda }}=x^{2}-1~.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/498e5f0200a9e684456385a4d6b121c2274c2737)
![{\displaystyle {\begin{aligned}{\frac {\ \partial {\mathcal {L}}\ }{\partial x}}\approx {\frac {{\mathcal {L}}(x+\varepsilon ,\lambda )-{\mathcal {L}}(x,\lambda )}{\varepsilon }},\\[5pt]{\frac {\ \partial {\mathcal {L}}\ }{\partial \lambda }}\approx {\frac {{\mathcal {L}}(x,\lambda +\varepsilon )-{\mathcal {L}}(x,\lambda )}{\varepsilon }},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0de4bda576fdb293b9e0b1f0ebe3f93d57c84f06)
![{\displaystyle {\begin{aligned}h(x,\lambda )&={\sqrt {(2x+2x\lambda )^{2}+(x^{2}-1)^{2}\ }}\\[4pt]&\approx {\sqrt {\left({\frac {\ {\mathcal {L}}(x+\varepsilon ,\lambda )-{\mathcal {L}}(x,\lambda )\ }{\varepsilon }}\right)^{2}+\left({\frac {\ {\mathcal {L}}(x,\lambda +\varepsilon )-{\mathcal {L}}(x,\lambda )\ }{\varepsilon }}\right)^{2}\ }}~.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a19179451d91b7f354ff6326de2c76749c3e9f0f)
