離散最適化基礎論第 11回組合せ最適化と半正定値計画法

Size: px

Start display at page:

Download "離散最適化基礎論第 11回組合せ最適化と半正定値計画法"

さやあんさい
5 years ago
Views:

1 :59 ( ) (11) / 38

2 1 (10/5) 2 (1) (10/12) 3 (2) (10/19) 4 (3) (10/26) (11/2) 5 (1) (11/9) 6 (11/16) 7 (11/23) (11/30) (12/7) ( ) (11) / 38

3 ( ) 8 (2) (12/14) 9 (1) (12/21) 10 (2) (1/11) (1/18) 11 (1/25) 12 (2/1) 13 (2/8) (2/15 ) ( ) ( ) (11) / 38

4 Lovász Lovász ( ) (11) / 38

5 1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) / 38

6 n 1 A R n n A (positive semidefinite matrix) x R n ( ) x Ax 0 ( ) ( ) ( ) 1 0 x x y = x y A A O A A ( ) (11) / 38

7 n 1 A R n n 1 A 2 A ( ) 3 J {1, 2,..., n} det(a JJ ) 0 A JJ J J A 4 L R n r A = LL r = rank A (A (Cholesky decomposition)) ( ) 1 0 1, ( ) ( ) (1 ) = ( ) (11) / 38

8 n 1 S n R n n n S+ n R n n n ( ) ( ) ( ) , S , S S n + S n + ( ) (11) / 38

9 1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) / 38

10 (semidefinite programming) n 1, m 0 C, A 1,..., A m R n n b 1,..., b m R ( X ) maximize C X subject to A i X = b i (i {1,..., m}) X O n n C X = C ij X ij = tr(c X ) i=1 j=1 ( ) (11) / 38

11 max. C X max. c x s. t. A i X = b i (i {1,..., m}) X O s. t. a i x = b i (i {1,..., m}) x 0 ( ) (11) / 38

12 maximize C X subject to A i X = b i (i {1,..., m}) X O { = X S n A i X = b i X O (i {1,..., m}) } {X X O} (S n + ) A i X = b i A i X b i A i X b i 2 ( ) (11) / 38

13 ( ) maximize C X subject to A i X = b i (i {1,..., m}) X O { = X S n A i X = b i X O (i {1,..., m}) } ( ) (11) / 38

14 1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) / 38

15 László Lovász (1948 ) lovasz/ ( ) (11) / 38

16 Lovász G = (V, E) n = V Lovász G Lovász (Lovász number) (LOV) maximize u V v V X uv subject to X uv = 0 ({u, v} E) X vv = 1 v V X O ( X S+) n G Lovász ϑ(g) ( ) (11) / 38

17 Lovász G = (V, E) n = V Lovász G Lovász ϑ(g) (LOV) maximize u V v V X uv subject to X uv = 0 ({u, v} E) X vv = 1 v V X O ( X S+) n ( ) (11) / 38

18 Lovász G = (V, E) Lovász ω(g) ϑ(g) χ(g) Lovász 1 ω(g) ϑ(g) 2 ϑ(g) χ(g) ( ) (11) / 38

19 Lovász (1) C G y R n { 1 (v C) y v = 0 (v C) X = 1 C yy ( ) (11) / 38

20 Lovász (2) X = 1 C yy X (LOV) X (c.f. ) {u, v} E u, v C v V X vv = v V X uv = 1 C y uy v = 0 1 C y v 2 = 1 C C = 1 X uv ϑ(g) = (LOV) u V v V = 1 C y uy v = 1 C C 2 = C = ω(g) u V v V ( ) (11) / 38

21 Lovász G = (V, E) Lovász ω(g) ϑ(g) χ(g) Lovász 1 ω(g) ϑ(g) ( ) 2 ϑ(g) χ(g) ( ) (11) / 38

22 Lovász (1) X (LOV) χ(g) = k V k V 1,..., V k j {1,..., k} y j R n { yv j 1 (v V j ) = 0 (v V j ) ( ) (11) / 38

23 Lovász (2) X (ky j 1) X (ky j 1) 0 0 k (ky j 1) X (ky j 1) j=1 k = k 2 y j X y j 2k j=1 k = k 2 k y j X 1 + j=1 k 1 X 1 j=1 X vv 2k1 X 1 + k1 X 1 j=1 v V j = k 2 X vv k X uv v V u V v V = k 2 kϑ(g) ϑ(g) k = χ(g) ( ) (11) / 38

24 Lovász G = (V, E) Lovász ω(g) ϑ(g) χ(g) Lovász 1 ω(g) ϑ(g) ( ) 2 ϑ(g) χ(g) ( ) ( ) (11) / 38

25 1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) / 38

26 Lovász G = (V, E) n = V Lovász G Lovász (Lovász number) (LOV) maximize G Lovász ϑ(g) u V v V X uv subject to X uv = 0 ({u, v} E) X vv = 1 v V X O ( X S n +) ϑ(g) ( ) (11) / 38

27 ϑ(g) χ(g) X ( ) 2 Xuv 2 X uv χ(g) 2 u V v V u V v V χ(g) ( ) ( ) (11) / 38

28 (1) (LOV) = X S n X uv = 0 ({u, v} E) X vv = 1 v V X O n 2 1 n(n + 1) E 1 2 X ( ) 1 (u = v) X uv = n 0 (u v) ( ) (11) / 38

29 (2) X uv = 0 ({u, v} E) (LOV) = X S n X vv = 1 v V X O X A R n n i a ii a ij j i ( ) (11) / 38

30 (1) A R n n A λ 1 x x x i k (x k 0 ) Ax = λx k n a kj x j = λx k j=1 a kj x j = (λ a kk )x k j k ( ) (11) / 38

31 (2) ( ) x k 0 a kj x j j k λ a kk = a kj x j x k x k j k A λ a kk a kk a kj j k λ [0, 2a kk ] λ 0 ( ) (11) / 38

32 Lovász G = (V, E) n = V Lovász G Lovász (Lovász number) (LOV) maximize u V v V X uv subject to X uv = 0 ({u, v} E) X vv = 1 v V X O ( X S n +) Lovász ( ) (11) / 38

33 1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) / 38

34 Lovász ω(g) ϑ(g) χ(g) ϑ(g) G ω(g) = χ(g) ω(g) = ϑ(g) = χ(g) ϑ(g) ω(g), χ(g) ( ) (11) / 38

35 1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) / 38

36 Lovász Lovász ( ) (11) / 38

37 ( ) OK OK ( ) (11) / 38

38 1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) / 38

離散最適化基礎論 第 11回 組合せ最適化と半正定値計画法

離散最適化基礎論第 11回組合せ最適化と半正定値計画法