\chapter{Numeric Tools for Unconstrained NLPs}\label{C:Numeric_Methods}
\section{The Steepest Descent Method}\label{S:SteepestDescent}
\setcounter{progress_ck_counter}{0}

\noi For many unconstrained NLPs, critical points of the objective function
are difficult to compute using algebraic means. In this chapter, we investigate
iterative numeric methods for overcoming this obstacle.

\newpar
During the past several years, numeric methods have evolved and improved dramatically. We
will not attempt to describe all developments in this field but will instead focus on three elementary tools: the \emph{Steepest Descent Method}\index{Steepest Descent Method},
\emph{Newton's Method}\index{Newton's Method}, and the
\emph{Levenberg-Marquardt Algorithm}\index{Levenberg-Marquardt Algorithm}.

\subsection{Method Derivation}

\noi Throughout this chapter, we assume $S \subseteq \R^n$ is open, $f:S \to \R$, and that our goal
is to solve the unconstrained NLP,
\begin{equation}\label{SteepestDescentStandardNLP}
\mbox{minimize } f(\vecx), \qquad \vecx \in S.
\end{equation}
For a differentiable function, the most elementary method of estimating
a solution to (\ref{SteepestDescentStandardNLP}) is the \emph{Steepest Descent
Method}. As the term ``descent'' suggests, it approximates the minimum of a function $f$. However, when applied to $-f$, it approximates
a maximum as well.

\newpar
Assume $\vecx_0$ belongs
to $S$, and recall from Exercise 3 of Section \ref{S:diff_Gradient} that if $\vecd$ is a unit vector in
$\R^n$, then the directional derivative\index{directional derivative} of $f$ at
$\vecx_0$ in the direction of $\vecd$ is given by
\begin{align*}
f'_{\vecd}\left(\vecx_0\right) &=\lim_{h \to 0^+} \frac{f\left(\vecx_0+h\vecd\right)-f(\vecx_0)}{h} \\
&= \nabla f(\vecx_0)^t \vecd.
\end{align*}
The Cauchy-Schwartz Inequality\index{Cauchy-Schwartz Inequality} dictates that
\begin{align*}
\left| \nabla f(\vecx_0)^t \vecd \right| &\leq \|\nabla f(\vecx_0) \| \| \vecd \| \\
&=  \|\nabla f(\vecx_0) \|,
\end{align*}
with equality in the absolute value possible if and only if
$\ds \vecd = \pm \frac{\nabla f(\vecx_0)}{\|\nabla f(\vecx_0)\|}$.
\newline
(See Appendix \ref{C:Linear_Algebra_Appendix}.)
Consequently $\ds f'_{\vecd}\left(\vecx_0\right)$ is a minimum when
$\vecd$ is chosen to have direction exactly opposite that of $\ds \nabla f(\vecx_0)$.
We summarize this fact by saying $\ds -\nabla f(\vecx_0)$ is the \emph{optimal descent direction}\index{optimal descent direction}
of $f$ at $x_0$.

\newpar
The Steepest Descent Method begins with an initial value $\vecx_0$ and a corresponding
optimal descent direction, $\ds -\nabla f(\vecx_0)$. If we define
\begin{equation}\label{E:SteepestDescent_steepest_descent_one_variable_function}
\phi(t)=f\left(\vecx_0-t\nabla f(\vecx_0)\right),
\end{equation}
then $\phi$ is a decreasing function for $t$ sufficiently small and positive.

\newpar
For example, suppose that $\ds A=\begin{bmatrix} 2 & 1 \\ 1 & 3 \end{bmatrix}$,
$\ds \vecb=\begin{bmatrix} 1 \\ -4 \end{bmatrix}$, and $c=6$, and that
\newline $\ds f:\R^2 \to \R$
is the positive definite quadratic function given by
\begin{align}\label{E:SteepestDescentBasicPositiveDefiniteQuadratic}
f(\vecx)&= \frac{1}{2}\vecx^t A \vecx +\vecb^t\vecx +c \\
&= x_1^2+x_1x_2+\frac{3}{2}x_2^2+x_1-4x_2+6. \notag
\end{align}
If $\ds \vecx_0=\begin{bmatrix} 1 \\ -1 \end{bmatrix}$, straightforward calculations show that $f(\vecx_0)=12.5$ and
\newline
$\ds \nabla f(\vecx_0)=\begin{bmatrix} 2 \\ -6 \end{bmatrix}$.
In this case, (\ref{E:SteepestDescent_steepest_descent_one_variable_function}) yields
$\phi(t)= 46t^2-40t+12.5$.

\newpar
Figures \ref{Fi:SteepestDescent_steepest_descent_example}
and \ref{Fi:SteepestDescent_steepest_descent_example2} provide two depictions of
the function $\phi$. Figure \ref{Fi:SteepestDescent_steepest_descent_example}
illustrates the graph of $f$,
along with an embedded arc consisting of the ordered triples
\begin{equation}\label{E:SteepestDescent_steepest_descent_curve_on_surface}
\left\{ \left. \begin{bmatrix} \vecx_0-t\nabla f(\vecx_0) \\ \phi(t) \end{bmatrix}
\quad \right| \quad 0 \leq t \leq 1 \right\}.
\end{equation}


\begin{figure}[h]
\centering
\psfrag{x1_axis_label}[Bc][Bc]{$x_1$}
\psfrag{x2_axis_label}[Bc][Bc]{$x_2$}
\psfrag{f_axis_label}[Bc][Bc]{$f$}
\psfrag{vecx_0}[Bc][Bc]{$\ds \vecx_0=\begin{bmatrix} 1 \\ -1 \end{bmatrix}$}
\includegraphics[width=.8\linewidth]{images/f08x01x01.eps}
%\scalebox{.6}{\includegraphics{c:/images/OR/nonlinear/SteepestDescent_steepest_descent_example_phi.eps} }
\caption{Plot of function $f$, together with curve of triples defined by
(\ref{E:SteepestDescent_steepest_descent_curve_on_surface}).
}
\label{Fi:SteepestDescent_steepest_descent_example}
\end{figure}


\newpage
\begin{figure}[h]
\centering
\psfrag{t_axis_label}[Bc][Bc]{$t$}
\psfrag{phi_axis_label}[Bc][Bc]{$\phi$}
\includegraphics[width=.7\linewidth]{images/f08x01x02.eps}
\caption{A plot of $\phi(t)=f\left(\vecx_0-t\nabla f(\vecx_0)\right)$.}
\label{Fi:SteepestDescent_steepest_descent_example2}
\end{figure}


\newpar
Figure \ref{Fi:SteepestDescent_steepest_descent_example2} depicts $\phi$ itself plotted as a function of $t$. The strict global minimum of $\phi$ is given by
$\ds t_0=\frac{10}{23}\approx .435$. Using $t_0$, we define
\begin{equation}
 \vecx_1=\vecx_0-t_0\nabla f(\vecx_0)=\begin{bmatrix} 3/23 \\ 37/23 \end{bmatrix}
 \approx \begin{bmatrix} .1304 \\ 1.609 \end{bmatrix}.
\end{equation}

\noi
Note that $f(\vecx_1)=\phi(t_0)<\phi(0)=f(\vecx_0)$. In fact, direct computation shows that $f(\vecx_1)=3.804$.

\newpar
Thus, through a process of minimizing a single-variable function, we have obtained from $\vecx_0$ a new value
$\vecx_1$, whose displacement from $\vecx_0$
is in the direction of steepest descent of $f$ at $\vecx_0$,
and whose corresponding objective function value is significantly less.
That this process can be repeated using $\vecx_1$ as the new initial value
leads to the creation of the algorithm known as the \emph{Steepest Descent Method}, sometimes
also referred to as
Cauchy's Method, in honor of its inventor. We now summarize the steps of the algorithm.

\newpar
{\underbar{The Steepest Descent Method}}\index{Steepest Descent Method!summary of steps} \newline
To obtain an approximate solution of NLP (\ref{SteepestDescentStandardNLP}) under
the assumption $f$ is differentiable on $S$:
\be
\item From the initial value $\vecx_0$ in $S$, compute the optimal descent direction, $\ds \vecd=-\nabla f(\vecx_0)$.
\item Since $S$ is open, for sufficiently small $t$, $\ds \vecx_0+t\vecd$ belongs to $S$.
Calculate the smallest positive local minimum, $t_0$, of the function $\phi(t)=f\left(\vecx_0+t\vecd\right)$.
\item Using $t_0$ from (2), define $\vecx_1=\vecx_0+t_0\vecd$. Then proceed to (1) and replace $\vecx_0$ with
$\vecx_1$. Compute the optimal descent direction at $\vecx_1$, a new single-variable function $\phi$, and so on.
\ee
Repeated application of steps (1)-(3) generates a sequence of values
\begin{equation*} \vecx_0,\vecx_1,\vecx_2,\ldots
\end{equation*} which, under ideal circumstances,
converges to the global minimum of $f$ on $S$. The decision
to terminate the algorithm generally follows one of two approaches, each of which depends upon
a specified tolerance, $\epsilon$. The first involves applying the algorithm until successive approximations, $\vecx_k$ and $\vecx_{k-1}$, satisfy $\ds \| \vecx_k-\vecx_{k-1} \| <\epsilon$. The second approach is to terminate the algorithm when $\ds \left\|  \nabla f\left(\vecx_k\right)\right\| <\epsilon$. Use of this latter inequality stems
from the fact
that at the global minimum, $\vecx_{\bigstar}$, of a differentiable function $f$, $\ds \nabla f\left(\vecx_{\bigstar}\right)=\zerovec$. Unless stated otherwise, we will always use
the second of these two approaches for deciding when to terminate the algorithm.

