\documentclass[12pt,letterpaper]{article}
\usepackage{latexsym}
\usepackage[english, activeacute]{babel}
\usepackage{amssymb,amsmath,amsthm}
%\usepackage{epsf}
\usepackage{epsfig}
%\usepackage[active]{srcltx}
%\usepackage{fullpage}
\usepackage{graphicx, float}
\usepackage{listings, color}
%\DeclareGraphicsExtensions{.eps} \graphicspath{{images/}}
%\linespread{1.3}
\parskip 1ex  \parindent 0ex
%\voffset -15mm
\oddsidemargin -0mm \topmargin 0mm \headheight 0pt \headsep 0pt
\textwidth 6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt
\renewcommand{\baselinestretch}{1.3}
\newtheorem{prop}{Proposition}
\newtheorem{Cor}{Corollary}
\newtheorem{lema}{Lemma}

\definecolor{mygreen}{RGB}{28,172,0} % color values Red, Green, Blue
\definecolor{mylilas}{RGB}{170,55,241}

\begin{document}
\pagestyle{empty}
\def \NATUR{ I \hspace*{-0.8ex} N}
\def \REALES{ I \hspace*{-0.8ex} R}
\renewcommand{\labelenumi}{\alph{enumi})}
\renewcommand{\labelenumii}{\roman{enumii})}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\hspace*{-4mm} {\includegraphics[bb=0 0 482 723, height=2.3cm]{}}
\hspace{-6mm}
\begin{tabular}{lcr}
CME 307 / MS\&E 311 & \hspace{3in} & Winter 2017-2018 \\ Optimization & & Jan 12, 2018 \\
Prof. Yinyu Ye & & Due Thursday Jan 25 5pm
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip

\begin{center}
{\large \bf Homework Assignment 1\\ Discussion Session Friday Jan 26 in Class}
\end{center}

\bigskip

\textbf{Optional Reading.} Read Luenberger and Ye?s \textit{Linear and Nonlinear Programming Fourth
Edition} Chapters 1, 2, 6 and Appendices A and B.

\textbf{Solve the following problems (10pts each for the first 8 problems):}

\begin{enumerate}
\item[1.] Do the followings:
\begin{itemize}
\item Consider the feasible set 
\[F:=\{x\in R^n:\ Ax=b,\ x\ge 0\}\]
where data matrix $A^{m\times n}$ and vector $b\in R^m$. Prove that $F$ is a convex set.

\item Fix data matrix $A$ and consider the $b$-data set for $F$ defined above:
\[B:=\{b\in R^m:\ F\ \mbox{is not empty}\}.\]
Prove that $B$ is a convex set.

\item Fix data matrix $A$ and consider the linearly constrained convex minimization problem 
\[\begin{array}{rl}
z(b):=\min  &  f(x) \\
\mbox{s.t.}&       Ax=b, \ x\ge 0
\end{array}
\]
where $f(x)$ is a convex function, and the minimal value function $z(b)$ is an implicit function of $b$. Prove that $z(b)$ is
a convex function of $b\in B$.
\end{itemize}

\item[2.] Show that the the dual cone of the $n$-dimensional nonnegative orthant cone $R^n_+$ is itself, that is,
\[(R^n_+)^*=R^n_+.\]
(Hint: show that $R^n_+\subset (R^n_+)^*$ and $(R^n_+)^*\subset R^n_+$.)

\item[3.] Using Theorem 5 in Lecture Note \#1 to prove that the linear system
\[A^TAx=A^Tb\]
always has a solution $x$ for any given matrix $A\in R^{m\times n}$ and vector $b\in R^m$.

\item[4.] Let $g_1, \ldots, g_m$ be a collection of concave functions on $R^n$ such that
\[ S = \{ x : g_i(x) > 0 \text{ for }i = 1,\ldots, m \} \neq \emptyset .\]
Show that for any positive constant $\mu$ and any convex function
$f$ on $R^n$, the function (called barrier function)
\[ h(x) = f(x) - \mu \displaystyle{\sum_{i=1}^m} \log(g_i(x))  \]
is convex over $S$.  (Hint: directly apply the convex/concave function definition or
analyze the Hessian of $h(x)$.)

\item [5.] Consider the min-risk portfolio management problem in Lecture Note \#2
\[
\begin{array}{rrl} 
&\min & x^TVx \\ 
&\mbox{s.t.}& r^Tx \ge \mu, \\ 
& & e^Tx = 1,\ x \ge 0, 
\end{array} 
\]
where data vector $r\in R^n$ representing expected return of $n$ stocks,  and $V\in R^{n\times n}$ representing co-variance matrix
of $n$ stocks, $\mu$ representing the desired return of an investment portfolio, and $e$ is the vector of all ones. The decision problem is to allocate a total 100\% of asset to each stock to minimize the risk while keep the desired return. Thus, $x_i$, $i=1,...,n$, represents the percentage of asset invested in stock $i$.

\begin{itemize}
\item Now, suppose that, for simplicity, the company's policy is to invest in each stock at one of the three possible levels: $5\%$, $10\%$ and $20\%$. How to add constraints to enforce this policy? (Hint: for each stock $i$, define three binary (taking values either $0$ or $1$) variables $y_{i1}$, $y_{i2}$ and $y_{i3}$ and let $x_i= 0.05y_{i1}+0.1y_{i2}+0.2y_{i3}$ and $y_{i1}+y_{i2}+y_{i3}\le 1$.)

\item Suppose that the company also does not want to invest in more than $20$ stocks. How to add constraints to enforce this additional policy?
\end{itemize}

\item[6.] Consider the SOCP problem described in Lecture Note \#3:
\[\begin{array}{rl}
       \min        & 2x_1+x_2+x_3\\
    \mbox{s.t.} & x_1+x_2+x_3=1,\\
                      &x_1-\sqrt{x_2^2+x_3^2}\ge 0.
  \end{array}
\]
\begin{itemize}
\item Show that the feasible region is a convex set.

\item Try to find a minimizer of the problem and ``argue'' why it is a minimizer.
\end{itemize}


\item[7.] Prove that the set $\{Ax:\ x\ge 0\in R^n\}$ is closed and convex cone. (Hint: apply Carath\'eodory's theorem in Lecture Note \#3 to prove the closeness .)
  
\item[8.] Farkas' lemma can be used to derive many
other (named) theorems of the alternative.  This problem concerns a few
of these pairs of systems. Using Farkas's lemma, prove each of the 
following results.

\noindent (a) Gordan's Theorem.  Exactly one of the following systems has a solution:
\begin{center}
(i)\quad $Ax > 0$ \\
(ii)\quad $y^T A = 0, \quad y \geq 0, \quad y \neq 0$.
\end{center}

\noindent (b) Stiemke's Theorem.  Exactly one of the following systems has a solution:
\begin{center}
(i)\quad $Ax \geq 0, \quad Ax \neq 0$ \\
(ii)\quad $y^T A = 0, \quad y > 0$
\end{center}

\noindent (c) Gale's Theorem.  Exactly one of the following systems has a solution:
\begin{center}
(i)\quad $Ax \leq b$ \\
(ii)\quad $y^T A = 0, \quad y^Tb < 0, \quad y \geq 0$
\end{center}

\item[9.] (20pts) Computation Team Work: Consider the sensor localization problem on plane $R^2$ with one sensor and three anchors $a_1=(1;0)$, $a_2=(-1;0)$ and $a_3=(0;2)$. Suppose the Euclidean distances from the sensor to the three anchors are $d_1$, $d_2$ and $d_3$ respectively and known to us.Then, from the anchor and distance information, we can locate the sensor by finding $x\in R^2$ such that
\[\|x-a_i\|^2=d^2_i,\ i=1,2,3.\]

Do the following numerical experimentations:
\begin{itemize}
\item Generate any sensor point in the convex hull of the three anchors, compute its distances to three anchors $d_i$, $i=1,2,3$, respectively. Then solve the SOCP relaxation problem
\[\|x-a_i\|^2\le d^2_i,\ i=1,2,3.\]
Did you find the correct location? What about if the sensor point was in the outside of the convex hull?

\item Now try the SDP relaxation
\[(a_i;-1)(a_i;-1)^T\bullet \left(\begin{array}{cc} I & x\\ x^T & y\end{array}\right) = d^2_i,\ i=1,2,3;\ \left(\begin{array}{cc} I & x\\ x^T & y\end{array}\right)\succeq 0\in S^3,\]
which can be written in the standard form
\[\begin{array}{cl}
(1;0;0)(1;0;0)^T\bullet Z &=1,\\
(0;1;0)(0;1;0)^T\bullet Z& =1,\\
(1;1;0)(1;1;0)^T\bullet Z& =2,\\
(a_i;-1)(a_i;-1)^T\bullet Z &= d^2_i,\ i=1,2,3,\\
Z &\succeq 0\in S^3.
\end{array}
\]
Did you find the correct location everywhere on the plane?
\end{itemize}

You can download CVX or MOSEK directly to solve these numerical problems.

\end{enumerate}

\end{document}

