Document

条件付最適化
• 経済学の基本的な問題は、希少な資源を、
如何に用いて、なんらかの目的を達成する
か
• 希少な資源は、ある種の制約に対応
• 目的の達成は、最適化に対応
• 経済学で多くの問題が、制約付の最適化問
題に帰着
ラグランジュ乗数法
f  x1,..., xn 
n変数の実数値関数
を
m個の等式制約
g1  x1 ,..., xn   0,
.....
g m  x1 ,..., xn   0
の下で最大化
m n
制約だけで、変数が決まらない
ラグランジュ乗数法のレシピ
1.ラグランジュアンを作る
L  x1 ,..., xn ; 1 ,..., m   f  x1 ,..., xn 
1 g1  x1 ,..., xn   ....  m g m  x1 ,..., xn 
1 ,..., m
ラグランジュ乗数
2.ラグランジュアンを各変数で(偏)微分して0とおく
L  x1 ,..., xn ; 1 ,..., m   f  x1 ,..., xn 
1 g1  x1 ,..., xn   ....  m g m  x1 ,..., xn 
微分して0とおく
L  x1 ,..., xn ; 1 ,..., m 
x1

f  x1 ,..., xn 
.....
x1
 1
g1  x1 ,..., xn 
x1
 ....  m
L  x1 ,..., xn ; 1 ,..., m 
xn

f  x1 ,..., xn 
xn
 1
g1  x1 ,..., xn 
xn
 ....  m
g m  x1 ,..., xn 
x1
g m  x1 ,..., xn 
xn
0
0
3.方程式を解くか解釈する
f  x1 ,..., xn 
g1  x1 ,..., xn 
gm  x1 ,..., xn 
 1
 ....  m
0
x1
x1
x1
.....
f  x1 ,..., xn 
g1  x1 ,..., xn 
gm  x1 ,..., xn 
 1
 ....  m
0
xn
xn
xn
n本の式
m個の等式制約とあわせ
n+m個の変数
x1,..., xn , 1,..., m が決まる
ラグランジュ乗数法の説明(2変数1制約)
max f  x, y  st g  x, y   0
レベル曲線(無差別曲
線) を描く
a0  a1  a2  a3
y
ここは、もっと
大きいが制約
を満たさない
f  x, y   a3
f  x, y   a2
C
制約を描くfの値が大きくなる
D
f  x, y   a1
f  x, y   a0
A
B
制約の下では、ここが最大
g  x, y   0
fの値が大きくなる
x
y
f  x, y   a3
f  x, y   a2
制約の下では、ここが最大
f  x, y   a1
f  x, y   a0
A
傾きが等しい
g  x, y   0
レベル曲線の傾きを求める
x
f  x, y  x   a1
両辺を微分
f x  x, y  x   f y  x, y  x  y '  x   0
f x  x, y 
y ' x  
f y  x, y 
レベル曲線の傾きを求める
f  x, y  x   a1
両辺を微分
f x  x, y  x   f y  x, y  x  y '  x   0
同様に
f x  x, y 
y ' x  
f y  x, y 
g  x, y   0 に対応するレベル曲線の傾きは
g x  x, y 

g y  x, y 
傾きが一致する
f x  x, y  g x  x, y 

f y  x, y  g y  x, y 
f x  x, y  f y  x, y 

g x  x, y  g y  x , y 
f x  x, y  f y  x, y 


g x  x, y  g y  x , y 
ラグランジュ乗数法の結果と比べる
L  f  x, y    g  x, y  ラグランジュアン
xとyで(偏)微分して0とおく
L
 f x  x, y    g x  x, y   0
x
L
 f y  x, y    g y  x , y   0
