{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "***\n", "# Problem Sheet 4\n", "***\n", "$\\newcommand{\\vct}[1]{\\mathbf{#1}}$\n", "$\\newcommand{\\mtx}[1]{\\mathbf{#1}}$\n", "$\\newcommand{\\e}{\\varepsilon}$\n", "$\\newcommand{\\norm}[1]{\\|#1\\|}$\n", "$\\newcommand{\\minimize}{\\text{minimize}\\quad}$\n", "$\\newcommand{\\maximize}{\\text{maximize}\\quad}$\n", "$\\newcommand{\\subjto}{\\quad\\text{subject to}\\quad}$\n", "$\\newcommand{\\R}{\\mathbb{R}}$\n", "$\\newcommand{\\trans}{T}$\n", "$\\newcommand{\\ip}[2]{\\langle {#1}, {#2} \\rangle}$\n", "$\\newcommand{\\zerovct}{\\vct{0}}$\n", "$\\newcommand{\\diff}[1]{\\mathrm{d}{#1}}$\n", "$\\newcommand{\\dom}{\\mathrm{dom} }$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## Part A\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problem 4.1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For the following linear programming problems,\n", "\n", "\\begin{align*}\\tag{LP1}\n", " \\maximize & x_1+2x_2 \\\\\n", " \\subjto &x_1+x_2\\leq 2\\\\\n", " & x_1-x_2\\leq 1\\\\\n", " &x_1\\geq -1\n", "\\end{align*}\n", "\n", "\\begin{align*}\\tag{LP2}\n", " \\maximize & x_1+x_2 \\\\\n", " \\subjto\n", " & x_2-x_1\\leq 2\\\\\n", " & x_1+x_2\\leq 8\\\\\n", " &x_1+2x_2\\leq 10\\\\\n", " &x_1\\leq 4\\\\\n", " &x_1\\geq 0\\\\\n", " &x_2\\geq 0.\n", "\\end{align*}\n", "\n", "(a) Sketch the polyhedron of feasible points and find the vertices;\n", "\n", "(b) Find a solution, if it exists (you can find the solution visually, but you may use a computer program such as CVXPY in Python or CVX in MATLAB to verify the result)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problem 4.2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Given a matrix $\\mtx{A}\\in \\R^{m\\times n}$ and $\\vct{b}\\in \\R^m$ such that the polyhedron $P=\\{\\vct{x}\\in \\R^n\\mid \\mtx{A}\\vct{x}\\leq \\vct{b}\\}$ is not empty and bounded. \n", "Show that if the optimal value of\n", "\n", "\\begin{equation*}\n", " \\maximize \\ip{\\vct{c}}{\\vct{x}} \\quad \\subjto \\mtx{A}\\vct{x}\\leq \\vct{b}\n", "\\end{equation*}\n", "\n", "is finite, it is attained at a vertex $\\vct{x}^*$ of $P$. \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problem 4.3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Formulate the following optimization problem as a linear programming problem,\n", "\n", "\\begin{equation*}\n", " \\minimize \\norm{\\vct{x}}_1 \\quad \\subjto \\mtx{A}\\vct{x}=\\vct{b},\n", "\\end{equation*}\n", "\n", "and describe the dual problem." ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problem 4.4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Show that there exists a vector $\\vct{x}\\neq \\zerovct$ satisfying \n", "\n", "\\begin{equation*}\\tag{P}\n", " \\vct{x}\\geq 0, \\quad \\mtx{A}\\vct{x}=\\zerovct\n", "\\end{equation*}\n", "\n", "if and only if there is no vector $\\vct{y}$ such that\n", "\n", "\\begin{equation*}\\tag{D}\n", " \\mtx{A}^{\\trans}\\vct{y}>\\zerovct.\n", "\\end{equation*}\n", "\n", "Give a geometric interpretation of this fact." ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## Part B\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problem 4.5" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(Compressive Sensing) Consider a signal $f\\colon [0,2\\pi]\\to \\R$\n", "with the property that $f(0)=f(2\\pi)$. In practice, one often does not see the whole signal, but only samples certain values at discrete time intervals. It turns out that optimization can help to reconstruct a signal using much fewer samples than commonly thought possible.\n", "\n", "\n", "\n", "To understand how the reconstruction from few samples works, we have to look at the Fourier Transform. A periodic function can be written as a Fourier Series\n", "\n", "\\begin{equation*}\n", " f(x) = \\frac{a_0}{2}+\\sum_{n=1}^\\infty a_n\\cos(nx)+b_n\\sin(nx).\n", "\\end{equation*}\n", "\n", "Setting $c_n=(a_n+ib_n)/2$, $c_{-n}=(a_n-ib_n)/2$ for $n>0$, and $c_0=a_0/2$, the series can also be written in exponential form as as\n", "\n", "\\begin{equation*}\\tag{1}\n", " f(x) = \\sum_{n=-\\infty}^\\infty c_n e^{inx},\n", "\\end{equation*}\n", "\n", "where $e^{ix} = \\cos(x)+i\\sin(x)$ and $i=\\sqrt{-1}$. While this representation involves complex numbers, the resulting function is real due to the way the imaginary parts in the summands combine. \n", "We can obtain the coefficients $c_n$ in the series (1) by computing\n", "\n", "\\begin{equation*}\n", " c_n = \\hat{f}(n) := \\frac{1}{2\\pi} \\int_0^{2\\pi} f(x) e^{-inx} \\ dx.\n", "\\end{equation*}\n", "\n", "The operation $f\\mapsto \\hat{f}$ is called the {\\em Fourier Transform}. A characteristic feature of many signals is that they are **sparse** in the Fourier domain, meaning that only very few summands in the expansion (1) are necessary to describe the signal accurately (in two dimensions, this principle is the basis of the JPEG image compression standard). For the particular function shown in the figure above, the representation is \n", "\n", "\\begin{equation*}\\tag{2}\n", " f(x) = 0.5\\sin(5x)+0.5\\cos(9x)-\\cos(11x)+0.2\\sin(13x)+1.7\\sin(30x).\n", "\\end{equation*}\n", "\n", "Often we are not so much interested in the analytic expression for the function $f$ but in its values at a discrete set of points\n", "\n", "\\begin{equation*}\n", " x_0=0, \\quad x_n=2\\pi, \\quad x_k=\\frac{2\\pi k}{n}.\n", "\\end{equation*}\n", "\n", "The goal of reconstructing $f$ then becomes the reconstruction of *all* values $f_j=f(x_j)$ from the knowledge of only a few samples $f_k$, $k\\in I\\subset \\{0,\\dots,n-1\\}$, $|I|=m\n", "\n", "The sparsity of DFT vector is the key reason why the following approach for reconstructing $\\vct{f}$ from few samples $\\vct{f}_I$ works. Consider the optimization problem\n", "\n", "\\begin{align*}\\tag{5}\n", " \\minimize & \\norm{\\vct{c}}_1,\\\\\n", " \\subjto & \\mtx{D}_I\\vct{c} = \\vct{f}_I,\n", " \\end{align*}\n", " \n", "with the function given as in (2), where $I\\subset[n]$ and $\\mtx{D}_I$ is the matrix consisting of the rows indexed by $I$ and $\\mtx{f}_I$ the subvector indexed by the entries of $I$ (the red dots in the first figure). For example,\n", "\n", "\\begin{equation*}\n", " \\mtx{D} = \\begin{pmatrix} 1 & 2 & 3\\\\\n", " 2 & 3 & 4\\\\\n", " 3 & 4 & 5\n", " \\end{pmatrix},\n", "\\ I=\\{1,3\\}, \\quad \\Longrightarrow \\mtx{D}_I = \\begin{pmatrix} 1 & 2 & 3\\\\\n", " 3 & 4 & 5\n", " \\end{pmatrix}\n", "\\end{equation*}\n", "\n", "In words, we are looking for a vector $\\vct{c}$ of minimal $1$-norm that satisfies *a small part* of the quadratic system of equations. Once we have such a solution $\\hat{\\vct{c}}$, the hope is that $\\mtx{D}\\hat{\\vct{c}}=\\vct{f}$ gives back the full vector. \n", "\n", "(a) Formulate the conditions $\\mtx{D}_I\\vct{c}=\\vct{f}_I$ as {\\em linear} constraints involving real numbers. Hint: split $\\vct{c}$ and $\\mtx{D}_I$ in real and imaginary parts and reformulate the matrix-vector product accordingly.\n", "\n", "(b) Solve the optimization problem~\\eqref{eq:l1min} as follows.\n", "\n", "- Set $n=512$ and generate points $x_i=2\\pi j/n$ with corresponding values $f_j=f(x_j)$. \n", "- Generate the matrix $\\mtx{D}$ (in Python, using {\\tt numpy.ifft;}) and\n", "choose a random set of $50$ indices to generate a matrix $\\mtx{D}_I$ and $\\vct{f}_I$. \n", "- Using CVXPY (Python) or CVX (MATLAB), solve the optimization problem (5) and compare the computed vector $\\hat{\\vct{f}}$ with the original $\\vct{f}$.\n", "\n", "(c) Repeat the experiment in Part (b) with different values of $m$ in order to determine how many samples are necessary to reconstruct the vector $\\vct{f}$ accurately.\n", "\n", "(d) Reformulate (5) as a linear programming problem." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python [py27]", "language": "python", "name": "Python [py27]" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.12" } }, "nbformat": 4, "nbformat_minor": 0 }