<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\input{preamble}


\begin{document}
\pagenumbering{gobble}

\title{3 - 3 - OPTIMERING I}
%fiskpkt i flere dim
%stive likn
%lineÃ¦r programmering

\maketitle
De aller fleste land har sitt hÃ¸yeste punkt pÃ¥ toppen av et fjell. 
Men noen land, 
for eksempel Monaco og Finland, 
har sitt hÃ¸yeste punkt et eller annet sted pÃ¥ landegrensen,
i en oppoverbakke mot en fjelltopp som ligger i nabolandet.
Kina og Nepal har pÃ¥ en mÃ¥te begge deler, 
siden de deler Mount Everest. 
I de to foregÃ¥ende ukene har vi lÃ¦rt om funksjoner fra 
$\mathbb{R}^n$
til 
$\mathbb{R}$
og om funksjoner fra 
$\mathbb{R}$
til 
$\mathbb{R}^n$. 
NÃ¥ skal vi kombinere dem for Ã¥ analysere slike problemstillinger. 

\begin{minipage}{115mm}
La oss fÃ¸rst introdusere litt notasjon. 
Et omrÃ¥de $\Omega \in \mathbb R^2$ formet 
ved Ã¥ ta snittet av fÃ¸rste kvadrant med en ellipse med halvakser 4 og 3, 
se figur. 
Hvis en kurve $\Gamma$ er randen til et omrÃ¥de $\Omega$, 
skriver vi
\begin{align*}
\partial \Omega = \Gamma.
\end{align*}
\end{minipage}
\begin{minipage}{80mm}
\includegraphics[scale=.18]{../figurer/arkitektonisk-perle-1}
\end{minipage}


Du gÃ¥r en skitur langs $\Gamma$
pÃ¥ et fjell $h: \Omega \to \mathbb R$. 
gitt ved
\begin{align*}
	h(x,y) = - x_1^2 - x_1x_2 - 2x_2^2 + 4 x_1 + 6x_2 + 8.
\end{align*}
I forrige semester lÃ¦rte vi Ã¥ finne toppen av fjellet. 
SpÃ¸rsmÃ¥lene vi skal svare pÃ¥ denne uken, 
er 

\begin{itemize}
	\item[\textbf{1:}] 
	Hvordan vet vi at et kritisk punkt er toppen av et fjell og ikke bunnen av en dal?
	\item[\textbf{2:}] 
	Hva er det hÃ¸yeste og laveste punktet pÃ¥ skituren?
\end{itemize}

La oss begynne med litt repetisjon.

\begin{oppgave}{1}
	Finn toppen av fjellet gitt av $h$.
\end{oppgave}

\begin{center}
	\includegraphics[scale=.28]{../figurer/L1020235}
\end{center}

\clearpage


Det finnes fire andrederiverte. 
Hvis du partiellderiverer to ganger med hensyn pÃ¥ Ã©n variabel, 
fÃ¥r du de \textbf{rene} annenordens partiellderiverte:
\[
\frac{\partial f^2}{\partial x_1^2}
\quad
\text{og }
\quad
\frac{\partial f^2}{\partial x_1^2},
\]
Deriverer du med hensyn pÃ¥ Ã©n variabel og sÃ¥ med hensyn pÃ¥ den andre, 
fÃ¥r du de \textbf{blandede}:
\[
\frac{\partial f^2}{\partial x_1\partial x_2}
\quad
\text{og }
\quad
\frac{\partial f^2}{\partial x_2 \partial x_1}.
\]
De to siste er som regel identiske,
men det finnes patologiske eksempler der de ikke er det;
dette skal vi se pÃ¥ senere.
Det er vanlig Ã¥ sette opp de andreordens deriverte i 
\textbf{hessematrisen}:
\[
f''(x)=
\left(\;
\begin{matrix}
\frac{\partial^2 f}{\partial x_1^2} &amp;\frac{\partial^2 f}{\partial x_1x_2}  \\[3mm]
\frac{\partial^2 f}{\partial x_2x_1} &amp;\frac{\partial^2 f}{\partial x_2^2}
\end{matrix}
\;\right)
\begin{comment}
\begin{pmatrix}
\frac{\partial^2 f}{\partial x_1^2} &amp;\frac{\partial^2 f}{\partial x_1x_2} &amp; \cdots&amp;\frac{\partial^2 f}{\partial x_1x_n} \\[2mm]
\frac{\partial^2 f}{\partial x_2x_1} &amp;\frac{\partial^2 f}{\partial x_2^2} &amp; \cdots&amp;\frac{\partial^2 f}{\partial x_2x_n} \\[2mm] 
\vdots &amp; \vdots &amp; \vdots &amp; \vdots \\[2mm]
\frac{\partial^2 f}{\partial x_nx_1} &amp;\frac{\partial^2 f}{\partial x_n x_2} &amp; \cdots&amp;\frac{\partial^2 f}{\partial x_n^2} \\ 
\end{pmatrix}
\end{comment}
\]

