5 制約付き最適化問題

5

制約付きの最適化問題を扱う. 今までと同様に最小化問題で主に説明するが最大 化問題も同様である. また変数を一般に

n

C

R ⁿ

x = (x 1 , x 2 , . . . , x n )

(P )

f (x)

x ∈ C

最小化問題

(P )

C

, C

C

x

f (x)

例

12.

この問題は次のように定式化できる. 辺の長さを

x

y

xy

a > 0

最大化

xy

制約

(x, y) ∈ C := { (x, y) | x + y = a, x ≥ 0, y ≥ 0 }

不等式を用いて最大解を求める. (x, y)を

C

x, y ≥ 0

√ xy ≤ x + y 2 = a

2

となり,

xy ≤ a ² /4

x = y

(x, y) = (a/2, a/2)

補足

.

n

例

13.

x ² + y ² = 1

(1, 2)

一般に点

(x, y)

(1, 2)

!

(x − 1) ² + (y − 2) ²

2

(x − 1) ² +(y − 2) ²

最小化

f(x, y) := (x − 1) ² + (y − 2) ²

制約

(x, y) ∈ C := { (x, y) ∈ R ² | x ² + y ² = 1 }

(x, y)

C

C

x ² + y ² = 1

f (x, y) = 1 − 2x − 4y + 3 = − 2x − 4y + 4

| − 2x − 4y | = |& ( − 2, − 4), (x, y) '| ≤ ( ( − 2, − 4) (( (x, y) (

= !

( − 2) ² + ( − 4) ² !

x ² + y ² = √

20 · 1 = 2 √ 5

f(x, y) = − 2x − 4y + 4 ≥ − 2 √

5 + 4

シュワルツの不等式では, 等号は二つのベクトルの方向が同じ時に成り立つので, ある数

t

t( − 2, − 4)

(x, y)

C

t

y = 2x

C

x ² + (2x) ² = 1

± 1/ √

5, ± 2/ √

5)

この二つの点での目的関数値を考えると,

f (1/ √ 5, 2/ √

5) = − 10/ √

5+4 = − 2 √ 5+

4

(x, y) = (1/ √ 5, 2/ √

5)

6

6.1

上記の例のように, 不等式を用いて綺麗に解ける問題もあるが, 制約なしの最適化 問題で行ったように微分法を用いた一般的な解法を学ぶ.

例

13

まず, テーラー展開を考えると, 点

(¯ x, y) ¯

−∇ f (¯ x, y) ¯

(ゼロベクトルでなければ) f (¯ x, y) ¯

13

「減少方向ベクトルが

C

例

13

(1, 2)

(1 √

5, 2/ √

5)

−∇ f(1/ √

5, 2 √ 5) = (2(1/ √

5 − 1), 2(2 √

5 − 2)) = 2(1/ √

5 − 1, 2 √ 5 − 2)

0 y

x (1, 2)

これは

(1/ √ 5, 2 √

5)

(1, 2)

C

(1, 2)

定理

8 (ラグランジュの乗数法).

最小化

f (x)

g(x) = 0

を考える.

x ¯

∇ g(¯ x) * = (0, . . . , 0)

λ

∇ f(¯ x) = λ ∇ g(¯ x) g(¯ x) = 0

が成り立つ.

Proof. 2

x = (¯ x 1 , x ¯ 2 )

g(¯ x) = 0

約を満たすことから成り立つ. いま, 関数

u(t) = (x 1 (t), x 2 (t))

t = 0

u(0) = ¯ x, g(u(t)) = 0

x

u(t)

f (u(t)) ≥ f (¯ x) = f (u(0))

最小化

f(u(t))

は

t = 0

f ◦ g

t = 0

_dt ^d f (u(t)) " "

t=0 = ∇ f(¯ x)u ^! (0) = 0

g(u(t))

t = 0

_dt ^d g(u(t)) " "

t=0 = ∇ g(¯ x)u ^! (0) = 0

∇ f (¯ x), ∇ g(¯ x) 2

u ^! (0)

λ

∇ f (¯ x) = λ ∇ g(¯ x)

さて,上記のような

u(t)

∇ g(¯ x) * = 0

g x

(¯ x) * = 0

