単体法で生成される解の数と 強多項式アルゴリズム

RIMS

(COSS) Kyoto, JAPAN

.

.

. . .

.

.

単体法で生成される解の数と 強多項式アルゴリズム 

北原知就

(T. KITAHARA),

(S. MIZUNO )

Tokyo Institute of Technology,

July 21–23, 2015

目次

.

. .

1

.

. .

2 LP

.

. .

3

.

. .

4

.

. .

5

.

.

6

Contents

.

. .

1

.

. .

2 LP

.

. .

3

.

. .

4

.

. .

5

.

. .

6

導入

1. 導入

導入

単体法

Dantzig

これまでのところ，反復回数の上界について，良 い結果は得られていない．

Klee–Minty

の例を示した．

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 5 / 53

導入

基底解の数

単体法の反復回数は，

問題の退化，

巡回現象，

によって無限回になり得る．そこで，ここでは生成さ れる 実行可能基底解 の数に注目する．

導入

LP の標準形

LP

min c ₁ x ₁ + c ₂ x ₂ + · · · + c _n x _n

subject to a 11 x 1 + a 12 x 2 + · · · + a 1n x n = b 1 , ...

a _m1 x ₁ + a _m2 x ₂ + · · · + a _mn x _n = b _m , ( x 1 , ^{x 2} , · · · , ^{x n} ) ^T ≥ ⁰ .

行列形式

min c ^T x ,

subject to Ax = b , ^x ≥ ⁰ .

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 7 / 53

導入

Dantzig のピボット規則

Dantzig

毎回の反復で，目的関数の係数が最小の変数を入 力変数に選ぶ．

導入

主結果

Dantzig

基底解の個数の上界は次式で与えられる．

( n − ^m ) d ^min { ^m , ⁿ − ^m } γ

δ ^log ( min { ^m , ⁿ − ^m } ^m γ δ ) e,

δ

γ

d ^a e

∈ <

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 9 / 53

導入

主結果

得られた上界

( n − ^m ) d ^min { ^m , ⁿ − ^m } γ

δ ^log ( min { ^m , ⁿ − ^m } γ δ ) e

LP

主問題が非退化の時，反復回数の上界となる．

導入

解析について

Ye（2010)

然な拡張．

LP

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 11 / 53

導入

上界のタイトさ

得られた上界

( n − ^m ) d ^min { ^m , ⁿ − ^m } γ

δ ^log ( min { ^m , ⁿ − ^m } γ δ ) e Klee-Minty

^γ _δ

x1

x

u0

u1

u2

u3

u4

u5

u6

u7

Contents

.

. .

1

.

. .

2 LP

.

. .

3

.

. .

4

.

. .

5

.

. .

6

LPに対する単体法

2. LP に対する単体法

LPに対する単体法

LP とその双対

LP

min c ^T x ,

subject to Ax = b , ^x ≥ ⁰ .

双対問題

max b ^T y ,

subject to A ^T y + s = c , ^s ≥ ⁰ .

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 15 / 53

LPに対する単体法

仮定

.

. ^.

1

rank( A ) = m．

.

.

.

2 主問題は最適解を持つ．

.

.

.

3 初期実行可能基底解

x ⁰

x ^∗ :

( y ^∗ , ^{s ∗} ) :

z ^∗ : LP

LPに対する単体法

変数等の分割

添え字集合

B ⊂ { ¹ , ² , . . . , ⁿ }

補集合

N = { ¹ , ² , . . . , ⁿ } − ^B

^A

^x

を次のように分割する．

A = [ A _B , ^A N ] , ^c = [ c B

c _N ]

, ^x =

[ x B

x _N ]

.

LP

min c ^T

B x B + c ^T

N x N ,

subject to A _B x _B + A _N x _N = b , x _B ≥ ⁰ , ^{x N} ≥ ⁰ .

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 17 / 53

LPに対する単体法

辞書

基底の集合

B = { ^B ⊂ { ¹ , ² , . . . , ⁿ }| | ^B | = m , ^det ( A _B ) , ⁰ }.

基底

B ∈ B

^N = { ¹ , ² , . . . , ⁿ } − ^B

の表現

min c ^T

B A ^{− 1}

B b + ( c N − ^A _N ^T ( A ^{− 1}

B ) ^T c B ) ^T x N , subject to x _B = A ^{− 1}

