Loading [MathJax]/jax/output/HTML-CSS/jax.js

拘束のある問題

提供: Internet Web School

(版間での差分)
(ラグランジュ乗数法)
 
(間の43版分が非表示)
1 行: 1 行:
==等式拘束のある問題==
==等式拘束のある問題==
 +
 +
 +
 +
==陰関数定理とラグランジュ乗数==
 +
 +
以下の問題を考える.
 +
 +
 +
<math>L(x,y)=x+y</math>とするとき,
 +
半径1の円周
 +
 +
<math>x^2+y^2=1  \qquad (1)</math>
 +
 +
上の点<math>(x,y)</math>で<math>L(x,y)=x+y</math>の最大にするものを求めよ.
 +
 +
 +
===関数の極値条件===
 +
 +
実数値関数<math>F(x)</math>が<math>x=x_0</math>で極小値または極大値をとり,かつ,<math>x=x_0</math>で微分可能であれば,
 +
 +
<math>F(x)</math>の<math>x=x_0</math>での微分係数は<math>0</math>である。
 +
 +
<math>\frac{dF}{dx}(x_0) = 0</math>
 +
 +
 +
===陰関数===
 +
 +
半径1の円の方程式
 +
 +
<math>x^2+y^2=1\qquad (1)</math>
 +
 +
に注目する。判りやすいように,
 +
 +
<math>1\ge x \ge -1,1 \ge y \ge 0</math>
 +
としておく.
 +
 +
<math>g(x)=\sqrt{1-x^2}</math>
 +
とすると,
 +
<math>1\ge x \ge -1,1 \ge y \ge 0</math>では<math>(1)</math>の方程式を満たす<math>x,y</math>については
 +
<math>y=g(x)</math>
 +
という関係が成り立っている.
 +
 +
この<math>g(x)</math>という関数は,<math>(1)</math>式の中には出てこない.<math>(1)</math>からこのように間接的に導き出される関数を陰関数と呼ぶ.
 +
 +
 +
一般化すれば特定の条件のもとに
 +
<math>f(x,y)=0</math>という式から陰関数<math>y=g(x)</math>が定義される。
 +
 +
上の例では <math>f(x,y)=x^2+y^2-1</math>
 +
 +
しかし,何時でも上の例のように,<math>f(x,y)=0</math>から陰関数<math>y=g(x)</math>が定義されるわけではない.
 +
 +
===陰関数定理===
 +
 +
ある領域D<math>\subseteq R\times R</math>で関数<math>f(x,y)</math>が連続でかつ,<math>x,y</math>について偏微分可能で,
 +
その偏導関数
 +
 +
<math>\frac{\partial f}{\partial x}(x,y) \qquad (1)</math>
 +
 +
<math>\frac{\partial f}{\partial y}(x,y) \qquad (2)</math>
 +
 +
も<math>(x,y)</math>について連続とする。
 +
 +
D内の1点<math>(x_0,y_0)</math>で
 +
 +
<math>f(x_0,y_0)=0</math>
 +
 +
であり,
 +
 +
<math>\frac{\partial f}{\partial y}(x_0,y_0)\neq 0 \qquad (4)</math>
 +
 +
とする.
 +
このとき,<math>x_0</math>を含む開区間<math>(a,b)</math>とその上の連続関数<math>g(x)</math>が存在し,
 +
 +
1) 開区間<math>(a,b)</math>上で<math>f(x,g(x))=0</math>
 +
 +
2) <math>y_0=g(x_0)</math>
 +
 +
3) 開区間<math>(a,b)</math>上で,
 +
 +
<math>\frac{dy}{dx}=-\frac{\partial f / \partial x}{\partial f / \partial y} \qquad (5)</math>
 +
 +
 +
 +
上の定理で<math>x,y</math>の役目を反対にすれば,<math>x_0=g(y_0)</math> となる陰関数の存在が示される.
 +
 +
===ラグランジュ乗数法===
 +
 +
 +
関数<math>L(x,y)</math>が,制約条件
 +
<math>f(x,y)=0</math>
 +
の元に<math>(x,y)=(x_0,y_0)</math>で極値(極大値か極小値)をとるとする。
 +
 +
