Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.mccme.ru/ium/postscript/f12/nesterov-Lect4_Combi.pdf Äàòà èçìåíåíèÿ: Fri Sep 7 23:12:32 2012 Äàòà èíäåêñèðîâàíèÿ: Mon Feb 4 19:34:15 2013 Êîäèðîâêà:

Lecture 4: Nonlinear analysis of combinatorial problems
Yurii Nesterov, CORE/INMA (UCL)

September 12, 2012


Outline

1 Bo olean quadratic problem 2 Simple b ounds 3 SDP-relaxation and its quality 4 General constraints 5 Generating functions of integer sets 6 Knapsack volume 7 Fast computations 8 Further extensions


Boolean quadratic problem
Let Q = Q
T

be an (n â n)-matrix.

Maximization: find f (Q ) max{ Qx , x : xi = ±1, i = 1 . . . n}.
x

Minimization: find f (Q ) min{ Qx , x : xi = ±1, i = 1 . . . n}.
x

Clearly f (-Q ) = -f (Q ). Trivial Properties Both problems are NP-hard. They can have up to 2n local extremums. Very often we are happy with approximate solutions


Simple bounds: Eigenvalues
Upp er b ound. For any x R n with xi = ±1, we have x Therefore, f (Q ) max Qx , x = n · max (Q ).
x
2

2

= n.

=n

Lower b ounds. 1. If Q f (Q ) = max Qx , x
|xi |1

0, then max Qx , x
x
2

=1

= max (Q ).

2. Consider random x with Prob (xi = 1) = Prob (xi = -1) = 1 . 2 Then n f (Q ) Ex ( Qx , x ) = Qi ,j Ex (xi xj )
i ,j =1 n

=
i =1

Q

i ,i

= Trace (Q ).
max

Example: Q = ee T , Trace (Q ) = relative quality is n.

(Q ) = n. In both cases,


Polyhedral bound
For Boolean x R n , we have
n

Qx , x =
i ,j =1

Qi ,j xi xj
i ,j

|Qi ,j | = Q

def

1

.

How go o d is it? Random hyp erplane technique. (Krivine 70's, Goemans, Williamson 95) Let us fix V Mn . Consider the random vector = sgn [V T u ] with random u R n , uniformly distributed on the unit sphere. ([ · ] denotes component-wise operations.) Lemma 1: E (i j ) = Lemma 2: For X
2

arcsin

vi ,vj vi · vj

. X. X.

0, we have arcsin[X ]
3 40

Pro of: arcsin[X ] = X + 1 [X ]3 + 6

[X ]5 + . . .


Quality of polyhedral bound (Q
Let Q = V T V (this means that Q f (Q ) E ( Q , ) = Denote D = diag (Q )- Denote S1 = Q , In Thus, Q , DQD = S1 +
S
n i =1

0)
= vi , vj ). Then arcsin
Q (i , j ) Q (i ,i ) Q M def
(j ,j )

i ,j

2

n

Q
i ,j =1

(i ,j )

=

2

.

1/2

. Then Q , DQD
i =j

.
1

M

, S2 =

|Qi ,j |. Then S1 + S2 = Q
( i =j Qi ,j )2 Qi ,i Qj

.

M

= S1 + S1 +

,j

S1 +
i =j

S

2 2 ,j

Qi ,i Qj



2 2 i ,i

2

Q

-S

S nS1 -S1

2 2

=Q
1 M

1

- S2 +

2 S2 (n-1)( Q

1

-S2 )

.

1

The minimum is attained for S2 = Q Q 1 f (Q ) Q , DQD It is better than the eigenvalue bound!


· (1 -

1 n 2 1+ n

). Thus, Q
1

.


SDP-bounds: Primal Relaxation (Lov´ asz)

For X , Y Mn , we have XY , Z M = X , ZY Then Q 1k , 1 n
def k n

T

M

= Y,XTZ

M

.

Denote 1k : (1k )j = ±1, j = 1 . . . n, k = 1 . . . 2n . n n = Q , 1k (1k )T nn
M

. Therefore
M

f (Q ) = max Q , X
X P
n

,

where Pn = Conv {1k (1k )T , k = 1 . . . 2n }. Note that: nn The complete description of Pn is not known. For X Pn we have: X f (Q ) max{ Q , X 0, and d (X ) = 1n . Thus,
M

:X

0, d (X ) = 1n }.


Dual Relaxation (Shor)
Problem: f (Q ) = max{ Qx , x : xi2 = 1, i = 1 . . . n}.
x n i =1

Its Lagrangian is L(x , ) = Qx , x +
x

i (1 - (xi )2 ). Therefore
x

f (Q ) = max min L(x , ) min max L(x , ) = min{ 1n , : Q


D ( )} = s (Q ). }.

def

Note: Both relaxations give exactly the same upper bound: s (Q ) = min max{ 1n , + X , Q - D ( )
X0 M

= max min{ 1n - D (X ), + X , Q
X0

M

}.

= max{ X , Q
X0

M

: d (X ) = 1n }.

Any hope? (Looks as an attempt to approximate Q by D ( ).)


Trigonometric form of Quadratic Boolean Problem
2 We have seen that f (Q ) arcsin[V T V ] with d (V T V ) = 1n . Let us show that 2 f (Q ) = max Q , arcsin[V T V ] M .

Pro of: Choose arbitrary a, a = 1. Let x be the global solution. Define vi = a if xi = 1, and vi = -a otherwise. Then V T V = x (x )T and f (Q ) = max
X0 2 2

vi =1

arcsin[V T V ] = x (x )T . 0 : d (X ) = 1n }, we get
M

Since {X = V T V : d (X ) = 1n } {X Q , arcsin[X ]

: d (X ) = 1

n

.

2 Corollary: s (Q ) f (Q ) s (Q ).

Relative accuracy does not depend on dimension!


General constraints on squared variables
Consider two problems: = max{ Qx , x : [x ]2 F }, = min{ Qx , x : [x ]2 F }, where F is a bounded closed convex set. Trigonometric form: = max{ = min{
2

D (d )QD (d ), arcsin[X ] : X 0, d (X ) = 1n , d 0, [d ]2 F },

D (d )QD (d ), arcsin[X ] : X 0, d (X ) = 1n , d 0, [d ]2 F }. Relaxations: Define the support function (u ) = max{ u , v : v F }, and Q }, = max{- (u ) : Q + D (u ) 0}, = (d (Q )), = - (-d (Q )). Simple relations: .


2

= min{ (u ) : D (u )


Main result

Denote () = + (1 - ) , and = Theorem. 1. Let

- -

, =

- -

.

2 2 = max{ ( ), 1 - }, and = min{1 - ( ), }, 1 where () = arcsin() + 1 - 2 ( 1 + 2 2 ).

Then 2. 0

( ) ( ) .
- ( ) -



24 49

. . Then
| - ()| ¯ -

3. Define = ¯

(2- )- 1+ -2



12 37

.


Main limitation: Absence of linear constraints

Example. Let > 0. Consider the problem = max{ Qx , x : [x ]2 = 1n , c , x = },
x

= min{ Qx , x : [x ]2 = 1n , c , x = }.
x

Natural relaxation: = max{ Q , X : d (X ) = 1n , X
X

0, Xc , c = 2 }, 0, Xc , c = 2 }.

