grupp: 48 namn1: Wilhelm Cronholm namn2: Markus Kollind ************************************************************ Laboration 2 Gjord av Wilhelm Cronholm (77 08 03-2474) och Markus Kollind (73 06 25-4918) Del I ===== Uppgift 1: a) Lösningspunkten är (-2.25, -3.0625) och hittades med newtons metod (steglängd 1) på ett steg från alla startpunkter. Med BL tar det nio steg innan avbrottskriteriet är uppfyllt och funktionen konvergerar mot samma lösning som Newtons metod. b) Funktionen är konvex och alltså är erhållen lösning ett globalt minimum. c) Eftersom funktionen är kvadratisk och approximationen i newtons metod är Taylorutvecklingen av funktionen av grad två blir approximationen exakt. -------------- uppgift 2: a) BL når inte fram till ett optimalt värde på 200 iterationer men konvergerar mot (1,1). Newtons metod (stegläng ett) hittar optimum på 5 iterationer men hoppar väldigt mycket innan den stannar i optimum. Newtons metod (Marquardts modifikation) hittar optimum på 13 iterationer och närmar sig snällt vilket också gäller Newtons metod med linjesökning. b) Funktionen är inte konvex men punkten (1,1) är ett globalt minimum eftersom funktionen inte kan ha lägre värden än 0. c) Vid startpunkten (0,2) ger BL inte heller någon lösning även om den konvergerar mot den rätta. Newtons metod med linjesökningen får en steglängd som är 0 vilket gör att den inte kan komma vidare. Övriga metoder konvergerar mot (1,1). Övriga startpunkter som testades resulterade bara i att BL inte hittade en optimal lösning inom 200 iterationer medan de övriga metoderna hittade optimum. -------------- Uppgift 3: a) Med BL som lösningsmetod hittas ett minimum efter 4 iterationer i punkten (2.99978, 0.99993). Detta är dock ett lokalt minimum, vilket lätt inses efter studier av grafen. Med Newtons metod kan inte nästa iterationspunkt hittas. Detta kommer sig av att Hessianen är noll vilket gör att den inte är inverterbar. Med Marquardtmodifieringen hittas samma minpunkt som med BL. b) Om vi startar i punkten (-3,2) och använder Newtons metod hittas en stationär punkt i (-3,1). Om vi startar i punkten (2,-1) hittas stationärpunkten (3,-1). Vid start i punkten (-2.5, -0.5) letar sig Newtons metod uppåt till maxpunkten (-3,-1). Totalt hittas alltså 4 stationära punkter, en minpunkt (3,1), en maxpunkt (-3,-1) och två sadelpunkter (-3,1), (3,-1). --------------------------------------------------------- Del II ====== Uppgift 1: a) Lösningen till problemet ges genom fmincon: x = (0.6250, 1.2500) lambda = (0, 0.125) f = -1.5625 (negerade värdet till det givna problemet) b) L(x,l) = -x(1) + 2*x(1)^2 - 2*x(2) + x(2)^2 - x(1)*x(2) + l(1)*(x(1)^2 - x(2)) - l(2)*(2*x(1) - x(2)) KKT-villkoren blir: l(1), l(2) >= 0 lambda tillåten x(1)^2-x(2) >= 0 x tillåten -2*x(1)+x(2) >= 0 -"- l(1)*(x(1)^2-x(2)) = 0 komplementaritet l(2)*(-2*x(1)+x(2)) = 0 -"- 4*x(1) - 1 - x(2) + 2*x(1)*l(1) - 2*l(2) = 0 2*x(2) - 2 - x(1) - l(1) +l(2) = 0 Alla är uppfyllda för givna lösningen. Konvexiteten: Första villkoret beskriver en konvex mängd eftersom funktionen x(1)^2 - x(2) är konvex. Andra villkoret är linjärt och beskriver därmed också en konvex mängd. Hessianen till funktionen (för minimeringsproblemet) är [4 1;1 2] och är därmed positivt definit. Därmed är funktionen konvex. -------------- Uppgift 2: a) Vid optimering med startpunkten (0,0) hittades ingen lösning. När vi hade startpunkten (1,1) blev resultatet x = (3.4, 1.2) för vilken f = 3.4, för startpunkten (-1,-1) hittades lösningen x = (-3,-2) för vilken f = -3, för startpunkten (3.7,0) hittades lösningen x = (3.6056,0) för vilken f = 3.6056 och för en egenvald punkt (1,-6) hittas lösningen x = (-3,-2) igen. b) Vi kan garantera att punkten x = (-3,-2) är optimum. Villkoren beskriver två cirklar, en med centrum i origo med radie sqrt(13) vilken man skall vara utanför samt en med centrum i (1,-2) med radie 4 som man skall vara utanför. Området är inte konvext men man kan lätt se att det globala optimat finns i (-3,-2). Varje given lösning är en KKT-punkt men inte nödvändigtvis optimal. Punkten (0,0) ligger utanför området och en lösning kan därför inte hittas. -------------------------------------------------------------- Del III: ======== Uppgift 1: EPA konvergerar för exempel 2 mot en punkt som är ungefär (0.44, 3.15) vilken ligger på gränsen för det fjärde villkoret. För exempel tre konvergerar EPA mot punkten (5/sqrt(2),-5/sqrt(2)). För exempel två konvergerar IPA mot punkten (3.221, 0.75) och exempel tre konvergerar mot punkten (-5/sqrt(2),5/sqrt(2)). -------------- Uppgift 2: Både EPA och IPA konvergerar mot globala optimum för exempel 3. För exempel 2 konvergerar EPA mot ett globalt optimum och IPA konvergerar mot ett lokalt. -------------- Uppgift 3: I exempel 2 finns det de två optima algoritmerna har hittat samt ytterligare ett optima i punkten (sin(0.75),0.75). I exempel 3 finns de två otima som algoritmen hittat.