応用解析学参考資料クーン・タッカーの定理

(1)

応用解析学参考資料

クーン・タッカーの定理

Ver. 1, 2009/01/03,

西岡

1

不等式制約条件付きの最適化問題

不等式の制約条件が付いた最適化問題を考える

.

この問題は等式制約条件付きの最適値問題より格段に複雑である

.

1.1

クーン・タッカーの定理

問題

1.1 (

不等式制約条件付きの最適化問題

).

滑らかな関数

f(x, y), g(x, y)

と実数

b

が与えられている

.

このとき

(1.1) max

(x,y)

f (x, y) subjects to g(x, y) ≤ b

の値と最適解

(x

^∗

, y

^∗

)

をもとめよ

. ⋄

•

^{この問題も最適解}

(x

^∗

, y

^∗

)

の満たす十分条件を調べて

,

最適解の候補者を探す方法で解決できる

.

ただ一般に

,

等式制約条件の場合より候補者の数が多くなる

.

•

^{前と同様に}

(1.1)

に対応するラグランジュ関数を

(1.2) L(x, y, λ) ≡ f (x, y) + λ (

b − g(x, y) )

で定義する^*1

.

定理

1.2 (

クーン・タッカー

).

不等式制約条件付き最適化問題

(1.1)

の最適解

(x

^∗

, y

^∗

)

が

| g

x

(x

^∗

, y

^∗

) | + | g

y

(x

^∗

, y

^∗

) | ̸ = 0

を満たしている

.

このとき

,

ある

λ

^∗

∈ R

¹ が存在して

,

次が成立する

:

L

x

(x

^∗

, y

^∗

, λ

^∗

) = f

x

(x

^∗

, y

^∗

) − λ

^∗

g

x

(x

^∗

, y

^∗

) = 0, L

_y

(x

^∗

, y

^∗

, λ

^∗

) = f

_y

(x

^∗

, y

^∗

) − λ

^∗

g

_y

(x

^∗

, y

^∗

) = 0, L

λ

(x

^∗

, y

^∗

, λ

^∗

) = b − g(x

^∗

, y

^∗

) ≥ 0 and λ

^∗

≥ 0, λ

^∗

L

_λ

(x

^∗

, y

^∗

, λ

^∗

) = λ

^∗

(

b − g(x

^∗

, y

^∗

) )

= 0. ⋄ (1.3)

注意

1.3.

「等式制約条件」の最適値問題と

(1.3)

の第

3

式

,

第

4

式が異なる

. ⋄

1.2

クーン・タッカーの定理の解説

Step 1.

本来の「不等式制約条件」

max

(x,y)

f (x, y) subjects to g(x, y) ≤ b

*1 (1.1)で制約条件が逆の不等式g(x, y)≥bならラグランジュ関数は(1.2)と別のものとなる.この点が, 等式制約条件の場

合と異なる.

(2)

に

s ≡ b − g(x, y)

を代入して見かけ上「等式制約条件」に変える

.

(1.4) max

(x,y)

f (x, y) subjects to g(x, y) + s = b, s ≥ 0.

この見かけ上は「等式制約条件の最適値問題」を考える

. Step 2. (1.4)

の最適値を

x

^∗

, y

^∗

, s

^∗ とする

.

制約条件下で

,

x

^∗

→ x

^∗

+ ∆x, y

^∗

→ y

^∗

+ ∆y, s

^∗

→ s

^∗

+ ∆s

という微小変動を行う

.

テイラー展開から

0 ≥ f (x

^∗

+ ∆x, y

^∗

+ ∆y) − f (x

^∗

, y

^∗

)

= f

_x

(x

^∗

, y

^∗

) ∆x + f

_y

(x

^∗

, y

^∗

) ∆y + small order terms.

(1.5)

一方

,

制約条件から

0 = b − b

= {

g(x

^∗

+ ∆x, y

^∗

+ ∆y) + s

^∗

+ ∆s }

− {

g(x

^∗

, y

^∗

) + s

^∗

}

= g

x

(x

^∗

, y

^∗

) ∆x + g

y