<math>L(x,y)</math>が<math>(x,y)</math>について微分可能な関数で,
 +
関数<math>f(x,y)</math>は<math>(x_0,y_0)</math>が上の陰関数定理を適用できる条件を満たしているものとする。
 +
<math>x_0</math>の近傍で関数<math>g(x)</math>が存在して,<math>x_0</math>のその近傍では
 +
<math>f(x,g(x))=0</math> が成り立ち,<math>y_0=g(x_0)</math>,<math>f(x_0,g(x_0))=0</math>も成り立っている.
 +
<math>x,y</math>の役目を反対にすれば,<math>x_0=g(y_0)</math> となる陰関数を用いることになるが議論は全く同様に
 +
できる.
 +
 +
 +
関数<math>L(x,y)</math>は<math>(x_0,y_0)</math>で極値(極大値か極小値)をとるから
 +
<math>F(x)=L(x,g(x))</math>も<math>x=x_0</math>で極値を取る.
 +
 +
 +
 +
極値条件により
 +
 +
<math>\frac{dF}{dx}(x_0)=0 \qquad  (6)</math>
 +
 +
である.
 +
 +
この<math>x</math>についての微分を求めると<math>F(x)=L(x,g(x))</math>は合成関数であるから
<math>
<math>
-
\frac{\partial}{\partial x_1}\bigl{[} l({\bf x}) + \lambda_1 g_1({\bf x}) \bigr{]} =0
+
\frac{dF}{dx}(x_0)=\frac{\partial}{\partial x}L(x_0,g(x_0))+\frac{\partial}{\partial y}L(x_0,g(x_0))\frac{d}{dx}g(x_0) \qquad (7) \\
 +
\frac{dy}{dx}=-\frac{\partial f / \partial x}{\partial f / \partial y} \qquad(8)
</math>
</math>
 +
 +
<math>y=g(x)</math>であるから<math>(8)</math>式を上の<math>(7)</math>式に代入し
 +
 +
 +
 +
<math>\lambda=\frac{\partial}{\partial y}L(x_0,g(x_0))\{-\frac{\partial f}{\partial y}(x_0,g(x_0))\}^{-1} \qquad (9)</math>
 +
 +
という変数を使うと,
 +
 +
<math>0=\frac{dF}{dx}(x_0)=\frac{\partial}{\partial x}L(x_0,g(x_0))+\lambda\frac{\partial}{\partial x}f(x_0,g(x_0)) \qquad (10)</math>
 +
 +
また
 +
 +
<math>\lambda \frac{\partial}{\partial y}f(x_0,g(x_0)=-\frac{\partial}{\partial y}L(x_0,g(x)) \qquad (11)</math>
 +
 +
から
 +
 +
<math>0=\frac{\partial}{\partial y}L(x_0,g(x_0))+\lambda \frac{\partial}{\partial y}f(x_0,g(x_0)) \qquad (12) </math>
 +
 +
すなわち<math>\lambda</math>という新しい変数を使って
 +
 +
<math>H(x,y,\lambda)=L(x,y)+\lambda f(x,y) \qquad (13)</math>
 +
 +
という関数を造ると:
 +
 +
関数<math>L(x,y)</math>が制約条件<math>f(x,y)=0</math>
 +
を充たすという条件の下に
 +
<math>(x,y)=(x_0,y_0)</math>で極値(極大値か極小値)をとる
 +
という条件から<math>H</math>についての制約のない場合の極値条件
<math>
<math>
-
\frac{\partial}{\partial x_1}\bigl{\{}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x}) \bigr{ \} } =0\\
+
\frac{\partial}{\partial x}H(x_0,y_0,\lambda)=0  \qquad (14) \\
 +
\frac{\partial}{\partial y}H(x_0,y_0,\lambda)=0  \qquad (15) \\
 +
\frac{\partial}{\partial \lambda}H(x_0,y_0,\lambda)=f(x_0,y_0)=0 \qquad (16)
</math>
</math>
 +
 +
が導かれる.制約条件付きの極値問題から,<math>\lambda</math>という人工的な変数を使って
 +
 +
