狠狠撸

MAXCUT via Semide?nite Programming
Yuya Masumura
December 5, 2018
1

Introduction: Motivation
NP 困難な問題に対して, 半正定値計画問題 (SDP) を利用した
様々な近似アルゴリズムが開発されている.
SDP を利用した近似アルゴリズムの例
? 0.8785-approximation for MAXCUT(Goemans, Williamson ’95)
? 0.8785-approximation for MAX2SAT(Goemans, Williamson ’95)
? 7/8-approximation for MAX3SAT(Karlo?, Zwick ’97)
? etc.
2

Introduction: Textbook
Approximation Algorithms and Semide?nite Programming Chap.1-2, 4, 8
? B. G¨artner と J. Matouˇsek による本
? タイトル通り, 半正定値計画を使った
近似アルゴリズムがテーマ
他にも参考文献として,
最適化法 (田村, 村松) と非線形最適化の基礎 (福島) を使用しました.
3

Outline
Introduction
Cone Programming
Semide?nite Programming
0.878-approximation Algorithm for Maximum Weighted Cut Problem
Appendix
4

Introduction: Goal
Goal
? 半正定値計画問題 (SDP) についての基本的な事実を理解する
? 問題の定義
? 弱双対定理, 双対定理
? そのために, まず錐計画問題における以下の内容を理解する
? 錐の定義
? 弱双対定理, Farkas の補題, 双対定理
? 半正定値計画問題を使った近似アルゴリズムを理解する
? 今回は最大カット (MAXCUT) の 0.8785-近似アルゴリズム
また, 最大カット問題の近似率に関するいくつかの結果のみ紹介する.
(時間があれば...)
錐計画, 半正定値計画に対する解法は詳細に扱いません＞＜
5

Outline
Introduction
Cone Programming
Cone
Cone Linear Programming
Duality of Cone Linear Programming
Appendix
6

Remember...
非線形ゼミでの思い出....
これを錐線計画で示しましょう！
7

Cone
De?nition 2.1
集合 K ∈ Rn
が以下を満たすとき, K を錐 (cone) とよぶ.
x ∈ K, α ∈ [0, ∞) ? αx ∈ K (1)
また, 錐が
? 凸集合なら凸錐 (convex cone),
? 閉集合なら閉錐 (closed cone),
? 閉集合でかつ凸集合なら閉凸錐 (closed convex cone)
という.
8

Another De?nition of Closed Convex Cone
閉凸錐の定義として, 以下のようなものもある.
(以降では, 証明を簡単にするためにこの定義を用いる)
De?nition 2.2
閉集合 K ∈ Rn
が以下を満たすとき,
K を閉凸錐 (closed convex cone) とよぶ.
1. x ∈ K, α ∈ [0, ∞) ? αx ∈ K
2. x, y ∈ K ? x + y ∈ K
9

Examples of Closed Convex Cone
簡単な例
以下の K1 から K4 はいずれも閉凸錐.
ただし, 0 ?= ai
∈ Rn
(i = 1, . . . , m) で, m は任意の正整数.
? K1 = {x ∈ Rn
| x =
∑m
i=1 βiai
, βi ≥ 0 (i = 1, . . . , m)}
? K2 = {x ∈ Rn
| ?ai
, x? ≤ 0 (i = 1, . . . , m)}
? K3 = {x ∈ Rn
| x2
1 ≥ x2
2 + · · · + x2
n, x1 ≥ 0}
? K4 = {x ∈ R3
| x1x3 ? x2
2 ≥ 0, x1 + x3 ≥ 0}
いずれも錐であることはすぐに確かめられる.
10

K1 and K2
K1 と K2 が凸錐であることはすぐに確かめられる.
K1 が閉集合になっていることはすぐに示せなかった....(cf. Rockafellar
”Convex Analysis”)
K2 は各 ai で定義される以下の閉半空間
{x ∈ Rn
| ?ai
, x? ≤ 0}
の共通部分なので, 閉集合である.
11

