<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
<HTML>
<HEAD>
<TITLE>The Quasi-Newton Method.</TITLE>
<META NAME="description" CONTENT="The Quasi-Newton Method.">
<META NAME="keywords" CONTENT="vol1">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<LINK REL="STYLESHEET" HREF="vol1.css">
<LINK REL="next" HREF="node132.html">
<LINK REL="previous" HREF="node130.html">
<LINK REL="up" HREF="node128.html">
<LINK REL="next" HREF="node132.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html2201"
HREF="node132.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="icons.gif/next_motif.gif"></A>
<A NAME="tex2html2197"
HREF="node128.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="icons.gif/up_motif.gif"></A>
<A NAME="tex2html2191"
HREF="node130.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="icons.gif/previous_motif.gif"></A>
<A NAME="tex2html2199"
HREF="node1.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="icons.gif/contents_motif.gif"></A>
<A NAME="tex2html2200"
HREF="node216.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
SRC="icons.gif/index_motif.gif"></A>
<BR>
<B> Next:</B> <A NAME="tex2html2202"
HREF="node132.html">The Corrected Gauss-Newton No</A>
<B> Up:</B> <A NAME="tex2html2198"
HREF="node128.html">Outline of the Available</A>
<B> Previous:</B> <A NAME="tex2html2192"
HREF="node130.html">The Modified Gauss-Newton Method.</A>
<BR>
<BR>
<!--End of Navigation Panel-->
<H2><A NAME="SECTION001313000000000000000">
The Quasi-Newton Method.</A>
</H2>
This is identical to the modified Gauss-Newton method,
except in the way that the Hessian matrix is approximated.
<P>
This matrix is first initiated to zero.
At each iteration, a new estimation of the Hessian is
obtained by adding a rank one or two correction matrix to the last
estimate such that <I>H</I><SUP>(<I>k</I>+1)</SUP>, the estimate of the Hessian matrix at the
<I>k</I>+1<SUP><I>th</I></SUP> iteration, satisfies
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
(J(a^{(k+1)})^T~J(a^{(k+1)})~+~H^{(k+1)})~(x^{(k+1)}-x^{(k)})~=~J(a^{(k+1)})~r(a^{(k+1)})~-~J(a^{(k)})~r(a^{(k)})
\end{displaymath} -->
(<I>J</I>(<I>a</I><SUP>(<I>k</I>+1)</SUP>)<SUP><I>T</I></SUP> <I>J</I>(<I>a</I><SUP>(<I>k</I>+1)</SUP>) + <I>H</I><SUP>(<I>k</I>+1)</SUP>) (<I>x</I><SUP>(<I>k</I>+1)</SUP>-<I>x</I><SUP>(<I>k</I>)</SUP>) = <I>J</I>(<I>a</I><SUP>(<I>k</I>+1)</SUP>) <I>r</I>(<I>a</I><SUP>(<I>k</I>+1)</SUP>) - <I>J</I>(<I>a</I><SUP>(<I>k</I>)</SUP>) <I>r</I>(<I>a</I><SUP>(<I>k</I>)</SUP>)
</DIV>
<BR CLEAR="ALL">
<P></P>
The so-called BFGS updating formulas are applied in this algorithm
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
H^{(0)}~=~0~~~~~H^{(k+1)}~=~H^{(k)}~+~C^{(k)}
\end{displaymath} -->
<I>H</I><SUP>(0)</SUP> = 0 <I>H</I><SUP>(<I>k</I>+1)</SUP> = <I>H</I><SUP>(<I>k</I>)</SUP> + <I>C</I><SUP>(<I>k</I>)</SUP>
</DIV>
<BR CLEAR="ALL">
<P></P>
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
C^{(k)}={1 \over \alpha^{(k)}y^{(k)T}d^{(k)}}y^{(k)}y^{(k)T}-{1 \over
d^{(k)T}W^{(k)}d^{(k)}}W^{(k)}d^{(k)}d^{(k)T}W^{(k)}
\end{displaymath} -->
<IMG
WIDTH="610" HEIGHT="58"
SRC="img287.gif"
ALT="\begin{displaymath}C^{(k)}={1 \over \alpha^{(k)}y^{(k)T}d^{(k)}}y^{(k)}y^{(k)T}-{1 \over
d^{(k)T}W^{(k)}d^{(k)}}W^{(k)}d^{(k)}d^{(k)T}W^{(k)}\end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P>
where
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
W^{(k)}=J(a^{(k+1)})^T~J(a^{(k+1)})+H^{(k)}
\end{displaymath} -->
<I>W</I><SUP>(<I>k</I>)</SUP>=<I>J</I>(<I>a</I><SUP>(<I>k</I>+1)</SUP>)<SUP><I>T</I></SUP> <I>J</I>(<I>a</I><SUP>(<I>k</I>+1)</SUP>)+<I>H</I><SUP>(<I>k</I>)</SUP>
</DIV>
<BR CLEAR="ALL">
<P></P>
and
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
y^{(k)}=J(a^{(k+1)})r(a^{(k+1)})-J(a^{(k)})r(a^{(k)})~~,
\end{displaymath} -->
<I>y</I><SUP>(<I>k</I>)</SUP>=<I>J</I>(<I>a</I><SUP>(<I>k</I>+1)</SUP>)<I>r</I>(<I>a</I><SUP>(<I>k</I>+1)</SUP>)-<I>J</I>(<I>a</I><SUP>(<I>k</I>)</SUP>)<I>r</I>(<I>a</I><SUP>(<I>k</I>)</SUP>) ,
</DIV>
<BR CLEAR="ALL">
<P></P>
please see Gill, Murray and Pitfield (1972) for more details.
After some iterations and around the optimum, <I>H</I><SUP>(<I>k</I>)</SUP> converges to
the Hessian.
<P>
This method requires the knowledge of the derivatives and, as the
gradients are only computed once per iteration and consequently, the
Hessian is more roughly approximated than with the modified
Gauss-Newton method, this is better designed
for a great number of parameters i.e. <I>p</I> > 10.
<HR>
<!--Navigation Panel-->
<A NAME="tex2html2201"
HREF="node132.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="icons.gif/next_motif.gif"></A>
<A NAME="tex2html2197"
HREF="node128.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="icons.gif/up_motif.gif"></A>
<A NAME="tex2html2191"
HREF="node130.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="icons.gif/previous_motif.gif"></A>
<A NAME="tex2html2199"
HREF="node1.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="icons.gif/contents_motif.gif"></A>
<A NAME="tex2html2200"
HREF="node216.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
SRC="icons.gif/index_motif.gif"></A>
<BR>
<B> Next:</B> <A NAME="tex2html2202"
HREF="node132.html">The Corrected Gauss-Newton No</A>
<B> Up:</B> <A NAME="tex2html2198"
HREF="node128.html">Outline of the Available</A>
<B> Previous:</B> <A NAME="tex2html2192"
HREF="node130.html">The Modified Gauss-Newton Method.</A>
<!--End of Navigation Panel-->
<ADDRESS>
<I>Petra Nass</I>
<BR><I>1999-06-09</I>
</ADDRESS>
</BODY>
</HTML>