<math>目的の関数+\lambda\times (制約条件を表す関数)</math>
 +
の制約条件のない場合の極値条件が導かれる.
 +
 +
ただしこの議論は「その点が最大(小)値を与える」<math>\Rightarrow</math>
 +
「その点が極値を与える」<math>\Rightarrow </math> 「その点での<math>微分係数=0</math>」
 +
 +
 +
という必要条件の連鎖であるので注意が必要である.
 +
 +
「<math>微分係数=0</math>」は必要条件であるから,
 +
これが満たされても,極値かどうかチェックの必要があり,さらには<math>H</math>の極値を与える<math>(x_0,y_0)</math>が求められたとしても,
 +
それが最大(小)値を与えるのか確かめる必要がある。
 +
 +
また,少なくとも<math>L</math>と<math>f</math>が<math>x,y</math>について微分可能であることも必要である.
 +
 +
ここで使われた<math>\lambda</math>はラグランジュ乗数と呼ばれる.
 +
上の問題に適用すると
 +
 +
 +
<math>f(x,y)=x^2+y^2 -1,L(x,y)=x+y</math>
 +
 +
拘束条件<math>f(x,y)=x^2+y^2 -1=0</math> を充たし,<math>L(x,y)=x+y</math>の極値を与える
 +
<math>x_0,y_0</math>が存在すると仮定すれば,
 +
 +
<math>x_0 \neq 0</math> または <math>y_0 \neq 0</math> であり,
 +
 +
陰関数の存在条件
 +
<math>\frac{\partial f}{\partial x}(x_0,y_0) = 2x_0 \neq 0 </math>
 +
または
 +
<math>\frac{\partial f}{\partial y}(x_0,y_0) = 2y_0 \neq 0 </math>
 +
が成り立っている.
 +
 +
そこで,
 +
 +
<math>H(x,y,\lambda)=x+y+\lambda (x^2+y^2 -1)</math>
 +
 +
とおけば
<math>
<math>
-
\frac{\partial}{\partial x_1}\bigl{[}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x}) \bigr{ ]} =0\\
+
1+ 2\lambda  x_0 = \frac{\partial}{\partial x}H(x_0,y_0,\lambda)=0  \qquad (17) \\
-
\frac{\partial}{\partial x_2}\bigl{[}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x}) \bigr{ ]} =0 \\
+
1+ 2\lambda  y_0 = \frac{\partial}{\partial y}H(x_0,y_0,\lambda)=0  \qquad (18) \\
-
\cdots \\
+
x_0^2+y_0^2 -1 = \frac{\partial}{\partial \lambda}H(x_0,y_0,\lambda)=0 \qquad (19)
-
\frac{\partial}{\partial x_n}\bigl{[}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x})\bigr{ ]}=0
+
</math>
</math>
 +
 +
 +
<math>(17) </math>式から <math>\lambda \neq 0 </math> であり,
 +
 +
 +
<math>(18),(19) </math>式から
 +
 +
<math>x_0 = -\frac{1}{2\lambda} ,y_0 = -\frac{1}{2\lambda}</math>
 +
 +
これを<math>(19)</math> 式に代入して
 +
 +
<math>\frac{1}{2\lambda^2} -1 = 0</math>
 +
 +
よって
 +
 +
<math>\lambda=\frac{\sqrt{2}}{2} </math> または <math>\lambda=-\frac{\sqrt{2}}{2} </math>
 +
 +
<math>\lambda=\frac{\sqrt{2}}{2} </math> のとき<math>x_0 = y_0= -\frac{\sqrt{2}}{2}</math> であり,<math>L(x_0,y_0)=x_0+y_0= -\sqrt{2} </math>
 +
 +
<math>\lambda=-\frac{\sqrt{2}}{2} </math> のとき<math>x_0 = y_0= \frac{\sqrt{2}}{2}</math> であり,<math>L(x_0,y_0)=x_0+y_0= \sqrt{2} </math>
 +
 +
 +
従って
 +
等式拘束条件
 +
<math>x^2+y^2=1 </math>
 +
の下で<math>L(x,y)=x+y </math> の
 +