\newpar
Table \ref{Ta:SteepestDescent_steepest_descent_example} lists results of the Steepest Descent Method applied
to the function
\newline
$\ds f(x_1,x_2)=x_1^2+x_1x_2+\frac{3}{2}x_2^2+x_1-4x_2+6$ using an initial value
$\ds \vecx_0=\begin{bmatrix} 1 \\ -1 \end{bmatrix}$ and a tolerance of $\epsilon=.01$. We elect to terminate the algorithm
when
$\ds \left\|  \nabla f\left(\vecx_k\right) \right\| <\epsilon$, which occurs after the ninth iteration. The ending
value, to four significant digits, is given by $\ds \vecx_9 = \begin{bmatrix} -1.397 \\ 1.796 \end{bmatrix}$. This is very close
to the exact global minimum of $f$,
$\ds \vecx_{\bigstar} = \begin{bmatrix} -\frac{7}{5} \\ \frac{9}{5} \end{bmatrix}$.

\begin{table}[h]
\caption{Results of Steepest Descent Method applied to \newline
$ f(x_1,x_2)=x_1^2+x_1x_2+\frac{3}{2}x_2^2+x_1-4x_2+6$}
\label{Ta:SteepestDescent_steepest_descent_example}
\begin{tabular}{|c|c|c|}
\hline
$k$ & $\vecx_k^t$ &      $\ds \left\|  \nabla f\left(\vecx_k\right)\right\|$ \\ \hline
0 &   $[1,-1]$  &     $2\sqrt{10}$ \\ \hline
                      1 & $[0.1304, 1.609]$ & 3.025\\  \hline
                      2 & $[-0.9326, 1.255]$ & 1.231\\  \hline
                     3 & $[-1.102, 1.763]$ & 0.5895\\  \hline
                    4 & $[-1.309, 1.694]$ & 0.2394\\  \hline
                    5 & $[-1.342, 1.793]$ & 0.1151\\  \hline
                   6 & $[-1.382, 1.779]$ & 0.04743\\  \hline
                  7 & $[-1.389, 1.799]$ & 0.02247\\  \hline
                              8 & $[0.004646, 0.00001]$ & 0.02077\\  \hline
                 9 & $[-1.397, 1.796]$ & 0.009220\\  \hline

\end{tabular}
\end{table}

\subsection{A Maple Implementation of the Steepest Descent Method}\index{Steepest Descent Method!Maple implementation}

\noi Maple's basic programming structures are well suited for implementing
the Steepest Descent Method. The worksheet \textbf{Steepest Descent Method.mw} demonstrates one means for doing so, creating a procedure, \mf{SteepestDescentMethod}, which approximates the minimum of a function of two variables, $f$. The procedure call takes the form
\begin{equation*}
\mbox{\mf{SteepestDescentMethod(\ma{function,initial,N,tolerance})},}
\end{equation*}
where \ma{function} is a
differentiable function to be minimized, \ma{initial} is the initial value, $\ds \vecx_0$, (written as a
list), \ma{N} is the maximum number of iterations, and \ma{tolerance} is the specified tolerance. The algorithm terminates when either the number of iterations is reached or the gradient norm is less than the desired tolerance. The returned value is the last iterate. Intermediate
iterates are stored in a list of points, \mf{iterates}, a global variable accessible outside of the procedure.

\newpar The following worksheet constructs the procedure and approximates the minimum of
$\ds f(x_1,x_2)= x_1^2+x_1x_2+\frac{3}{2}x_2^2+x_1-4x_2+6$ using an initial value of
$\ds \vecx_0=\begin{bmatrix} 1 \\ -1 \end{bmatrix}$, $N=10$, and a tolerance of
$.01$. (Note: Because this worksheet uses the \mf{LinearAlgebra} package version of the \mf{Norm} command, it is important to load the \mf{LinearAlgebra} package after loading \mf{VectorCalculus}.)