y
分母が0のときは、入れ替える
両方とも0だと困る
f x  x, y    gx  x, y 
f y  x, y    g y  x, y 
ラグランジュ乗数法の説明(一般的な場合)
記法は重たいがチェックは難しくない
max f  x1,..., xn 
st
g1  x1 ,..., xn   0,
.....
g m  x1 ,..., xn   0
仮定
g1
x1
g1
x2
g1
xm
g 2
x1
g 2
x2
g 2
xm  0
g m
x1
g m
x2
g m
xm
必要ならば変数の
順番を入れ替える
どう並べ替えてもつぶ
れるケースは厄介
二変数で一制約で、双方の
偏導関数が0の場合が対応
陰関数定理を適用
g1 1  xm1 ,..., xn  ,..., m  xm1 ,..., xn  , xm1 ,..., xn   0,
.....
g m 1  xm1 ,..., xn  ,..., m  xm1 ,..., xn  , xm1 ,..., xn   0
を最初の点の近傍で満たす 1  xm1,..., xn  ,..., m  xm1,..., xn 
が存在
g1 1  xm1 ,..., xn  ,..., m  xm1 ,..., xn  , xm1 ,..., xn   0,
.....
g m 1  xm1 ,..., xn  ,..., m  xm1 ,..., xn  , xm1 ,..., xn   0
両辺を微分
 g1
 x
 1
 g 2
 x
 1


 g m
 x
 1
g1
x2
g 2
x2
g m
x2
g1  1
xm  xm 1

g 2   2
xm 
 xm 1


g m   m
xm 
 xm 1
1
xm  2
 2
xm  2
 m
xm  2
1 
 g1
 x
xn 

 m 1
 g 2
 2 
xn     xm 1




 m 
 g m
 x
xn 
 m 1
g m
g1 1 g1 2
g1

 ...  m

0
x1 xm1 x2 xm1
xm xm1 xm1
g1
xm  2
g 2
xm  2
g m
xm  2
などを纏めたもの
g1 
xn 

g 2 
xn 


g m 
xn 
極大(小)条件は
f 1  xm1,..., xn  ,..., m  xm1,..., xn  , xm1,..., xn 
の条件無し最適化
微分して0
 f

 x1
f
x2
 1
 x
 m 1
  2
f  
 xm 1
xm  


  m
 x
 m 1
1
xm  2
 2
xm  2
 m
xm  2
1 
xn 

 2 
 f
xn    
 xm 1


 m 
xn 
f 1
f 2
f m
f

 ... 

0
x1 xm1 x2 xm1
xm xm1 xm1
f
xm  2
などを纏めたもの
f 

xn 
 f

 x1
f
x2
f 
   1 2
xm 
 g1
 x
 1
 g 2

m   x1


 g m
 x
 1
最適化の条件から
 f

 xm 1
f
xm  2
 f
f 




xn 
 x1
f
x2
g1
x2
g 2
x2
g m
x2
 1
 x
 m 1
  2
f  
  xm 1
xm 


  m
 x
 m 1
g1 
xm 

g 2 
xm 


g m 
xm 
1
xm  2
 2
xm  2
 m
xm  2
となる
1 2
が存在
1 
xn 

 2 
xn 


 m 
xn 
m 
 f

 xm 1
f
xm  2
 f
f 




xn 
 x1
f
x2
 f

 x1
   1 2
 g1
 x
 1
 g 2

m   x1


 g m
 x
 1
g1
x2
g 2
x2
g m
x2
 1
 x
 m 1
  2

f 
 xm 1
xm  


  m
 x
 m 1
f
x2
1
xm  2
 2
xm  2
 m
xm  2
f 
   1 2
xm 
g1  1
xm  xm 1

g 2   2
xm 
 xm 1


g m   m
xm 
 xm 1
1
xm  2
 2
xm  2
 m
xm  2
1 
xn 

 2 
xn 


 m 
xn 
 g1
 x
 1
 g 2

m   x1


 g m
 x
 1
1 
xn 

 2 
xn 


 m 
xn 
g1
x2
g 2
x2
g m
x2
g1 
xm 

g 2 
xm 


g m 
xm 
 f

 xm 1
f
xm  2
f 
    1 2
xn 
 g1
 x
 1
 g 2
 x
 1


 g m
 x
 1
  1 2
 g1
 x
 m 1
 g 2

m   xm 1


 g m
 x
 m 1
g1
x2
g 2
x2
g m
x2
g1
xm  2
g 2
xm  2
g m
xm  2
 g1
 x
 1
 g 2

m   x1


 g m
 x
 1
g1  1
xm  xm 1

g 2   2
xm 
 xm 1


g m   m
xm 
 xm 1
g1 
xn 

g 2 
xn 


g m 
xn 
g1
x2
g 2
x2
g m
x2
1
xm  2
 2
xm  2
 m
xm  2
g1  1
xm  xm 1

g 2   2
xm 
 xm 1