(x

^∗

, y

^∗

) ∆y + ∆s + small order terms.

small order terms

を無視すると

,

∆x = − g

_y

(x

^∗

, y

^∗

)

g

x

(x

^∗

, y

^∗

) ∆y − ∆s g

x

(x

^∗

, y

^∗

)

これを

(1.5)

に代入して

0 ≥ {

− g

_y

(x

^∗

, y

^∗

)

g

x

(x

^∗

, y

^∗

) f

_x

(x

^∗

, y

^∗

) + f

_y

(x

^∗

, y

^∗

) }

∆y

− f

x

(x

^∗

, y

^∗

)

g

x

(x

^∗

, y

^∗

) ∆s + small order terms.

(1.6)

Step 3. (1.6)

で

∆s = 0

とおくと

,

− λ

^∗

g

y

(x

^∗

, y

^∗

) + f

y

(x

^∗

, y

^∗

) = 0, λ

^∗

= f

x

(x

^∗

, y

^∗

)/g

x

(x

^∗

, y

^∗

).

(1.7)

Step 4. (1.6)

で

∆y = 0

とおく

.

Case 1. s

^∗

= 0

のとき

, ∆s > 0

なので

, f

x

(x

^∗

, y

^∗

)

g

x

(x

^∗

, y

^∗

) = λ

^∗

≥ 0.

Case 2. s

^∗

> 0

のとき

, ∆s

は正の値も負の値もとるので

, f

x

(x

^∗

, y

^∗

)

g

_x

(x

^∗

, y

^∗

) = λ

^∗

= 0.

この

Case 1, 2

を纏めて書くと

λ

^∗

≥ 0, s

^∗

≥ 0, λ

^∗

· s

^∗

= 0.

s

^∗

= b − g(x

^∗

, y

^∗

)

に注意すると

, Step 3 + Step 4

から

(1.3)

が得られる

. 2

•

^{この定理}

(

クーン・タッカー

)

から

,

問題

1.1

の解

(x

^∗

, y

^∗

)

が次の手順で求められることが判った

:

==========

(3)

Step 1. (1.3)

を満たす

(x

^∗

, y

^∗

, λ

^∗

)

をすべて見つける

.

定理

1.2

より

,

これらの

(x

^∗

, y

^∗

, λ

^∗

)

が最適解の候補者である

.

Step 2. Step 1

で求めた

(x

^∗

, y

^∗

, λ

^∗

)

を実際に

f (x, y)

に代入し

,

真の最適解を決定する

.

==========

例題

1.4.

不等式制約条件付きの最適化問題

max (

x

²

+ y )

subjects to g(x, y) = x

²

+ y

²

≤ 1

の最適値と最適解を求めよ

.

[

解答

]

この場合のラグランジュ関数は

L(x, y, λ) = x

²

+ y + λ (

1 − x

²

− y

²

)

となる

. (1.3)

より最適解の候補者を求めよう

.

0 = L

x

(x, y, λ) = 2x − 2λx, 0 = L

y

(x, y, λ) = 1 − 2λy, 0 ≤ L

λ

(x, y, λ) = 1 − x

²

− y

²

, λ ≥ 0,

0 = λ L

λ

(x, y, λ) = λ (

1 − x

²

− y

²

) .

第

1

式より

, x ̸ = 0, λ = 1

もしくは

x = 0 .

一方

,

第

2

式より

, λ ̸ = 0, y = 1/2λ

が判る

. Case 1. x = 0

の場合

.

第

5

式より

0 = λ(1 − (1/2λ)

²

) → λ = ± 1/2.

第

3, 4

式も考慮すると

, (x, y, λ) = (0, 1, 1/2).

Case 2. x ̸ = 0, λ = 1

の場合

.

第

2

式より

y = 1/2.

ついで第

5

式より

0 = 1 · (1 − x

²

− ( 1

2 )

²

) = 3

4 − x

²

→ x = ±

√ 3 2 .

これは第

3, 4

式を満たしているから

(x, y, λ) = ( ±

^√₂³

,

¹₂

, 1)

以上がが最適解の候補者となる

.

この候補者を実際に

f (x, y)