\begin{oppgave}{2}
	Finn hessematrisen til fjellet $h$.
\end{oppgave}

I hessematrisen finner vi all info om hvorvidt et kritisk punkt er topp eller bunn. 

\begin{oppgave}{3}
Finn fram til Taylors andreordens formel for en funksjon fra $f: \mathbb R^2 \to \mathbb R$
\[
f\left(x+ h\right)\approx f(x)+f'\left(x\right)h + h^T f''(x)h
\]
ved Ã¥ sende en rett linje gjennom $x$ i retning $h$ og bruke kjerneregelen.
\end{oppgave}


Hessematrisen er som regel symmetrisk 
og fÃ¸lgelig som regel ortogonalt diagonaliserbar.


\begin{oppgave}{4}
	Forklar hvorfor vi nÃ¥ trenger Ã¥ vite om hessematrisen 
	er positivt eller negativt definitt eller ingen av delene, og
	vis at funksjonen $h$ pÃ¥ fÃ¸rste side har et toppunkt i 
	$(3/7,1/7)^T$ og ikke et bunnpunkt eller en sadel. 
\end{oppgave}


\begin{center}
	\includegraphics[scale=.27]{../figurer/L1007227}
\end{center}

\clearpage

Monaco og Finland har sitt hÃ¸yeste punkt 
i en oppoverbakke langs landegrensen,
og hvis du Ã¸nsker Ã¥ finne det hÃ¸yeste punktet pÃ¥ skituren pÃ¥ fÃ¸rste side, 
hjelper det ikke Ã¥ finne toppen av fjellet,
for skituren gÃ¥r ikke innom der. 
Her har du to valg, 
enten kan du parametrisere $\Gamma$,
sette inn i uttrykket for $h$,
og sÃ¥ derivere med hensyn pÃ¥ $t$ og sette lik null og sÃ¥ videre slik du gjorde pÃ¥ skolen,


\begin{oppgave}{5}
		PrÃ¸v dette. 
		Du mÃ¥ sette opp parametriseringer for alle de tre bitene av $\Gamma$.\\
		(Den krumme delen vil gi opphav til en likning som ikke er helt god Ã¥ lÃ¸se med penn og papir, 
		sÃ¥ du blir nok nÃ¸dt til Ã¥ kjÃ¸re envariabel Newtons metode.)
\end{oppgave}