g m    m
  x
xm 
m 1
1 
 g1

 x
xn

 m 1
 g 2
 2 

xn     xm 1




 m 
 g m
 x
xn 
 m 1
1
xm  2
1 
xn 

 2 
xn 


 m 
xn 
 2
xm  2
 m
xm  2
g1
xm  2
g 2
xm  2
g m
xm  2
g1 
xn 

g 2 
xn 


g m 
xn 
 f

 x1
f
x2
f 
   1 2
xm 
と
 f

 xm 1
は
f
xm  2
f 
   1 2
xn 
 g1
 x
 1
 g 2

m   x1


 g m
 x
 1
 g1
 x
 m 1
 g 2

m   xm 1


 g m
 x
 m 1
g1
x2
g 2
x2
g m
x2
g1
xm  2
g 2
xm  2
g m
xm  2
g1 
xm 

g 2 
xm 


g m 
xm 
g1 
xn 

g 2 
xn 


g m 
xn 
g m 
g 2
f  g1
  1
 2
 ...  m
  0, i  1,..., n
xi  xi
xi
xi 
と同じ
g m 
g 2
f  g1
  1
 2
 ...  m
  0, i  1,..., n
xi  xi
xi
xi 
L  x1 ,..., xn ; 1 ,..., m 
 f  x1 ,..., xn   1 g1  x1 ,..., xn   ....  m g m  x1 ,..., xn 
を 各 xi , i  1,..., n について微分して0
ラグランジュ乗数法
極大化の二階(十分)条件
縁付のヘッセ行列についての行列式についての条件

 0



 0


  g1
 x
1

 g1
  x
2



  g1
 x
n

0

g1
x1

g1
x2
0

g m
x1

g m
x2
g
 m
x1
2 L
x12
2 L
x1x2
g m
x2
2
 L
x2 x1
 L
x2 2
g
 m
xn
2 L
xn x1
2 L
xn x2

2
g1 
xn 



g m 

xn 

2
 L 
x1xn 

2
 L 
x2 xn 


2 L 
xn 2 

縁付のヘッセ行列
0
0

g1
x1
0
0

g m  0
x1
g
 1
x1
g
 m
x1
0
0
かつ
2 L
x12


g1
x1
g m
x1


調べてわかればOK
0
0

g1
x1

g1
x2

g1
xn
0
0

g m
x1

g m
x2

g m
xn
g1
x2
g m
x2 ,
0
0
g
 1
x1
g
 m
x1
2 L
x12
2 L
x1x2
g
 1
x2
g
 m
x2
2 L
x2 x1
2 L
x2 2
g1
,
x1
g
 m
x1
2 L
x12
2 L
x1x2
2 L
x1xn
g
 1
x2
g
 m
x2
2 L
x2 x1
2 L
x2 2
2 L
x2 xn
g
 1
xn
g
 m
xn
2 L
xn x1
2 L
xn x2
2 L
xn 2
プラスとマイナスが一階おきに現れれば極大、すべてマイナスな
らば、極小
例1 家計の理論
n 財の数
x1 ,..., xn
各財の消費量
u  x1,..., xn 
連続微分可能
 x ,..., x  u  x ,..., x   u  が
1
n
1
各
u0
n
0
について凸集合
uは準凹関数
家計の問題
u  x1,..., xn 
I
を
所得
p1 ,..., pn
を与えられたものとして
予算制約
p1 x1  ....  pn xn  I
で最大化
2財の場合
u  x, y  を px  qy  I
無差別曲線(レベル曲線の一種)
各
u0
に対して
を満たす
u  x, y   u0
 x, y 
の組合せ
の制約で最大化
無差別曲線の傾き
y    x, u0 
u0に対応する無差別曲線
u  x,  x, u0   u0
恒等式
両辺をxで微分
  x, u0 
ux  x,  x, u0    u y  x,  x, u0  
0
x
  x, u0  u x  x,  x, u0  


x
u y  x,  x, u0  
限界代替率
  x, u0  u x  x,  x, u0  


x
u y  x,  x, u0  
限界的にxの消費を減らしたときに
効用を一定にするために、必要な、
yの増加量
第2財の第1財で計った限界代替率
無差別曲線の傾き
 x, y  u  x, y   u 
