% This is a LaTex file.
% Homework for the course "Scientific Computing",
% Spring semester, 1996, Jonathan Goodman.
% A latex format for making homework assignments.
\documentstyle[12pt]{article}
% The page format, somewhat wider and taller page than in art12.sty.
\topmargin -0.1in \headsep 0in \textheight 8.9in \footskip 0.6in
\oddsidemargin 0in \evensidemargin 0in \textwidth 6.5in
\begin{document}
% Definitions of commonly used symbols.
% The title and header.
\noindent
{\scriptsize Scientific Computing, Spring 1996} \hfill
\begin{center}
\large
Assignment 5.
\normalsize
\end{center}
\noindent
Given March 4, due March 18.
\vspace{.3in}
% The questions!
\noindent
{\bf Objective:} To practice optimization methods and robust numerical software.
\vspace{.5cm}
This assignment asks you to write good, robust numerical software for
finding the minimum of a function of 2 variables. In the real
world, you would minimize a function of $n$ variables. This assignment
keeps some of the flavor of the more general problem but leaves out
some (for this purpose) irrelevant details. The code has several
components. In your writeup, hand in and explain tests of each
component separately. Among these components are the line search
program and the linear algebra program. In particular, the routines
should have built in safeguards and you should hand in examples of
the safeguards being activated and tested.
\begin{description}
\item[(1)]
{\bf Line Search:}
Write a program that attempts to minimize a function of a
single variable, $\phi(t)$. The algorithm should have two phases.
The first phase searches for some positive $t$ that yields an
objective function value less than $\phi(0)$. It can do this by
computing $\phi(t)$ and $\phi(2t)$ for some $t>0$. If
$\phi(t) < \phi(2t) $ and $\phi(t) < \phi(0)$, then
$t$ is the end of phase one. Start with $t = 1$. If
$\phi(2t) < \phi(t)$, then replace $t$ by $2t$ and repeat.
If $\phi(t) > \phi(0)$, replace $t$ by $t/2$ and repeat.
If these $t$ adjustments do not yield a reasonable $t$ value
after a reasonable time, give up and report failure.
The second phase is a Newton search for the minimum. This should
have a safeguard against negative $\phi^{\prime\prime}$ and a safeguard
against wild iterates (e.g., ones that violate the criteria of
phase 1). Try your algorithm on the function
$\phi(t) = 1/(1+t^2)$ with various initial guesses.
Large initial guesses present a greater challenge.
Observe the action of phase one and the eventual quadratic convergence
under phase two.
\item[(2)]
Write a program that performs unsafeguarded Newton's method for a function
of two variables. To do this, you will need a subroutine that solves
the linear system $Ax=b$ when $A$ is a $2 \times 2$ symmetric matrix.
When $x$ is close to an optimum, $A$ should be positive definite. Therefore,
the Choleski factorization of $A$ may be appropriate. Try your program
on the examples
\begin{equation}
f(x,y) = \phi\left(x^2 + a(y-b\sin(cx))^2 \right) \;\; .
\end{equation}
The easy cases are $a=2$, $b=c=0$. Try initial guesses close and far
from the solution ($x=y=0$). With a good initial guess you should see
quadratic convergence to the minimizer. With a poor initial guess
you should see wild behavior.
\item[(3)]
Add two safeguards to the program from step (2). Do a phase one line
search to make sure the step is not crazy and check that the Newton
step is a descent direction. Use this to minimize the objective function
(1) with $a=30$, $b=1$, and $c=6$, starting from initial guess
$(x_1,x_2) = (3,1)$. Make a contour plot of the objective function
showing the minimization iterates.
\end{description}
\end{document}