grupp: 44 namn1: Cecilia Peng namn2: Jorild Engkvist ************************************************************ Lab 2 Grupp: 44 Av: Cecilia Peng och Jorild Engkvist 1a) Med startpunkt (10 10) löst med BL konvergerar metoden mot punkten (-2.2491 -3.06255). Det krävdes 9 iterationer. Med samma startpunkt, fast löst med Newton (med steglängd 1), konvergerar metoden mot punkten (-2.25 -3.0625). Det krävdes 1 iteration. Med startpunkt (-5 -5) löst med Newton (med steglängd 1) konvergerar metoden mot punkten (-2.25 -3.0625). Det krävdes 1 iteration. Med samma startpunkt, fast löst med BL, konvergerar metoden mot punkten (-2.25225 -3.06234). Det krävdes 1 iteration. 1b) Ja, det är optimum eftersom gradienten för målfunktionen är lika med noll och hessianen för den är positivt definit. 1c) Newton konvergerar alltid i en iteration eftersom vi har en funktion av grad 2. Newtons metod bygger på taylorutveckling till grad 2, eftersom funktionen är av grad två så blir taylorutvecklingen exakt lika med funktionen. 2a) Med startpunkt (-1.5 -1) löst med Newton (med steglängd 1) konvergerar metoden mot punkten (1 1). Det krävdes 5 iterationer. När vi däremot löser med BL, konvergerar inte metoden. I alla fall inte utan att överskrida Max Antal Iterationer som är på 200. Om vi använder Newtons modiferade metod konvergerar den mot (1.00002 1.00003) och den behöver 13 iterationer. Med Newton (Marquardt) fick vi samma resultat som Newtons modiferade metod. 2b) Nej, funktionen är inte konvex ty hessian är inte positivt semidefinit överallt. Det är globalt optimum eftersom funktionen är större än eller lika med noll och värdet i optimum är noll. 2c) BL klarar inte av Rosenbrocks funktion, oberoende av startpunkt. Den går till en punkt i närheten av optimum i "floddalen" och kommer inte vidare utan väldigt många iterationer. Newtons metod ( steglängd = 1) och Newtons modiferade metod klarar inte av alla startpunkter, t.ex ( 0 3 ), där funktionen är konkav. Däremot klarar Newton (Marquardt) detta. Samtliga Newtons metoder går till floddalen i första interationen och följer sedan denna. Newton ( steglängd = 1) kan gå förbi optimum för att sedan vända och gå tillbaka. De andra Newton-metoderna går direkt på optimum. 3a) Newton ( steglängd = 1) fungerar inte för att hessianen inte är inverterbar. Newton (Marquardt) uppför sig som BL, i det här fallet. 3b) Vi hittade 4 stationära punkter. Det förekommer lokalt minimum ( 3 1 ), sadelpunkter (3 -1) och (-3 1) samt lokalt maximum (-3 -1). Del 2 1a) Vi fick x=(0,625 1,25) och målfunktionens värde i punkten x, 1,5625. 1b) Vi har valt att titta på problemet som ett min-problem och gjort om alla bivillkoren till större än villkor. Primal tillåtenhet är uppfyllt ty båda bivillkoren är uppfyllda. Lösningen är komplementär om lambda_1 är lika med noll och eftersom bivillkor två är lika med noll. Dual tillåtenhet är också uppfyllt eftersom det existerar ett lambda_2 så att gradienten av f är lika med lambda_2 gånger gradienten av andra bivillkoret samt detta lambda_2 är större än noll. Detta medför att KKT är uppfyllt.Vi beräknade hessianen av funktionen och fann att den var konstant och positiv definit. Detta medför att funktionen är strikt konvex. Hessianen för båda bivillkoren var negativ semi-definita för alla x. Detta medförde att de var konkava. Detta i sin tur medför att alla x som uppfyller båda bivillkoren är en konvex mängd. Då f är konvex och skall minimeras på en konvex mängd så är det ett konvext problem. Tillsammans med uppfyllda KKT villkor är detta tillräckligt för att garantera globalt min. Detta medför att ursprungsproblemet är konkavt och uppfyller KKT vilket garanterar ett globalt maximum. 2) Vi har använt fmincon. Med startpunkten (0,0) hittades ingen tillåten lösning. I startpunkten (1,1) hittade vi optimum i punkten (3,4 1,2) med värdet 3,4. Då är båda villkoren aktiva. När vi började i punkten (-1,-1) hittade vi optimum i punkten (-3 -2) och målfunktionsvärdet är -3. Båda villkoren är aktiva. Målfunktionsvärdet blir 3,6056 i punkten ( 3,6056 0) när vi startar i punkten (3,7 0). Villkor 2 är aktivt. Problemet är inte konvext eftersom hessianen av det andra bivillkoret är positivt definit. Detta innebär att det inte finns någon global minimum. Anledningen till att vi inte hittade någon tillåten lösning med startpunkt (0 0) är att den ligger för långt utanför gränserna. Del 3 1) Vi använde metoderna "yttre straffmetod" och "inre straffmetod" på problem 2 och lösningen konvergerar mot punkten (3,2 0,75). För problem 3 konvergerar lösningen mot punkten (3,5355 -3,5355) med yttre straffmetod och punkten (-3,5355 3,5355) med inre straffmetod. 2) Yttre straffmetod på problem 2 och 3 konvergerar mot ett lokalt optimum. Det ser vi genom att titta på nivåkurvorna. 3) Till problem 2 finns optimum i punkterna (1/3 3,1344) och (3,2 0,75). Till problem 3 finns optimum i punkterna (-3,5355 3,5355) och (3,5355 -3,5355).