1 制約付最適化問題

パターン認識第

12, 13

1 制約付最適化問題

一般的な制約付最適化問題は以下のように表わされる:

min

θ f (θ) (1a)

s.t. h 1 (θ) = 0, h 2 (θ) = 0, · · · , h q (θ) = 0, (1b) g 1 (θ) ≤ 0, g 2 (θ) ≤ 0, · · · , g r (θ) ≤ 0. (1c)

θ ∈ R ^s

h j : R ^s → R , j = 1, 2, · · · , q

g k : R ^s → R , k = 1, 2, · · · , r

θ

s

q

r

h(θ) =



 

 

 h 1 (θ) h ₂ (θ)

.. . h q (θ)



 

 

 = 0, g(θ) =



 

 

 g 1 (θ) g ₂ (θ)

.. . g r (θ)



 

 

 ≤ 0 (2)

と表す.

2 等式制約のみを持つ最適化問題

まずは,等式制約のみを持つ最適化問題:

min

θ f (θ) (3a)

s.t. h(θ) = 0 (3b)

について考えよう. 具体的なイメージをつかむため, まずは図

1

図

1

f (θ),

h 1 (θ) = 0

•

1(a)

f (θ)

f (θ) = c (c

h ₁ (θ) = 0

この問題は等式制約

h 1 (θ) = 0

θ ^∗

•

1(b)

θ ^∗

•

1(c)

θ ^∗

2

非線形最適化問題を解析する際には,最適解

θ ^∗

θ ^∗

f (θ)

f ˜ (θ) = f (θ ^∗ ) + ( ∂f

∂θ | θ=θ

) _>

(θ − θ ^∗ ) (4)

(a) (b) (c)

1:

(a) (b) (c)

図

2:

θ ^∗

h j (θ), j = 1, 2, · · · , q,

˜ h j (θ) = h j (θ ^∗ ) + ( ∂h j

∂θ | θ=θ

) _>

(θ − θ ^∗ ), j = 1, 2, · · · , q (5)

図

2

θ ^∗

θ ^∗

図

2(a)

2(b)

(c)

2(b)

(c)

θ ^∗

2(b)

(c)

θ ^∗

2(b)

び

(c)

θ ^∗

図

2

θ ^∗

θ ^∗

2

(あるいは交平面,

∂f

∂θ

θ=θ

, ∂h 1

∂θ

θ=θ

, ∂h 2

∂θ

θ=θ

, · · · , ∂h q

∂θ

θ=θ

(6)

(3)

θ ^∗

,

∂f

∂θ

θ=θ

+

∑ q j=1

λ j

∂h j

∂θ

θ=θ

= 0, (7a)

h(θ ^∗ ) = 0 (7b)

となる.

(7a)

λ 1 , λ 2 , · · · , λ q

(Lagrange multiplier)

3 ラグランジュ関数

制約のない最適化問題:

min

θ f (θ) (8)

において

θ ^∗

0

∂f

∂θ

θ=θ

= 0 (9)

となることであった. 等式制約付最適化問題においてもこのような単純な形式で最適性条件を表現でき るとうれしい. このような目的で以下のようなラグランジュ関数

(Lagrangian)

L(θ, λ) = f (θ) +

∑ q j=1

λ j h j (θ) = f (θ) + λ ^> h(θ), (10)

ここで,

λ = [

λ ₁ λ ₂ · · · λ _q ] _>

である. ラグランジュ関数は未知変数

θ

λ

L

θ

0

∂L

∂θ = ∂f

∂θ +

∑ q j=1

λ j

∂h j

∂θ = 0 (11)

となり, (7a)と等し くなることがわかる. また, ラグランジュ関数

L

λ

0

∂L

∂λ = h(θ) = 0 (12)

となり, (7b)と同じ条件が導かれることがわかる. すなわち,等式制約付最適化問題の最適性条件はラグ ランジュ関数の微分係数が

0

課題

1:

θ min

,θ

θ 1 θ 2 (13a)

s.t. θ 1 + θ 2 = 1. (13b)

•

L(θ ₁ , θ ₂ , λ ₁ )

•

θ 1 , θ 2 , λ 1

0

1

• 3

1

θ 1 , θ 2 , λ 1

4 不等式制約付最適化問題

続いて,等式制約だけでなく不等式制約もある最適化問題について考えよう. 以下のように不等式制約 条件が

r

g ₁ (θ) ≤ 0, g ₂ (θ) ≤ 0, · · · , g _r (θ) ≤ 0. (14)

r

2

•

:

θ ^∗

g k (θ ^∗ ) = 0 (15)

となっているもの,

•

θ ^∗

g _k (θ ^∗ ) < 0 (16)

となっているもの.

{ g k (θ) } ^r k=1

(解に影響を与えないので)

アクティブ制約の番号とノンアクティブ制約の番号の集まりを

A = { k | g _k (θ ^∗ ) = 0 } , (17a)

A ¯ = { k | g k (θ ^∗ ) < 0 } , (17b)

と表すことにする. アクティブ制約は等式制約と同じように扱うことができるので,最適性条件は,

∂f

∂θ

θ=θ

+

∑ q j=1

λ j

∂h j

∂θ

θ=θ

+ ∑

k ∈A

µ k

∂g k

∂θ

θ=θ

= 0, (18a)

h(θ ^∗ ) = 0 (18b)

g _A (θ ^∗ ) = 0 (18c)

g A ¯ (θ ^∗ ) < 0 (18d)

と表すことができそうである. (18)において,等号制約

h j (θ ^∗ ) = 0, j = 1, 2, · · · , q,

λ j , j = 1, 2, · · · , q,

g k (θ ^∗ ) = 0, k ∈ A ,

µ k , k ∈ A ,

(a) (b) (c)

図

3:

その理由を図

3

3(a)

1(c)

3(b)

(c)

3(b)

g 1 (θ) ≤ 0

3(c)

g 1 (θ) ≤ 0

(a) (b) (c)

図

4:

図

3(a), (b), (c)

4(a), (b), (c)

4(a)

θ ^∗

4(b)

(c)

4(b)

θ ^∗

きだけでなく,下側への移動させることもできる. しかし

,

f (θ)

θ ^∗

4(c)

f (θ)

(解こうとしている最適化問題が最小

) θ ^∗

3

4

図

3

4

(b)

(c)

∂f

∂θ

θ=θ

+ µ ₁ ∂g _k

∂θ

θ=θ

= 0, (19)

と表される. 最急降下法において学んだように

, (19)

∂f /∂θ | θ=θ

f (θ)

∂g 1 /∂θ | θ=θ

g 1 (θ)

(b)

µ ₁

(正か

µ _k ≥ 0, k ∈ A (20)

という条件が必要であることがわかる.

(18)

(20)

µ _k g _k (θ) = 0, k = 1, 2, · · · , r, (21)

と呼ばれる条件を導入すると,アクティブ不等式制約とノンアクティブ不等式制約を陽に区別すること なく, (18)および

(20)

(21)

g k (θ) ≤ 0

である

(g _k (θ) = 0),

µ _k

0

ければならないことを示している.

以上より,等式制約および不等式制約を持つ制約付き最適化問題の最適性条件は

∂f

∂θ

θ=θ

+

∑ q j=1

λ _j ∂h _j

∂θ

θ=θ

+

∑ r k=1

µ _k ∂g _k

∂θ

θ=θ

= 0, (22a)

h(θ ^∗ ) = 0, (22b)

g(θ ^∗ ) ≤ 0, (22c)

µ k ≥ 0, k = 1, 2, · · · , r, (22d)

µ _k g _k (θ ^∗ ) = 0, k = 1, 2, · · · , r, (22e)

g k (θ) ≤ 0

µ k = 0

(22e)

g _k

課題

2:

min − θ 1 θ 2 (23a)

s.t θ ₁ ≥ − 1 (23b)

θ ₁ + θ ₂ ≥ − 1 (23c)

θ ₁ + 2θ ₂ ≤ 4. (23d)

•

•

5

θ 1 = 2, θ 2 = 1

最適解において,すべての最適性条件が成り立っていることを確認せよ.

-4 -2 0 2 4

-4 -2 0 2 4

theta2

theta1

QRVKOCN

図

5:

5-2

5 _双対問題

5.1

制約付最適化問題

min

θ f (θ) (24a)

s.t. h(θ) = 0 (24b)

g(θ) ≤ 0. (24c)

のラグランジュ関数は

L(θ, λ, µ) = f (θ) +

∑ q j=1

λ _j h _j (θ) +

∑ r k=1

µ _k g _k (θ) (25a)

= f (θ) + λ ^> h(θ) + µ ^> g(θ) (25b)

と定義される. ここで,

θ =



 

 

 θ ₁ θ 2

.. . θ _s



 

 

 , λ =



 

 

 λ ₁ λ 2

.. . λ _q



 

 

 , µ =



 

 

 µ ₁ µ 2

.. . µ _r



 

 

 , (26)

である.

5.2

ラグランジュ関数

(25)

θ, λ, µ

θ

φ(λ, µ) = inf

θ

{

f (θ) + λ ^> h(θ) + µ ^> g(θ) }

(27)

λ, µ

θ

λ, µ

ラグランジュ双対関数は

φ(λ, µ) ≤ f(θ ^∗ ), µ ≥ 0, (28)

という重要な性質を持っている. ここで

θ ^∗

f (θ ^∗ )

(28)

(証明)

h( ˜ θ) = 0, (29a)

g( ˜ θ) ≤ 0 (29b)

を満たす任意の

θ ˜

,

L( ˜ θ, λ, µ) = f ( ˜ θ) + ∑

j=1

λ _j h _j ( ˜ θ) +

∑ r k=1

µ _k g _k ( ˜ θ) ≤ f ( ˜ θ) (30)

が成り立つ. これは,右辺第

2

h j ( ˜ θ) = 0, j = 1, 2, · · · , q, (31)

0

3

µ _k ≥ 0, g _k ( ˜ θ) ≤ 0, k = 1, 2, · · · , r, (32)

φ(λ, µ) = inf

θ L(θ, λ, µ) ≤ L( ˜ θ, λ, µ) ≤ f ( ˜ θ) ≤ f (θ ^∗ ) (33)

となる

(証明終わり).

5.3

制約付最適化問題

(24)

(primal problem)

,

(P)

h(θ) = 0

g(θ) ≤ 0

f (θ)

min

θ f (θ) (34a)

s.t. h(θ) = 0, g(θ) ≤ 0. (34b)

φ(λ, µ)

µ ≥ 0

(dual problem)

(D)

µ ≥ 0

φ(λ, µ)

max

λ,µ φ(λ, µ) (35a)

s.t. µ ≥ 0. (35b)

サポートベクトルマシンにおける最適化問題を含む凸計画問題の多くは,主問題の最小値

f (θ ^∗ )

φ(λ ^∗ , µ ^∗ )

(strong duality)

る

(強双対性の証明は省略する).

を解くかわりに双対問題を解くこと問題が解決できる. サポートベクトルマシンの学習における最適化 問題においては,主問題の代わりに双対問題が解かれることになる.

6 二次計画問題における双対問題の導出

サポートベクトルマシンにおける双対問題を導出する練習として, 一般的な二次計画問題の双対問題 を導出してみよう. 一般的な二次計画問題として

min

θ

1

2 θ ^> Aθ + b ^> θ (36a)

s.t. Cθ + d = 0 (36b)

Eθ + f ≤ 0 (36c)

を考える. ここで,

A ∈ R ^{s × s} , b ∈ R ^s , C ∈ R ^{q × s} , d ∈ R ^q , E ∈ R ^{r × s} , f ∈ R ^r

A

• step 1

ラグランジュ関数は

L(θ, λ, µ) = 1

2 θ ^> Aθ + b ^> θ + λ ^> (Cθ + d) + µ ^> (Eθ + f ) (37)

• step 2

θ

ラグランジュ双対関数

inf θ L(θ, λ, µ)

θ

θ

0

∂L

∂θ = A θ ¯ + b + C ^> λ + E ^> µ = 0 (38a)

⇐⇒ θ ¯ = − A ^{− 1} (C ^> λ + E ^> µ + b) (38b)

θ

• step 3 step 2

(38b)

φ(λ, µ) = L( ¯ θ, λ, µ) = − 1

2 λ ^> CA ^{− 1} C ^> λ − 1

2 µ ^> EA ^{− 1} E ^> µ − λ ^> CA ^{− 1} E ^> µ (39a) +(d ^> − b ^> A ^{− 1} C ^> )λ + (f ^> − b ^> A ^{− 1} E ^> )µ (39b)

+const. (39c)

と

λ

µ

以上より,制約付最小化問題

(36)

max

λ,µ − 1

2 λ ^> CA ^{− 1} C ^> λ − 1

2 µ ^> EA ^{− 1} E ^> µ − λ ^> CA ^{− 1} E ^> µ

+(d ^> − b ^> A ^{− 1} C ^> )λ + (f ^> − b ^> A ^{− 1} E ^> )µ (40a)

s.t. µ ≥ 0 (40b)

と与えられる.