経済数学（法政用）：第１１章
細矢祐誉
テーマ：最適化理論（ＫＫＴ定理）
・復習：ラグランジュ未定乗数法の原理
前章までの内容を思い出してみよう。まず、標準的な消費者の効用最大化問題

maxf (x)subject to. x ∈ Rn+ ,p·x≤m(1)と、それに付随するラグランジュ関数

L(x, λ) = f (x) + λ(m − p · x)(2)を考えよう。このとき、次の二つの関係を論じていたのだった。

1. x∗ は問題 (1) の最大点である。
2. ある λ∗ が存在して、DL(x∗ , λ∗ ) = 0T である。
たとえば、1. から 2. を導出する証明を（概略だけ）振り返ってみよう。ここでは、x∗ ≫ 0が (1) の最大点であるとし、v ∈ Rn で、ただし p · v = 0 であるとする。このとき、

x(t) = x∗ + tv として、g(t) = f (x(t)) とすると、|t| > 0 が十分 0 に近ければ x(t) ≥ 0であり、また

p · x(t) = p · x∗ + tp · v = p · x∗ ≤ mである。よって、

g(t) = f (x(t)) ≤ f (x∗ ) = f (x(0)) = g(0)が成り立つ。したがって g は 0 で極大になるので、g ′ (0) = 0 である。合成微分の公式
から

0 = g ′ (0) = Df (x∗ )vとなる。つまり、p · v = 0 ⇒ Df (x∗ )v = 0 がわかったのであり、ここから容易に、あるλ∗ が存在してDf (x∗ ) = λ∗ pTが成り立つことがわかる。これはDx L(x∗ , λ∗ ) = 0Tを意味する。一方で f が増加的（つまり x ≫ y なら f (x) > f (y)）であれば p · x∗ = mでしかあり得ないので、

0 = m − p · x∗ = Dλ L(x∗ , λ∗ )となり、合わせてDL(x∗ , λ∗ ) = 0Tを得る。ここまでで使っている仮定を整理すると、• x∗ ≫ 0 である。
• f は x∗ で全微分可能である。
• f は増加的である。
以上であり、これだけ成り立っていれば 1. から 2. が導出できることになる。
今度は 2. から 1. を導出する理屈を考えてみよう。いま、Dλ L(x∗ , λ∗ ) = 0 なので、

m = p · x∗ である。一方で Dx L(x∗ , λ∗ ) = Df (x∗ ) − λ∗ pT = 0 なので、Dx L(x∗ , λ∗ ) = λ∗ pTであることがわかる。ここで背理法の仮定として、ある x ≥ 0 について、p · x ≤ m かつf (x) > f (x∗ ) であったと仮定してみよう。f が連続であるとすれば、x をほんの少しだけすべての座標を減らしても f (x) > f (x∗ ) という関係を維持できるので、我々は p · x < mを仮定できる。ここで x(t) = (1 − t)x∗ + tx と定義し、g(t) = f (x(t)) とする。f が準凹であれば、0 ≤ t ≤ 1 に対してg(t) = f ((1 − t)x∗ + tx) ≥ min{f (x), f (x∗ )} = f (x∗ ) = g(0)であるため、ここからg(t) − g(0)≥0t↓0tg ′ (0) = limがわかる。一方で合成微分の公式から

g ′ (0) = Df (x∗ )(x − x∗ ) = λ∗ [p · x − p · x∗ ] = λ∗ [p · x − m]がわかる。よって、p · x < m より、λ∗ ≤ 0 がわかるが、もし f が増加的で Df (x∗ ) ̸= 0であればこれはあり得ない。以上をまとめると、• f は連続で準凹、増加的である。
• f は x∗ で微分可能で、Df (x∗ ) ̸= 0 である。

この条件があれば、2. から 1. を導出できる。ここまでが標準のセットアップであった。
・非線形制約問題
経済学には、(1) 以外の形をした問題がたくさん出てくる。たとえば、(1) の双対問題として紹介される支出最小化問題

minp·ysubject to. y ∈ Rn+ ,f (y) ≥ f (x)は、(1) と異なる点がふたつある。一つ目は max ではなく min である点だが、これはmax−p·ysubject to. y ∈ Rn+ ,f (y) ≥ f (x)と書き換えてしまえばそれだけで解決する問題なので、重要ではない。むしろ問題なのは、制約条件が p · x ≤ m ほど単純ではないということである。上で書いた証明において、たとえば 1. から 2. を導出するところについては、x(t) = x∗ + tv としたときに、