に代入して

, (x

^∗

, y

^∗

) = ( ± √

3/2, 1/2)

が最適解

(

二つある

),

最適値は

5/4

である

. 2

2

最適化問題の応用

企業および消費者の行動を最適化問題の立場から説明する

.

I.

消費者の行動

個人の消費者が

2

種類の商品

X, Y

を量

x, y

だけ消費する

.

彼は予算制約の下で

,

自己の満足

(=

効用

)

が最大になる

ように行動する

.

ここで満足の度合いは

,

効用関数

u(x, y)

で表現出来るとする

.

効用関数は消費が多ければ

,

満足が大きいので

,

u(x, y)

は

x, y

の増加関数

⇔ u

x

(x, y) ≥ 0, u

y

(x, y) ≥ 0

.

(4)

例題

2.1.

消費者の予算を

m,

効用関数を

u(x, y) = x

²

y

としたときの

,

消費者の行動を調べる

.

商品

X

の価格を

P

X

, Y

の価格を

P

Y とすると

,

消費者の行動は

,

次の最適解である

:

(2.1) max

x≥0, y≥0

u(x, y) subjects to P

X

x + P

Y

y ≤ m

この

(2.1)

に対応するラグランジュ関数は

L(x, y, λ) = x

²

y + λ (

m − P

X

x − P

Y

y )

となり

,

クーン・タッカーの定理

1.2

から

0 = L

_x

(x, y, λ) = 2x y − λP

_X

, 0 = L

_y

(x, y, λ) = x

²

− λP

_Y

, 0 ≤ L

λ

(x, y, λ) = m − P

X

x − P

Y

y, λ ≥ 0

0 = λ L

_λ

(x, y, λ) = λ (

m − P

_X

x − P

_Y

y ) . u(0, y) = 0

だから

x ̸ = 0.

よって第

1

式と第

2

式から

2x y P

X

= λ = x

²

P

Y

⇒ x = 2P

_Y

P

X

y

第

5

式から

0 = m − P

_X

× 2P

_Y

P

X

y − P

_Y

y ⇒ y = m 3P

Y

, x = 2m 3P

X

つまり最適解

(x

^∗

, y

^∗

)

は

(2m/3P

X

, m/3P

Y

). 2

II.

企業の行動

企業は

,

資本

K

と労働

L

から製品を量

q

だけを生産する

.

ここで企業は資本と労働量の制約の下で

,

利潤が最大になる

ように行動する

.

例題

2.2.

生産量

q

は

q = 6 K

^1/3

L

^1/2

で表される

(=

生産関数

).

いま

,

生産物の価格

p,

資本の価格^*2

r,

労働の価格^*3

w

とすると

,

企業の利潤

π(K, L) = p q − r K − w L = 6 p K

^1/3

L

^1/2

− r K − w L

制約条件

K ≥ 0, L ≥ 0

の下で

, π(K, L)

を最大にする

.

まず極値は次式を満たしている

.

0 = π

_K

(K, L) = 2 p K

⁻^2/3

L

^1/2

− r, 0 = π

_L

(K, L) = 3 p K

^1/3

L

⁻^1/2

− ω

これから

,

(K

^∗

, L

^∗

) = ( 6

³

p

⁶

r

³

w

³

, 18

²

p

⁶

r

²

w

⁴

)

.

*2 資本を借りるための賃貸率.

*3 賃金率

(5)

この

(K

^∗

, L

^∗

)

で極大値をとるか調べる

. π

KK

(K, L) = − 4

3 p K

⁻^5/3

L

^1/2

⇒ π

KK

(K

^∗

, L

^∗

) < 0 π

LL

(K, L) = − 2

3 p K

^1/3

L

⁻^3/2

⇒ π

LL

(K

^∗

, L

^∗

) < 0

H (K, L) ≡ π

_KK

(K, L) × π

_LL

(K, L) − π

_KL

(K, L)

²

= p

²

K − 4/3 L

⁻¹

⇒ H (K

^∗

, L

^∗

) > 0

となるから

,

ヘシアンによる判定より極大値となることが示された

. 2

3

