伊藤　好彦

特別研究報告書

線形二次錐計画問題に対する

半無限計画変換を用いた単体法的アプローチ  

指導教員 林 俊介 助教     

京都大学工学部情報学科 数理工学コース 平成１７年４月入学 平成２１年３月卒業

伊藤 好彦

平成２１年１月３０日提出

摘要

線形二次錐計画問題とはアフィン集合と二次錐の直積をアフィン変換した集合との共通集合上において，

アフィン関数を最小化する問題である．線形二次錐計画問題の解法としては内点法

(

)

そこで，本報告書では線形二次錐計画問題を線形半無限計画問題に変換し，線形半無限計画問題に対す る単体法的手法として知られている

Dual-Simplex Primal-Exchange

線形半無限計画問題とは，目的関数が線形で，制約条件が有限個の線形等式と無限個の線形不等式で表さ れるような問題である．さらに，この線形半無限計画変換に基づく単体法的手法と，既存の主双対内点法 のソルバーとの比較実験を行う．特に，構造が似ている複数の線形二次錐計画問題を逐次的に解く場合に，

単体法的手法が有効であることを確認する

目 次

1

4

2

5

2.1

. . . . 5

2.2

. . . . 6

3

9 3.1 Dual-Simplex Primal-Exchange

. . . . 9

3.2 LSOCP

LSIP

DSPE

. . . . 11

3.3

. . . . 13

4

14 4.1 LSOCP

. . . . 14

4.2

LSOCP

. . . . 16

4.2.1 b

. . . . 16

4.2.2 c

. . . . 19

4.2.3 A

. . . . 20

5

23

1

線形二次錐計画問題

(Linear Second-Order Cone Programming: LSOCP) [1]

(LSOCP) minimize c

x

subject to Ax + b ∈ K (1)

ここで，

A ∈ R

, b ∈ R

, c ∈ R

K ⊆ R

n

K

:=

 



© u = (u

, u) ∈ R × R

u

≥ kuk, u

∈ R, u ∈ R

ª

(n

≥ 2) R

= { u ∈ R u ≥ 0 } (n

= 1)

,

K = K

× K

× · · · × K

と表される集合である集合である．ただし，n1

+ n

+ · · · + n

= n

n

u

u

n − 1

1

u

(u

, u) ∈ R × R

¡

1

u

¢ ∈ R

実際，LSOCPは幅広いクラスの問題に応用できることが知られている．たとえば，現実の応用例として，

Antenna array weight design

[5]．また，非負象限は 1

(Linear Programming: LP)

(Quadraric Programming:

QP)

(SemiDefinide Programming: SDP) [11]

SDP

LSOCP

SDP

LSOCP

よく知られているのが内点法

[14]

[10, 14]

実装面においても非常に有効であり，実際にいくつかのソフトウェアが開発されている

[9, 8]

LP

(

) [2]

(

)

SDP

LP

SDP

[6]

LSOCP

(dictionary)

の実装報告が栗田

·

[13]

このように，

LSOCP

前者の方が後者に比べて理論的にも実用的にも優れている．実際，村松の単体法的アルゴリズムは

LSOCP

LSOCP

LP

(extreme

point)

式時間で収束することが理論的に保証されている．

しかしながら，LSOCPに対して単体法的アルゴリズムを考えることは単に理論的な興味だけでなく，次 のような実用的な利点が考えられる．たとえば，アルゴリズムの部分問題のように，複数の

LSOCP

LSOCP

LSOCP

LSOCP

LSOCP

本報告書では，

LSOCP

LSOCP

(Linear Semi-Infinite Programming: LSIP)

LSIP

Dual-Simplex Primal-Exchange

(DSPE

)

LSIP

で表されるような制約条件の下で，線形関数を最小化するような問題である．なお，本報告書で提案する アプローチは，先に述べた

LSOCP

LSOCP

LSIP

[6]

LSOCP

DSPE

算機に実装することができる．

本報告書の構成を述べる．2節では，LSOCPと

LSIP

LSIP

3

LSIP

DSPE

LSIP

れた

LSOCP

4

LSOCP

3

単体法的アルゴリズムと既存の主双対内点法のソルバーとの比較実験およびその考察を行う．特に，構造が 似ている複数の

LSOCP

5

2

2.1

本節では，

LSIP

LSIP

.

LSIP

minimize c

x

subject to a

x ≥ b

(∀t ∈ T ) (2)

c ∈ R

T

a

= a(t) = (a

(t), . . . , a

(t))

T

R

= b(t)

T

R

問題

(2)

[15]

Haar

T

a

, b

T

maximize Z

T

b(t)µ(dt) subject to

Z

T

a(t)µ(dt) = c µ ∈ W, µ ≥ 0

(3)

ここで，Wは

T

≥ 0

T

⊆ T

