再定式化と平滑化による 一般化半無限計画問題の解法

特別研究報告書

再定式化と平滑化による 一般化半無限計画問題の解法

指導教員 福島 雅夫 教授

京都大学工学部情報学科 数理工学コース

平成

12

17

3

道古 真也

再定式化と平滑化による一般化半無限計画問題の解法 道古 真也

摘要

半無限計画問題

(SIP: Semi-Infinite Program)

SIP

(GSIP: Generalized Semi-Infinite

Program)

GSIP

SIP

ことができる．一般に凸でない最適化問題の解法アルゴリズムにおいて大域的収束性を保証す ることはできない．そこで現実には局所的最適解や停留点を求めるようなアルゴリズムの研究 が重要となる．本報告書では

GSIP

GSIP

(MPEC)

GSIP

GSIP

,

目 次

1 ^序論 1

2 一般化半無限計画問題 2

2.1

. . . . 2

2.2 Fritz John

. . . . 3

2.3

. . . . 5

2.4 NCP

. . . . 5

3 数値解法 6

3.1

. . . . 6

3.2

. . . . 9

4 収束解析 9 5 数値実験 13

5.1

. . . . 13

5.1.1

. . . . 13

5.1.2

. . . . 14

5.2

. . . . 15

5.3

. . . . 16

6 結論 18

1

半無限計画問題

(SIP: Semi-Infinite Program)

x = (x

, ..., x

) ∈ <

min

f (x) s.t. g(x, y) ≤ 0 ∀ y ∈ Y f : <

→ < , g : <

× <

→ <

ここで

Y

x

(GSIP: Generalized Semi-Infinite Program)

GSIP

min

f (x) s.t. g(x, y) ≤ 0 ∀ y ∈ Y (x)

様々な分野で（一般化）半無限計画問題としてモデル化できる問題が数多く存在し，近年活 発に研究されている．例を挙げるとまず数学においては関数を別の（より次元の低い）多項式 で近似するチェビシェフの近似問題がある．工学においてはロボットの軌道制御，経済におい てはロバスト最適化によるポートフォリオ決定問題など応用可能な分野は非常に幅広い

[1, 2]

一般に凸でない問題の解法アルゴリズムにおいて大域的収束性を保証することはできない．

そこで現実的な問題として局所的最適解や停留点を求めるようなアルゴリズムの研究が重要と なる．本報告書では

GSIP

GSIP

SIP

GSIP

SIP

（局所的に）等価な最適化問題の列に帰着させる．概念としては次のようになる．

GSIP

P

solver x

本報告書で紹介する手法においてもこのように通常の最適化問題の列を生成する．この手法 では

GSIP

計画問題

(MPEC)

いて平滑化する．このようにして得られたパラメトリック最適化問題は微分可能な通常の非線

形計画問題であるため汎用のソフトウェアで解くことができる．ここでパラメータを０に近づ けた時のパラメトリック非線形計画問題の解の極限として，

GSIP

[3]

本報告書の構成を記す．第２節では一般化半無限計画問題の定式化及び数学的準備を行う．

第３節において本報告書の核となるアルゴリズムを紹介し，第４節では収束解析，第５節では 数値実験結果を記す．最後に第６節で結論を述べる．

2

2.1

本節では，本報告書における主な仮定と最適性の１次の必要条件を表す

FJ

(Fritz John

point)

GSIP : min

x

f (x) s.t. x ∈ M (1)

M = { x ∈ <

| g

(x, y) ≤ 0 , ∀ y ∈ Y (x) , j ∈ J } (2) Y (x) = { y ∈ <

| v

(x, y) ≤ 0 , l ∈ L } (3)

f : <

→ < , g

: <

× <

→ < , j ∈ J = { 1, ..., p } , v

: <

× <

→ < , l ∈ L =

{ 1, ..., s }

M

上でかつ実行可能な点

x ¯

∂M

M

x ¯ ∈ ∂M ∩ M

点

x ¯

U

∪

Y (x)

Y

x ¯

仮定 A 点集合写像

Y

x ¯

本報告書を通じて仮定

A

x ¯

U

x

j ∈ J

GSIP

Q

(x) : max

y

g

(x, y) s.t. y ∈ Y (x) (4)

問題

Q

