{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Nonconvex least squares\n",
    "\n",
    "Suppose a signal $x\\in\\{-1,1\\}^{n}$ is sent over over a noisy channel, and received as $b=Ax + v$ where $v\\sim\\mathcal{N}(0,\\sigma^{2}I)$ is Gaussian noise. Based on the received signal $b\\in\\mathbb{R}^{m}$, the **maximum likelihood estimate** $x_{\\text{ML}}^{*}$ of the original signal $x$ is obtained by solving\n",
    "\n",
    "$$x_{\\text{ML}}^{*} = \\underset{x\\in\\mathbb{R}^{n}}{\\arg\\min}\\quad \\|Ax - b\\|_{2}^{2}\\\\\n",
    "\\qquad\\qquad\\qquad\\qquad\\text{subject to} \\quad x_{j}^{2} = 1, \\quad\\forall j =1,..., n,$$\n",
    "\n",
    "where $A\\in\\mathbb{R}^{m\\times n}$ and $b\\in\\mathbb{R}^{m}$ are known. Assume that $\\text{rank}(A)=n$, that is, $A^{\\top}A$ is nonsingular."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (a) [2 + 15 = 17 points] Primal and its convex relaxation\n",
    "\n",
    "(i) **Why** the primal problem above is nonconvex?\n",
    "\n",
    "(ii) A convex relaxation of the primal is obtained by simply deleting the nonconvex constraint, and is therefore a convex optimization problem. **Numerically solve the convex relaxation of the primal** in MATLAB/Python/Julia using cvx/cvxpy/Convex.jl for the $A,b$ data given in the starter code $\\texttt{AM229F20HW7problem.m}$ (inside CANVAS). **Report the numerically computed optimal value, and the percentage error between true $x$ and $\\text{sign}(x_{a})$ where $x_{a}$ is the minimizer of the convex relaxation. Submit your code**. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (b) [30 + 15 = 45 points] Dual\n",
    "\n",
    "(i) **Derive the Lagrange dual problem** of the original primal problem as an SDP.\n",
    "\n",
    "**Hint:** use epigraph form followed by Schur complement lemma for possibly singular matrices (see textbook Appendix A.5.5, printed page number 651).\n",
    "\n",
    "(ii) Use the same code (and problem data) in part (a)(ii) to numerically solve the dual problem of part(b)(i). **Report the numerically computed optimal value of the dual problem, and submit your code (same file as in part(a))**. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (c) [20 + 15 + 3 = 38 points] Bidual\n",
    "\n",
    "(i) Starting from part (b)(i), **prove that the bidual (dual of the dual) problem** can be written as:\n",
    "\n",
    "$$\\text{minimize}\\quad \\operatorname{trace}(A^{\\top}AZ) -2b^{\\top}Az + b^{\\top}b\\\\\n",
    "\\text{subject to} \\quad \\operatorname{diag}(Z) = \\mathbf{1}, \\quad \\begin{pmatrix}\n",
    "Z & z\\\\\n",
    "z^{\\top} & 1\n",
    "\\end{pmatrix} \\succeq \\mathbf{0}.$$\n",
    "\n",
    "(ii) Use the same code (and problem data) in part (a)(ii) and (b)(ii) to numerically solve the bidual problem of part(c)(i). **Report the numerically computed optimal value, and the percentage error between true $x$ and $\\text{sign}(z)$ where $z$ is the minimizer in part (c)(i). Submit your  code (same file as in part(a))**.\n",
    "\n",
    "(iii) **Explain what you observe** by comparing the numerically computed optimal solutions from (a)(ii), (b)(ii) and c(ii). "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "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.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}