grupp: 24 namn1: Jaleh Arzani namn2: August Johansson ************************************************************ Laboration 2 Grupp 24 Jaleh Arzani August Johansson Del I ----- 1. a) Startpunkt (10, 10): BL: x* = (-2.2491, -3.06255), f(x*) = -11.1562 nås efter 9 iterationssteg. Startpunkt (-5, -5) Newton steg 1: x* = (-2.25, -3.0625), f(x*) = -11.1562 efter 1 iteration. Startpunkt (10, -10) BL: x* = (-2.24857, -3.06238), f(x*) = -11.1562 efter 13 iterationer. Newton steg 1: x* = (-2.25, -3.0625), f(x*) = -11.1562 efter 1 iteration. b) Lösningen som erhållits är ett globalt minimum då målfunktionen är konvex (dess Hessian är positivt definit). c) Målfunktionen är en kvadratisk funktion, vilket innebär att vi kan Taylor- utveckla den exakt till andra ordningen. Newtons metod konvergerar alltså i ett steg. 2. a) Resultaten visas i nedanstående tabell. Metod x* f(x*) antal iterationer -------------------------------------------------------------------------- BL: Ingen konvergens efter 200 iterationer Newton mod: (1.00002, 1.00003) 1.6535e-9 13 LM: (1.00002, 1.00003) 1.6535e-9 13 Newton steg 1: (1, 1) 2.9716e-25 5 b) Funktionen är inte konvex eftersom dess Hessian är inte positivt definit för alla x. Därmed är inte heller punkten ett globalt minimum. c) Startpunkt: (0, 3) BL: Ingen konvergens. LM: x* = (1.00004, 1.00007), f(x*) = 2.2392e-9, 8 iterationer. Newton steg 1: x* = (0.999445, 0.99889), f(x*) = 3.0832e-7, 3 iterationer. Startpunkt: (0, 3) BL: Ingen konvergens. LM: x* = (0.999995, 0.999991), f(x*) = 2.6568e-11, 14 iterationer. Newton steg 1: x* = (1, 1), f(x*) = 2.0031e-27, 5 iterationer. 3. a) Startpunkt: (0, 0) BL: x* = (2.99978, 0.99993), f(x*) = -58 uppnåddes efter 4 iterationer. Newton steg 1: ingen steglängd kan beräknas. LM: x* = (3, 0.999999), f(x*) = -58 efter 3 iterationer. Med Newton steg 1 kan ingen steglängd beräknas då Hessianen i (0, 0) blir noll. b) Vi väljer att använda Levenberg-Marquardts metod (LM). Startpunkt (-3, 4) gav x* = (-3, 1) och f(x*) = 50 efter 1 iteration. Med punkten (0, -1) som startpunkt erhölls x* = (3, -1) och f(x*) = -50 efter en iteration. Båda dessa punkter är sadelpunkter. Väljer vi startpunkten (-1, -3) erhålls just den lokala maxpunkt som finns här, f(x*) = 58. Förutom dessa tre punkter får vi även det lokala minimum i uppgift 3 a. Del II ------ 1. a) Problemet löstes med hjälp av MATLAB-funktionen fmincon (startpunkt (0, 0)). Vi fick minimum i punkten x* = (0.625, 1.25), med målfunktionsvärde z* = 1.5625. b) KKT: Primal tillåtenhet: g1(x*) = -0.625^2 + 1.25 = 0.8594 g2(x*) = 2*0.625 - 1.25 = 0 Komplementaritet: Då g1(x*) > 0 => lambda1 = 0 Då g2(x*) = 0 => inget krav på lambda2. Dual tillåtenhet: En räkning ger \nabla_x = (0.25 - 2*lambda2, -0.125 + lambda2) = 0, dvs lambda2 = 0.125. Vi har alltså lambda >= 0. Målfunktionen är konkav eftersom dess Hessian är konstant med egenvärdena -3-sqrt(2) och -3+sqrt(2), som båda är mindre än noll. På motsvarande sätt fås att g1 och g2 är konkava funktioner, så att bivillkoren definierar en konvex mängd. Problemet är alltså konvext, varför x* är ett globalt minimum. 2. Vi provkörde några punkter, och resultaten visas i följande tabell: startpunkt slutpunkt målfunktionsvärde ------------------------------------------------------------- (0, 0) tillåten lösning saknas -- (1, 1) (3.4, 1.2) 3.4 (-1, -1) (-3, -2) -3 (3.7, 0) (3.6056, 0) 3.6056 (2.5, -2.5) (-3, -2) -3 (3, -6) (-3, -2) -3 (-5, 2) (-3, -2) -3 (0.01, 0.01) (-3, -2) -3 (0.001 0.001) (3.4, 1.2) 3.4 Vi får punkten (-3, -2) som kandidat till globalt minimum. Dock kan vi inte använda KKT-villkoren för att avgöra detta, då problemet inte är konvext. Istället ritar vi upp målfunktionen över det tillåtna området i MATLAB, och utifrån denna figur kan vi konstatera att punkten (-3, -2) är ett globalt minimum. Del III ------- 1. Exempel 2. EPA: konvergens mot x* = (1/3, 3.2220), med f(x*) = -0.0777 IPA: konvergens mot x* = (3.2220, 3/4), med f(x*) = 0.3244 Exempel 3. EPA: konvergens mot x* = (3.5355, -3.5355), med f(x*) = -12.5 IPA: konvergens mot x* = (3.5355, -3.5355), med f(x*) = -12.5 2. I exempel 2 så fås ett globalt minimum i x* = (1/3, 3.2220), där f(x*) = -0.0777. Detta pga att funktionen är konvex i det intressanta området. I exempel 3 får av samma orsak globalt minimum i x* = (3.5355, -3.5355). 3. I exempel 2 får vi lokala optima i de två punkterna ovan samt i de två punkter där sin(x2) - x1 = 0. Detta sker i x3 = (0.6816, 3/4), med f(x3) = 0.9407, och x4 = (1/3, 2.8018) där f(x4) = 1.0429. I exempel 3 fås förutom den punkt x* vi erhållit ovan också ett globalt min i x* speglat i symmetriaxeln, x2 = (-3.5355, 3.5355) med samma målfunktionsvärde.