B b − ^A _B ^{− 1 A N x N} , x B ≥ ⁰ , ^{x N} ≥ ⁰ ,

この形式を辞書という．

LPに対する単体法

実行可能基底解

¯ c N

= c N

− ^A _N ^T

( A ^{− 1}

B

) ^T c B

(reduced cost)

min c ^T

B A ^{− 1}

B b + ¯ c ^T

N x _N , subject to x B = A ^{− 1}

B b − ^A _B ^{− 1 A N x N} ≥ ⁰ , x _N ≥ ⁰ .

主問題の実行可能基底解は次のようになる．

x _B = A ^{− 1}

B b ≥ ⁰ , ^x N = 0 .

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 19 / 53

LPに対する単体法

δ ^と γ

δ ^:

γ ^:

4

LP

v ₁ = ( 2 , ³ , ⁰ , ⁰ ) , ^v 2 = ( 2 , ¹ , ⁰ , ⁰ ) ,

v ₃ = ( 0 , ⁴ , ⁰ , ⁶ ) , ^{v 4} = ( 0 , ⁰ , ³ , ⁷ ) .

LP

δ = 1

γ = 7

LPに対する単体法

Dantzig のピボット規則

¯ c _N

≥ ⁰

そうでないときはピボットを行う．Dantzigの規則で は，縮小コストが最小の変数を入力に選ぶ．正確には，

j ^k ∈ ^{arg min}

j ∈ N

¯ c _N

.

となる添え字を選ぶ．

∆ ^k = − ¯ c _j

> ⁰

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 21 / 53

LPに対する単体法

表記

x ^∗ :

( y ^∗ , ^{s ∗} ) :

z ^∗ :

x ^k :

k

B ^k : x ^k

N ^k : x ^k

¯ c _N

: k

∆ ^k : − ^{min j} ∈ N

_c ¯ _j

j ^k : Dantzig

Contents

.

. .

1

.

. .

2 LP

.

. .

3

.

. .

4

.

. .

5

.

. .

6

単体法によって生成される基底解の数

3. 単体法によって生成される

基底解の数

単体法によって生成される基底解の数

∆ ^k の下界 ( 補題 3.2)

次の命題は，最小係数の絶対値

∆ ^k

.

Lemma

.

.

.

. . .

.

.

x ^k

Dantzig

t

このとき，

∆ ^k ≥ ^{c T x t} − ^{z ∗} min { ⁿ − ^m , ^m }γ

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 25 / 53

単体法によって生成される基底解の数

証明

. x ^∗

Dantzig

_c ¯ _N

≥ − ∆ ^t e

z ^∗ = c ^T x ^∗

= c ^T

B

A ^{− 1}

B

b + ¯ c ^T

N

x ^∗

N

≥ ^{c T x t} − ∆ ^t e ^T x ^∗

N

≥ ^{c T x t} − ∆ ^t min { ⁿ − ^m , ^m }γ,

ここで，2番目の不当式は

x ^∗

γ

単体法によって生成される基底解の数

ギャップの定比率の減少 ( 定理 3.3)

次の定理は，解が更新されるとき，ギャップ

( c ^T x − ^{z ∗} )

.

Theorem

.

.

.

. . .

.

.

x ^k

x ^{k +1}

Dantzig

k

+ 1

目の点とする．もし

x ^{k +1} , ^{x k}

c ^T x ^t+1 − ^{z ∗} ≤ ( 1 − δ

min { ⁿ − ^m , ^m } )( c ^T x ^t − ^{z ∗} ) .

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 27 / 53

単体法によって生成される基底解の数

証明. x

^t

j

k

x ^t+1

j

= 0

x ^t+1 = x ^t

よって

x ^t+1

j

, ⁰

δ

^x _j ^t+1

≥ δ

すると，

c ^T x ^t − ^{c T x t+1} = ∆ ^t x ^t+1

j

≥ ∆ ^t δ

≥ _{min { n −} ^δ _{m , m }γ} ( c ^T x ^t − ^{z ∗} ) .

2

3.2

単体法によって生成される基底解の数

基底解の要素の上界 ( 補題 3.5)

.

Lemma

.

.

.

. . .

.

.

x ^t

Dantzig

t