0
が凸集合だと右の形
消費者選択
予算制約
px  qy  I
I
q
の下での効用最大化
B
D
予算線と無差別曲線の接点Aが解
A
予算線と無差別曲線の傾きが等しい
C
I
p
I p
y  x
q q
  x, u0  ux  x, y  p



x
u y  x, y  q
消費者選択(ラグランジュ乗数法)
限界代替率=価格比が機械的に出る
max u  x, y 
ラグランジュアン
st px  qy  I
L  u  x, y     px  qy  I 
ux  x, y  p

u y  x, y  q
両辺をxとyで微分して0とおく
L u  x, y 

p  0
x
x
L u  x, y 

 q  0
y
y
ux  x, y    p
uy  x, y   q
消費者選択(n財のケース)
max u  x1,..., xn 
限界代替率=価格比
st p1 x1  ....  pn xn 
ラグランジュアン
が任意のペアにつ
I いて成立
L  u  x1,..., xn     p1x1  ....  pn xn  I 
x1 ,...., xn で微分して0とおく
L u  x1 ,..., xn 

  pi  0
xi
xi
u  x1 ,..., xn 
 ui  x1 ,..., xn    pi
xi
ui  x1 ,..., xn  pi

u j  x1 ,..., xn  p j
例2消費者選択(Cobb Douglas 効用関数)
max u  x, y   x y
st px  qy  I

1
ラグランジュアン

1
Lx y
   px  qy  I 
xとyで微分して0とおく
L
 1 1
x y p  0
x
L
 1    x y    q  0
y
x
p
 1 1
y
1   x

y

 q
x
 1 1
y
1   x

x
p
y

x y

1
x y
   px  qy    I

代入
1
x y

I
 I  px
1   I  qy
  px
 1
1


x

 y   qy
 q  y

1
α、1-αは支出割合
n財のケース
max x1 x2 ....xn   i 1 xi
Σが和でΠは積
st p1 x1  ....  pn xn  I
1
n
2
n
i
ラグランジュアン
L  x1 x2 ....xn    p1x1  ....  pn xn  I 
x1 ,...., xn で微分して0とおく
1
n
2
L
  j x j 1
x j
 j xj
1

n


i
x
i1 i   p j  0
n
x
i 1 i
i
p
j
 j xj
1

n
x
i
i 1 i
p

j
j
x j
 j 1 j
n


x
   
n
i
i 1 i
   j 1 p j x j  I
n
i
x
i1 i
n

代入
 j I  pj xj

i
x
i1 i   p j x j
n
I
n
j 1
 j 1
i
x
i 1 i
n

例3 効用関数の序数性
max u  x1,..., xn 
st p1 x1  ....  pn xn  I
の解を

1
n
とし
を厳密な増加関数とすると
 x ,..., x  は
1
 x ,..., x 
n
max  u  x1,..., xn 
st p1 x1  ....  pn xn  I
の解
対数線形効用関数
1
2
n
max x1 x2 ....xn
と

1
2
st p1 x1  ....  pn xn  I
max ln x1 x2 ....xn
n

n
i 1
 i ln  xi 
st p1 x1  ....  pn xn  I
は同じ
max  i 1 i ln  xi 
n
st p1 x1  ....  pn xn  I
ラグランジュアン
L   i 1 i ln  xi     p1 x1  ....  pn xn  I 
n
x1 ,...., xn
L i
   pi  0
xi xi
で微分して0とおく
i   pi xi
1   i 1 i    i 1 pi xi   I
n
このほうが簡単に出る
n
i I  pi xi
1

I
経済学へのラグランジュ乗数法の適用
• 前のスライドのように明確に解ける例は、少
ない
• 「家計は、限界代替率と価格比を等しくする」
というタイプの命題
• ありがたみが理解しにくい。
一階の条件と比較静学
• 目的関数と制約がパラメータに依存し、その
変化によって変わるというとき、最適解が如
何に変化するか
max f  x1,..., xn ,1,..., k 
st
g1  x1 ,..., xn , 1 ,...,  k   0,
.....
g m  x1 ,..., xn , 1 ,...,  k   0
ラグランジュアン
1 ,...,  k
パラメーター
L  x1 ,..., xn ; 1 ,..., m ; 1 ,...,  k 
 f  x1 ,..., xn , 1 ,...,  k 
