week 9

\(\def\Real{\mathbb{R}}
\def\Comp{\mathbb{C}}
\def\Rat{\mathbb{Q}}
\def\Field{\mathbb{F}}
\def\Fun{\mathbf{Fun}}
\def\e{\mathbf{e}}
\def\f{\mathbf{f}}
\def\bv{\mathbf{v}}
\)

Linear Proramming

Barvinok, 4.

Convex closed cones, their polars.

General LP problems. Dual problems for general LP.

Polyhedral cones, strong duality.


Sample problems

  1. Let \(K=\Real_+^3\) be the cone of vectors with nonnegative coordinates. Consider a mapping \(A:\Real^3\to\Real^2\) given by the matrix
    \[
    A=\left(
    \begin{array}{ccc}
    3&2&1\\1&2&3\\
    \end{array}
    \right).
    \]
    Describe \(A(K)\)

    Answer: cone spanned by the rays \((3t,t),(t,3t),t\geq0\), or, equivalently, given by \(\{y\leq 3x, x\leq 3y \}\).

  2. Same question for \(K=\{xy\geq z^2, x\geq 0\}\), and \(A:\Real^3\to\Real^2\) given by
    \[
    A=\left(
    \begin{array}{ccc}
    1&0&0\\0&0&1\\
    \end{array}
    \right):
    \]
    describe \(A(K)\)

    Answer: the set \(\{x\gt 0\}\cup (0,0)\) in the \(\langle x,z\rangle\) plane.

  3. Find the optimum for the LP
    \[
    \begin{array}{rll}
    ax&+by&\to\min,\ \mathrm{subject\ to}\\
    -x&+y&\leq 1\\
    x&-y&\leq 1\\
    x&+y&\leq 3\\
    x&&\geq 0\\
    &y&\geq 0
    \end{array}
    \]
    as a function of \(a,b\).

    Answer:

    • \(0\) for \(a,b\geq 0\);
    • \(a\) for \(a\leq 0 \leq a+b\);
    • \(b\) for \(b\leq 0\leq a+b\);
    • \(2a+b\) for \(a+|b|\leq 0\);
    • \(2b+a\) for \(|a|+b\leq 0\);

10 Responses to week 9

  1. Tianyi March 28, 2016 at 10:52 am #

    What does it mean exactly by “Describe A(K)”? How would I describe the set?

    • yuliy March 29, 2016 at 12:08 am #

      It is a convex cone on the plane. Any such cone is either all of the plane, or a ray, or the wedge between two rays. Describe which of those alternatives happens, and give the directions of the rays, if necessary.

  2. Chen March 28, 2016 at 8:06 pm #

    Hi Professor, what do we need to describe for Q1 and Q2? Could you give an example?

    • yuliy March 29, 2016 at 12:17 am #

      See comment above.

  3. Tianyi He March 29, 2016 at 8:28 pm #

    I am having trouble solving Question 1, I can see that it is mapping R3+ to R2, but I am not sure about how exactly A(K) is mapped to in R2+. I see that two vectors are linearly independent in R3, but I do not see the relationship it has on the space it mapped to in R2. Can I have some hint on this one?

    • yuliy March 29, 2016 at 11:18 pm #

      Cone K is a convex hull of three rays (which?). Hence A(K) will be the convex hull of the images of these three rays. Find these images, and you’ll be done.

    • Tianyi March 30, 2016 at 1:45 pm #

      Thanks for the hint! Just to confirm if I have your hint correctly. R3+ is the convex hull of x,y,z axes, and the projection of those three rays to R2 through A(K) would be a convex hull (cone) of a ray passing through (3,1) from origin and (1,3) from origin in the positive quadrant. So for transformation of convex hull we can just transform the boundaries (vertices) and the take the convex hull of those?

    • yuliy March 30, 2016 at 4:36 pm #

      More or less correct.

  4. Yudu March 29, 2016 at 9:57 pm #

    Hi Professor, from my intuition, the answer to the 1st question is the positive subset of R2. Is it correct? If so, can you give a proof for it?

    • yuliy March 29, 2016 at 11:18 pm #

      What is a “positive subset of R2”?

Leave a Reply