µ(T

) ≥ 0

T

µ

Haar

supp λ := { t ∈ T λ

6= 0 }

λ : T → R

R

:= { λ : T → R

|supp λ| < ∞ }

(3)

(2)

1具体的には“有限個のディラック測度の重み和として表されるような離散測度”を指す．

に対する

Haar

maximize X

t∈T

λ

b

subject to X

t∈T

λ

a

= c λ ∈ R

(4)

ここで，

P

t∈T は

t ∈ supp λ

t ∈ T

(4)

(3)

(3)

(4)

[4, Chapter 8].

(4)

Haar

LSIP

また

LSIP

(2)

(4)

この命題は，

3

DSPE

命題

2.1. x

LSIP(2)

λ ∈ R

LSIP

(4)

λ

(a

x − b

) = 0 (t ∈ T ) (5)

x,λ

(2)

(4)

証明

. [4, Theorem 7.1 (i)]

[4, Theorem 7.6 (iii)]

2.2

本節では，二次錐を無限個の線形不等式制約で書き換えることにより

LSOCP

LSIP

k

K

命題

2.2. k − 1

T ˜ := ©

t ∈ R

ktk ≤ 1 ª

とする．このとき，

(u

, u) ∈ K

u

≥ t

u (∀t ∈ T ˜ ) (6)

が成り立つことである．

証明. まず，対偶を用いて必要性を示す．(6)式を満たさないような

(u

, u) ∈ R

t ∈ T

u

< t

u

u

< t

u ≤ kt

uk ≤ ktkkuk ≤ kuk

, u) ∈ / K

次に，十分性を示す．

(6)

(u

, u)

t

:= u/kuk

t

∈ T ˜

u

≥ (t

)

u = µ u

kuk

¶

u = kuk

(u

, u) ∈ K

次に，以下のように

K

A

b

A =



 

 

 

 

 

 µ (a

)

(A

)

¶ µ (a

)

(A

)

¶ .. . µ (a

)

(A

)

¶



 

 

 

 

 



b =



 

 

  µ b

b

¶ .. . µ b

b

¶



 

 

 

ここで，aⁱ

∈ R

, A

∈ R

, (b

, b

) ∈ R × R

(i = 1, . . . , p)

制約は

µ

(a

)

x + b

(A

)

x + b

¶

∈ K

(i = 1, . . . , p)

と書くことができる．したがって，命題

2.2

LSOCP(1)

LSIP

minimize c

x

subject to (a

− A

t

)

x ≥ (t

)

b

− b

(∀t

∈ T ˜

i = 1, . . . , p) (7)

T ˜

= ©

t

∈ R

¯

¯ kt

k ≤ 1 ª

である．次に

LSIP(7)

LSOCP(1)

およびそれらに対する最適性の条件について述べる．まず，LSOCP(1)に対する双対問題が以下のように 表わされることに注意する．

maximize −b

y subject to A

y = c

y ∈ K

(8)

また，LSOCPの主問題

(1)

LSOCP

(8)

命題

2.3. x ∈ R

(1)

y ∈ R

(8)

(Ax + b)

y = 0 (9)

が成り立つならば，

x, y

(1)

(8)

証明.

LSOCP

[16,

5.9]

一方，

LSIP (7)

maximize

λ¹,λ²,...,λ^p

X

X

tⁱ∈T˜ⁱ

λ

((t

)

b

− b

) subject to

X

X

tⁱ∈T˜ⁱ

λ

(a

− A

t

) = c λ

∈ R

(i = 1, . . . , p)

(10)

また，

LSIP(2)

(4)

2.1

に与えられる．

λ

n

(a

− A

t

)

x − ((t

)

b

− b

) o

= 0 (i = 1, . . . , p) (11)

LSIP(7)

(10)

LSOCP(1)

LSOCP(1)

LSIP(7)

x ∈ R

(8)

(10)

(10)

λ = (λ

)

∈ R

× · · · × R

LSOCP

(8)

y ∈ R

命題

2.4.

(10)

λ

y ∈ R

y :=



 

 

 

 

 

  µ y

y

¶ µ y

y

¶

.. . µ y

y

¶



 

 

 

 

 

 

=



 

 

 

 

 

  µ P

t¹∈T˜¹

λ

− P

t¹∈T˜¹

λ

t

¶ µ P

t²∈T˜²

λ

− P

t²∈T˜²

λ

t

¶

.. . µ P

t^p∈T˜^p

λ

− P

t^p∈T˜^p

λ

t

¶



 

 

 

 

 

 

(12)

と置くと，このとき，

y

(8)

(y

, y

) ∈ R × R

(i = 1, 2, . . . , p)

証明

.

(10)

Λ

λ ∈ Λ

(12)

y = (y

, y

)

i = 1, . . . , p

(y

)

− ky

k

=



 X