1 g1  x1 ,..., xn , 1 ,...,  k   ....  m g m  x1 ,..., xn , 1 ,...,  k 
L  x1 ,..., xn ; 1 ,..., m ; 1 ,...,  k 
 f  x1 ,..., xn , 1 ,...,  k 
1 g1  x1 ,..., xn , 1 ,...,  k   ....  m g m  x1 ,..., xn , 1 ,...,  k 
x1 ,..., xn で微分して0とおき一階の条件を求める
f  x1 ,..., xn , 1 ,...,  k 
g1  x1 ,..., xn , 1 ,...,  k 
g m  x1 ,..., xn , 1 ,...,  k 
 1
 ....  m
0
x1
x1
x1
.........
f  x1 ,..., xn , 1 ,...,  k 
g  x ,..., xn , 1 ,...,  k 
g  x ,..., xn , 1 ,...,  k 
 1 1 1
 ....  m m 1
0
xn
xn
xn
f  x1 ,..., xn , 1 ,...,  k 
g1  x1 ,..., xn , 1 ,...,  k 
g m  x1 ,..., xn , 1 ,...,  k 
 1
 ....  m

x1
x1
x1
.........
f  x1 ,..., xn , 1 ,...,  k 
g1  x1 ,..., xn , 1 ,...,  k 
g m  x1 ,..., xn , 1 ,...,  k 
 1
 ....  m

xn
xn
xn
一階の条件(n本)
g1  x1 ,..., xn , 1 ,...,  k   0,
.....
制約(m本)
g m  x1 ,..., xn , 1 ,...,  k   0
i について微分すると
xn 1
m
x1
,...,
,
,...,
についての nm本の連立方程式
i
i i
i
全部を
これを解くと最適化する変数に対するパラメータの変化の限界的
な効果が得られる
例 費用関数
min rK  wL
st F  K , L  Y
生産量を一定にして、費用最小化
ラグランジュアン
rK  wL   F  K , L  Y 
ラグランジュアン
rK  wL   F  K , L  Y 
KとLで(偏)微分して0
r   FK  K , L
w   FL  K , L
一階の条件
FK , FL
偏導関数
rの変化の効果を見る
F  K , L  Y
r   FK  K , L
w   FL  K , L
rで(偏)微分
制約
一階の条件
λも変化することを
忘れないこと
K
L
FK  K , L 
 FL  K , L 
0
r
r

K
L
1
FK  K , L    FKK  K , L 
  FKL  K , L 
r
r
r

K
L
0
FL  K , L    FLK  K , L 
  FLL  K , L 
r
r
r
K
L
FK  K , L 
 FL  K , L 
0
r
r

K
L
1
FK  K , L    FKK  K , L 
  FKL  K , L 
r
r
r

K
L
0
FL  K , L    FLK  K , L 
  FLL  K , L 
r
r
r
 K L
,
,
r r r
について解くとr (資本賃料)の上がる効果が
得られる
一般の場合はややこしい
生産関数が一次同次のときは次次章
非線形計画法とクーン・タッカー条件
max f  x1,..., xn 
st
g1  x1 ,..., xn   0,
.....
制約が不等号
g m  x1 ,..., xn   0
この問題が非線形計画法(non linear
programming)
m<nは仮定しない⇒普通は有効な制約はnより小さい
目的と制約がすべて一次式なのは線形計画
法で、シンプレックス法で解く
ラグランジュアン
L  x1 ,..., xn ; 1 ,..., m   f  x1 ,..., xn 
1 g1  x1 ,..., xn   ....  m g m  x1 ,..., xn 
各変数で微分して0とおく
L  x1 ,..., xn ; 1 ,..., m  f  x1 ,..., xn 

x1
x1
g1  x1 ,..., xn 
g m  x1 ,..., xn 
1
 ....  m
0
x1
x1
....
L  x1 ,..., xn ; 1 ,..., m  f  x1 ,..., xn 

xn
xn
g1  x1 ,..., xn 
g m  x1 ,..., xn 
1
 ....  m
0
xn
xn
f  x1 ,..., xn 
g1  x1 ,..., xn 
g m  x1 ,..., xn 
 1
 ....  m
0
x1
x1
x1
....
f  x1 ,..., xn 
g  x ,..., xn 
g  x ,..., xn 
 1 1 1
 ....  m m 1
