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