最大値は<math>x = y= \frac{\sqrt{2}}{2}</math>のときで<math>\sqrt{2} </math>
 +
 +
Microsoft Excel のソルバーで解くこともできる.
 +
 +
データの入力とソルバーのパラメータは以下の通りである.解析には非線形問題を選択する.
 +
[[ファイル:LP-Fig50.1.jpg|800px]]
 +
 +
ソルバーの出力は以下の通りであり前期の解析解と同じである.
 +
 +
[[ファイル:LP-Fig50.2.jpg|800px]]
 +
 +
上記の議論を一般化したものが以下である.
 +
44 行: 267 行:
</math>
</math>
-
が一次独立とする.このとき,一変数関数の場合と同様,以下が成立つ.すなわち,
+
が一次独立とする.これは前項の<math>(4)</math>式の陰関数の存在条件
 +
<math>\frac{\partial f}{\partial y}(x_0,y_0)\neq 0 \qquad (4)</math>
 +
に相当する.
 +
 
 +
<math>m</math>個の<math>n</math>次元
 +
ベクトルからなる<math> n\times m </math>行列
 +
<math>
 +
\Bigl{[} \frac{\partial g_1 }{\partial {\bf x}}(\bar{\bf x}),
 +
\frac{\partial g_2 }{\partial {\bf x}}(\bar{\bf x}),
 +
\cdots,\frac{\partial g_m }{\partial {\bf x}}(\bar{\bf x})
 +
\Bigr{]}
 +
</math>
 +
の階数が<math> m </math> であることと同値である.
 +
 
 +
 
 +
 
 +
このとき,一変数関数の場合と同様,以下が成立つ.すなわち,
<math>m</math>次元のラグランジュ乗数ベクトル
<math>m</math>次元のラグランジュ乗数ベクトル
62 行: 301 行:
<math>
<math>
-
\frac{\partial}{\partial x_1}\bigl{\{}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x}) \bigr{ \}} =0\\
+
\frac{\partial}{\partial x_1}\bigl{[}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x}) \bigr{]} =0\\
-
\frac{\partial}{\partial x_2}\bigl{\{}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x})\bigr{ \}}=0 \\
+
\frac{\partial}{\partial x_2}\bigl{[}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x}) \bigr{]} =0 \\
\cdots \\
\cdots \\
-
\frac{\partial}{\partial x_n}\bigl{\{}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x})\bigr{ \}}=0  
+
\frac{\partial}{\partial x_n}\bigl{[}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x})\bigr{]}=0  
</math>
</math>
-
が成りたつ.
 
 +
が成りたつ.
==不等式拘束のある問題==
==不等式拘束のある問題==
81 行: 320 行:
</math>
</math>
-
を定義しておく.この(正錐)</math>P</math>を使って,<math>{\bf p},{\bf q} \in R^m</math>の
+
を定義しておく.この(正錐)<math>P</math>を使って,<math>{\bf p},{\bf q} \in R^m</math>の
順序(大小)を
順序(大小)を
87 行: 326 行:
{\bf p} \ge {\bf q} \Leftrightarrow {\bf p} - {\bf q} \in P
{\bf p} \ge {\bf q} \Leftrightarrow {\bf p} - {\bf q} \in P
</math>
</math>
 +
で定義する.
で定義する.
-
<math>R^n<math>から<math>R^m</math>への微分可能な写像
+
<math>R^n</math>から<math>R^m</math>への微分可能な写像
<math>
<math>
108 行: 348 行:
不等式制約
不等式制約
 +
<math>G({\bf x})  
<math>G({\bf x})  
=
=
131 行: 372 行:
\right )
\right )
</math>
</math>
 +
について,この項では以下のクーン・タッカーの条件が成立つものとする.
について,この項では以下のクーン・タッカーの条件が成立つものとする.
 +
 +
===クーン・タッカーの条件===
<math>
<math>
-
G({\bf x}) \le {\bf 0}を充たす任意の{\bf x} \in R^nについて \\
+
G({\bf x}) \le {\bf 0}
-
G({\bf x})+ \frac{d G}{d {\bf x}}^T({\bf x}) {\bf k}となる
+
-
{\bf k}=(k_1,k_2,\cdots,k_n)^T \in R^nが
+
-
存在する.\\
+
</math>
</math>
 +
