\(\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.

- 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. - Find Lovasz’ theta for the cyclic graph of order \(5\) (both computational and theoretical solutions admissible).
- 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\). - 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\). - 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.

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.

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.

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?

Thank you! corrected.

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

Vector \((x_1,x_2)\).

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

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

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))?

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

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

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