From 1b93b0de8686955792d2db7bd2859cff8c91cf0e Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Tue, 13 Mar 2012 22:51:11 +0100 Subject: [PATCH] Fixing up on problem 3 --- rapport.tex | 60 ++++++++++++++++++++++++++++------------------------- 1 file changed, 32 insertions(+), 28 deletions(-) diff --git a/rapport.tex b/rapport.tex index c3fc802..37fd0d4 100644 --- a/rapport.tex +++ b/rapport.tex @@ -60,10 +60,11 @@ Her må vi også skrive noe. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{a)} \subsubsection{SR-1} -SR-1 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 SR-1-metoden for løsning av testproblemet +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 \begin{equation} \label{eq:testproblem} \min_{x\in\mathbb{R}^n} \left\{ \frac{1}{2} x'Ax + b'x \right\}, @@ -75,25 +76,23 @@ Før første iterasjon setter vi $x$ til origo. Hessianen $B$ og inversen $H$ setter vi lik identitetsmatrisen, og gradienten $g$ er eksakt lik $-b$ fra likning \eqref{eq:testproblem}. -Vi starter hver iterasjon med følgende oppdatering av gjeldende posisjon -$x$: +Vi starter hver iterasjon med å oppdatere gjeldende posisjon $x$ \begin{lstlisting}[language=Matlab] p = -H*g; x = x + p; \end{lstlisting} -der $g$ er gradienten i gjeldende punkt. Vi ser at steget $p$ er et -newton-steg bare at vi bruker vår tilnærming $H$ i stedet for den ekte -inversen til hessian-matrisen. Vi fortsetter med å oppdatere gradienten -$g$. +Vi ser at steget $p$ er et newton-steg bare at vi bruker vår tilnærming +$H$ i stedet for den ekte inversen til hessian-matrisen. Vi fortsetter +med å oppdatere gradienten $g$ \begin{lstlisting}[language=Matlab] y = -g; g = A*x - b; y = g + y; \end{lstlisting} Siden denne koden er spesifikk til testproblemet har vi at gradienten i -punktet $x$ er lik $A\cdot x - b$. Variabelen $y$ vil etter dette være -lik endringen i gradienten $g_{k+1} - g_k$. Neste steg er å oppdatere -vår hessian-tilnærming $B$ og inversen $H$ +punktet $x$ er lik $Ax - b$. Variabelen $y$ vil etter dette være lik +endringen i gradienten $g_{k+1} - g_k$. Neste steg er å oppdatere vår +hessian-tilnærming $B$ og inversen $H$ \begin{lstlisting}[numbers=left,escapeinside={@}{@},language=Matlab] v = y - B*p; @\label{lst:hessoppdatering}@B = B + v*v'/(v'*p); @@ -117,7 +116,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 +SR-1-metoden starter vi med $x$ i origo og $g = -b$. Ved første iterasjon velger vi stegretningen $p = -g$, altså den mest synkende retningen. @@ -129,17 +128,16 @@ alfa = -(p'*g)./(p'*Ap); x = x + alfa*p; \end{lstlisting} der $alfa$ tilsvarer koefissienten $\alpha_i$ foran $p_i$ i -dekomponeringen av løsningsvektoren $x^* = \sum_i\alpha_i p_i$. Videre -oppdaterer vi gradienten og konstruerer neste vektor $p$ i basisen. +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 \begin{lstlisting}[language=Matlab] g = g + alfa*Ap; beta = (g'*Ap)./(p'*Ap); p = -g + beta*p; \end{lstlisting} -Ettersom $A$ er hessianen til testproblemet, og den er konstant, kan vi -oppdatere gradienten ved å legge til hessianen ganget med steget. Den -neste $p$-en lager vi ved en slags Gram-Schmidt-ortogonalisering. En -full utledning av metoden og konvergensegenskapene finnes i +En full utledning av metoden og konvergensegenskapene finnes i \citep*[s.~102]{nocedal2006numerical}. \subsection{b)} @@ -156,18 +154,19 @@ 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 -\ref{tab:indreprod} 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, og ut -over disse har det sneket seg inn indreprodukt av søke-vektorer som ikke -er så langt unna hverandre i itereringen. +\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 +over disse har det sneket seg inn noen indreprodukt av søkevektorer som +ikke er så langt unna hverandre i itereringen. \begin{table} - \caption{Alle $A$-indreproduktene mellom søkeretningene, med verdi + \caption{\sf Alle $A$-indreproduktene mellom søkeretningene, med verdi over $10^{-13}$} \label{tab:indreprod} \begin{center} \begin{tabular}{ c c } +\hline $\left<1, 1\right>$ & 272.4474186805212000 \\ $\left<1, 2\right>$ & 54.4486696594180870 \\ $\left<2, 2\right>$ & 25.3888003438768630 \\ @@ -184,6 +183,7 @@ $\left<10, 10\right>$ & 0.0000401791556377 \\ $\left<11, 11\right>$ & 0.0000000160341393 \\ $\left<11, 12\right>$ & 0.0000000160341393 \\ $\left<12, 12\right>$ & 0.0000000160341393 \\ +\hline \end{tabular} \end{center} \end{table} @@ -199,8 +199,12 @@ 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. -SR-1-metoden beholder ikke den positiv definitte egenskapen til -hessian-tilnærmingen. +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? \bibliographystyle{plain} \bibliography{refs} -- 2.47.3