を充たす任意の<math>{\bf x} \in R^n</math>について
 +
 +
<math>G({\bf x})+ \frac{d G}{d {\bf x}}^T({\bf x}) {\bf k} \lt 0 </math>
 +
 +
となる
 +
<math> {\bf k}=(k_1,k_2,\cdots,k_n)^T \in R^n</math>が存在する.
ただし,
ただし,
 +
<math>
<math>
163 行: 411 行:
</math>
</math>
-
<math>G({\bf x}) \le {\bf 0}<math/>
+
ここで,
 +
<math>G({\bf x}) \le {\bf 0}</math>
は順序(大小関係)を
は順序(大小関係)を
171 行: 420 行:
{\bf p} \ge {\bf q} \Leftrightarrow {\bf p} - {\bf q} \in P
{\bf p} \ge {\bf q} \Leftrightarrow {\bf p} - {\bf q} \in P
</math>
</math>
 +
定義する場合,
定義する場合,
179 行: 429 行:
と同値になる.
と同値になる.
 +
 +
===停留条件===
 +
 +
以上のクーン・タッカーの条件下で,
 +
微分可能な写像
微分可能な写像
189 行: 444 行:
<math>\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)</math>
<math>\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)</math>
-
で極少(極大)値をとるものとすると,<math>m</math>次元のラグランジュ乗数ベクトル
+
で極小(極大)値をとるものとすると,<math>m</math>次元のラグランジュ乗数ベクトル
<math>
<math>
203 行: 458 行:
</math>
</math>
-
は,<math>\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)</math>で停留条件を充たす.
+
は,<math>\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)</math>で極値条件(停留条件)を充たす.
すなわち
すなわち
 +
<math>
<math>
\frac{d l}{d {\bf x}}(\bar{\bf x})+ \frac{d G}{d {\bf x}}(\bar{\bf x})
\frac{d l}{d {\bf x}}(\bar{\bf x})+ \frac{d G}{d {\bf x}}(\bar{\bf x})

2021年1月2日 (土) 16:44 時点における最新版

目次

[非表示]

等式拘束のある問題

陰関数定理とラグランジュ乗数

以下の問題を考える.


L(x,y)=x+yとするとき, 半径1の円周

x2+y2=1(1)

上の点(x,y)L(x,y)=x+yの最大にするものを求めよ.


関数の極値条件

実数値関数F(x)x=x0で極小値または極大値をとり,かつ,x=x0で微分可能であれば,

F(x)x=x0での微分係数は0である。

dFdx(x0)=0


陰関数

半径1の円の方程式

x2+y2=1(1)

に注目する。判りやすいように,

1x1,1y0 としておく.

g(x)=1x2 とすると, 1x1,1y0では(1)の方程式を満たすx,yについては y=g(x) という関係が成り立っている.

このg(x)という関数は,(1)式の中には出てこない.(1)からこのように間接的に導き出される関数を陰関数と呼ぶ.


一般化すれば特定の条件のもとに f(x,y)=0という式から陰関数y=g(x)が定義される。

上の例では f(x,y)=x2+y21

しかし,何時でも上の例のように,f(x,y)=0から陰関数y=g(x)が定義されるわけではない.

陰関数定理

ある領域DR×Rで関数f(x,y)が連続でかつ,x,yについて偏微分可能で, その偏導関数

fx(x,y)(1)

fy(x,y)(2)

(x,y)について連続とする。

D内の1点(x0,y0)

f(x0,y0)=0

であり,

fy(x0,y0)0(4)

とする. このとき,x0を含む開区間(a,b)とその上の連続関数g(x)が存在し,

1) 開区間(a,b)上でf(x,g(x))=0

2) y0=g(x0)

3) 開区間(a,b)上で,

dydx=f/xf/y(5)


上の定理でx,yの役目を反対にすれば,x0=g(y0) となる陰関数の存在が示される.

ラグランジュ乗数法

関数L(x,y)が,制約条件 f(x,y)=0 の元に(x,y)=(x0,y0)で極値(極大値か極小値)をとるとする。

