grupp: 10 namn1: Andreas Holmström namn2: Erik Jonsson ************************************************************ ==================================================================== || DEL 1 ==================================================================== Uppgift 1: ------------ a) Vi använde avbrottskriteriet "Iterationsavstånd < 0.0001" i alla fall. Startpunkt (10,10): Brantaste lutningen: Konvergerar mot (-2.24997,-3.0625) Antal iterationer: 11 Newton: Konvergerar mot (-2.25,-3.0625) Antal iterationer: 1 Startpunkt (-5,-5): Brantaste lutningen: Konvergerar mot: (-2.25005,-3.06251) Antal iterationer: 12 Newton: Konvergerar mot (-2.25,-3.0625) Antal iterationer: 1 Egen startpunkt, (0,0): Brantaste lutningen: Konvergerar mot (-2.24998,-3.06248) Antal iterationer: 8 Newton: Konvergerar mot (-2.25,-3.0625) Antal iterationer: 1 b) Ja. Fast med brantaste lutningen får vi aldrig den exakta punkten, vilket vi får med Newton. c) Newtons metod approximerar funktionen med taylorutvecklingen av ordning två, och minimerar denna approximation exakt. Eftersom vi i detta fallet har en andragradsfunktion, kommer taylorutvecklingen av ordning två ge funktionen själv. Så Newton löser i själva verket problemet exakt i en iteration. Uppgift 2 --------- a) Newton-Marquardt: (0.999999,0.999998), 13 iterationer Newton, modifierad: (0.999999,0.999998), 13 iterationer Newton, steglängd 1: (1,1), 4 iterationer Brantaste lutningsmetoden når inte optimum på 200 iterationer b) Funktionen är inte konvex. (1,1) är den enda stationärpunkten, och vi ser att f(1,1) = 0. Detta är det lägsta värdet funktionen kan anta, eftersom funktionen är icke-negativ. Alltså är (1,1) ett globalt minimum. c) Vi ser att brantaste-lutningsmetoden är jättedålig på att hitta optimum, även om man startar jättenära. De andra metoderna lyckas däremot alltid hitta fram. Uppgift 3 --------- a) Newtons metod fungerar inte därför att hessianen är [0 0, 0 0]. Då får den problem när den skall beräkna steglängden, eftersom inversen till hessianen är odefinierad. Med Levenberg-Marquart fungerar det däremot bättre, eftersom den modifierar hessianen så att den blir positivt definit. b) Vi konstanterar att steg-1-Newton även hittar sadelpunkter. Totalt hittade vi fyra stationärpunkter: (-3,-1): Maxpunkt (3,1): Minpunkt (-3,1): Sadelpunkt (3,-1): Sadelpunkt ==================================================================== || DEL 2 ==================================================================== Uppgift 1 --------- a) Vi skrev in följande kommando: arne = fmincon('upg1f',[0 0],[],[],[],[],[],[],'upg1g') och fick ut lösningen (0.625, 1.25). b) Vi fick följande KKT-villkor: Primal tillåtenhet: -x1^2 + x2 >= 0 2x1 - x2 >= 0 Komplementaritet: lamda1*(-x1^2 + x^2) = 0 lamda2*(2*x1-x2) = 0 Dual tillåtenhet: -1 + 4*x1 - x2+ 2*lamda1*x1 - 2*lamda2 = 0 -2 + 2*x2 - x1 - lamda1 + lamda2 = 0 lamda1, lamda2 >= 0 Problemet är konvext, ty området är konvext, och funktionen är konkav (vilket skall gälla, eftersom vi har ett maximeringsproblem). Att funktionen är konkav ser man lätt på hessianen. KKT-villkoren är uppfyllda i punkten (0.625,1.25) med lamda1 = 0 och lamda2 = 1/8. Eftersom problemet är konvext måste detta även vara ett globalt optimum. Uppgift 2 --------- Vi använde matlabfunktionen fmincon för alla sökningar. Eftersom problemet var såpass lätt, ritade vi upp området för att kunna kontrollera våra lösningar. Vi misstänkte att lösaren skulle kunna fastna i två olika punkter: (-3,-2), som är det globala minimumet, men även (3.4,1.2), som bara är ett lokalt minimum. När vi började sökningen från (0,0) hittade den ingen tillåten lösning. Däremot gjorde den det när vi började i (1,1) och (-1,-1). Både (0,0), (1,1) och (-1,-1) ligger ju utanför det tillåtna området, så det verkar inte vara det som är problemet. Vi noterade att gradienten för andra bivillkorsfunktionen är noll i punkten (0,0), och vi tänkte att det kanske hade med det att göra. så vi provade ävan att börja i punkten (1,-2), eftersom gradienten till andra bivillkorsfunktionen är noll i den puntken. Mycket riktigt fick vi även då ett konstigt resultat; Lösaren tyckte att (1,-4) var ett optimum, och den tyckte dessutom att båda bivillkoren var aktiva, trots att punkten ligger långt inne i området. Om man stoppar in (1,-4) som startpunkt får man däremot den korrekta lösningen (-3,-2). Så vår slutsats blev att lösaren ballar ur när gradienten till något bivillkor är noll. Från (1,1) kom vi till (3.4,1.2), och från (-1,-1) kom vi till (-3,-2). När vi provade med (3.7,0) kom vi till en helt annan punkt: (3.6,0). Om man studerar skissen på området ser man lätt att normalen till andra bivillkoret är parallell med målfunktionens gradient. Om vi däremot flyttar oss pyttelite i x2-riktning, kommer lösaren ge oss någon av de båda punkterna (-3,-2) eller (3.4,1.2). Eftersom området inte är konvext, kan vi inte garantera ett globalt minimum utan att studera området i detalj. ==================================================================== || DEL 3 ==================================================================== Uppgift 1 --------- Problem2: Både EPA och IPA konvergerar mot (3.2,0.75) Däremot verkade EPA konvergera mot en annan punkt i början. Sedan tog den ett jätteskutt genom det tillåtna området. Den punkt metoden verkade konvergera mot först var en sadelpunkt. Först när vi kom såpass nära punkten att vi fick numeriska problem, ville metoden hoppa vidare till en annan punkt. Vilken punkt den hoppade till verkade rättså slumpartat, men det var alltid en bättre punkt. Problem3: EPA konvergerar mot (3.5,-3.5), medans IPA konvergerar mot (-3.5,3.5). Eftersom både bivillkoren och målfunktionen är helt symmetriska, måste båda dessa punkter vara likvärdiga. Uppgift 2 --------- IPA konvergerade alltid mot ett lokalt optimum. I ett fall konvergerade EPA istället mot en sadelpunkt, men det var bara otur som gjorde att det var just denna metod som råkade ut för detta (se uppg1). Vi har ingen garanti för att metoden skulle konvergera mot ett globalt optimum. Uppgift 3 --------- Till problem 1 finns följande lokala optimum: (0.5,3.2), (3.2,0.75), (0.75,0.75) Till problem 2 finns följande lokala optimum: (3.5,-3.5), (-3.5,3.5)