(x)

ϕ

(x) =





max

g

(x, y), if Y (x) 6 = φ

−∞ , otherwise (5)

Q

(x)

Y

(x) = { y ∈ Y (x) | g

(x, y) = ϕ

(x) } (6)

明らかに

M = { x ∈ <

| ϕ

(x) ≤ 0, j ∈ J }

M ∩ U

{ x ∈ U | ϕ

(x) ≤ 0, j ∈ J

(¯ x) } ,J

(¯ x) = { j ∈ J | ϕ

(¯ x) = 0 }

U

j ∈ J

(¯ x)

Q

(¯ x)

Y

(¯ x)

Y

(¯ x) = Y

(¯ x) =: { y ∈ Y (¯ x) | g

(¯ x, y) = 0 } (7)

2.2 Fritz John

続いて副問題

Q

(¯ x)

M

x ¯

,

[4]

ベクトル

∇

v

(¯ x, y), l ¯ ∈ L

(¯ x, y) ¯

y ¯ ∈ Y (¯ x)

(LICQ: linear independence constraint qualification)

∇

v

(¯ x, y)η < ¯ 0, l ∈ L

(¯ x, y) ¯

η

Mangasarian-Fromovitz

(MFCQ)

L

(¯ x, y) = ¯ { l ∈ L | v

(¯ x, y) = 0 ¯ }

Q

(¯ x)

ここで

v(x, y) = (v

(x, y), ..., v

(x, y))

,γ ∈ <

s × s

diag(γ ),j ∈ J

(¯ x)

Q

(¯ x)

L

(¯ x, y, γ) = g

(¯ x, y) − γ

v(¯ x, y) (8)

y ¯ ∈ Y

(¯ x)

Q

(¯ x)

y ¯

MFCQ

KKT

(9) ∼ (12)

γ

∇

L

(¯ x, y, γ) = 0 ¯ (9)

− diag(γ )v(¯ x, y) = 0 ¯ (10)

γ ≥ 0 (11)

− v(¯ x, y) ¯ ≥ 0 (12)

さらに

LICQ

γ

x, ¯ y ¯

KKT

KT

(¯ x, y) = ¯ { γ ∈ <

| γ satisfies (9) ∼ (12) }

さらに

γ

> 0, l ∈ L

(¯ x, y) ¯

y ¯

(SCS: strict complementary slackness)

LICQ

(¯ x, y) ¯

KKT

γ ¯

(¯ x, y, ¯ ¯ γ)

y ¯

(SOSC: second order sufficiency condition)

η

∇

L

(¯ x, y, ¯ γ ¯ )η < 0, ∀ η ∈ T

Y (¯ x)

T

Y (¯ x) = { η ∈ <

| ∇

v

(¯ x, y)η ¯ = 0, l ∈ L

(¯ x, y) ¯ }

定義 2.1

x ¯ ∈ ∂M ∩ M, j ∈ J

(¯ x)

. y ¯ ∈ Y

(¯ x)

LICQ

SCS, SOSC

y ¯

Q

(¯ x)

仮定 B

Q

(¯ x)

仮定

B

Q

(¯ x)

Y (¯ x)

Y

(¯ x) = { y ¯

, k ∈ J

(¯ x) }

と表現できる．ここで

J

(¯ x)

y ¯

¯ γ

[5]

y ¯

, γ ¯

, ∀ k ∈ J

(¯ x)

y

(¯ x) = ¯ y

, γ

(¯ x) = ¯ γ

y

(x), γ

(x)

Q

(x)

,KKT

y

(

), γ

(

)

y

(

)

x ¯

ϕ

(x) = g

(x, y

(x)), k ∈ J

(¯ x), j ∈ J

(¯ x)

ϕ

∇ ϕ

(¯ x) = ∇

L

(¯ x, y ¯

, γ ¯

)

定理 2.1

x ¯

B

x ¯

M

M

= { x ∈ U | ϕ

(x) ≤ 0, k ∈ J

(¯ x), j ∈ J

(¯ x) }

は一致する．

定理

2.1

B

GSIP

[6]

min

f(x) s.t.

x ∈ M

よって通常の非線形計画問題に対する局所的最適性の条件を

GSIP

特に最適性の１次の必要条件として