p · x(t) = p · x∗ ≤ m であることが非常に重要な役割を果たしていた。したがって、これが成り立たないかもしれない今回の状況では上のロジックは使えない。一方、2. から 1.
を導出するロジックについては、p · x < m であるならば、x(t) = (1 − t)x∗ + tx とした
ときに、Df (x∗ )(x − x∗ ) = λ∗ (p · x − m) と変形できて、λ∗ ≤ 0 が出てくることが、本質的に重要であった。これもまた、今回のセットアップではできそうにない。ではどうすればよいか？
もう少し複雑な問題を考えよう。たとえば、次のような問題がある。ここで pH , pL > 0
かつ pH + pL = 1 とし、また 0 < cL < cH とする。

max

pH [b(xH ) − wH ] + pL [b(xL ) − wL ]subject to. wH ≥ cH (xH ), wL ≥ cL (xL ),wH − cL (xH ) ≤ wL − cL (xL ), wL − cH (xL ) ≤ wH − cH (xH ).
これは、契約理論における「真実表明的な直接顕示メカニズム」の設計問題で出てくる問題である。橋をかける企業と政府が交渉しているとし、x は橋の品質、b(x) は品質によって保証される橋の社会的便益である。ただし企業が橋をかける費用は品質の関数であり、また pH の確率で cH で、pL の確率で cL である。cH と cL のどちらが真の費用関数かは、最初の段階では企業しか知らない。したがって政府は費用関数を聞き取り調査して、その後で相手のコストに合わせて要求品質 xH , xL と、企業に与える報酬 wH , wL を支払う。ここで、企業は自分のコストについて嘘をつくことができるので、政府はそれを勘案して報酬体系を作らなければならない。最初の制約は参加制約と呼ばれ、これを下回ると企業はコスト割れするため、橋の建設を拒否する。二番目の制約は誘因両立制約と呼ばれ、これが成り立っていないと企業は自分のコストについて嘘をつきたくなる。このふたつの条件を元にして最適品質と報酬を決めるのが政府の目的である。
この主の問題では、条件が複数あることに注意しよう。したがって、いままでで使った問題よりもさらに高度になる。これらの問題を解決する一般的原理とはなにか？
・問題の定式化
以上のところから、問題を定式化しよう。

max

f (x)

subject to. x ∈ A,(3)g(x) ≤ 0
これが今回考える問題である。ただし、A ⊂ Rn で、f : A → R とし、一方で g : A → Rmとする。g がベクトル値関数であるというのが、上で述べた多数の制約を扱えるという問題に対応している。
これに対して今度は、

L(x, λ) = f (x) + λT g(x)(4)と定義しよう。転置記号から明らかなように、今回はもはや λ は数ではなくてベクトルである。ここで、また次のようなふたつの仮説を対比してみよう。

1. x∗ は問題 (3) の最大点である。
2. ある λ∗ ≥ 0 について、Dx L(x∗ , λ∗ ) = 0T となる。さらに、λ∗i gi (x∗ ) = 0 が常に成り立つ。
今回の目的は、1. と 2. の同値性を示すことである。まず 1. から 2. の方向を考えてみよう。
定理１：x∗ は A の内部に位置し、問題 (3) の最大点であるとする。また、f は x∗ で微分可能、g は連続で x∗ の付近で連続微分可能であるとし、gi (x∗ ) = 0 となる座標 i の集合を E とした時、ベクトル族 (Dgi (x∗ ))i∈E は一次独立であるとする*1 。このとき、あるλ∗ ≥ 0 が存在して、Dx L(x∗ , λ∗ ) = 0T が成り立ち、また λ∗i gi (x∗ ) = 0 が常に成り立つ。
注意：定理１のうち、「x∗ が A の内部にある」という条件は、以前の「x∗ ≫ 0」という条件に対応している。f の微分可能性が必要なのは当たり前であるが、一方で、増加的という条件に対応する条件はない。その代わり、ベクトル族の一次独立性という、見慣れない条件が追加されている。これは、以前には、p ̸= 0 という条件に当たるもので、当たり前だったから仮定されていなかった。
証明：最初に、E が空集合であるときを考える。この場合、x∗ は f の極大点であるから、Df (x∗ ) = 0T である。したがって λ∗ = 0 とすれば主張が正しいことがわかる。
したがって以降、E は空集合でないとし、簡単のために番号を付け替えて、E ={1, 2, ..., k} ということにしておこう。もちろん、1 ≤ k ≤ m である。ここで、陰関数定理と呼ばれる次の補題を紹介する（証明は省略。なお、本当は陰関数定理はもっと細かい主張を多数含む）。
補題１：f : B → Rm とし、ただし B は Rn+m の部分集合とする。また、(x∗ , y ∗ ) は Bの内部に位置するとし、f (x∗ , y ∗ ) = a であるとし、また f は (x∗ , y ∗ ) の周囲で連続微分可能で、Dy f (x∗ , y ∗ ) は逆行列を持つ*2 とする。このとき、x∗ の近くで定義されたある関数 y(x) が存在して、以下の性質を満たす。

