%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                     %
%              Scientific Word   Wrap/Unwrap  Version 2.5             %
%                                                                     %
% If you are separating the files in this message by hand, you will   %
% need to identify the file type and place it in the appropriate      %
% directory.  The possible types are: Document, DocAssoc, Other,      %
% Macro, Style, Graphic, PastedPict, and PlotPict. Extract files      %
% tagged as Document, DocAssoc, or Other into your TeX source file    %
% directory.  Macro files go into your TeX macros directory. Style    %
% files are used by Scientific Word and do not need to be extracted.  %
% Graphic, PastedPict, and PlotPict files should be placed in a       %
% graphics directory.                                                 %
%                                                                     %
% Graphic files need to be converted from the text format (this is    %
% done for e-mail compatability) to the original 8-bit binary format. %
%                                                                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                     %
% Files included:                                                     %
%                                                                     %
% "/document/chap7.tex", Document, 11382, 3/22/1999, 5:22:10, ""      %
%                                                                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%% Start /document/chap7.tex %%%%%%%%%%%%%%%%%%%%%%

%% This document created by Scientific Notebook (R) Version 3.0


\documentclass[12pt,thmsa]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{sw20jart}

%TCIDATA{TCIstyle=article/art4.lat,jart,sw20jart}

%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{Created=Mon Aug 19 14:52:24 1996}
%TCIDATA{LastRevised=Sun Mar 21 21:22:09 1999}
%TCIDATA{CSTFile=Lab Report.cst}
%TCIDATA{PageSetup=72,72,72,72,0}
%TCIDATA{MapleDefs=
%$f \left( x\right) =x^{5}-4x^{3}+2x^{2}-10x+12 $
%$r=\frac{3}{2}-\frac{1}{2}\sqrt{5} $
%$m \left( x\right) =e^{x^{2}}-x^{3}-0.5\sin 3x $
%$g \left( x\right) =x-\frac{2.0xe^{x^{2}}-3.0x^{2}-1.5\cos 3.0x}{2.0e^{x^{2}}+4.0x^{2}e^{x^{2}}-6.0x+4.5\sin 3.0x}\allowbreak  $
%}

%TCIDATA{AllPages=
%F=36,\PARA{038<p type="texpara" tag="Body Text" >\hfill \thepage}
%}


\input{tcilatex}
\begin{document}


\vspace{1pt}``One Dimensional Search methods''

Chong/Zak Chapter 7

Author: Robert Beezer

History:

1999/03/15\qquad First version.

\vspace{1pt}

\vspace{1pt}

Setting: \ $f:R\rightarrow R$ \ is unimodal (i.e. has just one local
minimizer) on the interval \ $\lbrack a_{0},b_{0}\rbrack $. \ Draw it and
find it.

\vspace{1pt}

\subsubsection{Golden Section Search}

\vspace{1pt}

\begin{enumerate}
\item  Move from \ $\lbrack a_{0},b_{0}\rbrack $ \ to \ $\lbrack
a_{1},b_{1}\rbrack $. \ Compare \ $f(a_{1})$ \ to \ $f(b_{1})$ \ to see
which is smaller. \ Note that just one evaluation is not enough to see where
the answer lies.\bigskip 

\item  Desire \ $a_{1}-a_{0}=b_{0}-b_{1}=\rho (b_{0}-a_{0})$, \ \ $\rho <%
\frac{1}{2}$ \ \ so intervals are symmetric. (Sketch)

Careful argument: \ 

\begin{enumerate}
\item  Suppose \ $f(a_{1})<f(b_{1})$. \ This implies that \ $x^{\ast }\in
\lbrack a_{0},b_{1}\rbrack $.

\item  Now call \ $a_{1}$ \ by the name $b_{2}$. \ We know its value, so we
might as well use it. \ Where will \ $a_{2}$ \ go?

\item  The scenario on the reduced interval is 
\[
b_{1}-b_{2}=\rho (b_{1}-a_{0})
\]
\ \ Which becomes 
\[
b_{1}-a_{1}=\rho (b_{1}-a_{0})
\]
\[
(b_{0}-a_{0})-(a_{1}-a_{0})-(b_{0}-b_{1})=\rho ((b_{0}-a_{0})-(b_{0}-b_{1}))
\]
\[
(b_{0}-a_{0})-\rho (b_{0}-a_{0})-\rho (b_{0}-a_{0})=\rho ((b_{0}-a_{0})-\rho
(b_{0}-a_{0}))
\]