x ^t

¯ _j ∈ ^{B t}

x ^t

¯ j > ⁰

x

x ¯ j ≤ ^min { ^m , ⁿ − ^m } ^{c T x} − ^{z ∗} c ^T x ^t − ^{z ∗ x}

t

¯ j

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 29 / 53

単体法によって生成される基底解の数

証明．

( x ^k ) ^T s ^∗ = ∑

j ∈ B

x ^k

j s ^∗

j = ∑

j ∈ B

∩ N

x ^k

j s _j

| ^{B k} ∩ ^{N ∗} | ≤ ^min { ^m , ⁿ − ^m }

¯ _j ∈ ^{B k}

x _¯ ^k

j s _¯ ^∗

j ≥ ¹

| ^{B k} ∩ ^{N ∗} | ( x ^k ) ^T s ^∗ = ¹

| ^{B k} ∩ ^{N ∗} | ( c ^T x ^k − ^{z ∗} ) > ⁰

_¯ ^k

j > ⁰

| ^{B k} ∩ ^{N ∗} | ≤ ^min { ^m , ⁿ − ^m }

s _¯ ^∗

j ≥ ¹

min { ^m , ⁿ − ^m } ^x _¯ ^k

j

( c ^T x ^k − ^{z ∗} ) .

となる．

単体法によって生成される基底解の数

証明の続き．任意の実行可能解

x

c ^T x − ^{z ∗} = x ^T s ^∗ ≥ ^{x ¯} j s ^∗

¯ j

x ¯ j ≤ ^{c T x} − ^{z ∗} s ^∗

¯ j

≤ ^min { ^m , ⁿ − ^m } ^{c T x} − ^{z ∗} c ^T x ^t − ^{z ∗ x}

k

¯ j .

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 31 / 53

単体法によって生成される基底解の数

最適解で 0 になる変数 ( 補題 3.6)

.

Lemma

.

.

.

.

.

x ^t

Dantzig

t

x ^t

¯ _j ∈ ^{B t}

.

.

.

1

x ^t

¯ j > ^0.

.

.

.

2

t

d ^min { ^m , ⁿ − ^m } ^γ _δ ^log ( min { ^m , ⁿ − ^m } ^γ _δ ) e

¯ j

0

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 32 / 53

単体法によって生成される基底解の数

証明．l

≥ ^t + 1

˜ _l

_t + 1

l

このとき，Lemma 3より，ある添え字

¯ _j ∈ ^{B k}

x _¯ ^l

j ≤ ^min { ^m , ⁿ − ^m } ^{c T x l} − ^{z ∗} c ^T x ^k − ^{z ∗ x}

k

¯ j

を満たす．ここで，x

_¯ ^k

j ≤ γ

^{Theorem 2}

x ^l

¯ j ≤ ^min { ^m , ⁿ − ^m }γ ( 1 − δ

min { ^m , ⁿ − ^m }γ ) ^{˜ l} .

˜ _l > ^min { ^m , ⁿ − ^m } ^γ _δ ^log ( min { ^m , ⁿ − ^m } ^γ _δ )

x ^l

¯ j < δ

δ

^x _¯ ^l

j = 0

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 33 / 53

t

l

min { ^m , ⁿ − ^m } ^γ _δ ^log ( min { ^m , ⁿ − ^m } ^γ _δ )

^l = 0

単体法によって生成される基底解の数

基底解の数の上界

補題

3.6

( y ^∗ , ^{s ∗} )

s ^∗

j

j

x _j

.

Theorem

.

.

.

. . .

.

.

最適解をもつ

LP

Dantzig

c ^T x

( n − ^m ) d ^min { ^m , ⁿ − ^m } γ

δ ^log ( min { ^m , ⁿ − ^m } γ δ ) e.

この結果は，巡回によって最適解が求まらない場合に も有効である．

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 35 / 53

単体法によって生成される基底解の数

主問題が非退化の場合

主問題が非退化であれば，任意の

k

x ^{k +1} , ^{x k}

(生成される実行可能基底解の数)=(反復回数)．

.

Corollary

.

.

.

. .

主問題が非退化であるならば，多くとも