\begin{maplelist}
\item \mf{restart: with(VectorCalculus):with(LinearAlgebra):}
\item \mf{SteepestDescentMethod 
\newline := proc (function, initial, N, tolerance)
\newline local x,f,Delf,d,j,epsilon,phi,t0; global iterates:
\newline \# Create local and global variables. \newline
x:=array(0 .. N):
\newline \# Define array of iterates. \newline
f:=unapply(function, [x1, x2]):
\newline \# Create function. \newline
Delf:=unapply(Gradient(function, [x1, x2]), [x1, x2]): \newline
\# Create corresponding gradient function. \newline
x[0]:=evalf(initial):
\newline \# Set initial array value.\newline
epsilon := 10:
\newline \# Set initial epsilon to a large value. \newline
j:=0: while (tolerance <= epsilon and j<=N-1) do \newline
\# Create loop structure to perform algorithm. \newline
d:=-Delf(op(x[j])): \# Compute optimal descent direction. \newline
phi:=unapply(simplify(f(x[j][1]+t*d[1],x[j][2]+t*d[2])),t): \newline
t0:=subs(fsolve(D(phi)(t) = 0, \{t = 0..infinity\}, 
\newline maxsols = 1),t): \newline
\# Determine minimum of phi. \newline
x[j+1]:=[x[j][1]+t0*d[1],x[j][2]+t0*d[2]]: \newline
\# Use minimum of phi to construct next iterate. \newline
epsilon:=evalf(Norm(Delf(x[j+1][1],x[j+1][2]),Euclidean)):\newline
\# Update epsilon using gradient.\newline
j:=j+1: \newline
\# Increase loop index. \newline
end do:\newline
iterates:=[seq(x[i],i=0..j)]:RETURN(x[j]):end:
\newline
\# Construct iterates and return last array value.}
\item \mf{f:=(x1,x2)->x1\^{}2+x1*x2+3/2*x2\^{}2+x1-4*x2+6; \newline \# Enter function.}
\mo{f:=(x_1,x_2) \rightarrow x_1^2+x_1x_2+\frac{3}{2}x_2^2+x_1-4x_2+6}
\item \mf{SteepestDescentMethod(f(x1, x2), [1, -1], 10, .01);\newline
\# Procedure call using initial value [1,-1], bound of 10
\newline  iterations, and tolerance, .01.}
\mo{ [-1.396540715, 1.795964168]}
\item \mf{iterates;
\newline \# Print iterates.}
\begin{align*}
 &    [[1, -1], [.1304347826, 1.608695652], [-.9323671494), 1.254428341],\\
&    [-1.101799342), 1.762724918], [-1.308883132), 1.693696988], \\
& [-1.341896490), 1.792737062], [-1.382246149), 1.779287175], \\
& [-1.388678705), 1.798584838], [-1.396540715), 1.795964168]]
\end{align*}
\end{maplelist}

\noi
Note that the list, \mf{iterates}, can then be plotted using the \mf{pointplot} command.


\subsection{A Sufficient Condition for Convergence}\index{Steepest Descent Method!convergence conditions}

\noi Of course, the preceding worksheet illustrates an ideal situation, in which
the sequence of iterates obtained using the Steepest Descent Method
converges to a global minimum. The following Waypoint illustrates how this is not always the case in general.

\begin{progress_ck}
Apply the Steepest Descent Method to the function, $f:\R^2 \to \R$, defined
by $\ds f(x_1,x_2)=x_1^4+x_2^4-4x_1x_2+1$. Use a tolerance of $\epsilon=.1$,
and investigate the outcome using three different initial values,
$\ds \vecx_0=\begin{bmatrix} 1 \\ 2 \end{bmatrix}$, $\ds \vecx_0=\begin{bmatrix} -1 \\ -2 \end{bmatrix}$,
and $\ds \vecx_0=\begin{bmatrix} -1 \\ 1 \end{bmatrix}$. Compare your results
with those obtained using algebraic methods from Section \ref{S:optimality_sufficient_SOC}.
\end{progress_ck}

\newpar
The preceding example, and others like it, demonstrate how the Steepest Descent Method can generate a sequence,
$\ds \left\{\vecx_k \right\}$, that converges to a critical point of $f$ that
is a local, but not global, minimum or that is a saddle point. Thus, additional conditions must
be met in order to ensure that the sequence of iterates converges in the first place, and, if it does, whether it yields a local or global minimum.