Cancel \ $(b_{0}-a_{0})$ \ from both sides to obtain

\[
1-2\rho =\rho (1-\rho ) 
\]
\[
\rho ^{2}-3\rho +1=0 
\]
whose solutions are $\rho =\frac{3}{2}+\frac{1}{2}\sqrt{5}=\allowbreak
2.\,\allowbreak 618\,033\,989$ $\ \ \ $and $\ \ \ \rho =\frac{3}{2}-\frac{1}{%
2}\sqrt{5}=\allowbreak .\,\allowbreak 381\,966\,011\,\allowbreak 3$. \ Use
the latter.\bigskip
\end{enumerate}

\item  \ This is the ``Golden Ratio'', \ a root of \ 
\[
\frac{\rho }{1-\rho }=\frac{1-\rho }{1} 
\]

``The ratio of the shorter side of a rectangle to the longer equals the
ratio of the longer to the sum of the two''

\[
\frac{x}{y}=\frac{y}{x+y} 
\]

(Letting $x=ty$ \ \ yields the same thing.)

Use this repeatedly and the size of the uncertain interval \ $\lbrack
a_{n},b_{n}\rbrack $ \ will be \ $(1-\rho )^{n}(b_{0}-a_{0})$ .\bigskip

\item  Example: \ \ $f(x)=x^{5}-4x^{3}+2x^{2}-10x+12$ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \FRAME{itbpF}{3in}{2.0003in}{0.8856in}{}{}{}{\special{language
"Scientific Word";type "MAPLEPLOT";width 3in;height 2.0003in;depth
0.8856in;display "USEDEF";function
\TEXUX{$x^{5}-4x^{3}+2x^{2}-10x+12$};linecolor "black";linestyle
1;linethickness 1;pointstyle "point";xmin "-5";xmax "5";xviewmin
"0.8";xviewmax "2.2";yviewmin "-10";yviewmax "5";viewset"XY";rangeset"X";phi
45;theta 45;plottype 4;numpoints 49;axesstyle "normal";xis
\TEXUX{x};var1name \TEXUX{$x$};}}

$r=\frac{3}{2}-\frac{1}{2}\sqrt{5}$

\begin{enumerate}
\item  Begin with \ $\lbrack 0,3\rbrack $

\item  $a_{1}=0+r(3-0)=\allowbreak 1.\,\allowbreak 145\,89$,\ \ $%
f(0+r(3-0))=\allowbreak -.\,\allowbreak 875\,709\,092\,\allowbreak 4$

$b_{1}=0+(1-r)(3-0)=\allowbreak 1.\,\allowbreak 854\,101\,966$, \ \ $%
f(0+(1-r)(3-0))=\allowbreak -3.\,\allowbreak 249\,676\,699$

New interval is now \ $\lbrack a_{1},b_{0}\rbrack =\allowbreak \left[
1.\,\allowbreak 1459\,,3\right] $

\item  $a_{2}=b_{1}=0+(1-r)(3-0)=\allowbreak 1.\,\allowbreak 854\,101\,966$,
\ \ $f(0+(1-r)(3-0))=\allowbreak -3.\,\allowbreak 249\,676\,699$ \ (Recycled)

$b_{2}=1.\,\allowbreak 1459+(1-r)(3-1.\,\allowbreak 1459)=\allowbreak
2.\,\allowbreak 291\,796\,819$, $\ \ f(1.\,\allowbreak
1459+(1-r)(3-1.\,\allowbreak 1459))=\allowbreak 14.\,\allowbreak
661\,375\,07 $

New interval is now \ $\lbrack a_{1},b_{2}\rbrack =\lbrack \allowbreak
1.\,\allowbreak 145\,9,\allowbreak 2.\,\allowbreak 2918\rbrack $

\item  $a_{3}=\allowbreak 1.\,\allowbreak 145\,9+r(\allowbreak
2.\,\allowbreak 2918-1.\,\allowbreak 145\,9)=\allowbreak 1.\,\allowbreak
583\,594\,852$, \ \ $f(\allowbreak 1.\,\allowbreak 145\,9+r(\allowbreak
2.\,\allowbreak 2918-1.\,\allowbreak 145\,9))=\allowbreak -4.\,\allowbreak
746\,479\,497$