( n − ^m ) d ( min { ^m , ⁿ − ^m } γ

δ ^log ( min { ^m , ⁿ − ^m } γ δ ) e

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 36 / 53

Contents

.

. .

1

.

. .

2 LP

.

. .

3

.

. .

4

.

. .

5

.

. .

6

特殊な線形計画問題への適用

4. 特殊な線形計画問題への適用

特殊な線形計画問題への適用

完全ユニモジュラ行列の場合

.

Corollary

.

.

.

. . .

.

.

A

( n − ^m ) d ^min { ^m , ⁿ − ^m }k ^b k ^{1 log} ( min { ^m , ⁿ − ^m }k ^b k ¹ ) e.

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 39 / 53

特殊な線形計画問題への適用

マルコフ決定問題

マルコフ決定問題：

min c ^T

1 x ₁ + c ^T

2 x ₂ ,

subject to ( I − θ ^{P 1} ) x ₁ + ( I − θ ^{P 2} ) x ₂ = e , x ₁ , ^x 2 ≥ ⁰ ,

ここで

P 1

P 2

m × ^m

θ

1

m d ^{m 2} 1 − θ ^log

m ²

1 − θ e

特殊な線形計画問題への適用

その他の話題

上下限制約付き線形計画問題への拡張

双対単体法が生成する異なる実行可能基底解の数 の上界

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 41 / 53

Contents

.

. .

1

.

. .

2 LP

.

. .

3

.

. .

4

.

. .

5

.

.

6

単体法で生成される解の最大数の下界

5. 単体法で生成される解の 最大数の下界

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 43 / 53

単体法で生成される解の最大数の下界

Klee-Minty 問題の一変種

北原-水野

(2011)

max ∑ m

i=1 x _i subject to x ₁ + y ₁ = 1

2 ∑ k − 1

i=1 x _i + x _k + y _k = 2 ^k − ¹ ( k = 2 , ³ , . . . , ^m )

x ≥ ⁰ , ^y ≥ ⁰ .

単体法で生成される解の最大数の下界

問題の性質

実行可能基底解において，任意の

i ∈ { ¹ , . . . , ^m }

i

y i

1

2 ^m

実行可能基底解の各要素は整数である．

非退化である．

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 45 / 53

単体法で生成される解の最大数の下界

Dantzig の規則との関連

.

Theorem

.

.

.

.

.

x = 0

Dantzig

反復回数は

2 ^m − ¹

全ての辞書において，縮約コストの要素は

1

− ¹

毎回の反復において目的関数は

1

したがって，任意の整数

k ∈ [ 0 , ^{2 m} − ¹ ]

目的関数値が

k

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 46 / 53

単体法で生成される解の最大数の下界

m = 2 のとき

x

x

v

v

v

v

δ = 1 , γ = 3 .

= 3 = ^γ _δ

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 47 / 53

単体法で生成される解の最大数の下界

m = 3 のとき

x

x

x

u

u

u

u

u

u

u

u

δ = 1 , γ = 7 .

= 7 = ^γ _δ

単体法で生成される解の最大数の下界

Klee-Minty 問題との比較

反復回数の上界：

( n − ^m ) d ^min { ^m , ⁿ − ^m } ^γ _δ ^log ( min { ^m , ⁿ − ^m } ^γ _δ ) e

γ/δ

Klee- Minty 100 ^{(m − 1)} 2 ^m − ¹

2 ^m − ^{1 2 m} − ¹

γ

δ

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 49 / 53

Contents

.

. .

1

.

. .

2 LP

.

. .

3

.

. .

4

.

. .

5

.

.

6

まとめ

5. まとめ

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 51 / 53

まとめ

問題，ピボット規則，仮定

問題：等式標準形の

LP

.

.

.

1

Dantzig

(最小係数規則)

仮定：

.

.

.

1

rank(A ) = m.

.

.

.

2 主問題は最適解を持つ．

.

.

.

3 初期実行可能解が得られている．

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 52 / 53

まとめ

主結果

生成される実行可能基底解の個数の上界

( n − ^m ) d ^min { ^m , ⁿ − ^m } γ

δ ^log ( min { ^m , ⁿ − ^m } γ δ ) e δ, γ

最大値

上界の初等的な導出

Klee-Minty

^γ _δ

Tomonari KITAHARA and Shinji MIZUNO (TIT) 単体法と強多項式アルゴリズム July 21–23, 2015 53 / 53