\documentclass[12pt,letterpaper]{article}
\usepackage{latexsym}
\usepackage[english, activeacute]{babel}
\usepackage{amssymb,amsmath,amsthm}
%\usepackage{epsf}
\usepackage{epsfig}
%\usepackage[active]{srcltx}
%\usepackage{fullpage}
%\usepackage[dvips]{graphicx}
%\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}
\renewcommand\a{{\bf a}}
\renewcommand\b{{\bf b}}
\newcommand\x{{\bf x}}
\renewcommand\d{{\bf d}}

\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 & & Feb 9, 2018 \\
Prof. Yinyu Ye & & Due Monday Feb 26 5pm
\end{tabular}

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

\begin{center}
{\large \bf Homework Assignment 3 \\  Discuss Session Friday March 2 in Class}
\end{center}
%\vfill

%{}

\bigskip

{\textbf{Reading.}} Read selected sections in Luenberger and Ye's {\sl Linear
and Nonlinear Programming Fourth Edition} Chapters 3, 8, 9 and 10.

{\textbf{Solve the following problems:}}
\begin{enumerate}
\item[1.]  (Problem 8.6 from L\&Y) Consider the iterative process
$$ x_{k+1} = \frac{1}{2} \left( x_k + \frac{a}{x_k} \right), $$
where $a > 0$. Assuming the process converges, to what does it converge? What is the order of convergence?

\item[2.] Let $f$ be a $\beta$-Lipschitz function. Prove that for any two points $x$ and $y$,
$$ f(x) - f(y) - \nabla f(y)^T (x-y) \leq \frac{\beta}{2} \|x-y\|^2. $$
({\em Hint: Use the Taylor Expansion formula.} )

\item[3.] Use the simplex method to solve the following LP, assuming that you start at the origin (a corner point):
\begin{align*}
\max_x \qquad & 2x_1 + 4x_2 + x_3 + 4_4 \\
\mbox{s.t.} \qquad & 
\begin{matrix} x_1  & +\, 3x_2 &        & +\,x_4 & \leq 4 \\
               2x_1 & +\, \phantom{1} x_2  &        &      & \leq 3 \\
                    & +\, \phantom{1} x_2  & +\, 4x_3 & +\,x_4 & \leq 3\end{matrix} \\
& x_i \geq 0, \qquad i = 1,2,3,4.
\end{align*}

\item[4.] In Logistic Regression (LR), we determine $x_0$ and $\x$ by maximizing
\[
\left(\prod_{i,c_i=1}\frac{1}{1+\exp(-\a_i^T\x-x_0)}\right)
\left(\prod_{i,c_i=-1}\frac{1}{1+\exp(\a_i^T\x+x_0)}\right).
\]
which is equivalent to maximizing the log-likelihood probability
\[
-\sum_{i,c_i=1}\log\left(1+\exp(-\a_i^T\x-x_0)\right)-\sum_{i,c_i=-1}\log\left(1+\exp(\a_i^T\x+x_0)\right).
\]
Equivalently, we minimize the log-logistic-loss
\[
f(\x,x_0)=\sum_{i,c_i=1}\log\left(1+\exp(-\a_i^T\x-x_0)\right)+\sum_{i,c_i=-1}\log\left(1+\exp(\a_i^T\x+x_0)\right).
\]
\begin{enumerate}
\item[(a)] Write down the gradient vector function of the log-logistic-loss function.

\item[(b)] Consider the specific problem described in question (b) of Problem 6 in HW2, and using the KKT conditions try to find a solution of $$\min\ f(\x,x_0).$$
%\begin{itemize}
%\item[(i)] try to find a solution of $$\min\ f(\x,x_0)$$ 
%\item[(ii)] try to find a solution of $$\min\ f(\x,x_0)+\mu\|\x\|_2^2$$ with a given small $\mu$, which model is called the LR with regularization.
%\end{itemize}
\end{enumerate}

\item[5] (Computation Team Work) Implement the steepest descent, the accelerated steepest descent, the conjugate direction, and the BB methods to numerically solve the problem in (4.b) (with some noises added) and/or your own classification data and compare their convergence speeds.

\item[6.] (Problem 8.24 from L\&Y) Consider a problem of the form
\begin{align*}
\min_x \qquad & f(x) \\
\mbox{s.t} \qquad & x \geq 0,
\end{align*}
where $x \in E^n$. A gradient-type procedure has been suggested for this kind of problem that accounts for the constraint. At a given point $x = (x_1, x_2, \dots, x_n)$, the direction $d = (d_1, d_2, \dots, d_n)$ is determined from the gradient $\nabla f(x)^T = g = (g_1, g_2, \dots, g_n)$ by
$$ d_i = \begin{cases} -g_i & \mbox{if } x_i > 0 \mbox{ or } g_i < 0 \\
                       0 & \mbox{if } x_i = 0 \mbox{ and } g_i \geq 0. \end{cases} $$
This direction is then used as a direction of search in the usual manner.
\begin{enumerate}
\item[(a)] What are the first-order necessary conditions for a minimum point of this problem?

\item[(b)] Show that $d$, as determined by the algorithm, is zero only at a point satisfying the first-order conditions.

