Instructions

Instructions

User Manual:

Open the PDF directly: View PDF .
Page Count: 3

Department of Computer Science

Institute of Theoretical Computer Science

Bernd G¨artner, David Steurer

Optimization for Data Science Special Assignment 1 FS19

Sunday, April 28, 2019 11:59 pm

hung.hoang@inf.ethz.ch

http://www.cadmo.ethz.ch/education/thesis/latex

http://ipe7.sourceforge.net/

–

–

always

S1S2

E

0.1 S1+0.1 S2+0.8 E

1.0

Approximate testing of intersections of balls

Rd

B1, B2,...,BnRdn d

BiciriBi={x:x−ciri}

BiRd

X, Y Rd

d(X, Y) = {x−y:xX, yY}X={x}

d(x, Y) = d({x}, Y)

i[n]hi(x) = d(x, Bi)h:Rd→R

h(x) = i[n]hi(x).

ε ε > 0 d

B1, B2,...,BnRdxRd

h(x)< ε n

i=1Bi=xRd

h(x)> 0

xh(x)< ε

ε

ε

Assignment 1. i[n]xRd

gi(x) = 0 x Bi

x−ci

x−ci.

gi(x)hi(x)gi(x)∂hi(x)hi

Assignment 2. x Rdj[n]gj(x)h(x)

gj(x)∂h(x)

Assignment 3. hih

Assignment 4. x0Rdx0−xR

RRxh γ R

T h(x)

t{0,...,T−1}(h(xt) − h(x))R

T.

Assignment 5. ε > 0 O(n/ε2)ε

Bi

ε

n

i[n]fi(x) = 1

2d(x, Bi)2f:Rd→R

f(x) =

n

X

i=1

fi(x).

fii[n]

f

f

Assignment 6.

fi(x) = 0 x Bi

1−ri

x−ci(x−ci).

f(x)

f

Assignment 7. u,vRdu=vα, β 1

u−vαu−βv.

Assignment 8. fi

fi(x) − fi(y)2x−y.

fi

f 2n f

Assignment 9. ε > 0 O(n3/2

ε)ε

Bi

R

x0