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

# ***
# # <font color="grey">Problem Sheet 2 Part A - Solutions</font>
# ***
# $\newcommand{\vct}[1]{\mathbf{#1}}$
# $\newcommand{\mtx}[1]{\mathbf{#1}}$
# $\newcommand{\e}{\varepsilon}$
# $\newcommand{\norm}[1]{\|#1\|}$
# $\newcommand{\minimize}{\text{minimize}\quad}$
# $\newcommand{\maximize}{\text{maximize}\quad}$
# $\newcommand{\subjto}{\quad\text{subject to}\quad}$
# $\newcommand{\R}{\mathbb{R}}$
# $\newcommand{\trans}{T}$
# $\newcommand{\ip}[2]{\langle {#1}, {#2} \rangle}$
# $\newcommand{\zerovct}{\vct{0}}$
# $\newcommand{\diff}[1]{\mathrm{d}{#1}}$

# ### Solution to Problem 2.1

# (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*}
# 
# (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$. 
# 
# (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$.

# ### Solution to Problem 2.2

# 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 to Problem 2.3

# 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}^d 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$.
# 

# In[ ]: