grupp: top02-15 namn1: Carl Bohman namn2: Peter Enarsson ************************************************************ Labb 2-Tillämpad Optimering Grupp Top02-15 Carl Bohman Peter Enarsson DEL 1 1a. Med Brantaste lutningsmetoden fick vi följande lösningar: Startpunkt(-5 -5) Funktionsvärde -11.1562 Lösningspunkt -2.25225 -3.06234 Antal iterationer 9 Startpunkt(10 10) Funktionsvärde -11.1562 Lösningspunkt -2.2491 -3.06255 Antal iterationer 9 Startpunkt(-10 -10)Funktionsvärde -11.1562 Lösningspunkt -2.25167 -3.06237 Antal iterationer 9 Med Newton fås för samma punkter som ovan ett likadant optimalvärde efter endast en iteration i punkten (-2.25 -3.0625). b. Hessianen till funktionen är positivt semidefinit och därmed är funktionen konvex. Vi har ett globalt minimum. c. Newtons metod använder en kvadratisk approximation av målfunktionen och löser exakt i varje steg. Eftersom vi redan har en kvadratisk funktion får vi en exakt lösning efter en iteration. 2a. Med brantaste lutningsmetoden hittar vi inte optimum efter maximala 200 iterationer när vi startar i (-1.5 -1), om vi sedan fortsätter och pluggar in sista punkten som startvärde får vi efter ytterligare 30 iterationer ett min i (0.991043 0.982117) vilket är nära det eftersökta (1 1). Med Newtons metoder får vi: Steglängd 1: Optimum i (1 1) efter 5 iterationer. Modifierade: Optimum i ( 1.00002 1.00003) efter 13 iterationer Marquardt: Optimum i ( 1.00002 1.00003) efter 13 iterationer b. Vi ser intuitivt att den icke är konvex, ty om du tar två punkter på "flodbottnen" på var sin sida om "kullen" så uppfyller inte dessa punkter definitionen ppå konvexitet. Vi kan således inte vara säkra på att punkten är ett globalt optimum. c. Om vi startar i punkten (0 3) så klarar inte Newtons steglängd 1 samt modifierade av detta, ty steglängden blir noll. Marquardt klarar fortfarande av det galant och brantaste lutningen gör sitt jobb sakta men säkert. 3a. Brantaste lutningsmetoden får på 4 iterationer fram punkten (3 1) som optimum. Newtons metod fastnar däremot direkt ty hessianen är ej inverterbar, innehåller endast nollor. Marquardt fungerar utmärkt eftersom metoden involverar att fixa till Hessianen så att den blir positivt definit. b. Vi hittar fyra stationära punkter. Ett lokalt max i (-3 -1) Ett lokalt min i (3 1) En sadelpunkt i (-3 1) En sadelpunkt i (3 -1) DEL 2 1a. Lösningen blir med bivillkor 2 aktivt och optimum i (0.6250 1.2500). b. Primal tillåtenhet uppfylld. Komplementaritet ger lambda1=0. Dual tillåtenhet lambda2=0.125 Bägge lambda större eller lika med 0. Punkten uppfyller således alla KKT-villkor. Konvexitet. Målfunktionen är konvex i vårt minimeringsproblem. Andra bivillkoret är linjärt således konvext. Första bivillkoret är också konvext. Detta tillsammans med KKT uppfyllt ger globalt optimum. 2a. Med startpunkt [0 0] hittas ingen tillåten lösning utan man stannar i punkten [0 0]. Det andra bivillkoret är inte uppfyllt. Med startpunkt [1 1] får man lösningen [3.4 1.2], båda bivillkoren binder. Målfunktionens värde blir 3.4. Med startpunkt [-1 -1] får man lösningen [-3 -2], båda bivillkoren binder. Målfunktionens värde blir -3. Med startpunkt [3.7 0] får man lösningen [13^(1/2) 0], andra bivillkoret binder. Målfunktionens värde blir 13^(1/2). Av detta att döma skulle man säga att den optimala punkten är [-3 -2] och att det optimala målfunktionsvärdet är -3. Punkten [-3 -2] uppfyller dock inte dual tillåtenhet i KKT-villkoren och kan därför inte vara optimal. Punkten [3.4 1.2] är inte heller en KKT-punkt eftersom den inte är dualt tillåten. Punkten [13^(1/2) 0] uppfyller alla KKT-villkor. Detta är ett minimum, men inte något globalt minimum eftersom vi har ett icke-konvext problem. (Bivillkor 2 är alla punkter utanför en cirkel, vilket inte är en konvex mängd). Del III 1. Yttre straffmetoden på problem 2 konvergerar mot punkten [0.68 0.75]. Detta är punkten där bivillkor 2 och 3 skär varandra. Inre straffmetod på problem 2 konvergerar mot [3.22 0.75]. Detta är punkten där bivillkor 3 och 4 skär varandra. Om vi tittar på målfunktionens nivåkurvor ser vi att punkten [0.68 0.75] är ett lokalt minimum. Kandidater till globalt minimum är [3.22 0.75] samt [0.3 3.1]. Det är svårt att direkt se vilket som är globalt minimum av dessa i grafen.Man kan om man vill räkna ut exakt var de aktuella bivillkoren skär varandra och sätta in i målfunktionen för att se vilken av punkterna som är globalt minimum.. Ett ytterligare lokalt optima finns i [0.3 2.8]. Yttre straffmetoden på problem 3 konvergerar mot punkten [3.54 -3.54]. Inre straffmetod på problem 3 konvergerar mot [-3.54 3.54]. Metoderna konvergerar mot var sitt lokalt optima. Eftersom problemet är helt symmetriskt så är båda dessa globala optima. I [0 0] finns en sadelpunkt.