1) y(x∗ ) = y ∗ が成り立つ。
2) f (x, y(x)) = a が常に成り立つ。
3) y は連続微分可能である。

*1 一般に、ベクトル v1 , ..., vk が一次独立であるとは、

a1 v1 + ... + ak vk = 0となるような数の組 a1 , ..., ak が、a1 = ... = ak = 0 しか存在しないことを言う。
*2 一般にある行列 A に対して、

1
0
AB =  .
 ..
00
1.
..
0...
...
..
.
...

00
.
.. 1となる行列 B を A の逆行列と呼び、A−1 と書く。線形代数の教科書を参照。

さて、以降 ĝ = (g1 , ..., gk ) とし、ḡ = (gk+1 , ..., gm ) としよう。このとき、x∗ は問題(3) の解であるから、制約をきつくした以下の問題
maxf (x)subject to. x ∈ A,ĝ(x) = 0,ḡ(x) ≫ 0の解である。一方で、任意の x ∈ A に対して x̂ = (x1 , ..., xk ) とし、x̄ = (xk+1 , ..., xn )としよう。Dg1 (x∗ ), ..., Dgk (x∗ ) は一次独立なので、必要ならば座標の番号を付け替えることで、その最初の k 列を取り出してできる行列 Dx̂ g(x∗ ) が逆行列を持つと仮定してよい*3 。そこで陰関数定理からある関数 x̂(x̄) が存在して、g(x̂(x̄), x̄) = g(x∗ )を満たす。すると x̄ が十分 x̄∗ に近ければ x(x̄) = (x̂(x̄), x̄) は上の問題の制約条件を満たすので、f (x(x̄)) ≤ f (x∗ ) = f (x(x̄∗ ))がわかる。よって x̄∗ は合成関数 f ◦ x の極大点なので、そこでの微分は 0 になり、

Df (x∗ )Dx(x̄∗ ) = Dx̂ f (x∗ )Dx̂(x̄∗ ) + Dx̄ f (x∗ ) = 0がわかる。一方で、陰関数定理の帰結

g(x̂(x̄), x̄) = g(x∗ )を x̄ で微分して x̄ = x̄∗ を代入すると、

Dx̂ g(x∗ )Dx̂(x̄∗ ) + Dx̄ g(x∗ ) = 0がわかるので、整理すると

Dx̂(x̄∗ ) = −(Dx̂ g(x∗ ))−1 Dx̄ g(x∗ )がわかる。これを上に代入して、Dx̄ f (x∗ ) = Dx̂ f (x∗ )(Dx̂ g(x∗ ))−1 Dx̄ g(x∗ )*3 このあたりは線形代数の教科書で各自勉強して欲しい。

がわかる。一方で当然ながら

Dx̂ f (x∗ ) = Dx̂ f (x∗ )(Dx̂ g(x∗ ))−1 Dx̂ g(x∗ )なので、これを合わせれば、

Df (x∗ ) = Dx̂ f (x∗ )(Dx̂ g(x∗ ))−1 Dg(x∗ )がわかるので、

λ̂∗ = −([Dx̂ f (x∗ )(Dx̂ g(x∗ ))−1 ]T )と定義し、λ̄∗ = 0 とすれば、Df (x∗ ) + (λ∗ )T Dg(x∗ ) = 0となって、

Dx L(x∗ , λ∗ ) = 0がわかる。もちろん、gi (x∗ ) ̸= 0 ならば λ∗i = 0 なので、λ∗i gi (x∗ ) = 0 も成り立つ。
残っている問題は λ∗i ≥ 0 を示すことだけである。議論はすべて同じなので、λ∗1 ≥ 0 だけを示す。まず 1 ≤ i ≤ k に対して