練習問題

3.1.

次の不等式制約条件付き最適化問題を解け

. (i) max( x

²

+ y

²

) subject to 2x

²

+ y

²

≤ 4.

(ii) max( x

²

+ y ) subject to 2x

²

+ y

²

≤ 4.

(iii) max (

2(x − y)

²

− x

⁴

− y

⁴

)

subject to x

²

+ y

²

≤ 5.

解答

(i)

ラグランジュ関数は

L(x, y, λ) = x

²

+ y

²

+ λ(4 − 2x

²

− y

²

)

となる

. λ ≥ 0

として

,

(a) 0 = L

x

(x, y, λ) = 2x − 4λx (b) 0 = L

_y

(x, y, λ) = 2y − 2λy (c) 0 ≤ L

λ

(x, y, λ) = 4 − 2x

²

− y

²

(d) 0 = λL

_λ

(x, y, λ) = λ(4 − 2x

²

− y

²

) (a)

より

, x(1 − 2λ) = 0

だから

, x = 0 or λ = 1/2.

Case 1. x = 0

のとき

, (d)

に代入すると

λ(4 − y

²

) = 0

であるから

, λ = 0 or y = ± 2

である

. λ = 0

のとき

, (b)

より

y = 0.

また

, y = ± 2

のとき

, (b)

より

λ = 1.

Case 2. λ = 1/2

のとき

, (b)

に代入すると

, y = 0

がわかる

.

さらに

λ, y

の値を

(d)

に代入すると

x = ± √

2

を得る

.

従って

,

(x, y, λ) = (0, 0, 0), (0, ± 2, 1), ( ± √ 2, 0, 1

2 )

.

これを実際に

f (x, y)

に代入し

(x

^∗

, y

^∗

) = (0, ± 2)

が最適解

,

最適値は

4

である

.

(ii)

L(x, y, λ) = x

²

+ y + λ(4 − 2x

²

− y

²

)

(6)

となる

. λ ≥ 0

として

,

(a) 0 = L

x

(x, y, λ) = 2x − 4λx (b) 0 = L

_y

(x, y, λ) = 1 − 2λy (c) 0 ≤ L

λ

(x, y, λ) = 4 − 2x

²

− y

²

(d) 0 = λL

_λ

(x, y, λ) = λ(4 − 2x

²

− y

²

)

(a)

より

, x(1 − 2λ) = 0

だから

, x = 0 or λ = 1/2.

また

, (b)

より

λy = 1/2 ̸ = 0

なので

, λ ̸ = 0

かつ

y ̸ = 0

でなければならない

.

すなわち

, (d)

より

(d

^′

) 4 − 2x

²

− y

²

= 0

である

.

Case 1. x = 0

のとき

, (d

^′

)

より

y

²

= 4.

すなわち

y = ± 2

を得る

.

これを

(b)

に代入して

λ = ± 1/4.

Case 2. λ = 1/2

のとき

, (b)

より

y = 1

を得る

.

これを

(d

^′

)

に代入して

x

²

= 3/2

ゆえに

x = ± √ 3/2

従って

,

(x, y, λ) = (0, ± 2, ± 1 4 ), ( ±

√ 3 2 , 1, 1

2 )

.

これを実際に

f (x, y)

に代入し

(x

^∗

, y

^∗

) = ( ±

√ 3 2 , 1)

が最適解

,

最適値は

5/2

である

.

(iii)

この最適値問題に対応するラグランジュ関数は

L(x, y, λ) = 2(x − y)

²

− (x

⁴

+ y

⁴

) + λ (5 − x

²

− y

²

).

これを

x, y, λ

について偏微分し

,

L

_x

(x, y, λ) = 4(x − y) − 4x

³

− 2λx = 0, (3.1)

L

y

(x, y, λ) = − 4(x − y) − 4y

³

− 2λy = 0, (3.2)

L

_λ

(x, y, λ) = 5 − x

²

− y

²

≥ 0, λ ≥ 0, (3.3)

λ (5 − x

²

− y

²

) = 0.

(3.4)

まず

(3.19)

より

λ = 0

もしくは

5 − x

