From bff5ed7e36ecab5869b6e1319a91bce402fe9e2d Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Sun, 18 Mar 2012 19:35:09 +0100 Subject: [PATCH] Fixed up the last part of problem 3 --- rapport.tex | 72 ++++++++++++++++++++++++++++++++--------------------- 1 file changed, 43 insertions(+), 29 deletions(-) diff --git a/rapport.tex b/rapport.tex index 1c65252..64e688a 100644 --- a/rapport.tex +++ b/rapport.tex @@ -288,12 +288,11 @@ Kanskje vi får plass til et bittelite numerisk eksempel her???? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{a)} -\subsubsection{SR-1} -SR-1 er en kvasi-newton-metode der vi ved hver iterasjon oppdaterer og -forbedrer vårt estimat for hessianen med en rang-1-matrise. Vi kaller -dette estimatet $B$, og vi trenger også inversen $H = B^{-1}$. I denne -oppgaven ser vi på en enkel og noe naiv implementasjon av SR-1-metoden -for løsning av testproblemet +\subsubsection{SR1} +SR1 er en kvasi-newton-metode der vi ved hver iterasjon oppdaterer vårt +estimat for hessianen, $B$, med en rang-1-matrise. Ved hvert steg trenger vi +også inversen til $B$, som vi kaller $H$. Vi ser på en enkel og noe naiv +implementasjon av SR1-metoden for løsning av testproblemet \begin{equation} \label{eq:testproblem} \min_{x\in\mathbb{R}^n} \left\{ \frac{1}{2} x'Ax + b'x \right\}, @@ -332,7 +331,7 @@ Dette er en rang-1-oppdatering som er konstruert slik at den oppfyller sekant-likningen. Utledningen finnes i \citep*[s.~144]{nocedal2006numerical}. -SR-1-metoden kan bryte sammen hvis nevneren i oppdateringen på linje +SR1-metoden kan bryte sammen hvis nevneren i oppdateringen på linje \ref{lst:hessoppdatering} eller \ref{lst:invoppdatering} er lik null. Hvis dette er tilfellet kan man f.eks. droppe å oppdatere $B$ og $H$ i dette steget. Ved neste iterasjon står vi i et annet punkt, og vi får @@ -345,7 +344,7 @@ basisen konstruerer vi slik at vektorene er ortogonale med hensyn på $A$-indreproduktet $\left_A = u'Av$. Vi ser fortsatt på testproblemet \eqref{eq:testproblem} og som for -SR-1-metoden starter vi med $x$ i origo og $g = -b$. Ved første +SR1-metoden starter vi med $x$ i origo og $g = -b$. Ved første iterasjon velger vi stegretningen $p = -g$, altså den mest synkende retningen. @@ -358,31 +357,33 @@ x = x + alfa*p; \end{lstlisting} der $alfa$ tilsvarer koefissienten $\alpha_i$ foran $p_i$ i dekomponeringen av løsningsvektoren $x^* = x_k + \sum_i\alpha_i p_i$. -Videre oppdaterer vi gradienten ved å legge til hessianen $A$ ganget med -steget, og lager neste vektor $p$ i basisen ved en slags -Gram-Schmidt-ortogonalisering +Videre oppdaterer vi gradienten og konstruerer neste vektor $p$ i +basisen: \begin{lstlisting}[language=Matlab] g = g + alfa*Ap; beta = (g'*Ap)./(p'*Ap); p = -g + beta*p; \end{lstlisting} -En full utledning av metoden og konvergensegenskapene finnes i +Ettersom $A$ er hessianen til testprobleme, kan vi oppdatere gradienten +ved å legge til $A$ ganget med steget. Neste vektor $p$ i basisen lager +vi ved en slags Gram-Schmidt-ortogonalisering. En full utledning av +metoden og konvergensegenskapene finnes i \citep*[s.~102]{nocedal2006numerical}. \subsection{b)} -Hvis vi starter SR-1-metoden med $B=A$ og $H=A^{-1}$, tilsvarer det +Hvis vi starter SR1-metoden med $B=A$ og $H=A^{-1}$, tilsvarer det newtons metode, og den vil konvergere i ett steg. Hvis vi starter i punktet $x_0$ er det neste punktet gitt ved \begin{equation} \label{eq:sr1exact} x_1 = x_0 - Hg = x_0 - A^{-1}g = x_0 - A^{-1}\left(Ax_0-b\right) = -A^{-1}b = x^*, + A^{-1}b = x^*, \end{equation} som er den eksakte løsningen. \subsection{c)} Litt numerisk eksperimentering tyder på at mange, men ikke alle, -søke-retningene i SR-1-metoden er tilnærmet ortogonale. Tabell +søke-retningene i SR1-metoden er tilnærmet ortogonale. Tabell \ref{tab:indreprod} viser alle indreproduktene med verdi over $10^{-13}$ for et testproblem med kondisjons-tall $\kappa = 30.0$. Som forventet gir indreproduktet av søkevektorene med seg selv de største verdiene. Ut @@ -418,22 +419,35 @@ $\left<12, 12\right>$ & 0.0000000160341393 \\ \end{table} \subsection{d)} -Søkeretningene i SR-1-metoden kan i noen tilfeller ta deg lenger vekk +Søkeretningene i SR1-metoden kan i noen tilfeller ta deg lenger vekk fra den eksakte løsningen. Dette reflekterer unøyaktigheter i den tilnærmede hessianen, men er ikke så lett å oppdage hvis man ikke vet -den eksakte løsningen. Vi forsøkte forskjellige måter å unngå dette, -uten at noen av de så ut til å virke særlig bra. - -Som nevnt tidligere kan SR-1-metoden bryte sammen i oppdateringen av -hessianen søke-retningene, og vi implementerte den foreslåtte løsningen, -uten at det hjalp mot de dårlige søke-retningene. - -Videre tenkte vi at dette var noe som skjedde i punkter der -hessian-tilnærmingen ikke lenger var positiv definitt. Vi forsøkte -derfor å droppe oppdateringen hvis $B$ hadde én eller flere negative -egenverdier, uten at dette så ut til å hjelpe mye. - -Rang-1-oppdatering? +den eksakte løsningen. + +Som nevnt i \emph{a)}, kan SR1-metoden bryte sammen i oppdateringen av +hessianen søke-retningene. Vi implementerte den foreslåtte løsningen i +\citep*[s.~145]{nocedal2006numerical}, men observerte at dette ikke +bedret problemet. + +I motsetning til BFGS-metoden kan ikke SR1-metoden garantere en positiv +definitt Hessian-approksimasjon langs iterasjonene. Vi mistenkte at +feilen øker i steg der approksimasjonen ikke er positiv definitt lenger, +og undersøkte hvordan metoden oppfører seg hvis vi unnlater å oppdatere +$B_k$ når dette fører til at $B_{k+1}$ får en negativ egenverdi. Dette +viste seg imidlertid å ikke være noen god løsning. Det vil riktig nok +bli lavere eller ingen økning i feilen i forhold til den vanlige metoden +i stegene der oppdatering gir negativ egenverdi, men metoden kan likevel +ta steg som gir større feil i andre tilfeller. Vi kunne også merke at +metoden alltid konvergerer saktere enn før, og i noen tilfeller +konvergerer den ikke i det hele tatt. + +I stedet for å la være å oppdatere $B$ når vi har negative egenverdier, +prøvde vi så å gjøre en rank-2-oppdatering hentet fra BFGS-metoden +beskrevet i \citep*[s.~140]{nocedal2006numerical}. Her ble resultatene +enda dårligere, og metoden konvergerte kun av og til, i tillegg til at +vi fremdeles fikk steg med større feil enn tidligere. Ved å undersøke +saken nærmere ser vi at vi får større feil i steg der produktet $v'p < +0$, men fant ingen metode for å forhindre dette. \bibliographystyle{plain} \bibliography{refs} -- 2.47.3