ECE 490, Week of Feb 4

Finishing Guler, Chapter 3 and starting Chapter 4.

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

Using linear constraints compatibility in packing problems, see e.g. here.

Exercises:

  • Can a triangle on plane be a linear image of a cube (in a high-dimensional space)?
  • Is the set of positive polynomials (i.e. such that \(p(x)>0\) for any \(x\)) convex?
  • Represent \(n\times n\) matrix with all coefficient \(1/n\) as a convex combination of permutation matrices.
  • Find the Minkowski sum of three segments, \([(0,0),(0,1)], [(0,0),(1,0)],[(0,0),(-1,1)]\).

Homework (due by midnight of Tuesday, Feb. 19).

  1. Consider the function
    \[
    f(x,y)=(y^4+2y^2+2)x^2-2(y^2+1)x+1.
    \]
    Find \(\inf_{x,y}f(x,y)=:c\). Find a sequence of points \(p_n=(x_n,y_n)\) such that the function converges to its \(\inf\) and its gradient converges to zero: \(f(p_n)\to c; \nabla f(p_n)\to 0\).
  2. Describe Minkowski sum of the unit circle and positive orthant \(\{(x\geq 0, y\geq 0\}\).
  3. Consider the function
    \[
    g(x,y)=\ln(e^x+e^y+e^{-x-y}).
    \]
    Find the range of the gradient of \(g\), that is all the vectors
    \[
    (p,q)=\left(\frac{\partial g}{\partial x},\frac{\partial g}{\partial y}\right).
    \]
  4. On the plane, a collection of vertical intervals \(I_k:=[(x_k,y_k^-),(x_k,y_k^+)], k=1,\ldots, K\) has the property that for any three of these intervals, there exists a straight line intersecting all three of them. Is it true that there is a straight line intersecting all \(K\) intervals?
  5. Find the largest radius \(r\) such that three non-overlapping open disks of radius \(r\) can fit into the unit square.

Solutions to HW2.

17 Responses to ECE 490, Week of Feb 4

  1. Boya Hou February 13, 2019 at 10:58 am #

    What particular results or theorem are we expected to use regarding problem 3?

    • Khaled Alshehri February 13, 2019 at 1:44 pm #

      You can use basic definitions

  2. Xuan Wang February 14, 2019 at 4:27 pm #

    What does it mean by “describe the Minkowski sum … “? Do we describe the region by words or draw a picture?

    • yuliy February 14, 2019 at 5:31 pm #

      Picture or formula (with explanation how you arrive at it), – either will do.

  3. Ziyang Liu February 14, 2019 at 4:57 pm #

    What is the exact deadline for this assignment? The gradescope indicates that the midnight of Monday, Feb.18 is the deadline, but according to this page, the midnight of Feb.19 is the deadline.

    • yuliy February 14, 2019 at 5:32 pm #

      Midnight of Tuesday, Feb 19. Sorry about the confusion.

  4. Hakan Tekgul February 15, 2019 at 2:01 pm #

    Can we get some hint or an example of vertical interval for problem 4? I am not sure where to start. Thanks!

    • yuliy February 15, 2019 at 5:05 pm #

      What is a straight line on the plane? Unless it is vertical (rarely answers the question!), it is given by \(\{y=ax+b\}\). What are the conditions on \(a,b\) to intersect a segment?

  5. Yiqing Xie February 15, 2019 at 4:39 pm #

    Can we get some hint for Problem 5? Plus, can we give an approximate solution for this problem?

    • yuliy February 15, 2019 at 5:02 pm #

      Use necessary conditions outlined int he lecture to enumerate possible optimal configurations of the disks.

      Approximate to 15 digits or an exact formula is fine.

  6. Jacob Scott White Heglund February 15, 2019 at 7:42 pm #

    In this image (https://imgur.com/lljoHQ4), there doesn’t appear to be any way for the right-most interval to be intersected while the other intervals are also intersected. In order for the right-most interval to be intersected, it would have to be moved up so that it lies in the shaded region.

    How can three arbitrary vertical line segments in R^2 be intersected with a straight line? It seems like there must be some strict conditions on the vertical intervals for this to be true.

    • yuliy February 15, 2019 at 10:21 pm #

      This picture is a nice illustration of a collection of segments which does not have the property stipulated in the problem, “that for any three of these intervals, there exists a straight line intersecting all three of them.”

    • Hakan Tekgul February 17, 2019 at 9:55 pm #

      I thought that the definition of vertical intervals, Ik:=[(xk,y−k),(xk,y+k)], indicate that we can have intervals such as (1,1),(1,-1) or (-3,5), (-3,-5) such that the y-coordinate has a change of sign. Isn’t this true?

  7. Guoming Yang February 16, 2019 at 5:06 pm #

    For problem 4 is it sufficient to show that the set of lines that cross a certain interval is convex then apply helly’s theorem?

    • yuliy February 16, 2019 at 5:22 pm #

      Perhaps.

  8. Xuan Wang February 18, 2019 at 10:36 pm #

    I’m still struggling with Problem 5. Can we have a bit more hints, maybe some reference of book chapters or web links? I’m still confused about what is the function that we should optimize.

    • yuliy February 19, 2019 at 9:39 am #

      Leture notes talk about packing disks. Also there is a link on this very page to relevant paper.

Leave a Reply