²

− y

²

= 0

となる

. Step 1. λ = 0

とする

.

(3.16)

と

(3.17)

から

y = x − x

³

, x = y − y

³ となるので

,

x = y(1 − y)(1 + y) = (x − x

³

)(1 − x + x

³

)(1 + x − x

³

)

= x − 2x

³

+ 3x

⁵

− 3x

⁷

+ x

⁷

− x

⁹ この代数方程式をとき

, x

の値を求める

.

− 2x

³

+ 3x

⁵

− 3x

⁷

+ x

⁹

= x

³

(x

²

− 2)(1 − x

²

+ x

⁴

)

となるが

,

任意の

x

にたいし

1 − x

²

+ x

⁴

> 3/4

なので

, x = 0, x = ± √

2

が上の代数方程式の解である

.

つまり最適解の候補者として

(3.5) (x, y, λ) = (0, 0, 0), ( ± √

2, ∓ √

2, 0)

(7)

が得られたが

,

これらはいずれも

(3.18)

. Step 2.

次に

5 − x

²

− y

²

= 0

とする

.

まず

λ

を消去するため

, (3.16) × y - (3.17) × x

を計算する

. 0 = (3.16) × y - (3.17) × x = (

2y(x − y) − 2x

³

y )

− (

− 2x(x − y) − 2xy

³

)

= 2(x − y)(x + y)(1 − xy)

これより

, x = y, x = − y, 1 = xy

の解が得られた

. Case 1 x = y

とする

. x

²

+ y

²

= 5

と合わせると

, (3.6) x

²

+ y

²

= 2x

²

⇒ (x, y) = ( ± √

5/2, ± √ 5/2)

一方

(3.16) + (3.17)

より

λ(x + y) = − 2x

³

− 2y

³

= − 2(x + y)(x

²

− xy + y

²

)

ここで

(3.21)

にたいしては

, x + y ̸ = 0, x ̸ = 0

である

.

すると

λ = − 2(x

²

− xy + y

²

) < 0

となるので

, (3.18)

に反し

, (3.21)

は最適解の候補者ではない

.

Case 2 x = − y

とする

. (3.21)

と同様の計算で

(3.7) (x, y) = ( ± √

5/2, ∓ √ 5/2).

一方

(3.16) − (3.17)

より

λ(x − y) = 4(x − y) − 2(x

³

− y

³

) = 2(x − y) (

2 − (x

²

+ xy + y

²

) ) (3.22)

にたいしては

, x − y ̸ = 0

だから

,

(3.8) λ = 2 (

2 − (x

²

+ xy + y

²

) )

ところがこの式に

(3.22)

を代入すると

, λ = − 1

となり

, (3.18)

に反する

.

よって

(3.22)

.

Case 3 xy = 1

とする

.

(x + y)

²

= x

²

+ y

²

+ 2xy = 5 + 2 = 7, (x − y)

²

= x

²

+ y

²

− 2xy = 5 − 2 = 3

となるので

,

x + y = ± √

7, x − y = ± √ 3

⇒ (x, y) = (

√ 7 ± √ 3

2 ,

√ 7 ∓ √ 3

2 ), ( − √ 7 ± √

3 2 , − √

7 ∓ √ 3

2 ).

(3.9)

ここで

, (3.24)

にたいしては

, x − y ̸ = 0

だから

,

やはり

(3.23)

が成立している

.

ところが

, (3.23)

に

(3.24)

を代入すると

, λ = − 8

となり

, (3.18)

に反する

.

よって

(3.24)

.

Step 3.

結局

(3.20)

の組み合わせだけが

,

最適解の候補者として残った

. f (x, y) ≡ 2(x − y)

²

− x

⁴

− y

⁴ に

(3.20)

を代入し

,

f (0, 0) = 0, f ( √ 2, − √

2) = f ( − √ 2, √

2) = 8

を得る

.

これより最適解は

(x

^∗

, y

^∗

, λ

^∗

) = ( ± √ 2, ∓ √

2, 0)

であり

,

最適値は

8

である

. 2

(8)

練習問題

3.2.