tⁱ∈T˜ⁱ

λ





2

−

° °

° °

° ° − X

tⁱ∈T˜ⁱ

λ

t

° °

° °

° °

2

≥



 X

tⁱ∈T˜ⁱ

λ



 −



 X

tⁱ∈T˜ⁱ

λ

kt

k





2

≥ 0

ここで，最初の不等号は

λ

≥ 0

kt

k ≤ 1

y ∈ K

(10)

(12)

c = X

a

X

tⁱ∈T˜ⁱ

λ

− X

A

X

tⁱ∈T˜ⁱ

λ

t

= X

¡ a

y

+ A

y

¢

= A

y

を得る．よって，

λ ∈ Λ

(12)

y

(8)

最後に

x, λ

(7)

(10)

(12)

y

LSOCP

(8)

命題

2.5.

(7)，(10)

x, λ

(11)

(12)

y

LSOCP

(9)

x, y

LSOCP

(1)

(8)

証明

. x, λ

(11)

(7)

(10)

x

(12)

y

LSOCP

(1)

(8)

さらに，(11)式より任意の

t

∈ T

(i = 1, 2, . . . , p)

((a

)

x + b

)λ

+ ((A

)

x + b

)

(−λ

t

) = 0

∈ supp λ

((a

)

x + b

)y

+ ((A

)

x + b

)

y

= 0 (13)

を得る．

(13)

i = 1, 2, . . . , p

(Ax + b)

y = 0

が成り立つ．よって，命題

2.3

x

y

LSOCP

(1)

(8)

3

前節では，

LSOCP

LSIP

LSIP

DSPE

[4, Chapter 12]

DSPE

LSOCP

LSIP

3.1 Dual-Simplex Primal-Exchange

DSPE

LP

LSIP

(exchange)

LSIP(2)

DSPE

DSPE

(4)

R

(4)

C ⊆ R

c ∈ C

定義

3.1. C ⊆ R

c

C

c = (1 − µ)c

+ µc

c

, c

∈ C \ {c}

µ ∈ (0, 1)

c

C

(extreme point)

問題

(4)

Λ := ©

λ ∈ R

¯

¯ P

λ

a

= c ª

と表す．Λは凸集合であるので，同 様に端点を定義できる．また，

Λ

• λ ∈ Λ

(t ∈ supp λ)

[3, Theorem 3.1]

•

λ ∈ Λ

| supp λ| = m

よって，DSPE法の初期点として，at

(t ∈ supp λ)

3.1

DSPE

{λ

} ⊆ R

Λ

LP

λ

∈ R

λ ∈ Λ

S ⊆ T

S

λ

(i) S ⊇ supp λ

(ii) a

(t ∈ S)

R

条件

(ii)

|S| = m

S

λ

しかし，条件

(i), (ii)

λ

S

S = supp λ

LP

DSPE

λ

(r = 1, 2, . . .)

3.1

2本定義はRⁿ内の凸集合に対する端点の定義の自然な拡張になっている．

以上のことをもとに，

DSPE

a

(t ∈ T )

m

r ∈ {0, 1, 2, . . .}

λ

6= 0

6= ∅