convexity of K3
K3 = {x ∈ Rn
| x2
1 ≥ x2
2 + · · · + x2
n, x1 ≥ 0}
は凸であることを確かめる.
(閉集合であることは補集合を調べればよい)
x, y ∈ K3 について, x2
1 ≥
∑n
i=2 x2
i , y2
1 ≥
∑n
i=2 y2
i
x + y について, 以下の式が非負であることを確かめる.
(x1 + y1)2
?
n∑
i=2
(xi + yi)2
= 2(x1y1 ?
n∑
i=2
xiyi)
x′
= (x2, x3, . . . , xn)?
, y′
= (y2, y3, . . . , yn)?
とおくと,
Cauchy–Schwarz の不等式より, ∥x′
∥∥y′
∥ ≥ x′?
y′
であるから,
x1y1 ≥ ∥x′
∥∥y′
∥ ≥ x′?
y′
=
n∑
i=2
xiyi
12

K4
x = (x1, x2, x3)?
の成分からなる対称行列 X ∈ R2×2
を考える.
X =
[
x1 x2
x2 x3
]
X の固有値を λ1, λ2 とする.
K4 の定義と, 行列のトレース, 行列式と固有値の関係より,
x ∈ K4 ?
{
λ1 + λ2 = TrX = x1 + x3 ≥ 0
λ1λ2 = detX = x1x3 ? x2
2 ≥ 0
? λi ≥ 0 (i = 1, 2)
つまり, K4 は 2 次の半正定値行列の全体を表す.
13

Cone of Positive Semide?nite Matrix Set
n 次半正定値対称行列の集合 Pn を以下のように定義する.
Pn = {M ∈ Rn×n
| x?
Mx ≥ 0 (?x ∈ Rn
} (2)
Lemma 2.1
Pn は閉凸錐である.
また, 以降では X が半正定値行列であるとき, X ? 0 と書く.
(証明)
α ∈ [0, ∞), M, N ∈ SDP とする. x ∈ Rn
に対して,
x?
(αM)x = α(x?
Mx) ≥ 0,
x?
(M + N)x = x?
Mx + x?
Nx ≥ 0 より凸錐である. 閉集合になって
いることを調べるために, PSDn の補集合を調べる. ?x?
M ?x < 0 となる
?x ∈ Rn
が存在するような n 次実対称行列 M があるとすると, M の近
傍の M′
についてもこの不等式は成り立ち, よって PSDn の補集合は開
集合となる.
14

Dual Cone
De?nition 2.3
錐 K ∈ Rn
に対して,
K?
= {y ∈ Rn
| ?y, x? ≥ 0 (x ∈ K)} (3)
を K の双対錐 (dual cone) もしくは, 極錐 (polar cone) という.
閉凸錐 K が K?
= K であるとき,
K を自己双対錐 (self-dual cone) という.
15

Separation Theorem for Closed Convex Cones
以下の分離定理 (Separation Theorem) を示す.
Theorem 2.1
K ? Rn
を閉凸錐, b ∈ Rn
K とする.
このとき, 以下を満たすある y ∈ Rn
が存在する
全ての x ∈ K について ?y, x? ≥ 0 かつ ?y, b? < 0
(証明の方針)
z = argmin
w∈K
∥b ? w∥ = argmin
w∈K
√
?b ? w, b ? w? とし,
y = z ? b が上の条件を満たしていることを示す.
このような z ∈ K が一意に存在するという事実は証明せずに用いる
(cf. 福島, “非線形最適化の基礎”, § 2.4, 定理 2.6).
16

Proof of Separation Theorem
(証明)
z = argmin
w∈K
∥b ? w∥ とし, y = z ? b とする. まず, ?y, z? = 0 を示す.
z = 0 のときは自明なので, z ?= 0 の場合を考える.
?y, z? > 0 と仮定する.
ある小さい α > 0 に対して, z′
= (1 ? α)z とする.
∥z′
? b∥2
= ?(y ? αz), (y ? αz)? = ∥y∥2
? 2α?y, z? + α2
∥z∥2
, また,
十分に小さい α > 0 に対して, 2α?y, z? > α2
∥z∥2
.
よって, ∥z′
? b∥2
< ∥y∥2
= ∥z ? b∥2
. これは z の選び方に反する.
?y, z? > 0 の場合も z′
= (1 + α)z とすれば同様. 以上より ?y, z? = 0.
0 < ?y, y? = ?y, z? ? ?y, b? = ??y, b?.
17

Proof of Separation Theorem
次に, ?y, x? ≥ 0 を示す. x ∈ K, x ?= z とする.
このとき, ?(b ? z), (x ? z)? ≤ 0 である. そうでないと仮定すると
(即ち, ?(b ? z), (x ? z)? > 0 とすると), z′
= αx + (1 ? α)z として,
∥b ? z′
∥2
=∥b ? αx ? (1 ? α)z)∥2
=∥(b ? z) ? α(x ? z)∥2
=∥ ? y ? α(x ? z)∥2
=∥y∥2
+ 2α?y, (x ? z)? + α2
∥x ? z∥2
=∥y∥2
+ 2α?y, x? + α2
∥x ? z∥2
また, ?y, z? = 0 より, ?(b ? z), (x ? z)? = ??y, (x ? z)? = ??y, x? > 0.
よって, 十分に小さい α > 0 に対して ?2α?y, x? > α2
∥x ? z∥2
.
即ち, ∥z′
? b∥2
< ∥y∥2
= ∥z ? b∥2
. これは z の選び方に反する.
以上より, ?(b ? z), (x ? z)? ≤ 0 を得る.
よって, 0 ≥ ?(b ? z), (x ? z)? = ??y, x? + ?y, z? = ??y, x?.
18

Dual Cone of K?
Theorem 2.2
閉凸錐 K ? Rn
に対して, (K?
)?
= K が成り立つ.
(i) K ? (K?
)?
(i.e., b ∈ K ? b ∈ (K?
)?
) を示す.
b ∈ K とする. K?
の定義より, 全ての y ∈ K?
に対して,
?y, b? = ?b, y? ≥ 0 より, b ∈ (K?
)?
(ii) K ? (K?
)?
(i.e., b /∈ K ? b /∈ (K?
)?
) を示す.
b ∈ Rn
K とする. 分離定理より, 全ての x ∈ K について,
?y, x? ≥ 0 かつ ?y, b? = ?b, y? < 0 となるベクトル y が存在する.
一つめの不等式より y ∈ K?
. また, 2 つめの不等式より b /∈ (K?
)?
.
19

Cone Linear Programming
K ? Rn
を閉凸錐とする.
このとき, 以下の非線形最適化問題を考える.
Minimize ?c, x? (4)
subject to ?ai, x? = bi (i = 1, . . . , m)
x ∈ K.
このように, 線形制約と錐制約のみをもち,
線形目的関数を最小化, または最大化する問題を
錐線計画問題 (cone linear programming problem) とよぶ.
20

Dual Problem
(4) の双対問題 (dual problem) を
Maximize b?
y (5)
subject to s +
m∑
i=1
yiai = c,
s ∈ K?
.
と定める. 双対問題に対し, (4) を主問題という.
21

Weak Duality
Theorem 2.3
x を主問題 (4) の許容解, (y, s) を双対問題 (5) の許容解とすると,
?c, x? ≥ b?
y
(証明)
x, (y, s) をそれぞれ主問題 (4), 双対問題 (5) の許容解とすると,
?c, x? ? b?
y = ?c, x? ?
m∑
i=1
yi?ai, x?
= ?c ?
m∑
i=1
yiai, x?
= ?s, x? ≥ 0.
22

Farkas Lemma, Cone Version
De?nition 2.4
錐 K ? Rn
とベクトル a1, . . . , am ∈ Rn
が与えられたとき,
錐 K の像 (image) を次のように定義する.
C[a1, . . . , am; K] =
?
??
??
?
?
?
?a1, x?
...,
?am, x?
?
?
? ∈ Rm
x ∈ K
?
??
??
C[a1, . . . , am; K] は明らかに錐の定義を満たす.
また, K が凸錐 ? C[a1, . . . , am; K] は凸錐
これが閉集合のとき, 次の Farkas の補題を満たす.
23

Farkas Lemma, Cone Version (and its Proof)
Lemma 2.2 (Farkas Lemma)
K ? Rn
を閉凸錐とし,
a1, . . . , am ∈ Rn
および b ∈ Rm
が与えられているとする.
もし K の像 C[a1, . . . , am; K] が閉集合ならば,
次の 1, 2 のうちどちらか一方のみ成り立つ.
1. ?ai, x? = bi (i = 1, . . . , m) を満たす x ∈ K が存在する.
2. b?
y < 0,
∑m
i=1 yiai ∈ K?
を満たす y ∈ Rm
が存在する.
(証明)
C := C[a1, . . . , am; K] とする.
まず, 1 と 2 が同時に成り立たないことを示す. もし成り立つとすると,
0 > b?
y =
m∑
i=1
?ai, x?yi =
m∑
i=1
?yiai, x? ≥ 0
となり矛盾するからである.
24

Proof of Farkas Lemma
Lemma 2.3 (Farkas Lemma)
K ? Rn
を閉凸錐とし,
a1, . . . , am ∈ Rn
および b ∈ Rm
が与えられているとする.
もし K の像 C[a1, . . . , am; K] が閉集合ならば,
次の 1, 2 のうちどちらか一方のみ成り立つ.
1. ?ai, x? = bi (i = 1, . . . , m) を満たす x ∈ K が存在する.
2. b?
y < 0,
∑m
i=1 yiai ∈ K?
を満たす y ∈ Rm
が存在する.
以下では, 1 が成り立たないとき, 2 が成り立つことを示す.
このとき, b ∈ Rm
C である.
C ? Rm
は閉凸錐なので, 先ほど示した分離定理より,
ある y ∈ Rm
が存在して, b?
y < 0 かつ全ての u ∈ C に対し ?y, u? ≥ 0.
即ち, 任意の x ∈ K に対し
∑m
i=1 yi?ai, x? = ?
∑m
i=1 yiai, x? ≥ 0.
K?
の定義より,
∑m
i=1 yiai ∈ K?
. したがって y は 2 を満たす.
25

Regular Duality
Theorem 2.4 (Duality Theorem)
主問題 (4) および双対問題 (5) に許容解が存在すると仮定する. この
ときもし, 集合 C[c, a1, . . . , am; K] が閉集合ならば, 双対ギャップは存
在せず, 主問題には最適解が存在する.
26

Proof of Duality Theorem
(証明)
主問題に最適解が存在することは,
C[c, a1, . . . , am; K] が閉集合より自明.
双対ギャップが存在すると仮定して, 矛盾を導く.
θP := inf{?c, x? | ?ai, x? = bi (i = 1, . . . , m), x ∈ K}
θD := sup{b?
y | s +
m∑
i=1
yiai = c, s ∈ K?
}
とおくと, 双対ギャップがあるので, θP > θD. このとき,
?
?
?
?
?
?
?c, x?
?a1, x?
...
?am, x?
?
?
?
?
?
?
=
?
?
?
?
?
?
θD
b1
...
bm
?
?
?
?
?
?
を満たす x ∈ K は存在しない.
27

したがって, Farkas の補題より, ある (y0, y) ∈ Rm+1
が存在して,
θDy0 + b?
y < 0 (6)
かつ
y0c +
m∑
i=1
yiai ∈ K?
(7)
を満たす. (7) は, K?
の定義より, 以下のように書き換えられる.
y0?c, x? +
m∑
i=1
yi?ai, x? ≥ 0, ?x ∈ K (8)
ここで, y0 について 3 つの場合に分け, いずれも矛盾することを示す.
28

(i) y0 = 0 のとき
(6) と (8) に y0 = 0 を代入すると,
m∑
i=1
yi?ai, x? ≥ 0, ?x ∈ K (9)
かつ
b?
y < 0 (10)
である. (9) は即ち
m∑
i=1
yiai ∈ K?
.
Farkas の補題より (ここでは, K の像として C[a1, . . . , am; K] を考える),
主問題 (4) には許容解が存在しない. これは仮定に反する.
29

(ii) y0 < 0 のとき
C[c, a1, . . . , am; K] が閉集合より, 主問題 (4) には最適解 x?
が存在して,
?c, x?
? = θP , ?ai, x?
? = bi (i = 1, . . . , m)
これを (8) に代入した結果と, (6) より,
y0θP + y?
b ≥ 0 > y0θD + b?
y
よって y0(θP ? θD) > 0. 更に, y0 < 0 より, θP < θD .
これは θP > θD に矛盾する.
30

(iii) y0 > 0 のとき
(8) を y0 で割ると,
?c +
m∑
i=1
(yi/y0)ai, x? ≥ 0, ?x ∈ K
よって, ?y = ?y/y0 すると, c ?
∑m
i=1 ?yiai ∈ K?
となる.
即ち, ?y は双対問題 (5) の許容解であり, その目的関数は (6) より,
b?
?y = ?b?
y/y0 > θD.
これは θD の定義に反する.
以上より, 定理の主張が示された.
31

Interior Point, Interior Feasible Solution
De?nition 2.5
閉凸錐 K とする. x ∈ K が
任意の s ∈ K?
, s ?= 0 に対して ?s, x? > 0
となるとき, x を K の内点 (interior point) という.
De?nition 2.6
錐線計画 (4) において, K の内点でかつ許容解である点を内点許容解
(interior feasible solution) という. 双対問題 (5) では, K?
の内点で
かつ許容解である点を内点許容解という.
32

Su?cient Condition for C[c, a1, . . . , am; K] be Closed Set
Proposition 2.1
双対問題 (5) に内点許容解が存在する
? C[c, a1, . . . , am; K] は閉集合である.
証明を行うにあたり, 以下の 2 つの事実を証明なしに用いる.
Fact 2.1
集合 S ? Rn
が閉集合
? S 内の任意の収束点列 {xi
∈ S | i = 1, 2, . . . } に対して
その極限 x?
= limi→∞ xi
が S に含まれる
Fact 2.2
集合 S ? Rn
が有界閉集合, 無限点列 X ? S のとき,
X には集積点が存在する.
即ち, X の部分点列 X′
= {xk
| k ∈ K} (K ? {0, 1, . . . }) が存在し,
limk∈K xk
= ?x となる点 ?x が存在する.
33

Proof
(証明)
表記の簡略化のため, C := C[a1, . . . , am; K] と書く.
C が閉集合でないと仮定して, 矛盾を導く.
Fact 2.1 より,
ある収束点列 {yk
∈ Rm+1
| k = 0, 1, 2, . . . } ? C が存在し,
その極限は yk
→ ?y /∈ C (k → ∞).
この yk
に対応する K の元 xk
とする.
即ち, 任意の k に対して yk
0 = ?c, xk
?, yk
i = ?ai, xk
? (i = 1, . . . , m) で
ある.
もし {∥xk
∥ | k = 0, 1, 2, . . . } が有界ならば,
Fact 2.2 より {xk
} の集積点 ?x が存在し, K は閉集合なので, ?x ∈ K.
?y は ?x に対応する点なので ?y ∈ C. これは ?y の取り方に反する.
したがって, ∥xk
∥ → ∞ となる場合を考える.
34

Proof
(続き)
?xk
= xk
/∥xk
∥ とする. ∥?xk
∥ は有界より, 点列 {?xk
} は集積点 ?x をもつ.
?x へ収束する部分列を {?xkj
| j = 0, 1, 2, . . . } とする. このとき,
ykj
= ∥xkj
∥
?
?
?
?
?
?
?c, ?xkj
?
?a1, ?xkj
?
...
?am, ?xkj
?
?
?
?
?
?
?
とすれば, 左辺および右辺のベクトルの各成分は収束するが,
∥xkj
∥ は発散している.
したがって, 右辺のベクトルの各成分は 0 に収束しなければいけない.
即ち, ?c, ?x? = 0, ?ai, ?x? = 0 (i = 1, . . . , m) が成り立つ.
35

Proof
(続き)
ここで双対問題の内点許容解 ?s = c ?
∑m
i=1 ?yiai とすると,
??s, ?x? = ?c ?
m∑
i=1
?yiai, ?x? = ?c, ?x? ? ?
m∑
i=1
?yiai, ?x? = 0
である. ∥?x∥ = 1 より ?x は非ゼロで K に含まれている. これは ?s が双
対問題の内点許容解であることに矛盾する.
36

Summary of Regular duality
以上より, 以下のことがわかった.
Corollary 2.1
主問題 (4) に許容解が存在し, かつ双対問題 (5) に内点許容解が存在する
? 最適値は一致し, 主問題には最適解が存在する.
これは主問題と双対問題を入れ替えても成り立つ. 即ち,
Corollary 2.2
双対問題 (5) に許容解が存在し, かつ主問題 (4) に内点許容解が存在する
? 最適値は一致し, 双対問題には最適解が存在する.
以上より,
Corollary 2.3
主問題 (4) および双対問題 (5) に内点許容解が存在する
? 最適値は一致し, 両者に最適解が存在する.
37

Outline
Introduction
Cone Programming
Dual of SDP
Duality
Some known Algorithms for SDP
Appendix
38

Semide?nite Matrix Set
n × n 次実対称行列全体の集合を Sn とおく. 即ち,
Sn = {X ∈ Rn×n
| X?
= X}.
また, n 次半正定値対称行列全体の集合 Pn とする. 即ち,
Pn = {X ∈ Rn×n
| u?
Xu ≥ 0 (?u ∈ Rn
} ? Sn
また, X, Y ∈ Sn に対して, X と Y の内積 ? を
X ? Y =
n∑
i=1
n∑
j=1
Xi,jYi,j
と定義する.
39

今, Ai, C ∈ Sn と bi ∈ R (i = 1, . . . , m) が与えられたときに,
以下の最適化問題を考える.
Minimize C ? X (11)
subject to Ai ? X = bi (i = 1, . . . , m)
X ∈ Pn.
これを
半正定値計画問題 (semide?nite programming problem) という.
この問題は, 線形制約と錐制約のみをもち, 線形目的関数を最小化, もし
くは最大化する問題なので, 錐線形計画の一種である.
40

Dual of SDP
半正定値計画問題の双対問題を, 以下のように決める.
Maximize b?
y (12)
subject to S +
m∑
i=1
yiAi = C
S ∈ P?
n
実は, Pn は自己双対錐である. 即ち, P?
n = Pn.
41

Dual Cone of P?
n
Sn?1
= {x ∈ Rn
| ∥x∥ = 1} とする.
Pn が自己双対錐であることを示す前に, 以下の補題の結果を証明なし
に用いる.
Lemma 3.1
X ∈ Rn×n
とする. 以下の 2 つは同値である.
1. X ? 0
2. 以下の式を満たすある単位ベクトル ei, . . . , en ∈ Sn?1
と
非負の実数 λ1, . . . , λn が存在する.
X =
n∑
i=1
λieie?
i .
(証明)
( 2 ? 1 )eie?
i が半正定値であることから, その非負結合なので X ? 0.
42

Dual Cone of P?
n
(1 ? 2)
X ? 0 より, X = QDQ?
とする. Q は正規直交基底で, D は各固有値
λi ≥ 0 (i = 1, . . . , n) を対角成分にもつ対角行列である.
D(i)
を行列の (i, i) 成分が λi, それ以外を 0 とする対角行列とすると,
X = Q(
n∑
i=1
D(i)
)Q?
=
n∑
i=1
QD(i)
Q?
=
n∑
i=1
λiei
ここで ei は Q の i 番目の列ベクトルとなる. Q は正規直交基底なので,
∥ei∥ = 1 (i = 1, . . . , n)
43

Proof of P?
n = Pn
Proposition 3.1
P?
n = Pn
(証明)
まず, Pn ? P?
n, 即ち, X ∈ Pn ? X ∈ P?
n を示す.
X, Y ? 0 とする. Lemma 3.1 より, X は λi ≥ 0 と単位ベクトル ei で
X =
∑n
i=1 λieie?
i とかけて, 更に Tr(AB) = Tr(BA) より,
X ? Y =Tr(
n∑
i=1
λieie?
i Y ) =
n∑
i=1
λiTr(eie?
i Y )
=
n∑
i=1
λiTr(e?
i Y ei) =
n∑
i=1
λie?
i Y ei ≥ 0
44

Proof of P?
n = Pn
次に, Pn ? P?
n, 即ち, Y ∈ P?
n ? Y ? 0 を示す.
任意の x ∈ Rn
について, xx?
? 0 なので
(?v ∈ Rn
, v?
(xx?
)v = (x?
v)?
(x?
v) ≥ 0),
0 ≤ Y ? xx?
= Tr(Y xx?
) = Tr(x?
Y x) = x?
Y x
よって Y ? 0 である.
45

Duality Theorem
錐線形計画のときと同様に, 半正定値計画問題でも以下が成り立つ.
Corollary 3.1
主問題 (11) および双対問題 (12) に内点許容解が存在する
? 最適値は一致し, 両者に最適解が存在する.
46

Some known Algorithms for SDP
半正定値計画問題に対するアルゴリズムとして, 以下のようなものが
ある.
ここでは名前のみ紹介する.
? 楕円体法 (ellipsoid method)
ある条件を伴って多項式時間で任意精度の解が得られる
? 内点法 (interior-point method)
? Hanzan’s algorithm
47

Outline
Introduction
Cone Programming
Relaxation to Vector Programming
Reformulation to SDP
Bounding Approximation Ratio
Appendix
48

Review: Maximum Weighted Cut Problem
Weighted Max Cut Problem
Input: G = (V, E): 無向グラフ, c: E → R+: 重み関数
Task: (13) を最大にする S ? V を求める
∑
u∈S
∑
v∈V S
c(u, v) (13)
V = {1, . . . , n}, cij = c(i, j) とする.
zi を i ∈ S のとき 1, そうでないとき ?1 とすると,
最大カットの問題は (14) のように定式化できる.
Maximize
∑
{i,j}∈E
cij
1 ? zizj
2
(14)
subject to zi ∈ {?1, 1}, i = 1, . . . , n
49

Maxcut: Relaxation to Vector Programming
再掲
Maximize
∑
{i,j}∈E
cij
1 ? zizj
2
(5)
subject to zi ∈ {?1, 1}, i = 1, . . . , n
これを, 次の vector programming (6) に緩和する.
Maximize
∑
{i,j}∈E
cij
1 ? u?
i uj
2
(6)
subject to ui ∈ Sn?1
, i = 1, . . . , n
ここで, Sn?1
= {x ∈ Rn
| ∥x∥ = 1} である.
50

Maxcut: Reformulation to SDP
ui を列としてもつ以下のような行列 U ∈ Rn×n
を考える.
U = [u1u2 . . . un] (7)
X = U?
U とすると, 以下が成り立つ.
Lemma 4.1
X は半正定値行列である.
Proof.
v ∈ Rn
とする.
v?
Xv = v?
U?
Uv
= (Uv)?
Uv ≥ 0
51

Maxcut: Reformulation to SDP
xij = u?
i uj を要素にもつ行列 X を考えると,
以下の半正定値計画問題 (8) に書き換えられる.
Maximize
∑
{i,j}∈E
cij
1 ? xij
2
(8)
subject to xii = 1, i = 1, . . . , n
X ? 0
これを解き, X から U を得ることで vector programming (6) の解を
得る.
(X の Cholesky 分解によって U は求まる)
52

Mapping from Sn?1
to S0
= {?1, 1}
ランダムに p ∈ Sn?1
を選び,
以下のようにして u ∈ Sn?1
から {?1, 1} に写す.
u →
{
1 if p?
u ≥ 0
?1 otherwise.
(9)
p は, 単位球面 Sn?1
上のベクトルを,
閉半球面 H = {u ∈ Sn?1
| p?
u ≥ 0} とその補集合に分割する.
53

Probability that u, u′
∈ Sn?1
map to di?erent values
Lemma 4.2
u, u′
が (9) によって異なる値に写される確率は,
1
π
arccos u?
u′
.
α ∈ [0, π] を u, u′
の角度とする.
cos α = u?
u′
∈ [?1, 1]
よって,
α = arccos u?
u′
∈ [0, π]
α = 0, π のとき, 補題は成り立つ.
54

Probability that u, u′
∈ Sn?1
map to di?erent values
α ?= 0, π のとき,
u, u′
で張る 2 次元の線型部分空間 L ? Rn
を考える.
p を L に射影した r ∈ L について, p?
u = r?
u かつ p?
u′
= r?
u′
.
よって, r が下図の半開空間 W に入っているとき, かつそのときのみ,
p?
u と p?
u′
は異なる値をとる.
p は Sn?1
から一様ランダムに選ばれるので, r の向きも [0, 2π] から一
様ランダムとなる. よって, r ∈ W となる確率は, 2α/2π = α/π.
55

Getting the Bound
vector programming (6) の解を u?
1, u?
2, dots, u?
n とする.
これまでの結果と, 期待値の線型性より,
p ∈ Sn?1
をランダムに選ぶ事によって以下が得られる.
E
?
?
∑
{i,j}∈E
cij
1 ? (p?
u?
i )(p?
u?
j )
2
?
? =
∑
{i,j}∈E
ci,j
arccos u?
i
?
u?
j
π
また, 数値計算によって, 以下の結果を得ることができる.
f(x) =
2 arccos (x)
π(1 ? x)
≥ 0.8785672 if x ∈ [?1, 1].
よって, 全ての x ∈ [?1, 1] について, 以下の不等式が成り立つ.
arccos (x)
π
≥ 0.8785672
1 ? x
2
.
56

Getting the Bound
以上より,
∑
{i,j}∈E
ci,j
arccos u?
i
?
u?
j
π
≥0.8785672
∑
{i,j}∈E
ci,j
1 ? u?
i
?
u?
j
2
≥0.8785672(Opt(G) ? ?)
≥0.878 · Opt(G)
ここで, ? ≤ 5 · 10?4
である.
57

Summary of Goemans-Williamson algorithm for Maxcut
カット S ? V に対するカット重み f(S) :=
∑
i∈S
∑
j∈V S cij とする.
Goemans-Williamson algorithm for maxcut
Input: G = ({1, . . . , n}, E, c)
Output: カット S とそのカット重み f(S)
1: 以下の vector programming を解き, u?
1, u?
2, . . . , u?
n を求める.
Maximize
∑
{i,j}∈E
cij
1 ? u?
i uj
2
subject to ui ∈ Sn?1
, i = 1, . . . , n
2: p ∈ Sn?1
を一様ランダムに選び, 以下のカット S を得る.
S := {i ∈ {1, . . . , n} | p?
u?
i ≥ 0}
3: return S, f(S)
58

Cholesky fanctorization
TBD
59

Inapproximability result of Maxcut
近似率に関して知られている結果
? P ?= NP の仮定の下で, 任意の ? > 0 に対して多項式時間
16/17 + ?-近似アルゴリズムは存在しない.
? Unique Games Conjecture の仮定の下で, 任意の ? > 0 に対して多
項式時間 0.8785 + ?-近似アルゴリズムは存在しない.
60

狠狠撸

半正定値計画問題と最大カット Sedemifinite Programming and Approximation Algorithm for Maxcut Problem

More Related Content

半正定値計画問題と最大カット Sedemifinite Programming and Approximation Algorithm for Maxcut Problem