eller du kan prÃ¸ve noe som kalles 
\textbf{Lagranges multiplikatormetode}.\footnote{
	\url{https://en.wikipedia.org/wiki/Lagrange_multiplier}
}
La oss si at du gÃ¥r pÃ¥ fjellet gitt av $z=f(x)$ og at gps-sporet
ditt er gitt av en kurve med likning $g(x)=C$.
I figuren under er en person ute og gÃ¥r sin foretrukne sÃ¸ndagstur i Ogndalen. 
Ekvidistanselinjene pÃ¥ kartet er de brune nivÃ¥kurvene til $f$, 
og vedkommende gÃ¥r en tur gitt av den rosa kurven. 

\begin{oppgave}{6}
Forklar ved hjelp av figuren at for det hÃ¸yeste punktet pÃ¥ turen,
bÃ¸r gradientene til $f$ og $g$ vÃ¦re parallelle,
og at dersom nivÃ¥kurvene er glatte, 
finnes det i dette punktet en konstant $\lambda$ slik at
\[
f'(x)=\lambda g'(x).
\]
(Se nÃ¸ye pÃ¥ ekvidistanselinjene, og husk at gradienten stÃ¥r normalt pÃ¥ nivÃ¥kurvene. 
Jeg har tegnet inn gradientene til $f$ og $g$ i to forskjellige punkter for Ã¥ illustrere.)
\end{oppgave}




\begin{oppgave}{7}
	PrÃ¸v oppgave 6 pÃ¥ nytt med Lagranges mutliplikatormetode.
\end{oppgave}

Du kan ogsÃ¥ tenke pÃ¥ Lagranges multiplikatormetode som Ã¥ lete etter 
kritiske punkter til 
\begin{align*}
	L(x) = f(x) + \lambda g(x).
\end{align*}

\begin{oppgave}{8}
	Hvorfor det?
\end{oppgave}



\begin{oppgave}{9}
Du gÃ¥r pÃ¥ elliptisk skitur pÃ¥ fjellet 
$h(x)=1-x_1^2-x_1x_2-x_2^2$, 
langs trajektorien gitt ved ellipsen med likning
\[
x_1^2+\frac{x_2^2}{4}=1.
\] 
Finn turens hÃ¸yeste punkt.
\end{oppgave}

%Trenger du flere oppggaver, kan du gjÃ¸re oppgave 8-12 i kap 9.7, og 1-7 i 9.20. 

\begin{center}
\includegraphics[scale=.39]{../figurer/lagrange.png}
\end{center}

\clearpage

\begin{oppgave}{10}
En ellipse med halvakser $a=\frac{1}{2}$ og $b=\frac{\sqrt{3}}{2}$, 
rotert $\pi/4$ radianer i forhold til koordinataksene, 
tilfredsstiller likningen
\[
6(x_1+x_2)^2+2(x_1-x_2)^2=3.
\]
%Hvor lange er halvaksene?
%og har parametrisering
%\[
%x(t)=\begin{pmatrix}\cos t\\ \cos(t+\pi/3)\end{pmatrix}
%\]
Finn den stÃ¸rste verdien til 
\[
	f(x) = x_1 + 2x_2   
\]
pÃ¥ ellipsen.
\end{oppgave}

Sjekk ogsÃ¥ oppgave 1d pÃ¥ fjorÃ¥rets kont, 
og 1a pÃ¥ fjorÃ¥rets ordinÃ¦r. 
Du finner alt her:\\
\url{https://folk.ntnu.no/mortano/eksamen/}\\ 
Sjekk ogsÃ¥ ut TMA4105 sine optimeringsoppgaver her:\\
\url{https://wiki.math.ntnu.no/_media/tma4105/2024v/interaktiv_5.pdf}\\
\url{https://wiki.math.ntnu.no/_media/tma4105/2024v/plenumsregning_5.pdf}\\
\url{https://wiki.math.ntnu.no/_media/tma4105/2024v/lf_anbefalte_5.pdf}\\
samt oppgavene i Arnes bok kapittel 9.8 og 9.20. 


\clearpage

\section*{UKENS NÃ˜TTER}

\textbf{Sporet} til en kvadratisk matrise er summen av diagonalelementene. 

\begin{oppgave}{1}
	Hva er sporet til hessematrisen til en harmonisk funksjon?
\end{oppgave}

For Ã¥ forklare at hessematrisen gir info om kritiske punkt, 
er det nyttig Ã¥ vite at den er symmetrisk. 
Men det finnes altsÃ¥ patologiske tilfeller der den ikke er det. 

\begin{oppgave}{2}
	Finn hessematrisen til 
	\begin{align*}
		f(x) = 
		\begin{cases}
			\frac{x_1x_2\left( x_1^2-x_2^2 \right)}{x_1^2+x_2^2} &amp; x \neq 0 \\
			0 &amp; x=0
		\end{cases}
	\end{align*}
	i $x=0$.
\end{oppgave}

I det virkelige liv mÃ¥ man stort sett jobbe numerisk.
Har du skjÃ¸nt tangentplanene, 
har du i prinsippet alt som trengs for Ã¥ forstÃ¥
\textbf{Newtons metode}\\
\begin{minipage}{100mm}
	\begin{align*}
		 x_{k+1}
		= 
		 x_{k}
		- 
		\Big ( f'( x_k)\Big)^{-1}
		 f( x_k)
	\end{align*}
	for lÃ¸sning av det ikkelineÃ¦re likningssettet
	\begin{align*}
		 f( x)= 
		\left(\; 
			\begin{matrix}
				f_1(x)\\[1mm]     
				f_2(x)
			\end{matrix}
		 \;\right)
		=
		\left(\; 
			\begin{matrix}
				0\\[1mm]     
				0
			\end{matrix}
		 \;\right).
	\end{align*}
	Her betyr $x_k$ iterasjon $k$, 
	altsÃ¥ en vektor i $\mathbb{R}^{2 \times 1}$.
\end{minipage}
\begin{minipage}{61mm}
	\begin{center}
		\begin{tikzpicture}[thick]
				\draw[blue] (-2,0) circle (2cm) node[right,xshift=1cm,yshift=2cm]{$f_1( x)=0$};
				\draw[red] (0,-1) circle (1.5cm) node[right,xshift=1.5cm,yshift=0cm]{$f_2( x)=0$};
				\node[below right] at (-.285,.705){$\circ$};
				\node[below right] at (0,1.25){$ r$};
				\draw[-&gt;] (-3.5,0) -- (2.5,0) node[right]{$x_1$};
				\draw[-&gt;] (-2.5,-1) -- (-2.5,1.3) node[above]{$x_2$};
		  \end{tikzpicture}
	  \end{center}
\end{minipage}

\begin{oppgave}{3}
	I oppgave 5 i Ã¸kt 3-1 regnet du faktisk ut et newtonsteg fra initialgjetningen 
	$x_0 = (1,1)^T$ nÃ¥r du 
	fant skjÃ¦ringspunktet mellom nullnivÃ¥kurvene til tangentplanene. 
    Finn skjÃ¦ringspunktene mellom sirklene numerisk. 
\end{oppgave}

%\reversemarginpar\marginnote{\includegraphics[scale=.08]{../figurer/herrdummefjes-4}}[7mm]
\begin{oppgave}{4}
    Finn skjÃ¦ringspunktene mellom de to ellipsene 
    \begin{align*}
        3 x_1^2 + 2 x_1 x_2 + x_2^2 - 2x_1 - x_2 = 1
        \hspace*{10mm}
        \text{og}
        \hspace*{10mm}
        x_1^2 + 2x_1 x_2 + 6 x_2^2  - x_1  - 2x_2 = 1.
    \end{align*}
\end{oppgave}

Newtons metode er en teknikk for Ã¥ lÃ¸se ikkelineÃ¦re likningssett,
men ogsÃ¥ en teknikk for Ã¥ finne kritiske punkter til skalarfelt. 
Det er derfor Newtons metode hÃ¸rer hjemme i denne Ã¸kten. 

\begin{oppgave}{5}
	Finn og klassifiser de kritiske punktene til 
	\begin{align*}
		V(x)=x_1^3 + x_1^2x_2 + x_1x_2^2 + 2x_2^3 - x_1^2 - x_2^2 - x_1x_2- x_1 -x_2.
	\end{align*}
\end{oppgave}




\end{document}
</pre></body></html>