From d17839bd5886c5c79861a77bc49fbdc790e043e4 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Bj=C3=B8rn=20Rustad?= <rustadbjornen@gmail.com>
Date: Mon, 3 Oct 2011 13:56:10 +0200
Subject: [PATCH] 8===D

---
 rapport.tex | 46 ++++++++++++++++++++++++++++------------------
 1 file changed, 28 insertions(+), 18 deletions(-)

diff --git a/rapport.tex b/rapport.tex
index b7ab5af..30222c1 100644
--- a/rapport.tex
+++ b/rapport.tex
@@ -46,18 +46,28 @@
 %                                %
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \abstract{
-ABSTRACTABSTBSSTRACTABSTRACTABSTRACT
+  In this project we explore how one can use the method of steepest descent and
+  Newtons method to approximate the solution to a minimization problem
+  numerically. The method of steepest descent converges more rapidly when
+  supplied with an optimal step size, but in most cases Newtons method converges
+  in even fewer iterations.
 }
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %                                %
 %        RESULTATER              %
 %                                %
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Resultater}
-This project explores how one can approximate the solution to a certain type of
-minimization problems. The function considered takes in a symmetric positive
-definite matrix, and two vectors. For this purpose we used the following
-randomly generated data:
+\section{Report}
+The function analyzed in this project was
+\begin{equation}
+  \label{eq:func_g}
+  g(\mathbf{x}) := -\mathbf{b}^{T}\mathbf{x} +
+  \frac{1}{2}\mathbf{x}^{T}H\mathbf{x} +
+  \frac{1}{12}\mathbf{x}^{T}C(\mathbf{x})\mathbf{x},
+\end{equation}
+which takes as input one symmetric definite matrix $H$, one vector
+$\mathbf{c}$ with positive elements, and one non-zero vector $\mathbf{b}$. For
+this purpose we used the following randomly generated data:
 \begin{equation}
   H = 
   \begin{bmatrix}
@@ -86,13 +96,6 @@ in the uniform distribution over $[-3, 3]$, while the numbers on the diagonal
 are square roots of positive numbers from the same distribution. The matrix $H
 = U^{T}U$ is then symmetric positive definite.
 
-The function analyzed in this project was
-\begin{equation}
-  \label{eq:func_g}
-  g(\mathbf{x}) := -\mathbf{b}^{T}\mathbf{x} +
-  \frac{1}{2}\mathbf{x}^{T}H\mathbf{x} +
-  \frac{1}{12}\mathbf{x}^{T}C(\mathbf{x})\mathbf{x}.
-\end{equation}
 From equation \eqref{eq:func_g} we get
 \begin{eqnarray}
   \label{eq:grad_g}
@@ -107,7 +110,6 @@ implemented in the Python code below.
 
 Consider the Hessian $\nabla^{2}g(\mathbf{x})$, and any vector $\mathbf{v} \in
 \mathbb{R}^{n}_{*}$.  Then we have
-
 \begin{eqnarray}
   \mathbf{v}^{T}(\nabla^{2}g(\mathbf{x}))\mathbf{v} &=& \mathbf{v}^{T}(H+C(\mathbf{x}))\mathbf{v} \nonumber \\
   &=& \mathbf{v}^{T}H\mathbf{v}+\mathbf{v}^{T}C(\mathbf{x})\mathbf{v}.
@@ -128,7 +130,7 @@ that the Hessian, $\nabla^{2}g(\mathbf{x})$, is positive definite.
   \label{fig:fn_resid}
 \end{figure}
 
-\begin{figure}[htb]
+\begin{figure}[b]
   \centering
   \includegraphics[width=0.9\textwidth]{surface}
   \caption{\sf Surface plot of function with points showing iteration of steepest
@@ -136,6 +138,12 @@ that the Hessian, $\nabla^{2}g(\mathbf{x})$, is positive definite.
   \label{fig:surface}
 \end{figure}
 
+The steepest descent method works by always taking a step in the direction
+opposite the gradient in the point considered (i.e. the direction of the
+steepest descent). The step size can be set to a constant or chosen in a more
+optimal way. In the case of a constant step size, the method is equivalent to
+the Euler method.
+
 Consider the equation
 \begin{equation}
   \label{eq:forward}
@@ -153,7 +161,9 @@ vector equation, we get the following iteration:
 where $t_{n+1} = t_n + \alpha$. Looking at this result, we see that it is
 equivalent to the steepest descent iteration with constant step size $\alpha$. 
 
-To find the optimal step length, $\alpha^*$, we solve the equation
+To find the optimal step length, $\alpha^*$, we walk along the line of steepest
+descent until we get to the lowest point. This point can be found analytically
+by solving the following equation for $\alpha$:
 \begin{eqnarray}
   \label{eq:poly}
   \frac{\partial}{\partial
@@ -162,7 +172,7 @@ To find the optimal step length, $\alpha^*$, we solve the equation
   &\Downarrow& \nonumber \\
   A\alpha^3 + B\alpha^2 + C\alpha + D &=& 0,
 \end{eqnarray}
-for $\alpha$. Where $A$, $B$, $C$, and $D$ are given by
+Where $A$, $B$, $C$, and $D$ are given by
 \begin{eqnarray}
   A &=& \frac{1}{3}\mathbf{u}^TC(\mathbf{u})\mathbf{u} \nonumber \\
   B &=& \mathbf{x}^TC(\mathbf{u}) \mathbf{u} \nonumber \\
@@ -208,7 +218,7 @@ The Newton method was also implemented to solve $\nabla g\left(\mathbf{x}^*\righ
 We see from table \ref{tab:time} that newtons method uses the least time to
 solve the problem, even though figure \ref{fig:fn_resid} shows that the
 combination method results in fewer iterations. This comes from the fact that
-computing the optimal step size requires solving a qubic equation and is
+computing the optimal step size requires solving a cubic equation and is
 computationally expensive.
 
 \end{document}
-- 
2.47.3