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

Leave a Reply