...

Semidefinite and Second Order Cone Programming Seminar Fall 2012 Lecture 11

by user

on
Category: Documents
2

views

Report

Comments

Transcript

Semidefinite and Second Order Cone Programming Seminar Fall 2012 Lecture 11
Semidefinite and Second Order Cone
Programming Seminar
Fall 2012
Lecture 11
Instructor: Farid Alizadeh
Scribe: Jingnan Fan
11/26/2012
1
Overview.
The first part of this lecture is about the calculation of four important quantities for a weighted undirected graph: size of largest clique, size of largest
independent set, minimum coloring number and minimum clique-covering number. We first formulate these problems by integer programming and then give
a SDP-relaxation.The second part is the general SDP-relaxation for 0/1 integer
programming problems.
2
Classic graph problems.
2.1
2.1.1
Four quantities: definition and ILP formulation.
Definitions.
For undirected graph G = (V, E) where V = {1, .., n} with assigned weights
w = {w1 , ..., wn } ≥ 0, we define four quantities on this graph:
• size of the largest clique ω(G, w): A subset of nodes is called a
clique or a complete subgraph if every two nodes in the subset are connected
by an edge. It is known that to find the maximum clique is a NP-hard
problem and is hard to approximate (by any constant).
• size of the largest independent set α(G, w): A subset of nodes is
called an independent set or an stable set if no two nodes in the subset
are connected. We will later see that finding a largest independent set is
equivalent to a maximum clique problem, so it is a NP-hard problem as
well.
1
scribe:Jingnan Fan
Lecture 11
Date: 11/26/2012
• minimum coloring number χ(G, w): In the unweighted case, it is the
minimum number of colors required to properly color G, i.e, no two connected nodes have a same color. As every nodes in a clique must have
different colors, we have ω(G) ≤ χ(G). In some graphs like a clique or
bipartite graph, we can have ω(G) = χ(G), but it is not always true. In
a pentagon, we have ω = 2 and χ = 3. Remark that a coloring for G is
actually a covering for G by independent sets, as a subset colored by a
same color must be independent. When the graph is weighted, this last
definition remains valid, while ”covering” means that each node i ∈ V
is covered at least wi times.(Independent sets can be used for covering
multiple times.) We can also consider the coloring problem for a weighted
graph as coloring on a graph obtained by ”splitting” each node i ∈ V to
dwi e nodes. So we also have ω(G, w) ≤ χ(G, w).
• minimum clique covering number ρ(G, w): is the minimum number of
node-disjoint cliques that cover every node.
2.1.2
Properties.
Recall that the complement of G, denoted by Ḡ, if the graph composed by the
same set of nodes V and the complement edge set Ē = {(i, j)|i 6= j, (i, j) ∈
/ E}.
Fact 1 Every clique in G is an independent set in Ḡ, every independent set in
G is a clique in Ḡ. Thus the following equalities hold:
1. ω(G, w) = α(Ḡ, w)
2. α(G, w) = ω(Ḡ, w)
3. χ(G, w) = ρ(Ḡ, w)
4. ρ(G, w) = χ(Ḡ, w)
5. α(G, w) ≤ ρ(G, w)
2.1.3
ILP formulation.
We formulate these problems as 0/1 integer linear programming problem:
• ILP for ω(G, w)
Let x be the characteristic vector of clique,then ω(G, w) is the optimal
value of
maximize wT x
x
subject to xi + xj ≤ 1, ∀(i, j) ∈
/E
xi ∈ {0, 1}, ∀i ∈ V.
2
(1)
scribe:Jingnan Fan
Lecture 11
Date: 11/26/2012
The polytope
CLIQUE(G) := conv{1K |K is a clique}
where 1K is the characteristic vector of K1 , is the convex hull of all the
feasible 0/1 solutions, then ω(G, w) is also the optimal value of
wT x
maximize
x
(2)
subject to x ∈ CLIQUE(G).
The most obvious LP-relaxation for (1) is
maximize
x
wT x
subject to xi + xj ≤ 1, ∀(i, j) ∈
/E
(3)
0 ≤ xi ≤ 1, ∀i ∈ V.
For some graph we can have feasible solutions in LP-relaxation (3) form
exactly CLIQUE(G), we have
Theorem 2 The polyhedra of feasible solutions of LP-relaxation (noted
by LP-CLIQUE(G)) is exactly CLIQUE(G) if and only if G is a perfect
graph, i.e, ω(G, w) = χ(G, w) for all w.
Remark 3 All bipartite graphs are perfect.
• ILP for α(G, w)
Let x be the characteristic vector of independent set,then α(G, w) is the
optimal value of
maximize
x
wT x
subject to xi + xj ≤ 1, ∀(i, j) ∈ E
(4)
xi ∈ {0, 1}, ∀i ∈ V
The polytope
INDP(G) := conv{1S |S is an independent set}
is the convex hull of all the feasible 0/1 solutions, then α(G, w) is also the
optimal value of
maximize wT x
x
(5)
subject to x ∈ INDP(G)
1 Recall that a subset K ⊆ {1, 2, . . . , n} may be represented by a vector of zeros and ones,
where the ith entry is one iff i ∈ K. This vector is called the characteristic vector of K.
3
scribe:Jingnan Fan
Lecture 11
Date: 11/26/2012
The standard LP-relaxation for (20) is
maximize
x
wT x
subject to xi + xj ≤ 1, ∀(i, j) ∈ E
(6)
0 ≤ xi ≤ 1, ∀i ∈ V.
We note the polyhedra of feasible solutions of LP-relaxation by LP-INDP(G).
• ILP for χ(G, w)
Let y = {yS |S is maximal independent set}, yS is the number of the maximal independent set S used for covering, then χ(G, w) is the optimal value
of
X
yS
minimize
y
S: S is a maximal independent set
X
subject to
yS ≥ wi , ∀i ∈ V
(7)
S3i: S is a maximal independent set
yS ∈ N, ∀S is a maximal independent set.
The standard LP-relaxation is
minimize
y
X
yS
S: S is a maximal independent set
X
subject to
yS ≥ wi , ∀i ∈ V
(8)
S3i: S is a maximal independent set
yS ≥ 0, ∀S is a maximal independent set.
• ILP for ρ(G, w)
Let y = {yK |K is maximal clique}, yK is the number of the maximal clique
K used for covering, then ρ(G, w) is the optimal value of
X
minimize
yK
y
K: K is a maximal clique
X
subject to
yK ≥ wi , ∀i ∈ V
(9)
K3i: K is a clique
yK ∈ N, ∀K is a maximal clique.
The standard LP-relaxation is
X
minimize
y
subject to
yK
K: K is a maximal clique
X
yK ≥ wi , ∀i ∈ V
K3i: K is a maximal independent set
yK ≥ 0, ∀K is a maximal independent set.
4
(10)
scribe:Jingnan Fan
Lecture 11
2.1.4
Date: 11/26/2012
Q-CLIQUE and Q-INDP.
The standard LP-relaxation polyhedron LP-CLIQUE(G) and LP-INDP(G) are
often large compared to CLIQUE(G) and INDP(G).So we look for a better LPrelaxation for maximum clique/independent set problems.
Define
Q-CLIQUE(G) := {x|x ≥ 0, 1TS x ≤ 1, ∀ maximal independent set S}
and
Q-INDP(G) := {x|x ≥ 0, 1TK x ≤ 1, ∀ maximal clique K}.
We have
CLIQUE(G) ⊆ Q-CLIQUE(G) ⊆ LP-CLIQUE(G),
and
INDP(G) ⊆ Q-INDP(G) ⊆ LP-INDP(G),
so if we note
ω̄(G, w) :=
wT x
max
x
(11)
subject to x ∈ Q-CLIQUE(G),
and
ᾱ(G, w) :=
wT x
max
x
(12)
subject to x ∈ Q-INDP(G),
we have
ω̄(G, w) ≥ ω(G, w),
and
ᾱ(G, w) ≥ α(G, w).
On the other hand, we notice that the dual problems of (11) and (12) are in
fact the LP-relaxation of the problems (7) and (9). Let’s note respectively by
χ̄(G, w) ρ̄(G, w) the optimal values of the dual problems of (11) and (12), then
we have
ω(G, w) ≤ ω̄(G, w) = χ̄(G, w) ≤ χ(G, w),
and
α(G, w) ≤ ᾱ(G, w) = ρ̄(G, w) ≤ ρ(G, w).
5
scribe:Jingnan Fan
Lecture 11
2.2
Date: 11/26/2012
SDP relaxation.
Let A(G) be the adjacent matrix of G defined by We introduce the number of
Lovàsz
θ(G) := min
λ[1] (X + wwT )
subject to: X ∈ Sn
Xij = 0, ∀(i, j) ∈ E
Xii = 0, ∀i ∈ V
=
min
z
(13)
T
subject to: zIn − X − ww 0
X ∈ Sn
Xij = 0, ∀(i, j) ∈ E
Xii = 0, ∀i ∈ V.
By duality,
θ(G)
:=
(wwT ) • Y
max
subject to: Y ∈ Sn
Y0
(14)
trace(Y) = 1
Yij = 0, ∀(i, j) ∈
/ E.
The key result of the Lovàsz number is that:
Theorem 4 (Lovasz Sandwich Theorem)
ω(G, w) ≤ θ(G, w) ≤ χ(G, w).
Proof:
• Let’s first prove the theorem for the unweighted
case, here wwT = Jn . If
P
1
K is a maximum clique, let YK = |K| i∈K,j∈K Eij , then we will have YK
is a feasible solution of (14) and Jn • YK = |K|. So ω(G) ≤ θ(G).
• There exists a partition of V into independents set V = {S1 , ..., Sχ(G) }.
For all node i, note S(i) the only subset in the partition containing i. For
P
Pχ(G)
any S ⊆ V, note eS = i∈S ei . Then let X = χ(G)(In − i=1 eSi eTSi ).
We show that (χ(G), X) is a feasible solution to (13). For all node i,
Xii = χ(G)(1 − (eS(i) eTS(i) )ii ) = 0; for all (i, j) ∈
/ E such that i 6= j,
6
scribe:Jingnan Fan
Lecture 11
Date: 11/26/2012
Xij = 0. Take any u ∈ Rn , we have
uT (χ(G)In − X − Jn )u
X
χ(G)
=
T
χ(G)u (
eSi eTSi )u − uT Jn u
i=1
X
χ(G)
=
χ(G)
(eTSi u)2 − (eT u)2
i=1
≥ 0.
• For weighted case, the idea is to convert the whole problem to an unweighted problem on ”replicated graph”.
3
General SDP-relaxation for 0/1 programming.
3.1
The SDP relaxation.
Consider the integer programming
max{w̄T x̄|Āx̄ ≥ b and x̄i ∈ {0, 1}, ∀i}.
(15)
One method to solve this ILP problem is solve the LP-relaxation and do the
cutting plane, but the LP-relaxation often enlarge too much the feasible polyhedra. Lovàsz and Schrijver proposed the following SDP-relaxation which gives
a better approximation. First we homogenize the problem by adding a new
variable x0 and imposing x0 = 1, thus the homogenize integer programming
problem is
max wT x
s.t.
Ax ≥ 0
(16)
x0 = 1
xi ∈ {0, 1}, ∀i,
where
x=
x0
x̄
, w=
0
w̄
,
and
A = [−b | Ā].
The LP-relaxation if the homogenize problem is
max
wT x
s.t.
Ax ≥ 0
x0 = 1
0 ≤ xi ≤ x0 , ∀i.
7
(17)
scribe:Jingnan Fan
Lecture 11
Date: 11/26/2012
Note I(P) polyhedron of feasible solutions in the integer problem (16) and note
P the polyhedron of feasible solutions in the LP-relaxation (17) without the
constraint x0 = 1,
Ax ≥ 0
P = x .
0 ≤ xi ≤ x0 , ∀i
For (J1 , J2 ) a partition of index set of rows of A, let
T
a x ≥ 0, ∀j ∈ J1
P1 =
x j
0 ≤ xi ≤ x0 , ∀i
=
{x|A1 x ≥ 0}
=
T
aj x ≥ 0, ∀j ∈ J2
x
0 ≤ xi ≤ x0 , ∀i
=
{x|A2 x ≥ 0},
and
P2
then
P = P1
\
P2 .
Define
M+ (P1 , P2 ) := {X ∈ Sn+1 |X 0, Xe0 = diag(X), (A1 ⊗ A2 )vect(X) ≥ 0},
and
N+ (P1 , P2 ) := {diag(X)|X ∈ M+ (P1 , P2 )}.
Obviously the problem
max
wT x
s.t.
x ∈ N+ (P1 , P2 )
(18)
is a semi definite programming problem. And the main result of Lovàsz and
Schrijver is that
Theorem 5
I(P) ⊆ N+ (P1 , P2 ) ⊆ P.
Proof:
1
be a integer solution. Then X = xxT ∈ M+ (P1 , P2 ).
x̄
Obviously X 0 and Xe0 = diag(X). We have also
• Let x =
(A1 ⊗ A2 )vect(X)
=
vect(A2 XAT1 )
=
vect(A2 xxT A1 )
≥ 0.
8
scribe:Jingnan Fan
Lecture 11
Date: 11/26/2012
• As e0 is a row of A2 , we have A1 diag(X) = A1 Xe0 ≥ 0. Thus, N+ (P1 , P2 ) ⊆
P1 . Similarly N+ (P1 , P2 ) ⊆ P2 .
Remark 6 If a solution x = Xe0 found by the SDP-relaxation problem (18) satisfies x0 = 1 and rank(X) = 1, then x is 0/1 integral. Indeed, when rank(X) = 1
and X = xxT , Xe0 = diag(X) implies that xi = x2i for all i, so xi ∈ {0, 1}.
3.2
Application to the maximum independent set problem.
Consider the maximum independent set problem:
w̄T x̄
maximize
x
subject to x̄i + x̄j ≤ 1, ∀(i, j) ∈ E
(19)
x̄i ∈ {0, 1}, ∀i
And its LP-relaxation is
maximize
x
wT x
subject to x0 − xi − xj ≥ 0, ∀(i, j) ∈ E
(20)
0 ≤ xi ≤ x0 , ∀i
x0 = 1.
Let
x0 − xi − xj ≥ 0, ∀(i, j) ∈ E
P1 = x 0 ≤ xi ≤ x0 , ∀i
and
P2 = x 0 ≤ xi ≤ x0 , ∀i .
Then the SDP-relaxation of the maximum independent set problem is
max
wT x
s.t.
x ∈ N+ (P1 , P2 ).
(21)
and we have
INDP(G) ≤ N+ (P1 , P2 ) ≤ LP-INDP(G).
We also observe that points in N+ (P1 , P2 ) satisfy following properties of INDP(G):
• For any independent set K,
1K x ≤ 1.
• For every odd cycle C with 2k + 1 nodes,
1C x ≤ k.
Although the SDP-relaxation gives a better approximation, it might not work
very well in practice. One reason is that we square the number of variables, and
another reason is that we do not have so far an analogy of branch and bound
method in SDP.
9
Fly UP