so2a.tex

\documentclass{article}
% Include macros here
\input{macros}
\usepackage{fancyhdr}
%\include{macros}
\usepackage{pifont}

% Number of problem sheet
\newcounter{problemSheetNumber}
\setcounter{problemSheetNumber}{2}
\newcommand{\matlabprob}{\ding{100} \ }
\newcommand{\examprob}{\ding{80} \ }
%\setcounter{section}{\theproblemSheetNumber}  
%\renewcommand{\theparagraph}{(\thesection.\arabic{paragraph})}
\newcounter{problems}
\setcounter{problems}{0}
%\setlength{\parindent}{0cm}
\renewcommand{\problem}[1]{\paragraph{(\theproblemSheetNumber.\theproblems)}\addtocounter{problems}{1}\label{#1}}
\renewcommand{\solution}[1]{\paragraph{Solution (\theproblemSheetNumber.\theproblems)}\addtocounter{problems}{1}\label{#1}}

\pagestyle{fancy}
\lhead{MATH36061}
\chead{Convex Optimization}
\rhead{October 13, 2016}

\begin{document} 
\begin{center}
{\Large {\bf Solutions to Part A of Problem Sheet \theproblemSheetNumber}}
\end{center}

\solution{pr:4}
\begin{itemize}
 \item[(a)] We apply the bound inductively,
 \begin{equation*}
  \norm{\vct{x}_k-\vct{x}^*}\leq r\cdot \norm{\vct{x}_{k-1}-\vct{x}^*}\leq r \cdot (r \cdot  \norm{\vct{x}_{k-2}-\vct{x}^*})\leq \cdots \leq r^k\cdot \norm{\vct{x}_{0}-\vct{x}^*}.
 \end{equation*}
\item[(b)] Let $\e>0$. We are guaranteed to have an error bounded by $\e$ if $r^N\cdot M<\e$, by Part (a).
Taking logarithms of this inequality,
\begin{equation*}
 N\ln(r) + \ln(M)\leq \ln(\e).
\end{equation*}
Negating this, we get
\begin{equation*}
 -N\ln(r) - \ln(M)=N\ln(1/r) - \ln(M)\geq \ln(1/\e).
\end{equation*}
Dividing by $\ln(1/r)$ gives
\begin{equation*}
 N  \geq \frac{1}{\ln(1/r)} \left(\ln(1/\e)+\ln(M)\right) > \frac{r}{1-r}\left(\ln(M)+\ln(1/\e)\right),
\end{equation*}
where we used the inequality $\ln(1/r)<1/r-1 = (1-r)/r$. 
\item[(c)] For quadratic convergence, the bound is derived in exactly the same way as for linear convergence. To determine the number of steps, we start with the bound
\begin{equation*}
 C^N\cdot M^{2^N}\leq \e.
\end{equation*}
Taking logarithms and negating,
\begin{equation*}
 N\ln(1/C)-2^N\ln(M) \geq \ln(1/\e).
\end{equation*}
Taking logarithms again, we get
\begin{equation*}
 N\cdot \left(\frac{\log_2(N)}{N}+\log_2(\ln(1/c)-\ln(M))\right) \geq \log_2 (\ln(1/\e)),
\end{equation*}
so that if 
\begin{equation*}
 N> C'\cdot \ln\ln(1/\e)
\end{equation*}
for a constant $C'$, we are guaranteed an error below $\e$.

\end{itemize}

\solution{pr:5} We first compute the derivatives,
\begin{align*}
 f(x) &= \sqrt{x^2+1}\\
 f'(x) &= \frac{x}{\sqrt{x^2+1}}\\
 f''(x) &= \frac{1}{(x^2+1)^{3/2}}.
\end{align*}
Note that the second derivative is always positive.
Newton's method then has the following form
\begin{equation*}
 x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)} = x_k - x_k(1+x_k^2) = -x_k^3.
\end{equation*}
For $|x_0|<1$ this clearly converges to $0$, while for $x_0>1$ this diverges. For $|x_0|=1$ the sequence alternates between $1$ and $-1$.

\solution{pr:6} We first have to think about what it means to be a steepest descent direction with respect to a norm. If we look for a vector $\vct{p}$ with $\norm{\vct{p}}_\infty=1$ such that $\ip{\vct{p}}{\nabla f(\vct{x})}$ is minimal. 
Set $\vct{v}=\nabla f(\vct{x})$, to ease notation. Since $\norm{\vct{p}}_\infty = 1$ is the same as saying that $\max_{1\leq i\leq n} |p_i| = 1$, this amounts to solving the minimization problem
\begin{align*}
 \minimize& \ip{\vct{p}}{\vct{v}}\\
 \subjto & -1 \leq p_i \leq 1, \quad 1\leq i\leq n.
\end{align*}
Suppose that a minimizer is found and the minimum has the form
\begin{equation*}
 \sum_{i=1}^n p_i v_i.
\end{equation*}
If $p_iv_i>0$, then we can decrease the objective function further by changing the sign of $p_i$, and then even further by setting $p_i=-1$ if $\mathrm{sign} \ v_i=1$ and $p_i=1$ otherwise. Therefore, the optimizer has the form
\begin{equation*}
 p_i = -\mathrm{sign} \ \nabla f(\vct{x})_i
\end{equation*}
for $1\leq i\leq n$.
\end{document}