From 2a7fa79533e12a497ddce10a4e1bdc1610341746 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Fri, 16 Mar 2012 11:59:56 +0100 Subject: [PATCH] Copied in problem 1 from Lars --- rapport.tex | 94 ++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 89 insertions(+), 5 deletions(-) diff --git a/rapport.tex b/rapport.tex index b83c8e9..e008cec 100644 --- a/rapport.tex +++ b/rapport.tex @@ -43,12 +43,96 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Oppgave 1} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\subsection{a)} -Hei og hå. Her skriver Lars noe gøy. +Vi har problemet +\begin{equation} + \label{eq:f} + \min_{x\in\Omega}{f(x)} = \min{\{x_{1}^{3}-6x_{1}^{2} + 11x_{1} + + x_{3} \}}, +\end{equation} +der $\Omega$ er gitt ved føringene +\begin{align} + -x_{1}^{2}-x_{2}^{2}+x_{3}^{2} &\geq 0 \label{eq:foring1} \\ + x_{1}^{2} + x_{2}^{2} + x_{3}^{2} - 4 &\geq 0 \label{eq:foring2} \\ + -x_{3} + 5 &\geq 0 \label{eq:foring3} \\ + x_{1} & \geq 0 \label{eq:foring4} \\ + x_{2} & \geq 0 \label{eq:foring5} \\ + x_{3} & \geq 0 \label{eq:foring6}. +\end{align} +\begin{figure}[h!] + \begin{center} + \includegraphics[width=12cm,height=9cm]{figur.png} + \caption{Området $\Omega$, nivåflater for $f(x) = 8$ og $f(x) = 2$, samt mulige KKT-punkter.} + \label{fig} + \end{center} +\end{figure} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\section{Oppgave 2} +Vi finner gradienten til $f$, som er gitt ved +\begin{equation} + \nabla f = [3x_{1}^{2}-12x_{1}+11, 0, 1], +\end{equation} +og ser at denne aldri kan være lik $0$, slik at vi kun vil kunne finne +lokale minimumspunkter på randen av $\Omega$. Siden området er lukket og +begrenset, vet vi også at det finnes minst ett lokalt minimumspunkt. +\subsection{a)} +Vi vil så vise at $x_a = (0,\sqrt{2},\sqrt{2})$ er et KKT-punkt.\\ +Dersom $x_a$ er et KKT-punkt, har vi at det må oppfylle KKT-ligningene +\begin{eqnarray} +\nabla_{x}\mathcal{L}(x,\lambda) = \nabla f(x) - \sum_{i\in\mathcal{A}}\lambda_i \nabla c_i(x) &=& 0,\\ +\lambda_i \cdot c_i(x) &=& 0, i \in \mathcal{E} \cup \mathcal{I},\\ +\lambda_i &\geq & 0, i \in \mathcal{I}, +\label{} +\end{eqnarray} +der \textit{Lagrange-funksjonen} $\mathcal{L}$ er definert +\begin{equation} +\mathcal{L}(x,\lambda) = f(x) - \lambda'c(x), +\label{} +\end{equation} +der $\lambda = (\lambda_1,\cdot\cdot\cdot,\lambda_m)'$ og $c(x) = (c_1(x),\cdot\cdot\cdot,c_m(x))'$. +Fra KKT-ligningene ser vi at for alle inaktive føringer, $i \in \mathcal{I}\setminus\mathcal{A}$ der $c_i(x) > 0$, vil de tilhørende $\lambda_i = 0$. I punktet vi vil undersøke, $x_a$, ser vi at føringene $(1)$, $(2)$ og $(4)$ er aktive, slik at $\lambda_3 = \lambda_5 = \lambda_6 = 0$. Ved å skrive ut komponentene til $\nabla_x\mathcal{L}$ og sette inn koordinatene til $x_a$ får vi dermed ligningene +\begin{eqnarray} +11 - \lambda_4 &=& 0\nonumber\\ +2\sqrt{2}\lambda_1 - 2\sqrt{2}\lambda_2 &=& 0\nonumber\\ +1 - 2\sqrt{2}\lambda_1 - 2\sqrt{2}\lambda_2 &=& 0, +\label{} +\end{eqnarray} +som gir oss $\lambda_1 = \lambda_2 = \frac{1}{4\sqrt{2}}$ og $\lambda_4 = 11$.\\ +Disse er positive $\Rightarrow x_a$ oppfyller KKT-ligningene $\Rightarrow x_a$ er et KKT-punkt. +\subsection{b)} +Vi vil bruke MATLAB-funksjonen \texttt{fmincon} til å finne andre KKT-punkter.\\ +Først modifiserte vi den oppgitte koden. +\begin{lstlisting} +OPTIONS = optimset('Algorithm','active-set','TolX',1e-10,'TolCon',1e-10,'TolFun',1e-10); +x = fmincon('foppg1',x0,[],[],[],[],[],[],'constraints',OPTIONS) +\end{lstlisting} +Ved å prøve forskjellige verdier for $x_0$ fant vi frem til punktene $x_b = (2.0004,0,2.0004)$, $x_c = (0,0,2)$ og $x_d = (\sqrt{2},0,\sqrt{2})$ som mulige KKT-punkter. +\subsection{c)} +Vi vil undersøke disse punktene nærmere, for å avgjøre om noen av dem kan være lokale minimumspunkter.\\ +Først undersøker vi punktet $x_b$, og ser om vi kan finne et KKT-punkt i nærheten av det analytisk. Vi ser at kun føringene $(1)$ og $(5)$ er aktive i et slikt punkt. Vi bruker at $x_2 = 0$, setter dette inn i $(1)$, og får dermed at +\begin{equation} +-x_{1}^{2} + x_{3}^{2} = 0 \;\;\;\Rightarrow \;\;x_{1}^{2} = x_{3}^{2} \;\;\Rightarrow\;\; x_{1} = \pm x_{3}. +\label{} +\end{equation} +Siden alle $x_i \geq 0$, har vi da at $x_1 = x_3$. Vi settee dette inn i funksjonsuttrykket (\ref{f}), og får da at med disse aktive føringene kan funksjonen uttrykkes +\begin{equation} +f_{1,5}(x)= x_{1}^{3}-6x_{1}^{2} + 12x_{1}. +\label{f15} +\end{equation} +Vi kan enkelt finne kritiske punkter til $f_{1,5}$ ved å finne punktene som oppfyller $\frac{\partial}{\partial x_1}f_{1,5} = 0$. Vi får kun ett slikt punkt, $x_1 = 2$, som nødvendigvis må være et sadelpunkt, siden $f_{1,5}$ er en tredjegradsfunksjon. Altså kan ikke $(2,0,2)$ være et lokalt minimumspunkt for $f$ i $\Omega$.\\ +\\ +Videre vil vi undersøke punktet $x_c = (0,0,2)$. Dette er også et KKT-punkt, og åpenbart det som gir lavest funksjonsverdi der $x_1 = x_2 = 0$. Vi mistenker likevel at det ikke er et lokalt minimumspunkt, og undersøker hva som skjer dersom vi lar $x_2 > 0$, og holder føring $(2)$ aktiv.\\ +Vi får da $x_{2}^{2} + x_{3}^{2} - 4 = 0\;\;\Rightarrow\;\;x_{3} = \sqrt{4-x_{2}^{2}}$. Vi kan da se at funksjonen minker når $x_2$ øker, slik at $x_c$ ikke kan være noe lokalt minimumspunkt.\\ +Så vil vi undersøke $x_d = (\sqrt{2},0,\sqrt{2})$, som er det eneste punktet hvor føringene $(1)$, $(2)$ og $(5)$ aktive. Dersom vi lar $x_2 > 0$, får vi ved å sette $(1)$ inn i $(2)$ at $x_3 = 2$, og får +\begin{equation} +f_{1,2}(x)= x_{1}^{3}-6x_{1}^{2} + 11x_{1} + 2. +\label{f15} +\end{equation} +Ved å derivere mhp. $x_1$, får vi +\begin{equation} +f_{1,2}(x_d) = 3x_{d_1}^{2}-12x_{d_1} + 11 = 17 - 12\sqrt{2} > 0, +\label{f15} +\end{equation} +slik at funksjonen minker når $x_1$ minker. Det finnes altså punkter med lavere funskjonsverdi i nærheten av $x_d$, og det kan ikke være noe lokalt minimumspunkt.\\ +Vi står da igjen med $x_a$ som eneste kandidat til minimumspunkt i $\Omega$. Dette må altså være minimumspunktet vårt, noe som også fremgår av Figur (\ref{fig}). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{a)} -- 2.47.3