次の不等式制約条件付き最適化問題を解け

. (i) max( x

²

+ y

²

) subject to x

²

+ 2y

²

≤ 4 and x ≤ 1.

[

ヒント

]:

L(x, y, λ

1

, λ

2

) = x

²

+ y

²

+ λ

1

(4 − x

²

− 2y

²

) + λ

2

(1 − x).

(ii) max( xy ) subject to 2x + y

²

≤ 3 and x ≥ 0.

(iii) max( 2x − y ) subject to x

²

− y ≤ 1 and x ≥ 0.

解答

(i)

ヒントよりラグランジュ関数は

L(x, y, λ

₁

, λ

₂

) = x

²

+ y

²

+ λ

₁

(4 − x

²

− 2y

²

) + λ

₂

(1 − x)

だから

, λ ≥ 0

として

,

(a) 0 = L

x

(x, y, λ

1

, λ

2

) = 2x − 4λ

1

x − λ

2

(b) 0 = L

_y

(x, y, λ

₁

, λ

₂

) = 2y − 4λ

₁

y (c) 0 ≤ L

λ1

(x, y, λ

1

, λ

2

) = 4 − x

²

− 2y

²

(d) 0 = λ

₁

L

_λ₁

(x, y, λ

₁

, λ

₂

) = λ

₁

(4 − x

²

− 2y

²

) (e) 0 ≤ L

λ₂

(x, y, λ

1

, λ

2

) = 1 − x

(f ) 0 = λ

2

L

λ₂

(x, y, λ

1

, λ

2

) = λ

2

(1 − x) (e)

より

x ≤ 1

に注意する

. (f )

から

, λ

2

= 0 or x = 1

である

.

Case 1. λ

2

= 0

のとき

, (a)

より

x(1 − λ

1

) = 0

なので

, x = 0 or λ

1

= 1

である

. (i) x = 0

のとき

(d)

より

, λ

1

(2 − y

²

) = 0

だから

λ

1

= 0 or y = ± √

2. ◦ λ

1

= 0 ⇒ (b)

より

y = 0.

◦ y = ± √

2 ⇒ (b)

より

λ

₁

= 1/2.

(ii) λ

₁

= 1

のとき

(b)

より

y = 0, (d)

に

λ

₁

, y

の値を代入して

, x = − 2 (x ≤ 1).

Case 2. x = 1

のとき

, (d)

より

λ

₁

(3 − 2y

²

) = 0.

これより

λ

₁

= 0 or y = ± √

3/2

である

. (i) λ

1

= 0

のとき

, (a)

より

λ

2

= 2, (b)

より

y = 0.

(ii) y = ± √

3/2

のとき

, (b)

より

λ

1

= 1/2, (a)

より

λ

2

= 1.

以上より

,

(x, y, λ

1

, λ

2

) = (0, 0, 0, 0, 0), (0, ± √ 2, 1

2 , 0), ( − 2, 0, 1, 0), (1, 0, 0, 2), (1, ±

√ 3

2 , 1/2, 1)

.

これを実際に

f (x, y)

に代入し

(x

^∗

, y

^∗

) = ( ± 2, 0)

が最適解

,

最適値は

4

である

.

(9)

(ii)

L(x, y, λ

1

, λ

2

) = xy + λ(3 − 2x − y

²

)

だから

, λ ≥ 0

として

,

(a) 0 = L

x

(x, y, λ) = y − 2λ (b) 0 = L

y

(x, y, λ) = x − 2λy (c) 0 ≤ L

_λ

(x, y, λ) = 3 − 2x − y

²

(d) 0 = λL

λ

(x, y, λ) = λ(3 − 2x − y

²

)

さらに

x ≥ 0

であることに注意する

. (a)

より

y = 2λ

を

(b)

に代入すると

x = 4λ

² が得る

.

これらを

(d)

に代入すると

, λ

だけの式を得られる

:

λ(3 − 2(4λ

²

) − 4λ

²

) = 0.

これを変形して

,

λ(1 − 2λ)(1 + 2λ) = 0.

λ ≥ 0

を考慮すると

, λ = 0 or λ = 1/2