Fritz John

[7]

定理 2.2

x ¯

GSIP

B

κ ≥ 0, λ

≥ 0, k ∈ J

(¯ x), j ∈ J

(¯ x)

κ ∇ f (¯ x) +

j∈J0(¯x)

X

k∈J₀^j(¯x)

λ

∇

L

(¯ x, y ¯

, γ

) = 0 (13)

定理

2.2

GSIP

FJ

(Fritz John point)

2.3

以下に本報告書における重要な仮定を記す．

仮定 C 副問題

Q

(x)

− g

(x, · ), v

(x, · ), l ∈ L

x ∈ <

仮定

C

Q

(x)

定義 2.2 仮定

C

l ∈ L

y ˆ

v

(x, y) ˆ < 0

Y (x)

仮定 D 任意の

x ∈ <

Y (x)

仮定

C

D

Y

(x)

x ¯

M

仮定

B

C

D

Q

(¯ x), j ∈ J

(¯ x)

y ¯

KKT

γ ¯

2.2

系 2.1

x ¯

GSIP

B,C,D

κ ≥ 0, λ

≥ 0, j ∈ J

(¯ x)

κ ∇ f (¯ x) +

j∈J0(¯x)

λ

∇

L

(¯ x, y ¯

, γ ¯

) = 0 (14)

次の補題はよく知られている

[8]

補題 2.2 仮定

C,D

y ¯

Q

(¯ x)

KKT

γ ¯

A

= A

(¯ x, y ¯

, γ ¯

) =





∇

L

(¯ x, y, ¯ γ) ¯ −∇

v(¯ x, y) ¯

− diag(¯ γ

) ∇

v(¯ x, y ¯

)

− diag(v(¯ x, y ¯

))



 が正則でありかつ

(9) ∼ (12)

2.4 NCP

関数

φ : <

→ <

NCP

[9]

φ(a, b) = 0 if and only if a ≥ 0, b ≥ 0, ab = 0

次式で定義される関数

ψ : <

→ <

min

NCP

ψ(a, b) = 1 2

a + b −

(a − b)

min

ψ

τ ∈ <

ψ

: <

→ <

ψ

(a, b) = 1 2

a + b −

(a − b)

+ 4τ

ψ

τ 6 = 0

性質 1

(i) ψ

(a, b) = 0 if and only if a > 0, b > 0, ab = τ

(ii) ψ

(a, b) = 0

(a, b)

∇ ψ

(a, b)

τ

(a + b)

(b, a)

3

本報告書で考察する方法は

GSIP

KKT

C

D

3.1

まず

GSIP

Stackelberg game

SG : min

x,y¹,...,y^p

f (x) s.t. g

(x, y

) ≤ 0, and y

solves Q

(x), j ∈ J

副問題

Q

(x)

{ y

solves Q

(x) }

KKT

(9) ∼ (12)

SG

(MPEC: mathematical program with equilibrium constraints)

M P EC : min

x,y¹,γ¹...,y^p,γ^p

f (x) s.t. g

(x, y

) ≤ 0

∇

L

(x, y

, γ

) = 0

− diag(γ

)v(x, y

) = 0 γ

≥ 0

− v(x, y

) ≥ 0, j ∈ J

GSIP

MPEC

MPEC

MFCQ

MFCQ

[10]

NCP

Ψ(a, b) = (ψ(a

, b

), ..., ψ(a

, b

))

Ψ

(a, b) = (ψ

(a

, b

), ..., ψ

(a

, b

))

NCP

MPEC

P : min

x,y¹,γ¹...,y^p,γ^p

f (x) s.t. g

(x, y

) ≤ 0

∇

L

(x, y

, γ

) = 0 Ψ(γ

, − v(x, y

)) = 0, j ∈ J

P

P

: min

x,y¹,γ¹...,y^p,γ^p

f (x) s.t. g

(x, y

) ≤ 0

∇

L

(x, y

, γ

) = 0 Ψ

(γ

, − v(x, y

)) = 0, j ∈ J

P

P

ψ

1(ii)

命題 3.1

τ 6 = 0

A

= A

(x, y

, γ

) =





∇

L

(x, y

, γ

) −∇

v(x, y

)

− diag(γ

) ∇

v(x, y

)