L(x,y)(x,y)について微分可能な関数で, 関数f(x,y)(x0,y0)が上の陰関数定理を適用できる条件を満たしているものとする。 x0の近傍で関数g(x)が存在して,x0のその近傍では f(x,g(x))=0 が成り立ち,y0=g(x0),f(x0,g(x0))=0も成り立っている. x,yの役目を反対にすれば,x0=g(y0) となる陰関数を用いることになるが議論は全く同様に できる.


関数L(x,y)(x0,y0)で極値(極大値か極小値)をとるから F(x)=L(x,g(x))x=x0で極値を取る.


極値条件により

dFdx(x0)=0(6)

である.

このxについての微分を求めるとF(x)=L(x,g(x))は合成関数であるから

dFdx(x0)=xL(x0,g(x0))+yL(x0,g(x0))ddxg(x0)(7)dydx=f/xf/y(8)

y=g(x)であるから(8)式を上の(7)式に代入し


λ=yL(x0,g(x0)){fy(x0,g(x0))}1(9)

という変数を使うと,

0=dFdx(x0)=xL(x0,g(x0))+λxf(x0,g(x0))(10)

また

λyf(x0,g(x0)=yL(x0,g(x))(11)

から

0=yL(x0,g(x0))+λyf(x0,g(x0))(12)

すなわちλという新しい変数を使って

H(x,y,λ)=L(x,y)+λf(x,y)(13)

という関数を造ると:

関数L(x,y)が制約条件f(x,y)=0 を充たすという条件の下に (x,y)=(x0,y0)で極値(極大値か極小値)をとる という条件からHについての制約のない場合の極値条件

xH(x0,y0,λ)=0(14)yH(x0,y0,λ)=0(15)λH(x0,y0,λ)=f(x0,y0)=0(16)


が導かれる.制約条件付きの極値問題から,λという人工的な変数を使って

+λ×() の制約条件のない場合の極値条件が導かれる.

ただしこの議論は「その点が最大(小)値を与える」 「その点が極値を与える」 「その点での=0


という必要条件の連鎖であるので注意が必要である.

0」は必要条件であるから, これが満たされても,極値かどうかチェックの必要があり,さらにはHの極値を与える(x0,y0)が求められたとしても, それが最大(小)値を与えるのか確かめる必要がある。

また,少なくともLfx,yについて微分可能であることも必要である.

ここで使われたλはラグランジュ乗数と呼ばれる. 上の問題に適用すると


f(x,y)=x2+y21,L(x,y)=x+y

拘束条件f(x,y)=x2+y21=0 を充たし,L(x,y)=x+yの極値を与える x0,y0が存在すると仮定すれば,

x00 または y00 であり,

陰関数の存在条件 fx(x0,y0)=2x00 または fy(x0,y0)=2y00 が成り立っている.

そこで,

H(x,y,λ)=x+y+λ(x2+y21)

とおけば

1+2λx0=xH(x0,y0,λ)=0(17)1+2λy0=yH(x0,y0,λ)=0(18)x20+y201=λH(x0,y0,λ)=0(19)


(17)式から λ0 であり,


(18),(19)式から

x0=12λ,y0=12λ

これを(19) 式に代入して

12λ21=0

よって

λ=22 または λ=22

λ=22 のときx0=y0=22 であり,L(x0,y0)=x0+y0=2

λ=22 のときx0=y0=22 であり,L(x0,y0)=x0+y0=2


従って 等式拘束条件 x2+y2=1 の下でL(x,y)=x+y の 最大値はx=y=22のときで2

Microsoft Excel のソルバーで解くこともできる.

データの入力とソルバーのパラメータは以下の通りである.解析には非線形問題を選択する.

ソルバーの出力は以下の通りであり前期の解析解と同じである.

上記の議論を一般化したものが以下である.


l:(x1,x2,,xn)Rn↦∈R

ˉx=(ˉx1,ˉx2,,ˉxn)m個の制約条件

g1(ˉx1,ˉx2,,ˉxn)=0g2(ˉx1,ˉx2,,ˉxn)=0g3(ˉx1,ˉx2,,ˉxn)=0gm(ˉx1,ˉx2,,ˉxn)=0

のもとでの極少(極大)値をとるものとする.さらにm個のn次元 ベクトル

g1x(ˉx)T=(g1x1(ˉx),g1x2(ˉx),g1xn(ˉx))g2x(ˉx)T=(g2x1(ˉx),g2x2(ˉx),g2xn(ˉx))g3x(ˉx)T=(g3x1(ˉx),g3x2(ˉx),g3xn(ˉx))gmx(ˉx)T=(gmx1(ˉx),gmx2(ˉx),gmxn(ˉx))

が一次独立とする.これは前項の(4)式の陰関数の存在条件 fy(x0,y0)0(4) に相当する.

m個のn次元 ベクトルからなるn×m行列 [g1x(ˉx),g2x(ˉx),,gmx(ˉx)] の階数がm であることと同値である.


このとき,一変数関数の場合と同様,以下が成立つ.すなわち, m次元のラグランジュ乗数ベクトル

λ=(λ1,λ2,,λm) が存在し,

l(x)+λ1g1(x)+λ2g2(x)++λmgm(x)

ˉx=(ˉx1,ˉx2,,ˉxn)で停留条件を充す.

すなわち

x1[l(x)+λ1g1(x)+λ2g2(x)++λmgm(x)]=0x2[l(x)+λ1g1(x)+λ2g2(x)++λmgm(x)]=0xn[l(x)+λ1g1(x)+λ2g2(x)++λmgm(x)]=0


が成りたつ.

不等式拘束のある問題

前項では,等式拘束問題を扱った.この項では不等式拘束問題を扱う. 先ず,Rmの部分集合

P={p|p=(p1,p2,,pm)TRm,p10,p20,,pm0}

を定義しておく.この(正錐)Pを使って,p,qRmの 順序(大小)を

pqpqP

で定義する.

RnからRmへの微分可能な写像

G:x=(x1,x2,,xn)RnG(x)=(g1(x)g2(x)g3(x)gm(x))Rm で定義されるものとする.

不等式制約

G(x)=(g1(x)g2(x)g3(x)gm(x))0=(0000)

について,この項では以下のクーン・タッカーの条件が成立つものとする.


クーン・タッカーの条件

G(x)0 を充たす任意のxRnについて

G(x)+dGdxT(x)k<0

となる k=(k1,k2,,kn)TRnが存在する.

ただし,


dGdxT(x)=(g1x1(x)g1x2(x)g1xm(x)g2x1(x)g2x2(x)g2xm(x)gmx1(x)gmx2(x)gmxn(x))

ここで, G(x)0 は順序(大小関係)を

P={p|p=(p1,p2,,pm)TRm,p10,p20,,pm0}pqpqP

定義する場合,

g1(x)0,g2(x)0,g3(x)0,,gm(x)0

と同値になる.

停留条件

以上のクーン・タッカーの条件下で,


微分可能な写像 l:(x1,x2,,xn)Rn↦∈R

が不等式制約G(x)0 のもとで

ˉx=(ˉx1,ˉx2,,ˉxn) で極小(極大)値をとるものとすると,m次元のラグランジュ乗数ベクトル

λ=(λ1,λ2,,λm)0 が存在し,

l(x)+G(x)λ=l(x)+λ1g1(x)+λ2g2(x)++λmgm(x)

は,ˉx=(ˉx1,ˉx2,,ˉxn)で極値条件(停留条件)を充たす.


すなわち

dldx(ˉx)+dGdx(ˉx)λ=(lx1(ˉx)lx2(ˉx)lxn(ˉx))+(g1x1(x)g2x1(x)gmx1(x)g1x2(x)g2x2(x)gmx2(x)g1xn(x)g2xn(x)gmxn(x))(λ1λ2λm)=(000)

が成りたつ.

さらにˉx=(ˉx1,ˉx2,,ˉxn)については,

G(ˉx)λ=λ1g1(ˉx)+λ2g2(ˉx)++λmgm(ˉx)=0

が成立つ.

λ=(λ1,λ2,,λm)0

λ10,λ20,,λm0

と同値になる.

個人用ツール