である

.

Case 1. λ = 0

のとき

, (a)

より

y = 0, (b)

に

λ, y

の値を代入すると

x = 0

を得る

. Case 2. λ = 1/2

のとき

, (a)

より

y = 1, (b)

に

λ, y

の値を代入すると

x = 1

を得る

.

いずれの場合も

x ≥ 0

を満たす

.

従って

,

(x, y, λ) = (0, 0, 0), (1, 1, 1/2)

.

これを実際に

xy

に代入し

(x

^∗

, y

^∗

) = (1, 1)

が最適解

,

最適値は

1

である

.

(iii)

L(x, y, λ

1

, λ

2

) = 2x − y + λ

1

(1 − x

²

+ y) + λ

2

x

である

.

L

x

(x, y, λ

1

, λ

2

) = 2 − 2λ

1

x + λ

2

= 0, (3.10)

L

y

(x, y, λ

1

, λ

2

) = − 1 + λ

1

= 0, (3.11)

L

λ₁

(x, y, λ

1

, λ

2

) = 1 − x

²

+ y ≥ 0, λ

1

≥ 0, (3.12)

L

λ₂

(x, y, λ

1

, λ

2

) = x ≥ 0, λ

2

≥ 0, (3.13)

λ

1

(1 − x

²

+ y) = 0, λ

2

x = 0.

(3.14)

まず

(3.14)

より次の分類が得られる

:

Case 1: λ

1

= 0, λ

2

= 0, Case 2: 1 − x

²

+ y = 0, λ

2

= 0, Case 3: λ

1

= 0, x = 0, Case 4: 1 − x

²

+ y = 0, x = 0

ところが

(3.11)

より

Case 1

および

Case 3

は不可能

.

残された

Case 2, Case 4

を考える

. Case 2. 1 − x

²

+ y = 0, λ

₂

= 0

の場合

.

(3.11)

より

λ

1

= 1.

すると

(3.10)

より

x = 1,

さらに

y = 0

となる

.

つまり最適解の候補者は

(x, y, λ

₁

, λ

₂

) = (1, 0, 1, 0).

(10)

Case 4. 1 − x

²

+ y = 0, x = 0

の場合

.

すぐに

y = 1

が判る

.

また

(3.10)

から

λ

2

= − 2

となる

.

これは

(3.13)

に反する

.

結局

,

最適解は

(3.15) (x

^∗

, y

^∗

, λ

^∗₁

, λ

^∗₂

) = (1, 0, 1, 0).

であり

,

最適値は

2

である

.

ここで

(3.15)

が本当に最適値かどうかを確かめよう

. p, q

を微少な量として

,

最適解

(3.15) x

^∗

, y

^∗

, z

^∗ の近傍

x = 1 + p, y = 0 + q

での

f(x, y) = 2x − y

の値を調べる

.

ここで制約条件を考えると

,

x

²

− y ≤ 1 ⇒ (1 + p)

²

− q ≤ 1 ⇒ 2p − q ≤ − p

²

, x ≥ 0 ⇒ 1 + p ≥ 0 ⇒ p

は正負の値をとれるが成立している

.

これを考慮すると

f (1 + p, 0 + q) = 2(1 + p) − q = 2 + 2p − q = f (1, 0) + 2p − q ≤ f (1, 0) − p

²

≤ f (1, 0)

となる

.

従って

, (3.15)

が最適解である

. 2

(iii)

この最適値問題に対応するラグランジュ関数は

L(x, y, λ) = 2(x − y)

²

− (x

⁴

+ y

⁴

) + λ (5 − x

²

− y

²

).

これを

x, y, λ

について偏微分し

,

L

x

(x, y, λ) = 4(x − y) − 4x

³

− 2λx = 0, (3.16)

L

_y

(x, y, λ) = − 4(x − y) − 4y

³

− 2λy = 0, (3.17)

L

λ

(x, y, λ) = 5 − x

²

− y

²

≥ 0, λ ≥ 0, (3.18)

λ (5 − x

²

− y

²

) = 0.

(3.19)

まず

(3.19)

より

λ = 0

もしくは

