#!/usr/bin/env python
# coding: utf-8

# # Nonconvex least squares
# 
# 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
# 
# $$x_{\text{ML}}^{*} = \underset{x\in\mathbb{R}^{n}}{\arg\min}\quad \|Ax - b\|_{2}^{2}\\
# \qquad\qquad\qquad\qquad\text{subject to} \quad x_{j}^{2} = 1, \quad\forall j =1,..., 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.

# ## (a) [2 + 15 = 17 points] Primal and its convex relaxation
# 
# (i) **Why** the primal problem above is nonconvex?
# 
# (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**. 

# ## (b) [30 + 15 = 45 points] Dual
# 
# (i) **Derive the Lagrange dual problem** of the original primal problem as an SDP.
# 
# **Hint:** use epigraph form followed by Schur complement lemma for possibly singular matrices (see textbook Appendix A.5.5, printed page number 651).
# 
# (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))**. 

# ## (c) [20 + 15 + 3 = 38 points] Bidual
# 
# (i) Starting from part (b)(i), **prove that the bidual (dual of the dual) problem** can be written as:
# 
# $$\text{minimize}\quad \operatorname{trace}(A^{\top}AZ) -2b^{\top}Az + b^{\top}b\\
# \text{subject to} \quad \operatorname{diag}(Z) = \mathbf{1}, \quad \begin{pmatrix}
# Z & z\\
# z^{\top} & 1
# \end{pmatrix} \succeq \mathbf{0}.$$
# 
# (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))**.
# 
# (iii) **Explain what you observe** by comparing the numerically computed optimal solutions from (a)(ii), (b)(ii) and c(ii).