ECE 490, Week of Apr 1

$$\def\Real{\mathbb{R}}$$

Conic duality: Guler, Chapters 11, 13 and Barvinok’s “A Course in Convexity“, Chapter 4.

Class notes (pretty incomplete, to be used just as a study guide), here.

Homework, due Apr. 16.

1. Warehouses numbered $$0,1,\ldots,N$$ are located along the road. Initially, the warehouse $$k$$ holds $$N-k$$ units of goods. Management wants to redistribute the goods so that warehouse $$k$$ holds $$k$$ units. Moving one unit from $$k$$ to $$l$$ costs $$|k-l|$$. What is the optimal movement plan?
Write this as a LP; find its dual and solve both.
2. Find Lovasz’ theta for the cyclic graph of order $$5$$ (both computational and theoretical solutions admissible).
3. Find Legendre dual for
$$f(x_1,x_2)=\min_{(s_1,s_2)}((x_1-s_1)^2+(x_2-s_2)^2)$$, where the minimum is taken over all combinations of $$s_1,s_2=\pm 1$$.
4. Find Legendre dual for
$$f(x_1,x_2)=\max_{(s_1,s_2)}((x_1-s_1)^2+(x_2-s_2)^2)$$, where the minimum is taken over all combinations of $$s_1,s_2=\pm 1$$.
5. Gradient descent with constant step size (choose one judiciously) is run for $$f=x_1x_2$$. Estimate the size of the vector after $$100$$\th iteration for initial position $$(1,1)$$; $$(.9999,1)$$.

Solutions here.

12 Responses to ECE 490, Week of Apr 1

1. Gwanhee Lee April 7, 2019 at 6:15 pm #

For Problem 1, how many units does Warehouse N have initially? If Warehouse (N-k-1) holds k units before we start, I think k becomes (-1) when the index of warehouse becomes N, which is less than 0.

• yuliy April 7, 2019 at 7:57 pm #

Of course, you’re right, – there last warehouse was $$N-1$$ originally, and I forgot to update the data when I switched to $$N+1$$ warehouses. Amended.

2. Gwanhee Lee April 11, 2019 at 1:45 pm #

1. For Problem 3 and 4, does the function means f(x_1, x_2)?
2. For Problem 5, can we use arbitrary step size(constant) that we want to use to estimate the vector?

• yuliy April 14, 2019 at 2:26 pm #

Thank you! corrected.

3. Zhijian Yang April 11, 2019 at 2:57 pm #

In Problem 5, what does “size of vector” mean? What is the vector? Thanks.

• yuliy April 14, 2019 at 2:27 pm #

Vector $$(x_1,x_2)$$.

4. Jacob Scott White Heglund April 12, 2019 at 11:12 am #

In Problem 2, is the cyclic graph defined as unidirectional (1->2, 2->3, 3->4, 4->5, 5->1) or undirected?

• yuliy April 14, 2019 at 2:28 pm #

In this theory, graphs are unoriented (simple, without self-loops).

5. Gwanhee Lee April 13, 2019 at 6:24 pm #

For Problem 5, do we have to estimate the size of vector for two cases (When (x_1, x_2)=(1,1), (.9999,1)) separately, or just one case(When (x_1, x_2)=(.9999, 1))?

• yuliy April 14, 2019 at 2:29 pm #

These are two separate questions: one, you start with $$(1,1)$$, another, with $$(.9999,1)$$.

6. Xuan Wang April 16, 2019 at 7:33 pm #

Gradescope doesn’t allow me to select the pages for each question?

• yuliy April 16, 2019 at 9:38 pm #

Not sure what does this mean… If in trouble, email your work to the TA (but only as a last resort).