$b_{3}=a_{2}=0+(1-r)(3-0)=\allowbreak 1.\,\allowbreak 854\,101\,966$, \ \ $%
f(0+(1-r)(3-0))=\allowbreak -3.\,\allowbreak 249\,676\,699$ \ (Recycled)

New interval is now $\lbrack a_{1},b_{3}\rbrack =\lbrack 1.\,\allowbreak
145\,9,1.\,\allowbreak 854\,1\rbrack $

\item  $a_{4}=\allowbreak 1.\,\allowbreak 145\,9+r(\allowbreak
1.\,\allowbreak 854\,1-1.\,\allowbreak 145\,9)=\allowbreak 1.\,\allowbreak
416\,408\,329$, \ \ $f(\allowbreak 1.\,\allowbreak 145\,9+r(\allowbreak
1.\,\allowbreak 854\,1-1.\,\allowbreak 145\,9))=\allowbreak -3.\,\allowbreak
817\,236\,831$

$b_{4}=a_{3}=\allowbreak 1.\,\allowbreak 145\,9+r(\allowbreak
2.\,\allowbreak 2918-1.\,\allowbreak 145\,9)=\allowbreak 1.\,\allowbreak
583\,594\,852$, \ \ $f(\allowbreak 1.\,\allowbreak 145\,9+r(\allowbreak
2.\,\allowbreak 2918-1.\,\allowbreak 145\,9))=\allowbreak -4.\,\allowbreak
746\,479\,497$ \ \ (recycled)

New interval is now $\lbrack a_{4},b_{3}\rbrack =\lbrack 1.\,\allowbreak
416\,4,\allowbreak 1.\,\allowbreak 8541\rbrack $

\item  Keep iterating.....

\item  Calculus gives us root of the derivative near \ $x=1.6313$.

\item  To obtain an accuracy of within $\ 0.1$ \ would require$\ \ \frac{\ln
(0.1/3)}{\ln (1-r)}=\allowbreak 7.\,\allowbreak 067\,983\,795$ \ iterations.
\end{enumerate}
\end{enumerate}

\vspace{1pt}

\subsubsection{Fibonnaci Search}

\vspace{1pt}

\begin{enumerate}
\item  \ Vary the value of \ $\rho $ \ across the iterations. \ \ An
interesting optimization problem (minimize the size of the resultant
interval at the end of the iterations) leads to the Fibonnaci numbers ($%
F_{0}=1,F_{2}=1$, etc) for the ratios. \ With \ $N$ \ iterations use \ 
\[
\rho _{k}=1-\frac{F_{N-k+1}}{F_{N-k+2}} 
\]

See the book for more details.
\end{enumerate}

\vspace{1pt}

