\documentclass[10pt,english,a4paper]{article}
\usepackage[T1]{url}
\usepackage[utf8]{inputenc}
\usepackage{graphicx, varioref, babel, fancyvrb, listings, amsmath, amsthm, amssymb, enumerate}
\usepackage{listings}
\usepackage[]{algorithm}
\usepackage{siunitx}
\usepackage{tcolorbox}
\tcbuselibrary{theorems}
\usepackage{hyperref}
\newcommand{\R}{\mathbb{R}}
% Just testing a new theorem style
%\newtcbtheorem{theorem}{Theorem}%
%{colback=white,colframe=black!75!white,fonttitle=\bfseries}{th}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}
\newtheorem*{proposition}{Proposition}
\lstdefinelanguage{matlab}
{
morekeywords={for,def,if,while,do,break,return,from,import,try,except,else,elif},
sensitive=false,
morecomment=[l]{\#}
}
\lstset{language=matlab,
backgroundcolor=\color[rgb]{.95,.95,.95},
numbers=none,xleftmargin=10pt,
numberstyle=\tiny,stepnumber=5,numbersep=5pt,
stringstyle=\color{red},
basicstyle=\ttfamily,
keywordstyle=\color{blue},
commentstyle=\color{green},
basewidth=0.45em,
showstringspaces=false,
captionpos=b,
frame=single
}
\def\st{\textnormal{ subject to }}
\def\lb{\left\{ }
\def\rb{\right\} }
%\begin{figure}
% \centering
% \includegraphics[height=7cm]{nameOfFile}
% \caption{}
%\end{figure}
\title{MAT3100 - Compulsory exercise 1 of 2, \the\year}
%\author{\O yvind Ryan}
\begin{document}
\maketitle
\section*{Exercise 1}
Consider the problem
\[
\begin{array}{rrrrr}
\text{max } 2x_1 &+& 3x_2 && \\
\text{s.t. } 2x_1 &+& x_2 &\leq& 10 \\
x_1 &+& 2x_2 &\leq& 10 \\
x_1 &+& x_2 &\leq& 6 \\
& & x_1,x_2 &\geq& 0
\end{array}
\]
\subsection*{a)}
Write down a matrix $A$ and vectors ${\bf b}$ and ${\bf c}$ so that the problem can be written on the form
\begin{align*}
\text{max } {\bf c}^T{\bf x} \\
\text{s.t. } A{\bf x} &\leq {\bf b} \\
{\bf x} &\geq {\bf 0}
\end{align*}
\subsection*{b)}
Sketch the feasible region of the problem.
\subsection*{c)}
Solve the problem using the Simplex method.
\subsection*{d)}
We consider the same constraints as in a), but change the objective function to $2x_1+2x_2$. Apply the simplex method again to find all optimal solutions to this modified problem.
\section*{Exercise 2}
Find any optimal solution to the problem
\[
\begin{array}{rrrrrrr}
\text{max } x_1 &+& x_2 &+& x_3 &&\\
\text{s.t. } 2x_1 &-& 2x_2 &+& x_3 &\leq& 4 \\
3x_1 &-& x_2 &+& 2x_3 &\leq& 2 \\
& & & & x_1,x_2,x_3 &\geq & 0
\end{array}
\]
\section*{Exercise 3}
In the field of compressive sensing one attempts to recover an unknown vector from an underdetermined set of (linear) measurements, i.e.,
find an unknown ${\bf x}\in\R^N$ that satisfies $A{\bf x}={\bf p}$, where
\begin{itemize}
\item ${\bf p}\in\R^m$ is the vector of measurements, and
\item $A$ is the $m\times N$ matrix which collects those measurements.
\end{itemize}
In practical applications $m$ is much smaller than $N$, and we can't expect to recover ${\bf x}$ in general. But if we have some additional information about ${\bf x}$, it turns out that the knowledge of the measurements in ${\bf p}$
may still be enough to recover ${\bf x}$. The additional information we will consider is {\em sparsity} (a vector is called sparse if it has mostly components that are zero):
For many ``magic" matrices $A$, if it is known that ${\bf x}$ is sparse, ${\bf x}$ can be recovered as the optimal solution to the problem
\begin{equation} \label{bp}
\begin{array}{rr}
\text{min } & \|{\bf x}\|_1\\
\text{s.t. } & A{\bf x}={\bf p},
\end{array}
\end{equation}
where $\|{\bf x}\|_1=|x_1|+|x_2|+\ldots+|x_N|$.
Note that the variable ${\bf x}$ here is unconstrained: It is not required to be non-negative.
In the following we will test if this procedure works for a very small vector and matrix.
\subsection*{a)}
Show that ${\bf x}$ is an optimal solution to \eqref{bp} if and only if it is an optimal solution to
\begin{equation} \label{bprewritten}
\begin{array}{rr}
\text{max } & \sum_i(-x_i^+-x_i^-)\\
\text{s.t. } & \begin{pmatrix}A & -A\\ -A & A\end{pmatrix} \begin{pmatrix}{\bf x}^+\\{\bf x}^-\end{pmatrix}\leq\begin{pmatrix}{\bf p}\\-{\bf p}\end{pmatrix} \\
& {\bf x}^+,{\bf x}^-\geq{\bf 0}
\end{array}
\end{equation}
This is a linear programming problem in standard form.\\
{\bf Hint}: Write $x_i=x_i^+-x_i^-$, where $x_i^+,x_i^-\geq 0$.
Let us test this procedure on the sparse vector ${\bf x}=(0,0,-1)$, and the matrix $A=\begin{pmatrix}1&0&-1\\0&1&-1\end{pmatrix}$, to see if ${\bf x}$ is recovered from the vector of measurements,
which here can be computed to be ${\bf p}=(1,1)$.
Of course, it does not sound like rocket science to recover a vector with 3 components from two measurements. But the magic is that solving the problem \eqref{bp} also can help recover sparse vectors ${\bf x}$
when $N$ is very large and $m$ is very small compared to $N$!
\subsection*{b)}
Solve \eqref{bprewritten}, with $A$ and ${\bf p}$ as given above, using the simplex method. Is the correct ${\bf x}$ recovered? Is the optimum unique?
To get started, you can use that the primal dictionary is
\[
\begin{array}{rrrrrrrrr}
\zeta &=& &-x_1 &-x_2 &-x_3 &-x_4 &-x_5 &-x_6 \\\hline
w_1 &=& 1 &-x_1 & &+x_3 &+x_4 & &-x_6 \\
w_2 &=& 1 & &-x_2 &+x_3 & &+x_5 &-x_6 \\
w_3 &=& -1 &+x_1 & &-x_3 &-x_4 & &+x_6 \\
w_4 &=& -1 & &+x_2 &-x_3 & &-x_5 &+x_6
\end{array}
\]
where we wrote ${\bf x}^+=(x_1,x_2,x_3)$, ${\bf x}^-=(x_4,x_5,x_6)$, and denoted the slack variables by $w_i$.\\
{\bf Hint}: The starting dictionary above is not primal feasible, but dual feasible. So write down the dual dictionary or apply the dual simplex method.
\\\\A couple of remarks should be made.
\begin{itemize}
\item For this particular exercise, simplex is not the easiest way to solve \eqref{bp}: That $A{\bf x}={\bf p}$ means simply that $x_1-x_3=x_2-x_3=1$, so that $x_1=x_2=x_3+1$, with $x_3$ arbitrary.
The problem thus boils down to minimizing $|x_1|+|x_2|+|x_3|=2|x_3|+|x_3+1|$, which is easily solved by hand.
\item For larger $A$ and ${\bf p}$, we depend on an implementation of simplex, since such problems are too tedious to solve by hand.
\end{itemize}
\end{document}