\newpar
General conditions on $f$ under which a sequence
of iterates leads to critical points are provided by
a special case of a theorem due to Zoutendijk\index{Zoutendijk, G.}. We shall omit the proof of this result, which can
be found in more advanced texts \cite{Nocedal},\cite{Zoutendijk}\index{Steepest Descent Method!convergence conditions}.

% See C:\Users\fishbacp\Documents\TEXTBOOK\General Articles\Articles Post Feb 2009
% Zoutendijk_Wolfe_Good_pp5-8_2_10_2009

\begin{theorem}\label{Th:SteepestDescent_Zoutendijk}
Assume $\ds S \subseteq \R^n$ is nonempty and open, and
suppose
\newline
$\ds f:S \to \R$ is differentiable on $S$. Choose $\vecx_0$ belonging to $S$, and define the \emph{lower level set}\index{lower level set},
\begin{equation*}
S_0=\left\{\vecx \mid \vecx \in S \mbox{ and } f(\vecx) \leq f(\vecx_0) \right\}.
\end{equation*}
Suppose that $\nabla f$ is \emph{Lipschitz continuous}\index{Lipschitz continuous} in an open set $\mathcal{O}$ containing $S_0$, meaning there exists
a constant $K$ (referred to as the \emph{Lipschitz constant})\index{Lipschitz constant} such that
\begin{equation*}
\left\| \nabla f(\vecx_1)-\nabla f(\vecx_2) \right\| \leq K\|\vecx_1-\vecx_2\| \mbox{ for all } \vecx_1, \vecx_2 \in
\mathcal{O}.
\end{equation*}
If there exists $m \in \R$ such that $m \leq f(\vecx)$ \mbox{ for all } $\vecx \in S$,
then the sequence $\left\{\vecx_k \right\}\subseteq S_0$ generated using the Steepest Descent Method satisfies
\begin{equation}\label{E:SteepestDescent_ZoutendijksResult}
\lim_{k \to \infty} \left\| \nabla f(\vecx_k) \right\| = 0.
\end{equation}
\end{theorem}

\newpar
This theorem does not state that the sequence $\ds \left\{\vecx_k \right\}$ converges to the global minimum of $f$
on $S$. In fact, it does not even state that this sequence converges at all. However, if even some subsequence of this sequence has a limit point, $\vecx_{\bigstar}$, in $S$, then the Lipschitz continuity
and (\ref{E:SteepestDescent_ZoutendijksResult}) guarantee $\nabla f (\vecx_{\bigstar})=\zerovec$. (We note
that if $S_0$ is closed and bounded, then such a subsequence must exist due to a fundamental
analysis result known as the \emph{Bolzano-Weierstrass Theorem}\index{Bolzano-Weierstrass Theorem}. The limit of the subsequence must belong
to $S_0$ or its boundary.) Because $\ds f(\vecx_k)$ is decreasing in $k$, $\vecx_{\bigstar}$ must
therefore correspond to either a local minimum or
a saddle point.

\newpar
Verifying that $\nabla f$ is Lipschitz continuous by definition can be tedious and should be avoided when possible. For several classes of functions, however, Lipschitz continuity follows from certain
\emph{matrix norm}\index{matrix norm} inequalities. (See Appendix \ref{C:Linear_Algebra_Appendix}.) Three straightforward
cases are the following:
\be
\item If $f: \R^n \to \R$ is the general quadratic function defined by
\newline
$\ds f(\vecx)= \frac{1}{2}\vecx^t A \vecx +\vecb^t\vecx +c$, where $A$ is an $n$ by $n$ matrix,
$\vecb$ belongs to $\R^n$, $c$ is real, then $\ds \nabla f(\vecx)=A\vecx+\vecb$ so that
\begin{align*}
\left\| \nabla f(\vecx_1)-\nabla f(\vecx_2) \right\|&=\|A\left(\vecx_1-\vecx_2\right)\| \\
&\leq \|A\| \|\vecx_1-\vecx_2\|,
\end{align*}
Here, $\ds \|A\|$ denotes the \emph{spectral norm}\index{spectral norm} of $A$, defined as the square root of the largest eigenvalue of $AA^t$.

\item If $f$ is as defined as above and $A$ is also symmetric,
eigenvalues of $AA^t$ are the eigenvalues of $A^2$, and the spectral norm
 reduces to $\ds \|A\|=\rho(A)$, where $\rho(A)$ is the \emph{spectral radius}\index{spectral radius}, or maximum of the absolute values of the eigenvalues of $A$.