= min{ Q , X : d (X ) = 1n , X
X

Denote by v any vector with [v ]2 = 1n . Assumptions: 1. There exists a unique v such that c , v = . 2. There exist v- and v+ such that 0 < c , v- < < c , v+ . Note: in this case = (unique feasible solution).


Consider the polytope Pn = Conv {Vi = vi viT , i = 1, . . . , 2n }. Lemma. Any Vi is an extreme point of Pn . Any pair Vi , Vj is connected by an edge. Note: ~ 1. In view of our assumption V Pn :
T T ~ V = v- v- + (1 - )v+ v+ , (0, 1),

~ V c , c = 2.

2. Pn {X : d (X ) = 1n , X

0}.

Conclusion: We can choose Q : > . Since , the relative accuracy of is +. Reason of the troubles: We intersect edges of Pn . This cannot happen if = 0.


Further developments

Boolean quadratic optimization with m homogeneous linear equality constraints (accuracy O (ln m)). Quadratic maximization with quadratic inequality constraints (accuracy O (ln m)).

Main bottleneck: absence of cheap relaxations.


Generating functions of integer sets

1. Primal generating functions. For set S Z n , define where x =
n i =1

f (S , x ) =
S

x ,

xii .

f (S , 1n ) = N (S ), the integer volume of S . Can be used for counting problems. Sometimes have short representation. Example: S = {x Z : x 0}. Then f (S , x ) =
1 1-x

.


2. Dual generating functions
2.1. Characteristic function of the set X Z n is defined as X (c ) =
x X

e

c ,x

, if X = ,

and 0 otherwise.

For counting problem, we have N (X ) = X (0). We can be approximate the optimal value of an optimization problem over X : 1 µ ln X µ c max{ c , x : x X (y )}
x

µ ln X

1 µ

c - µ ln N (X ), µ > 0.
m

2.2. Generating function of family X = {X (y ), y } Z is defined as g
X ,c

(v ) =
y

X

(y )

(c ) · v y .
X ,0

Dual counting function: fX (v ) = g

(v ).

Hop e: short representation. NB: Constructed by set parameters.


Example
n Let a Z+ . Consider the Boolean knapsack polytope 1 Ba n (b ) = {x {0, 1}n : a, x = b }. 1 Goal: Compute N (Ba n (b )) for a given b Z+ . (It is NP-hard.) n

Consider the function
def

f (z ) =
i =1

1+z

a

(i )

,

where

z C = {z C : |z | = 1}.
a
1

We will see later, that where a
def 1 n i =1

f (z )
b =0

1 N (Ba n (b )) z b , z C ,

=

|a |.

(i )

Thus, we need to compute the coefficient of z b in polynomial f (z ). For that, we compute all previous coefficients. Direct computation: O (n a 1 ) O ( a 1 · ln a 1 · ln n).


Knapsack volumes
u Ba (b ) = {x Z n : 0 x u , a, x = b }. Z
+

Notation:

u u Consider the family Ba = {Ba (b )}b
u fBa (z ) = =

. Its counting function is z C.

def

u N (Ba (b )) · z b ,

b =0 u
(i )

Since u is finite, this is a polynomial of degree a, u .
n

Lemma.

u fBa (z ) =

z
i =1 k =0

ka

(i )

.

Pro of. For n = 1 it is evident. Denote a+ = (a, a
(n+1) )T

Z
u

n+1 +

, and u+ = (u , u

(n+1) )T

n Z++1 .

For any b Z+ we have
(n+1)

u+ N (Ba+ (b )) =

a N (Bu (b - k · a

(n+1)

)).

k =0


Hence, in view of the inductive assumption, we have

u fBa + (z ) = +

u+ N (Ba+ (b )) · z

b

b =0 u
(n+1)

=
b =0 k =0

a N (Bu (b - ka

(n+1)

))

·z

b

=
b =0

a N (Bu (b ))

u

(n+1)

z
k =0

b +ka

(n+1)

u
u = fBa (z ) ·

(n+1)

z
k =0

ka

(n+1)

.


Complexity

Lemma. Let polynomial f (z ) be represented as a product of
n

several polynomials:

f (z ) =
i =1

pi (z ),

z C.

Then its coefficients can be computed by FFT in O (D (f ) ln D (f ) ln n )
n

arithmetic operations, where D (f ) =
i =1

D (pi ).

u Corollary. All a, u coefficients of the polynomial fBa (z ) can be computed by FFT in

O ( a, u ln a, u ln n) a.o.


Unbounded knapsack



Consider

fBa (z ) =

N (Ba (b )) · z

b



b =0

1 1-z a i =1

n

(i )

,

where z C \ {1}. Note:
n

1. The coefficients of the polynomial g (z ) = computed by FFT in O ( a
1

(1 - z
i =1

a

(i )

) can be

ln a

1

ln n) a.o.

2. After that, the first b + 1 coefficients of the generating function fBa (z ) can be computed in O (b min{ln2 b , ln2 n}) a. o.


Generating functions of knapsack polytopes
For characteristic function X (c ) =
y X

e

c ,y

of set X , define its

potential function: Note that Hence,
def

X (c ) = ln X (c ).
y X

X (c ) = max c , y X (c ) X (c ) + ln N (X ). X (c ) µX (c /µ) X (c ) + µ ln N (X ), µ > 0.
b Z
+

u u For a family of bounded knapsack polytopes Ba = {Ba (b )} the generating function looks as follows:

,

gB

u a

,c

(z ) =
b =0

B

u a

(b )

(c ) · z b
u Ba



exp(
b =0 n u

u Ba (b )

(c )) · z b , z )
ka
(i )

z C.

(i )

Short representation: g Unb ounded case: gB
a

,c

(z ) =
i =1 n k =0

e (1 - e
c
(i )

kc

(i )

.

-1

,c

(z ) =

z

a

(i )

.

i =1


Solving integer knapsack
f = max { c , x : a, x = b } = n
x Z
+

Find

B

a

(b )

(c ).

Since f is an integer value, we need accuracy less than one.
Note that N (Ba (b )) n

1+
i =1

b a (i

)

(1 + b )n .

Thus, if we take µ < -1 + µ
B

1 n
a

ln(1 + b ), then
(b )

(c /µ) < f µ
(b ) n

B

a

(b )

(c /µ). (c /µ)}, we need ·z
a
(i )

For finding coefficient B

a

(c /µ) = exp{
i =1

Ba (b )

Compute coefficients of f (z ) =

(1 - e

c

(i )

/µ

).
1 f (z )

Compute first b + 1 coefficients of the function g (z ) = This can be done in O ( a of exact real arithmetics.
1

.

· ln a

1

· ln n + b · ln2 n) operations


Further extensions

Problem: count the number of integer points in the set X = {x Z n : 0 x · 1n , Ax = b R m }, where |Ai ,j | . Dual counting: O (mn · (1 + · n)m ) a.o. Full enumeration: O (mn · (1 + )n ) a.o. For fixed m, the first bound is polynomial in n.