5 − x

²

− y

²

= 0

となる

. Step 1. λ = 0

とする

.

(3.16)+(3.17)

から

y = x − x

³

, x = y − y

³ となるので

,

x = y(1 − y)(1 + y) = (x − x

³

)(1 − x + x

³

)(1 + x − x

³

)

= x − 2x

³

+ 3x

⁵

− 3x

⁷

+ x

⁷

− x

⁹ この代数方程式をとき

, (3.16)+ (3.17)

の解を求める

.

H(x) ≡ − 2x

³

+ 3x

⁵

− 3x

⁷

+ x

⁹

= x

³

(x

²

− 2)(1 − x

²

+ x

⁴

)

となる

.

任意の

x

にたいし

1 − x

²

+ x

⁴

> 3/4

なので

, x = 0, x = ± √

2

が解である

.

つまり最適解の候補者として

(3.20) (x, y, λ) = (0, 0, 0), ( ± √

2, ∓ √

2, 0)

が得られたが

,

これらはいずれも

(3.18)

.

(11)

Step 2.

次に

5 − x

²

− y

²

= 0

とする

.

まず

λ

を消去するため

, (3.16) × y - (3.17) × x

を計算する

. 0 = (3.16) × y - (3.17) × x = (

2y(x − y) − 2x

³

y )

− (

− 2x(x − y) − 2xy

³

)

= 2(x − y)(x + y)(1 − xy)

これより

, x = y, x = − y, 1 = xy

の解が得られた

. Case 1 x = y

とする

. x

²

+ y

²

= 5

と合わせると

, (3.21) x

²

+ y

²

= 2x

²

⇒ (x, y) = ( ± √

5/2, ± √ 5/2)

一方

(3.16) + (3.17)

より

λ(x + y) = − 2x

³

− 2y

³

= − 2(x + y)(x

²

− xy + y

²

)

ここで

(3.21)

にたいしては

, x + y ̸ = 0, x ̸ = 0

である

.

すると

λ = − 2(x

²

− xy + y

²

) < 0

となるので

, (3.18)

に反し

, (3.21)

.

Case 2 x = − y

とする

. (3.21)

と同様の計算で

(3.22) (x, y) = ( ± √

5/2, ∓ √ 5/2).

一方

(3.16) − (3.17)

より

λ(x − y) = 4(x − y) − 2(x

³

− y

³

) = 2(x − y) (

2 − (x

²

+ xy + y

²

) ) (3.22)

にたいしては

, x − y ̸ = 0

だから

,

(3.23) λ = 2 (

2 − (x

²

+ xy + y

²

) )

ところがこの式に

(3.22)

を代入すると

, λ = − 1

となり

, (3.18)

に反する

.

よって

(3.22)

.

Case 3 xy = 1

とする

.

(x + y)

²

= x

²

+ y

²

+ 2xy = 5 + 2 = 7, (x − y)

²

= x

²

+ y

²

− 2xy = 5 − 2 = 3

となるので

,

x + y = ± √

7, x − y = ± √ 3

⇒ (x, y) = (

√ 7 ± √ 3

2 ,

√ 7 ∓ √ 3

2 ), ( − √ 7 ± √

3 2 , − √

7 ∓ √ 3

2 ).

(3.24)

ここで

, (3.24)

にたいしては

, x − y ̸ = 0

だから

,

やはり

(3.23)

が成立している

.

ところが

, (3.23)

に

(3.24)

を代入すると

, λ = − 8

となり

, (3.18)

に反する

.

よって

(3.24)

.

Step 3.

結局

(3.20)

の組み合わせだけが

,

最適解の候補者として残った

. f (x, y) ≡ 2(x − y)

²

− x

⁴

− y

⁴ に

(3.20)

を代入し

,

f (0, 0) = 0, f ( √ 2, − √

2) = f ( − √ 2, √

2) = 8

を得る

.

これより最適解は

(x

^∗

, y

^∗

, λ

^∗

) = ( ± √ 2, ∓ √

2, 0)

であり

,

最適値は

8

である

. 2

応用解析学 参考資料 クーン・タッカーの定理