ϕ

x 1

g(x ₁ , ϕ(x ₁ )) = 0 (x ₁

x ¯ ₁

ϕ(¯ x ₁ ) = ¯ x ₂

t = 0

u(t) = (¯ x 1 + t, ϕ(¯ x 1 + t))

u

補足

. 3

&∇ g(¯ x), d ' = 0

d

u ^! (0) = d

u(t)

∇ g(¯ x)

∇ f(¯ x)

∇ f(¯ x) = λ ∇ g(¯ x)

補足

.

定理の式を満たすような点

x ¯

C

C

証明はしないが

(実数の性質を使う)

定理

9.

制約付き最適化問題で特に等式制約を持つ問題は, 実行可能領域が有界閉集合に なる場合が多い. 最適解の存在があらかじめ分かっていると議論が楽になり, 1 階微

分の情報

(基本最適性条件)

6.2

制約は複数ある場合もある.

定理

10.

最小化

f(x)

制約

g ₁ (x) = 0, g ₂ (x) = 0, . . . , g _m (x) = 0

を考える.

x ¯

∇ g 1 (¯ x), . . . , ∇ g m (¯ x)

λ 1 , . . . , λ m

∇ f(¯ x) = λ 1 ∇ g 1 (¯ x) + · · · + λ m g m (¯ x) g 1 (¯ x) = 0, . . . , g m (¯ x) = 0

が成り立つ.

証明には次のような陰関数定理を用いる. 簡単のため変数の数が

3

2

定理

11. g 1 , g 2

3

g 1 (¯ x) = 0, g 2 (¯ x) = 0

rank

# ∇ g 1 (¯ x) ^T

∇ g 2 (¯ x) ^T

$

= 2

ϕ 1 , ϕ 2

# g 1 (x 1 , ϕ 1 (x), ϕ 2 (x)) g 2 (x 1 , ϕ 1 (x), ϕ 2 (x))

$

=

# 0 0

$

を満たすものが存在する.

解説.

g ₁ , g ₂

g ₁ (¯ x) = 0, g ₂ (¯ x) = 0

2 × 3

# g 1 (¯ x) g ₂ (¯ x)

$

= A¯ x =

# 0 0

$

と書ける. また, rank

%

∇g

(¯ x)

∇g

(¯ x)

&

= rank A

A = 2

1

1

g 1 , g 2

2

1

6.3

例

14.

最小化

f(x, y) := x − y

制約

(x, y) ∈ C := { (x, y) ∈ R ² | 2x ² + 3y ² − 1 = 0 }

基本最適性条件より,

C

8 (直後の補足にも注意)

g(x, y) = 2x ² + 3y ² − 1

∇ g(x, y) = (4x, 6y)

C

∇ g(x, y)

(x, y) ∈ C

8

C

f x (x, y) = 1 = λ4x f y (x, y) = − 1 = λ6y g (x, y) = 0

を満たす

(x, y), λ

(x, y)

(λ

く, 必ずしも計算する必要はない).

第一式より

4x * = 0

λ = 1/(4x)

y = − 2x/3

x = ± !

3/10

y = ∓ ! 2/15

C

(x, y) = ( ± !

3/10, ∓ !

2/15)

さて,

C

9

C

る

(講義ノートの包含関係を表す図を参照).

± !

3/10, ∓ ! 2/15)

J

− !

3/10, !

2/15)

例

15 (2

A

(P )

f(x, y) := '

x y ( A

# x y

$

制約

(x, y) ∈ C := { (x, y) ∈ R ⁿ | x ² + y ² = 1 }

A

まず

C

9

(¯ x, y) ¯

g(x, y) = x ² + y ² − 1

(x, y) ∈ C

∇ g(x, y)

8

λ ∈ R

∇ f (¯ x, y) = ¯ λ ∇ g(¯ x, y) ¯

A

# x ¯

¯ y

$

= λ

# x ¯

¯ y

$

, g(¯ x, y) = 0 ¯

を得る. これは

λ

A

x, y) ¯

1

C

A

ここで, (¯

x, y) ¯

A

f (¯ x, y) = ¯ λ(¯ x ² + ¯ y ² ) = λ

C

f

x, y) ¯

A

f

A