\subsubsection{Newton's Method}

\vspace{1pt}

\begin{enumerate}
\item  Again, a function of one variable. \ Assume it has two derivatives
(note that search methods above did not require even continuity, but just
unimodality!) \ This version of Newton's method is different than the one
for finding zeros of a function (which we should see soon), though we can
view it as a direct application of root-finding applied to the \emph{first
derivative} of $f(x).\bigskip $

\item  For \ $f(x)$ \ at a point \ \ $x^{(k)}$ \ build the best quadratic
approximation 
\[
q(x)=f(x^{(k)})+f^{\prime }(x^{(k)})(x-x^{(k)})+\frac{1}{2}f^{\prime \prime
}(x^{(k)})(x-x^{(k)})^{2} 
\]

which has a minimum when FONC 
\[
0=q^{\prime }(x)=f^{\prime }(x^{(k)})+f^{\prime \prime }(x^{(k)})(x-x^{(k)}) 
\]

with a solution of 
\[
x^{(k+1)}=x^{(k)}-\frac{f^{\prime }(x^{(k)})}{f^{\prime \prime }(x^{(k)})} 
\]
\bigskip

\item  Example: \ Minimize \ $m(x)=\exp (x^{2})-x^{3}-0.5\sin (3x)$ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \FRAME{itbpF}{3in}{1.7573in}{0.5907in}{}{}{}{%
\special{language "Scientific Word";type "MAPLEPLOT";width 3in;height
1.7573in;depth 0.5907in;display "USEDEF";function \TEXUX{$\exp
(x^{2})-x^{3}-0.5\sin (3x)$};linecolor "black";linestyle 1;linethickness
1;pointstyle "point";xmin "-5";xmax "5";xviewmin "-1";xviewmax "1";yviewmin
"0";yviewmax "5";viewset"XY";rangeset"X";phi 45;theta 45;plottype
4;numpoints 49;axesstyle "normal";xis \TEXUX{x};var1name \TEXUX{$x$};}}

\begin{enumerate}
\item  Graph suggests a local minimum near $x^{(0)}=0.4$.

\item  $g(x)=x-\frac{m^{\prime }(x)}{m^{\prime \prime }(x)}=\allowbreak x-%
\frac{2.0xe^{x^{2}}-3.0x^{2}-1.\,\allowbreak 5\cos 3.0x}{%
2.0e^{x^{2}}+4.0x^{2}e^{x^{2}}-6.0x+4.\,\allowbreak 5\sin 3.0x}\allowbreak $
\ \ \ \ will give iterates....

\item  $x^{(1)}=g(0.4)=\allowbreak .\,\allowbreak 417\,318\,826\,\allowbreak
4$

\item  $x^{(2)}=g(\allowbreak .\,\allowbreak 417\,318\,826\,\allowbreak
4)=\allowbreak .\,\allowbreak 417\,166\,883\,\allowbreak 7$

\item  $x^{(3)}=g(\allowbreak .\,\allowbreak 417\,166\,883\,\allowbreak
7)=\allowbreak .\,\allowbreak 417\,166\,872\,\allowbreak 3$

\item  $x^{(4)}=g(\allowbreak .\,\allowbreak 417\,166\,872\,\allowbreak
3)=\allowbreak .\,\allowbreak 417\,166\,872\,\allowbreak 3$

\item  As a check, plug in $x^{(4)}$ \ to the derivative: \ \ $m^{\prime
}(\allowbreak .\,\allowbreak 417\,166\,872\,\allowbreak 3)=\allowbreak
-2.\,\allowbreak 115\,309\,351\times 10^{-10}$

\item  Using the derivative, and finding its root numerically in Mathematica
gives the minimizer at \ $x=0.4171668803117407$.
\end{enumerate}
\end{enumerate}

\vspace{1pt}

\subsubsection{Secant Method}

\vspace{1pt}

\begin{enumerate}
\item  Similar to Newton's method above, but presume we do not have a second
derivative. \ The solution is to replace it by a secant line approximation
using values of the first derivative. \ This might make more sense in the
root-finding scenario, where we would assume we lacked a first derivative
and would approximate it by secant line information using values of the
function itself.\bigskip

\item  Here's the replacement. \ First Newton's method: 
\[
x^{(k+1)}=x^{(k)}-\frac{f^{\prime }(x^{(k)})}{f^{\prime \prime }(x^{(k)})} 
\]

and we substitute the difference quotient approximation: 
\[
f^{\prime \prime }(x^{(k)})\approx \frac{f^{\prime }(x^{(k)})-f^{\prime
}(x^{(k-1)})}{x^{(k)}-x^{(k-1)}} 
\]

to obtain 
\[
x^{(k+1)}=x^{(k)}-f^{\prime }(x^{(k)})\frac{x^{(k)}-x^{(k-1)}}{f^{\prime
}(x^{(k)})-f^{\prime }(x^{(k-1)})} 
\]

\item  Note that to run this iteration, we need two starting values an \ $%
x^{(-1)}$ \ and \ $x^{(0)}$.
\end{enumerate}

\vspace{1pt}

\subsubsection{Putting it all together: Looking both forward and backward}

\vspace{1pt}

These methods are applied to functions of one variable, like problems from
first-year calculus. \ However, for functions of several variables they will
be worthwhile once we decide on a feasible \emph{direction} within the
domain to follow, then we can concentrate on a ``slice'' of the function
that looks like a function of one variable \ (the \ $\alpha $ \ of
expressions like \ $x+$\ $\alpha d$). \ The problem is then to determine the
best direction in which to do the line search.

\vspace{1pt}

\vspace{1pt}

Problems: \ Zak/Chong \ Chapter 7, Page 98 \ \ 2, \ 7b

\vspace{1pt}

\end{document}

%%%%%%%%%%%%%%%%%%%%%%% End /document/chap7.tex %%%%%%%%%%%%%%%%%%%%%%%