− diag(v(x, y

))





が正則となるような

P

(x, y

, γ

, ..., y

, γ

)

(x, y

, γ

, ..., y

, γ

)

P

問題

P

∇

L

(x, y

, γ

) = 0 (15)

− diag(γ

)v(x, y

) = τ

e

(16)

γ

≥ 0 (17)

− v(x, y

) ≥ 0 (18)

ただし

e

= (1, ..., 1)

∈ <

(15) ∼ (18)

Q

(x)

Q

(x) : max

y

b

(x, y) := g

(x, y) + τ

l∈L

ln( − v

(x, y))

問題

Q

(x)

0 = ∇

b

(x, y) = ∇

g

(x, y) +

l∈L

τ

v

(x, y) ∇

v

(x, y)

y

b

(x, y)

∇

b

(x, y) = ∇

g

(x, y) +

l∈L

τ

v

(x, y) ∇

v

(x, y) −

l∈L

τ

[v

(x, y)]

∇

v

(x, y) ∇

v

(x, y)

j ∈ J, τ 6 = 0

(i) y

Q

(x)

(y

, γ

)

γ

= − τ

/v

x, y

), l ∈ L

(15) ∼ (18)

∇

b

(x, y

)

A

(x, y

, γ

)

(ii) ∇

g

(x, y), ∇

v

(x, y), l ∈ L

A

(x, y

, γ

)

証明 まず

(i)

∇

L

(x, y

, γ

) = 0

∇

b

(x, y

) = 0

1(i)

− diag(v(x, y

))

A

=A

(x, y

, γ

)

A

− diag(v(x, y

))

Schur complement S

S

= ∇

L

(x, y

, γ

) + ∇

v(x, y

)(diag(v(x, y

)))

diag(γ

) ∇

v(x, y

)

= ∇

g

(x, y

) −

l∈L

γ

∇

v

(x, y

) + ∇

v(x, y

)Diag γ

v

(x, y

)

!

∇

v(x, y

)

= ∇

g

(x, y

) +

l∈L

τ

v

(x, y

) ∇

v

(x, y

) − ∇

v(x, y

)Diag

τ

[v

(x, y

)]

∇

v(x, y

)

= ∇

g

(x, y

) +

l∈L

τ

v

(x, y

) ∇

v

(x, y

) −

l∈L

τ

[v

(x, y

)]

∇

v

(x, y

) ∇

v

(x, y

)

= ∇

b

(x, y

)

ただし

Diag(x

)

(l, l)

x

S

= ∇

b

(x, y

)

続いて

(ii)

S

(ii)

∇

g

(x, y), ∇

v

(x, y), l ∈ L

τ

/v

(x, y), l ∈ L

S

(i)

(ii)

GSIP

3.2

アルゴリズム*

ステップ

1.

: lim

τ

= 0

{ τ

}

x

∈ <

ステップ

2.

: P

(x

, y

, γ

, ..., y

, γ

)

ν := 0

ステップ

3.

: P

(x

, y

, γ

, ..., y

, γ

)

ステップ４

.

: (x

, y

, γ

, ..., y

, γ

) := (x

, y

, γ

, ..., y

, γ

),

ν := ν + 1,

ステップ２において

(y

, γ

, ..., y

, γ

)

∇

L

(x

, y

, γ

) = 0 Ψ

(γ

, − v(x

, y

)) = 0

を解くことが考えられる．しかし数値的に求めるにあたっての適切な初期点を得ることは容易 ではない．そこで

Q

(x

)

y

γ

γ

= − τ

v

(x

, y

)

として求めればよい．

Q

(x

)

Y (x

)

,

min

η s.t v

(x

, y) − η ≤ 0, l ∈ L

ステップ３に対しては非線形最適化問題を解く一般的なソフトウェアを適用することができる．

ただしステップ２およびステップ４より，実行不可能な初期点を用いることができることが必 要である．

4

３節においては

GSIP

MPEC

P

GSIP

C

D

３節での考察によって問題

P

, τ 6 = 0

SG

: min

x,y¹,...,y^p

f (x) s.t. g

(x, y

) ≤ 0, y

solves Q

(x), j ∈ J

仮定

B

GSIP

x ¯

x

(15) ∼ (18)