\item More generally, if $f$ all second-order partial derivatives of $f$
exist and are continuous on $\mathcal{O}$, then $\nabla f$ is Lipschitz continuous on $\mathcal{O}$
provided $\ds \|H_f(\vecx) \|= \rho\left(H_f(\vecx)\right)$
is bounded by a constant independent of $\vecx$ in $\mathcal{O}$.
We will omit the proof of this result, which follows from a generalization
to $\R^n$ of the Mean Value Theorem\index{Mean Value Theorem} \cite{Bazaraa}.
\ee

\newpar
The unconstrained \emph{ConPro Manufacturing Company} NLP\index{ConPro problem!unconstrained},
\begin{multline}\label{E:SteepestDescent_CMC}
 \mbox{minimize} f(x_1,x_2 )= -1400 x_1^{\frac{1}{2}}x_2^{\frac{1}{3}} + 350x_1 +200x_2, \\
	\quad \mbox{ where }\vecx=\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \in S=\R_+^2=\left\{(x_1,x_2) \mid x_1, x_2 >0 \right\},
\end{multline}
illustrates the usefulness of Theorem \ref{Th:SteepestDescent_Zoutendijk}. (Hereafter, we will
state the \CM objective in terms of minimization.) We first note that $f$ is bounded below on $S$. Now suppose we let $\ds \vecx_0=\begin{bmatrix} 10 \\ 10 \end{bmatrix}$, which corresponds to the lower level set
 $\ds S_0=\left\{\vecx \mid f(\vecx)\leq f(10,10)\right\}$ shown in Figure
\ref{Fi:SteepestDescent_conpro_initial_value_level_set}.


\begin{figure}[h]
\centering
\psfrag{x1_axis_label}[Bc][Bc]{$x_1$}
\psfrag{x2_axis_label}[Bc][Bc]{$x_2$}
\psfrag{open}[Bc][Bc]{$\mathcal{O}$}
\scalebox{.6}{\includegraphics{images/f08x01x03.eps} }
\caption{The lower level set $\ds S_0=\left\{\vecx \mid f(\vecx)\leq f(10,10)\right\}$.}
\label{Fi:SteepestDescent_conpro_initial_value_level_set}
\end{figure}

\newpar
Clearly we can draw an bounded, open set $\mathcal{O}$ in $S$ that contains $S_0$ and has the property that for any $\ds \vecx = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$ in $\mathcal{O}$,
$\delta < x_1,x_2 \leq M$ for some $\delta>0$ and finite $M$. The set contained within the dashed lines in Figure \ref{Fi:SteepestDescent_conpro_initial_value_level_set} is one such example.

\newpar
The eigenvalues of the Hessian of $f$ are given by
\begin{equation}\label{E:SteepestDescent_conpro_hessian_eigenvalues}
\lambda= \frac{175 \left(9x_1x_2^2+8x_1^3\pm \sqrt{81x_2^4x_1^2+64x_1^6}\right) }
{9x_1^{\frac{5}{2}}x_2^{\frac{5}{3}} },
\end{equation}
which are in fact both positive. The larger of these two eigenvalues is obtained by using
the positive root in (\ref{E:SteepestDescent_conpro_hessian_eigenvalues}). This fraction is bounded
by a constant
independent of $\vecx$ in $\mathcal{O}$, due to the fact that its numerator is bounded there
and its denominator is bounded away from zero. Specifically,
\begin{align*}
|\lambda| &= \frac{175 \left(9x_1x_2^2+8x_1^3+\sqrt{81x_2^4x_1^2+64x_1^6}\right) }
{9x_1^{\frac{5}{2}}x_2^{\frac{5}{3}} } \\
&\leq  \frac{175 \left(9MM^2+8M^3+\sqrt{81M^4M^2+64M^6}\right) }
{9\delta^{\frac{5}{2}}\delta^{\frac{5}{3}} } \\
&= \frac{175 \left(17M^3+\sqrt{145M^6}\right) }
{9\delta^{\frac{25}{6}}}.
\end{align*}

\noi Thus, $\nabla f$ is Lipschitz continuous
on $\mathcal{O}$, and we conclude that the hypothesis of
Theorem \ref{Th:SteepestDescent_Zoutendijk} is satisfied. The first eight Steepest Descent Method
iterates, starting from $\ds \vecx_0=\begin{bmatrix} 10 \\ 10 \end{bmatrix}$, are given in Table
\ref{Ta:SteepestDescent_CMC_SteepestDescent}. In the fourth column,
$\ds \left\|  \vecx_k-\vecx_{\bigstar} \right\|$ measures the distance from $\vecx_k$
to the true minimum of $f$, which we computed in Section \ref{S:optimality_sufficient_SOC} and
is given by
\begin{equation*}
\vecx_{\bigstar}=\left(\frac{784}{9}, \frac{2744}{27} \right) \approx (87.11, 101.63).
\end{equation*}