Dual-simplex primal-exchange method (DSPE

Step 0

λ

r := 0

S

⊆ T

λ

Step 1

a

x = b

(t ∈ S

)

x

Step 2 a

x

− b

< 0

t ∈ T

t

t

max

(a

x

− b

) ≥ 0

Step 3 supp g

⊆ S

P

t∈Sr

g

a

= a

g

∈ R

Step 4

−g

∈ R

そうでなければ，

µ

:= min

t∈Sr,g^r_t>0

{λ

/g

} t

:= argmin

t∈Sr,g^r_t>0

{λ

/g

}

Step 5 λ

S

 

 

 

 

 

 

 



λ

:= λ

− µ

g

(t ∈ S

, t 6= t

) λ

out

:= 0

λ

:= 0 (t ∈ T \ S

, t 6= t

) λ

in

:= µ

S

:= S

∪ {t

} \ {t

}

r := r + 1

Step 1

DSPE

定理

3.1. [4, Theorem 12.2] LSIP

DSPE

{(x

, λ

)}

r

3

(i) Step 2

x

, λ

(2)

(4)

(ii) Step 4

(4)

(2)

(iii)

Λ

X

t∈T

λ

b

< X

t∈T

λ

b

が成り立つ．

3この前提は非退化な端点が存在することに対する必要条件になっている．

このアルゴリズムについていくつか注意すべき点を述べる．

Step 2

x

ここで，毎回の反復で無限個の不等式制約の中でもっとも違反しているものを見つけることができれば，す なわち，t^r_in

= argmin

{a

x

− b

}

t

LSOCP

LSIP

t

Step 4

S

x

, g

n

3.2 LSOCP

LSIP

DSPE

本節では

LSIP(7)

DSPE

Step 1

x

Step 2

t

= argmin

{a

x

− b

}

t

∈ T

t

t

まず，LSIP(2)の

T

T ˜

(i = 1, . . . , p)

T = ˜ T

⊕ T ˜

⊕ · · · ⊕ T ˜

であることに注意する．したがって，

T

i ∈ {1, . . . , p}

t

∈ T ˜

t = (i, t

)

と表すことができる．次に，

r

x

T ˜

= ©

t

∈ R

¯

¯ kt

k ≤ 1 ª

を用いて，

t

s

(i = 1, . . . , p)

t

:= argmin

tⁱ∈T˜ⁱ

{(a

− A

t

)

x

− (t

)

b

+ b

}

= argmin

tⁱ∈T˜ⁱ

{(t

)

(−(A

)

x

− b

) + (a

)

x

+ b

}

= (A

)

x

+ b

k(A

)

x

+ b

k s

:= min

tⁱ∈T˜ⁱ

{(a

− A

t

)

x

− (t

)

b

+ b

}

= −k(A

)

x

+ b

k + (a

)

x

+ b

t

s

i

:= argmin

i=1,...,p

s

(14)

t

:= (i

, t

) (15)

とすることにより，trが陽に計算できる．なお，(14)において

i

s

:= min

i=1,...,p

s

(16)

について，

s

≥ 0

x

LSIP(2)

以上の議論をもとに

DSPE

LSIP(7)

DSPE

r

S

⊆ T

とする．また，任意の

t = (i, t

) ∈ T

˜

a

:= a

− A

t

(17)

˜ b

:= (t

)

b

− b

(7)

DSPE

LSOCP

LSIP

DSPE

Step 0

λ

r := 0

S

= supp λ

Step 1

a ˜

x = ˜ b

x

Step 2 t

(15)

t

:= t

(16)

s

Step 3 supp g

⊆ S

P

t∈Sr

g

˜ a

= ˜ a

g

∈ R

Step 4

µ

:= min

t∈Sr,g^r_t>0

{λ

/g

} t

:= argmin

t∈Sr,g^r_t>0

{λ

/g

}

Step 5 λ

S

 

 

 

 

 

 

 



λ

:= λ

− µ

g

(t ∈ S

, t 6= t

) λ

out

:= 0

λ

:= 0 (t ∈ T \ S

, t 6= t

) λ

in

:= µ

S

:= S

∪ {t

} \ {t

}

r := r + 1

Step 1

3.3

LP

LP

[12].

LP

LSIP(7)

DSPE

(10)

[3]

min ˜ λ

+ ˜ λ

+ · · · + ˜ λ

subject to

X

X

tⁱ∈T˜ⁱ

λ

(a

− A

t

) + X

λ ˜

e

= c

λ

∈ R

(i = 1, . . . , p), ˜ λ

≥ 0 (k = 1, . . . , m)

(18)

ただし，

c ≥ 0

˜ λ

∈ R (k = 1, . . . , m)

(10)

定理

3.2. [3, Theorem 6.1]

(10)

(18)

問題

(18)

v

4もし，cの成分で負のものがあれば，補助問題を生成する前に元の問題(10)の制約条件式で，cの成分が負になっている式の両 辺に−1をかけておけばよい．

•

(18)

v

≥ 0

•

v

> 0

(10)

• v

= 0

(10)

以上の第

1

λ

DSPE

(7)

二段階

DSPE

Step 1

(10)

(18)

DSPE

最適値が

0

Step 2

0

(10)

ルゴリズムを終了する．

Step 2 Step 1

(10)

DSPE

Step 1

(10)

人為変数に対応する添字が基底集合の中に残っていることがある．そのような場合でも，基底集合に残って いる人為変数に対応する添字を強制的に基底集合から追い出すようなピボット操作を行えばよい．すると，

最終的には元の問題

(10)

4

本節では，

LSOCP(1)

3

DSPE

SDPT3 [9]

とを適用し，それぞれの計算時間の比較を行う．また，構造が似ている複数の

LSOCP

SDPT3

DSPE

DSPE

本報告書では，実行可能解を持つような

LSOCP

LSOCP(1)

K

(i = 1, . . . , p)

b

b

= (b

, b

) ∈ R × R

b

(−1, 1)

r

(0, 1)

b

:= (1 + r)kb

k

A, c

(−1, 1)

A, b, c

≥ kb

k

x = 0

有界性や，

LSOCP

DSPE

Step 2

s

≥ −10

CPU

Pentium4 (3.2GHz × 2)

2GB

MATLAB 7.4

4.1 LSOCP

LSOCP(1)

DSPE

(SDPT3) [9]

まず，求めた解の精度を確かめるため，精度評価関数を定義する．命題

2.3

(x, y) ∈ R

× R