{1 if i = 1,Dgi (x )y =0 otherwise.
∗となるベクトル y を取る（このようなベクトルが存在することは一次独立性から示せるが、今回はその証明は省略する）。そして、ふたたび ĝ = (g1 , ..., gk ) として、

h(z, η) = ĝ(x∗ + ηy + (Dĝ(x∗ ))T z) − ηDĝ(x∗ )yと定義する。このとき、

h(0, 0) = ĝ(x∗ ) = 0, Dz h(0, 0) = Dĝ(x∗ )(Dĝ(x∗ ))Tとなる。この Dz h(0, 0) は逆行列を持つことが簡単に証明できる。よって 0 の付近で定義されたある連続微分可能な関数 ξ が存在して、ξ(0) = 0, ĝ(x∗ + ηy + (Dĝ(x∗ ))T ξ(η)) = ηDĝ(x∗ )yが常に成り立つ。これを η で微分して η = 0 と置くと、

Dĝ(x∗ )(y + (Dĝ(x∗ ))T Dξ(0)) = Dĝ(x∗ )yがわかるので、整理すると

Dĝ(x∗ )(Dĝ(x∗ ))T Dξ(0) = 0がわかる。両辺に Dĝ(x∗ )(Dĝ(x∗ ))T の逆行列を左から掛けることで、Dξ(0) = 0がわかる。そこで今度はx(η) = x∗ + ηy + (Dĝ(x∗ ))T ξ(η)と定義すると、ξ の定義からĝ(x(η)) = ηDĝ(x∗ )y = (η, 0, ..., 0)である。よって η ≥ 0 が十分 0 に近いならば、x(η) は問題 (3) の制約条件を満たす。x∗は問題 (3) の最大点なので、そのような η に対してf (x(η)) ≤ f (x∗ ) = f (x(0))
であり、よって、

f (x(η)) − f (x(0))
≤0
η↓0
η

Df (x∗ )y = Df (x∗ )x′ (0) = limがわかる。一方で、

Df (x∗ ) + (λ∗ )T Dg(x∗ ) = 0
なので、この両辺に y を掛けると、Df (x∗ )y + λ∗1 = 0がわかり、よって

λ∗1 = −Df (x∗ )y ≥ 0である。以上で証明が完成した。 ■続いて 2. から 1. への証明を行う。こちらは上の複雑な証明よりは、少しばかり簡単である。
定理２：A は凸集合で、x∗ は A の内部に属しているとし、f, g は共に準凹で連続*4 、x∗で微分可能であるとし、また (4) 式の L が、ある λ∗ ≥ 0 に対して、Dx L(x∗ , λ∗ ) = 0T*4 g が準凹というのは、gi がすべて準凹という意味である。

であり、かつ λ∗i gi (x∗ ) = 0 がすべての i = 1, ..., m について成り立つとする。さらにDf (x∗ ) ̸= 0 であるとする。このとき、x∗ は問題 (3) の最大点である。
注意：A が凸集合であるという条件があるが、これは以前には A に当たるものが Rn+ という、当たり前のように凸集合であるものだったから必要がなかった。一方、Df (x∗ ) ̸= 0が必要なのは相変わらずである。また x∗ が A の内部に属しているという条件が、どうしても必要であった。これは後に出てくる z が A に属していないと証明が破綻するからであるが、以前は x∗ よりほんの少しだけ少ない数を取れば z の用を足せたので、やはり必要なかった。
証明：いま x ∈ A, g(x) ≥ 0 であるとする。このとき、x(t) = (1 − t)x∗ + tx と定義すると、準凹性の条件から 0 ≤ t ≤ 1 のときにgi (x(t)) ≥ min{gi (x), gi (x∗ )} ≥ 0となるので、x(t) は (3) の制約条件を満たす。ここで gi (x∗ ) = 0 ならば gi (x(t)) ≥ gi (x∗ )なので、gi (x(t)) − gi (x(0))≥0t↓0tDgi (x∗ )(x − x∗ ) = limである。よって特に、m∑λ∗i Dgi (x∗ )(x − x∗ ) ≥ 0i=1がわかる。一方で、Dx L(x∗ , λ∗ ) = Df (x∗ ) + (λ∗ )T Dg(x∗ ) = 0 なので、ここから∗∗

Df (x )(x − x ) = −m∑λ∗i Dgi (x∗ )(x − x∗ ) ≤ 0i=1がわかることになる。
さて、c > 0 を十分小さく取り、w = −cDf (x∗ ) として、z = x∗ + w と定義しよう。cが十分小さければ z ∈ A が成り立つ。明らかに

Df (x∗ )(z − x∗ ) = Df (x∗ )w = −c∥w∥2 < 0であることに注意が必要である。ここで、y(t) = (1 − t)x + tz, x(t) = (1 − t)x∗ + tzと定義する。もし 0 < t < 1 であれば、Df (x∗ )(x(t) − x∗ ) = tDf (x∗ )(z − x∗ ) < 0,

Df (x∗ )(y(t) − x(t)) = (1 − t)Df (x∗ )(x − x∗ ) ≤ 0となるので、まとめるとDf (x∗ )(y(t) − x∗ ) < 0がわかる。
ここでもし f (y(t)) > f (x∗ ) であったとすれば、z(s) = (1 − s)x∗ + sy(t) とすると、

f (z(s)) ≥ min{f (y(t)), f (x∗ )} = f (x∗ )なので、f (z(s)) − f (z(0))≥0s↓0s0 > Df (x∗ )(y(t) − x∗ ) = limとなって矛盾が生ずる。よって、f (y(t)) ≤ f (x∗ ) である。t → 0 とすれば f の連続性からf (x) ≤ f (x∗ )を得ることになるが、x は (3) の制約条件を満たす任意の点であったのだから、x∗ は問題(3) の最大点である。以上で証明が完成した。 ■