(y

, γ

), j ∈ J

命題 4.1

x ¯ ∈ ∂M ∩ M

j

y ¯

,¯ γ

Q

(¯ x)

KKT

A

(¯ x, y ¯

, γ ¯

)

x ¯

U , τ ¯ = 0

T ,

y

: V → <

, γ

: V → <

(V := U × T )

y

(¯ x, 0) = ¯ y

, γ

(¯ x, 0) = ¯ γ

さらに各々の

(x, τ ) ∈ V

(y

(x, τ), γ

(x, τ ))

(15) ∼ (18)

証明 等式

(15),(16)

A

(¯ x, y ¯

, ¯ γ

)

補題

2.2

B

4.1

(A

)

j ∈ J

(¯ x)

3.1(i)

(x, τ ) ∈ V

g

(x, y

) ≤ 0, y

solves Q

(x)

g

(x, y

(x, τ )) ≤ 0

仮定

C,D

j ∈ J \ J

(¯ x)

Q

(x)

ϕ ˜

(x, τ)

(¯ x, 0)

U × T

τ ∈ T

P

x ¯

U

GSIP

(¯ x) min

x∈U

f (x) s.t. g

(x, y

(x, τ)) ≤ 0, ∀ j ∈ J

(¯ x)

補題 4.1

x ¯ ∈ ∂M ∩ M

B

τ ∈ T

x

GSIP

(¯ x)

(x

, y

, ..., y

), x

∈ U

SG

(¯ x, 0)

U × T

P

GSIP

(¯ x)

GSIP

(¯ x)

U

SG

SG,

GSIP

次の定理は

SG

4.1

[11]

N

定理 4.1

{ τ

}

lim

τ

= 0

{ (x

, y

, γ

, ..., y

, γ

) }

を

P

, ν ∈ N

x

{ x

}

B

MFCQ

GSIP

(x

)

このとき

x

GSIP

証明

(x

, τ

)

ν → ∞

(x

, 0)

4.1

ν , y

, j ∈ J

(x

)

y

= y(x

, τ

)

x

GSIP

(x

)

連続性の議論により

x

GSIP

(x

)

(x

, 0)

U

GSIP

(x

)

GSIP

MFCQ

GSIP

(x

)

Gauvin and Dubeau [11]

GSIP

(x

)

ω(τ )

τ

に関して連続となる

.

ω(τ

) = f (x

) → ω(0)

x

GSIP

定理

4.1

P

, ν ∈ N

GSIP

3.2

GSIP

FJ

続いて問題

P

FJ

GSIP

(¯ x)

GSIP

補題 4.2

x ¯ ∈ ∂M ∩ M

B

(¯ x, 0)

(x, τ)

(x, y

, γ

, ..., y

, γ

)

P

FJ

A

=





∇

L

(x, y

, γ

) −∇

v(x, y

)

− diag(γ

) ∇

v(x, y

)

− diag(v(x, y

))





, j ∈ J \ J

(¯ x)

は正則であるとする．このとき

x

GSIP

(¯ x)

FJ

証明

x

GSIP

(¯ x)

(x, y

, γ

, ..., y

, γ

)

P

y

Q

(x)

A

j ∈ J

(¯ x, 0)

(x, τ )

y

Q

(x)

y

(x, τ )

以上の考察と簡単な連続性の議論より

P

FJ

GSIP

(¯ x)

FJ

続いてこの節の核となる定理を証明する．

定理 4.2

{ τ

}

lim

τ

= 0

(x

, y

, γ

, ..., y

, γ

)

P

, ν ∈ N

FJ

(x

, y

, γ

, ..., y

, γ

)

x

B

A

=





∇

L

(x

, y

, γ

) −∇

v(x

, y

)

− diag(γ

) ∇

v(x

, y

)

− diag(v(x

, y

))





, j ∈ J \ J

(x

)

は正則であるとする．このとき

x

GSIP

FJ

証明 十分大きな

ν ∈ N

4.2

x

GSIP

(x

)

FJ

2.1

2.1

x

GSIP

FJ

次の命題では定理

4.2

命題 4.2

{ τ

}

lim

τ

= 0

(x

, y

, γ

, ..., y

, γ

)

P

, ν ∈ N

{ x

}

x

Y (x

)