0
xn
xn
xn
この一階の条件以外に、以下のスラック条件が出る
g1  x1 ,..., xn   0, 1  0, 1 g1  x1 ,..., xn   0
.....
g m  x1 ,..., xn   0, m  0, m g m  x1 ,..., xn   0
スラック条件
g1  x1 ,..., xn   0, 1  0, 1 g1  x1 ,..., xn   0
.....
g m  x1 ,..., xn   0, m  0, m g m  x1 ,..., xn   0
i  0  gi  x1,..., xn   0
制約が有効
gi  x1,..., xn   0  i  0 制約が無効
ラグランジュ乗数の意味と制約の有効無効
max x1 ,..., xn f  x1,..., xn 
st
g1  x1 ,..., xn   T1 ,
.....
g m  x1 ,..., xn   Tm
 v T1,..., Tm 
最大値の値
v T1 ,..., Tm 
 i
Ti
v T1 ,..., Tm 
 i
Ti
ラグランジュ乗数は、制約が限界的にゆるんだとき
の目的関数の増加
スラック条件
i  0  gi  x1,..., xn   Ti 制約が有効
制約が限界的
に緩むと目的
関数が増える
制約が限界的
gi  x1,..., xn   Ti  i  0 制約が無効
に緩んでも目
的関数は増え
ない
gi  x1,..., xn   Ti & i  0 の場合は、排除できないが、実際は少ない
非線形計画法について
• 一階の条件とスラック条件が必要条件であるための
条件、十分条件であるための条件は複雑
十分条件
x1 ,..., xn ; 1 ,...,  m
x1 ,..., xn
必要条件
ある
x1 ,..., xn
1 ,...,  m
が一階の条件とスラック条件を満たす
が解
が解
があって
x1 ,..., xn ; 1 ,...,  m
が一階の条件とスラック条件を満たす
非線形計画法について
• 一階の条件とスラック条件が必要条件であるための
条件、十分条件であるための条件は複雑
• 必要条件は関数と制約が行儀がいい以外、制約想
定という付加的な条件が必要
• 微妙なときに教科書をしらべればいい。
• 例 マンガサリアンの「非線形計画法」
• 実際は複雑な場合わけ
例
max u  x, y   2 x  1  2 y  1
px  qy  I , x  0, y  0
ラグランジュアン
2 x  1  2 y  1    px  qy  I   x x   y y
符号の向きに注意
xとyで微分して0とおく
1
  p  x ,
x 1
1
 q   y
y 1
1
1
  p  x ,
 q   y
x 1
y 1
一階の条件
スラック条件
  0, x  0, y  0
xx  0, y y  0
両辺にxとyをかけて加える
 px  qy  I    0
x

x 1
y
   px  qy    x x   y y
y 1
x

x 1
y
 I
y 1
x

x 1
y
 I
y 1
 0 x  y 0
x  0, y  0
1
1
  p  x ,
 q   y
x 1
y 1
x  y  1
x  0,  y  0
と矛盾
 0
 0
 px  qy  I    0
px  qy  I
ケース1
x  0, y  0
xx  0, y y  0
x   y  0
1
1
  p  x ,
 q   y
x 1
y 1
1
1
  p,
 q
x 1
y 1
1
1
  p,
 q
x 1
y 1
1
1
x  2 2  1, y  2 2  1
 p
 q
px  qy  I
p
q
1  1 1
px  qy  2 2  p  2 2  q  2     p  q  I
 p
q
  p q
 1 1
1

  ,
I  pq  p q
1
1
x
 I  p  q   1, y 
 I  p  q  1
1
1
2 1
2 1
p   
q   
 p q
 p q
ケース2
I
y
q
x  0, y  0
px  qy  I
1
1
  p  x ,
 q   y
x 1
y 1
1
1   p  x ,
 q
I
1
q
1

,
I
q
1
q
p
x   p 1 

I
q
1
q
yy  0  y  0
p
q  I  q
1  0
p  q  I  q
ケース3
対称性から
q
p  I  p
なら
I
y  0, x 
p
まとめると
I
p  q  I  q  なら x  0, y 
q
I
y  0, x 
q  p  I  p  なら
p
それ以外なら
x
1
 I  p  q   1,
1
2 1
p   
 p q
y
1
 I  p  q  1
 1 1
p2   
 p q