\begin{table}[h]
\caption{Results of the Steepest Descent Method applied to
the \CM objective function, $f$, from (\ref{E:SteepestDescent_CMC})  }
\label{Ta:SteepestDescent_CMC_SteepestDescent}
\begin{tabular}{|c|c|c|c|}
\hline
$k$ & $\vecx_k^t$ &  $\left\| \nabla f(\vecx_k) \right\|$ & $\ds \left\|  \vecx_k-\vecx_{\bigstar}\right\|$ \\
\hline
0 & $[10,10]$ & $173.245$ & $119.759$ \\ \hline
1 & $[91.680, 85.907]$ & $40.277$ & $16.373$ \\ \hline
2 & $[82.493, 95.792]$ & $3.6065$ & $7.444$ \\ \hline
3 & $[87.236, 100.200]$ & $2.788$ & $1.435$ \\ \hline
4 & $[86.558, 100.930]$ & $.420$ & $.892$ \\ \hline
5 & $[87.125, 101.455]$ & $.334$ & $.175$ \\ \hline
6 & $[87.043,101.543]$ & $.0152$ & $.110$ \\ \hline
7 & $[87.113,101.608]$ & $.0411$ & $.022$ \\ \hline
8 & $[87.103,101.619]$ & $.006$ & $.014$ \\ \hline
\end{tabular}
\end{table}


\subsection{The Rate of Convergence}

\noi While Theorem \ref{Th:SteepestDescent_Zoutendijk} is a statement about
convergence of the Steepest Descent Method, it does not convey information regarding rates of convergence. Theorem \ref{Th:SteepestDescent_ConvergenceRate} serves this purpose.\index{Steepest Descent Method!rate of convergence}

\begin{theorem}\label{Th:SteepestDescent_ConvergenceRate}
Suppose that $\ds S \subseteq \R^n$ is open, that $\ds f:S \to \R$
has continuous second-order partial derivatives, and that the Steepest Descent Method starting from $\vecx_0$ generates a sequence of iterates
$\ds \left\{\vecx_k\right\}$ converging to the local minimum of $f$, which
we label $\vecx_{\bigstar}$.
If $H_f(\vecx_{\bigstar})$ is positive definite, then the objective values satisfy
\begin{equation}\label{E:SteepestDescent_ConvergenceRate_Inequality1}
 f(\vecx_{k+1})-f(\vecx_{\bigstar})
 \leq \left( \frac{\lambda_n-\lambda_1}{\lambda_n+\lambda_1}\right)^2 \left(f(\vecx_{k})-f(\vecx_{\bigstar})\right),
 \quad k=0,1,\ldots,
\end{equation}
where $\lambda_n$ and $\lambda_1$ denote the largest and smallest eigenvalues of
$H_f(\vecx_{\bigstar})$, respectively.

\newpar
Furthermore, if $f$ is a positive definite quadratic function, meaning it takes
the form
\begin{equation}\label{E:SteepestDescent_ConvergenceRate_quadratic_mapping}
f(\vecx)=\frac{1}{2}\vecx^tA\vecx+\vecb^t\vecx+c,
\end{equation}
where $c$ is real, $\vecb$ belongs to $\R^n$, and $A$ is an $n$-by-$n$ positive definite matrix, then the Steepest Descent Method starting from any $\vecx_0$ in $\R^n$ generates a sequence of inputs,
$\ds \left\{\vecx_k\right\}$, that converges to the global minimum of $f$, $\vecx_{\bigstar}$, at
a rate governed by
\begin{equation}\label{E:SteepestDescentConvergenceRateInequality2}
\left\|\vecx_k-\vecx_{\bigstar} \right\|^2
\leq \frac{2}{\lambda_1} \left( \frac{\lambda_n-\lambda_1}{\lambda_n+\lambda_1}\right)^{2k} \left(f(\vecx_0)-f(\vecx_{\bigstar})\right), \quad k=0,1,\ldots.
\end{equation}
\end{theorem}

\newpar
Inequality (\ref{E:SteepestDescent_ConvergenceRate_Inequality1}) is sometimes rephrased
by stating that the sequence of objective values $\ds \left\{f(\vecx_k)\right\}$ converges
to $\ds f(\vecx_{\bigstar})$ at a \emph{linear rate}\index{Steepest Descent Method!linear rate of convergence}. Use of this term stems from the
fact that the ratio, $\ds \frac{ f(\vecx_{k+1})-f(\vecx_{\bigstar})}{f(\vecx_k)-f(\vecx_{\bigstar})}$, is bounded.