\item[(c)] Show that if $d \neq 0$, it is possible to decrease the value of $f$ by movement along $d$.
\end{enumerate}

Bonus Question: Several step-size rules could be used
\begin{itemize}
\item[(i)] Find the largest step-size $\alpha$ such that $\x+\alpha \d\ge 0$, say $\bar\alpha$, then the actual step-size is $\min\{\bar\alpha,\frac{1}{\beta}\}$.
 
\item[(ii)] Take $\frac{1}{\beta}$ as your initial step-size. If one coordinate of the new iterate become negative, halve the step-size and retry.
\end{itemize}
What is the convergence speed of the method?

\item[7.] Consider the problem from 6 above, but instead we solve the Barrier problem
\[\min_{x>0}\ \phi(\x):=f(\x)-\mu\sum_{j=1}^n\ln(x_j)\]
where $\mu$ is a small positive constant.
\begin{itemize}
\item[(a)] What are the first-order necessary conditions for the minimizer of $\phi(\x)$?

\item[(b)] Let $f(\x)=\frac{1}{2}\|A\x-\b\|^2$. Write out the gradient descent update with step-size $\alpha^k$ in this case, and describe how you would determine the step-size. Remember to ensure that $\x > 0$.
%Then develop the standard steepest gradient iterative process to find a KKT solution; mainly
%develop a step-size rule to keep each iterate $\x^k>0$ (besides a line search to minimize $\phi$ along the descent direction).

\item[(c)] Again let $f(\x)=\frac{1}{2}\|A\x-\b\|^2$, and at the $k$ step consider the (affine) scaled gradient vector
\[(X^k)^2\nabla\phi(\x^k),\]
where $X^k$ is the diagonal matrix of $k$th iterate $\x^k(>0)$. Let us generate the next iterate by
\[\x^{k+1}=\x^k-\alpha^k(X^k)^2\nabla\phi(\x^k),\]
for some step-size $\alpha^k$ (you also need a step-size rule to keep $\x>0$). Is this a descent direction for $\phi$? How is this direction different from (b), especially when some element in $\x^k$ is already close to zero?

\item[(d)] (Computation Team Work) Generate some random data and solve them with $\mu=0$ and $\mu=10^{-4}$, and observe any possible difference between methods (b) and (c).
\end{itemize}

\item[8.] Now consider the problem:
\[\min\ f(X)\quad \mbox{s.t.}\quad X\succeq 0,\]
and its Barrier problem
\[\min_{X\succ 0}\ \phi(X):=f(X)-\mu\ln\det(X)\]
where $\mu$ is a small positive constant.

\begin{itemize}
\item[(a)] What are the (symmetric) gradient matrix and the first-order necessary conditions for the minimizer of $\phi(X)$?

\item[(b)] Let $f(X)=\frac{1}{2}\|{\cal A}X-\b\|^2$, where
\[{\cal A}X=\left(\begin{array}{c}
                           A_1\bullet X\\
                           ...\\
                           A_m\bullet X
                           \end{array}\right).\]
for some symmetric data matrices $A_1$,...,$A_m$, and data vector $\b$.
Write out the gradient descent update with step-size $\alpha^k$ in this case, and describe how you would determine the step-size. Remember to ensure that $X^k \succ 0$.

\item[(c)] Again let $f(X)=\frac{1}{2}\|{\cal A}X-\b\|^2$, and at the $k$ step consider the scaled gradient matrix
\[X^k\nabla\phi(X^k)X^k,\]
where $X^k\succ 0$ is the $k$th iterate solution matrix. Let us generate the next iterate by
\[X^{k+1}=X^k-\alpha^kX^k\nabla\phi(X^k)X^k,\]
for some step-size $\alpha^k$ (again you need to develop a step-size rule to keep each iterate $X^k\succ 0$). What is the possible difference between the two iterative processes in (b) and (c), especially one of the eigenvalue of $X^k$ is already close to zero?

\item[(d)] (Computation Team Work) Apply this method for Sensor Network Localization problems in HW1 and HW2 varying
with $\mu=0$ to $\mu=10^{-4}$. (The solution quality could be very sensitive to the step-size rule and selection of $\mu$.)
\end{itemize}

\item[9.] (20pts Computation Team Work) 
All pieces of Computation Team Work stated above, and one more described below.

There is a simple nonlinear least squares approach for Sensor Network Localization:
\begin{equation}\label{snl-nls}
\begin{array}{lll}
&\min        & \sum_{(ij)\in N_x}\left(\|\x_i-\x_j\|^2 - d_{ij}^2\right)^2+\sum_{(kj)\in N_a} \left(\|\a_k-\x_j\|^2 - d_{kj}^2\right)^2
\end{array}
\end{equation}
which is an unconstrained nonlinear minimization problem.

\begin{itemize}
\item[(a)] Apply the Steepest Descent Method, starting with either the origin or a random solution as the initial solution for model (\ref{snl-nls}), to solve few selected SNL instances you created in HW1 and HW2. Does it work?

\item[(b)] Apply the Steepest Descent Method, starting from the SOCP or SDP solution (which may not have errors) as the initial solution for model (\ref{snl-nls}), to solve the same instances in (a). Does it work? Does the SOCP or SDP initial solution make a difference?
\end{itemize}

\end{enumerate}

\end{document}
