mock midterm 2

\(\def\Real{\mathbb{R}}
\def\Comp{\mathbb{C}}
\def\Rat{\mathbb{Q}}
\def\Field{\mathbb{F}}
\)


Sample problems

  1. Find Fenchel dual (conjugate, or \(\check{f}(p):=\sup_x px-f(x)\)) for
    1. \(f(x)=|x-1|+x/2\);

      Answer:
      \[
      \check{f}(p)=p-1/2 \mathrm{\ if}\ -1/2\leq p\leq 3/2; +\infty \mathrm{\ otherwise}.
      \]
    2. f\((x)=x^2/2+1/2 \ \mathrm{for} \ |x|\leq 1; |x| \ \mathrm{otherwise}\).

      Answer:
      \[
      \check{f}(p)=p^2/2-1/2 \mathrm{\ if}\ -1\leq p\leq 1; +\infty \mathrm{\ otherwise}.
      \]
  2. Is the subset of \(\Real^3\) given by
    \[
    a\gt 0; a^2-b^2\gt 0; a^3-a(b^2+c^2)\gt 0
    \]
    convex?

    Hint: when \(
    \left(
    \begin{array}{ccc}
    a&b&0\\
    b&a&c\\
    0&c&a\\
    \end{array}
    \right)
    \) is positive semidefinite?

    Answer: yes, the inequalities are the Sylvester condition for the matrix to be positive definite;
    convex combination of positive definite matrices is positive definite again.

  3. Find the conditions on vector \((a,b)\) to be a subdifferential for
    \[
    f(x,y)=\max(e^x,e^y,e^{-x-y})
    \]
    at the points \((0,0), (-2,1),(2,1)\).

    Answer: for \((0,0)\), \((a,b)\) is in the convex hull of the vectors \((0,1),(1,0),(-1,-1)\); for \((-2,1)\), \((a,b)\) is in the convex hull of the vectors \((0,e),(-e,-e)\); for \((2,1)\), \((a,b)=(e^2,0)\).

  4. Consider the problem
    \[
    x=(x_1,\ldots,x_d); f(x)\to \max,\ \mathrm{subject\ to}\ \sum_i p_i x_i\leq b, x_i\gt 0, i=1,\ldots, d,
    \]
    where \(f(x)=\prod x_i^{a_i}, a_i\gt 0\) is the Cobb-Douglas utility function (a standard microeconomic setting, where \(x_i\) are quantities of \(i\)-th good, \(p_i\) are corresponding prices, and \(b\) is the budget constraint).

    1. Is the optimum unique?

      Answer: Yes, it is given by
      \[
      x_i=\frac{ba_i}{ap_i},
      \]
      where \(a=\sum_i a_i\).

    2. If \(\{x_i(b)\}_{i=1,\ldots,d}\) is the optimal solution, find \({dx_i}/{db}\).

      Answer: \[
      {dx_i}/{db}=\frac{a_i}{ap_i},
      \]

    3. Can you find a concave \(f\) such that for some \(i\), \({dx_i}/{db}\lt 0\)?

      Answer: take, for example,
      \[
      f(x_1,x_2)=\min(x_1+3,2x_1+4x_2).
      \]
      As a minimum of linear functions, \(f\) is concave, and for \(p_1=p_2=1\), the optimum over the budget set \(x_1+x_2\leq b\) is attained at
      \[
      x_1=4b/3-1, x_2=1-b/3,
      \]
      that is
      \({dx_i}/{db}=-1/3\).

  5. Consider the problem
    \[
    \begin{array}{ccc}
    -x&+y&\to\min, \mathrm{subject\ to}\\
    x&+2y&\leq 2\\
    x&&\geq 0\\
    &y&\geq 0\\
    \end{array}.
    \]

    1. Solve it.

      Answer: \(x=2,y=0, p_*=-2\).

    2. Formulate and solve the dual problem.

      Answer: the original problem is equivalent to
      \[
      \begin{array}{ccc}
      -x&+y&\to\min, \mathrm{subject\ to}\\
      -x&-2y&\geq -2\\
      x&&\geq 0\\
      &y&\geq 0\\
      \end{array},
      \]
      for which the dual is
      \[
      \begin{array}{cc}
      -2\lambda &\to\max, \mathrm{subject\ to}\\
      -\lambda &\leq -1\\
      -2\lambda &\leq 1\\
      \lambda &\geq 0\\
      \end{array}.
      \]
      Solution, is, obviously, \(\lambda=1, d_*=-2\).

12 Responses to mock midterm 2

  1. Stephen March 26, 2016 at 5:16 pm #

    For problem 1, the Fenchel conjugate should be defined in terms of sup, right? If it is inf, there should be a negative sign.

    • yuliy March 26, 2016 at 5:27 pm #

      Thank you! Corrected.

  2. Stephen March 28, 2016 at 2:09 pm #

    Does Problem 2 have 3 separate subsets? Or is that one subset defined with three inequalities? It seems that each inequality supersedes the previous one.

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

      Defined by three inequalities: they are not implying each other.

  3. Anonymous March 29, 2016 at 6:20 pm #

    Hi Professor,

    Will you post solutions to the mock exam?

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

      Answers posted.

  4. Atlas March 30, 2016 at 2:14 pm #

    Problem 4: could we assume x_i > 0 , \forany i?

    Also, I think optimum exists iff \sum_i a_i \le 1. Is it correct?

    • yuliy March 30, 2016 at 5:08 pm #

      Yes, all variables are positive.

  5. Ann March 30, 2016 at 4:53 pm #

    Hi Professor, for question 2, I think the set may not be convex.
    (0,0,4) and (2,2,0) both satisfy the three inequalities, so they are in the given set.
    However, point (1,1,2), as a convex combination of these two points, does not satisfy the constraint a^3 – a(b^2+c^2) >= 0. Hence it is not in the given set. As it violates the definition of convex set, the given set is not convex.

    • yuliy March 30, 2016 at 5:07 pm #

      Right – should have been strict inequalities.

  6. Jia March 30, 2016 at 8:48 pm #

    Hi, professor.

    I think the solution to Problem4(c) should be x1= (4b/3)-1. If x1=(4b/3) and x2=1-(b/3), x1 + x2 equals 1+b which is greater than b, which violates the restriction.

    • yuliy March 30, 2016 at 10:42 pm #

      Thank you! – corrected.

Leave a Reply