\newpar
The proof of Theorem \ref{Th:SteepestDescent_ConvergenceRate} can be found in more advanced texts \cite{Bazaraa}. Instead of proving it, we examine its validity
in the context of the positive definite quadratic function
from (\ref{E:SteepestDescentBasicPositiveDefiniteQuadratic}). Thus,
$\ds f(\vecx)= \frac{1}{2}\vecx^t A \vecx +\vecb^t\vecx +c$,
where $\ds A=\begin{bmatrix} 2 & 1 \\ 1 & 3 \end{bmatrix}$,
$\ds \vecb=\begin{bmatrix} 1 \\ -4 \end{bmatrix}$, and $c=6$.

\newpar
Assume that
$\ds \vecx_0=\begin{bmatrix} 1 \\ -1 \end{bmatrix}$, in which case
$f(\vecx_0)=12.5$. Recall that the global minimum is given by $\ds \vecx_{\bigstar} = \begin{bmatrix} -\frac{7}{5} \\ \frac{9}{5} \end{bmatrix}$ and that $f(\vecx_{\bigstar})=1.7$.

\newpar
The Hessian, $H_f(\vecx)$ is simply $A$, whose eigenvalues are given by
$\ds \lambda_1=\frac{5-\sqrt{5}}{2}$ and $\ds \lambda_1=\frac{5+\sqrt{5}}{2}$. Thus
\begin{equation*}
 \left( \frac{\lambda_2-\lambda_1}{\lambda_2+\lambda_1}\right)^2 = \frac{1}{5}.
\end{equation*}
Using the first four Steepest Descent Method iterates from Table \ref{Ta:SteepestDescent_steepest_descent_example}, we obtain the values shown in Table
\ref{Ta:SteepestDescent_ConvergenceRateExample1}. In each row, the ratio of the second
entry to the third is always less than or equal to $\frac{1}{5}$, thereby
demonstrating the validity of inequality
(\ref{E:SteepestDescent_ConvergenceRate_Inequality1}) for these first few iterates.

\begin{table}[h]
\caption{Objective output differences}
\label{Ta:SteepestDescent_ConvergenceRateExample1}
\begin{tabular}{|c|c|c|}
\hline
$k$ & $\ds f(\vecx_{k+1})-f(\vecx_{\bigstar})$ & $\ds f(\vecx_k)-f(\vecx_{\bigstar})$ \\ \hline
0 & 2.1043 & 10.8000  \\ \hline
1 & .4100 & 2.1043   \\ \hline
2 & .0799 & .4100   \\ \hline
3 & .0156 & .0799   \\ \hline
4 & .0030 & .0156   \\ \hline
\end{tabular}
\end{table}

\newpar
Table \ref{Ta:SteepestDescent_ConvergenceRateExample2} focuses on the iterates
themselves and not their corresponding objective values. It illustrates the validity of inequality (\ref{E:SteepestDescentConvergenceRateInequality2}).

\begin{table}[h]
\caption{Error between $\vecx_k$ and $\vecx_{\bigstar}$}
\label{Ta:SteepestDescent_ConvergenceRateExample2}
\begin{tabular}{|c|c|c|}
\hline
$k$ & $\left\|\vecx_k-\vecx_{\bigstar} \right\|^2$ &
$\frac{2}{\lambda_1} \left( \frac{\lambda_n-\lambda_1}{\lambda_n+\lambda_1}\right)^{2k} \left(f(\vecx_0)-f(\vecx_{\bigstar})\right)$ \\ \hline
0 & 13.6000 & 15.6210 \\ \hline
1 & 2.3788 & 3.1260 \\ \hline
2 & .5163 & .6251 \\ \hline
3 & .0903 & .1250 \\ \hline
4 & .0196 & .0250 \\ \hline
\end{tabular}
\end{table}

\newpar
Perhaps the most important conclusion we can draw from
 Theorem \ref{Th:SteepestDescent_ConvergenceRate} is that eigenvalues
 play a crucial role in determining convergence rate. In particular, the greater the difference between the largest and smallest eigenvalues of $H_f(\vecx_{\bigstar})$, the closer that
$\ds \left( \frac{\lambda_n-\lambda_1}{\lambda_n+\lambda_1}\right)$ becomes to one. This in turn
slows down the rates of convergence. Exercises 1 and 2 provide further examples illustrating this phenomenon.

\section*{Exercises Section \protect\ref{S:SteepestDescent}}

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_SteepestDescentMethod}
\endinput

