grupp: top02-31 namn1: Johan Karström namn2: Erik Lundell ************************************************************ BY: Johan Karström 800226-0498 Erik Lundell 800625-0115 Del I använder avbrotts kriteriet Gradientlängd=0.0001 1. a) Metod: BL Newton 1 steg Startpunkt: [10 10] [10 10] Funktionsvärde: -11.1562 -11.1563 Lösningspunkt X1: -2.2491 -2.25 X2: -3.06255 -3.0625 Antal iterationer: 9 1 Metod: BL Newton 1 steg Startpunkt: [-5 -5] [-5 -5] Funktionsvärde: -11.1562 -11.1563 Lösningspunkt X1: -2.25225 -2.25 X2: -3.06234 -3.0625 Antal iterationer: 9 1 Metod: BL Newton 1 steg Startpunkt: [0 5] [0 5] Funktionsvärde: -11.1562 -11.1563 Lösningspunkt X1: -2.24983 -2.25 X2: -3.06249 -3.0625 Antal iterationer: 5 1 b) Punkten[-2.25 -3.0625] är ett globalt minimum ty Hessianen är posdef => konvex funktion. c) Funktionen är uppbyggd så att newtons metod tar oss dit på en iteration Ty steget p = inv(hess f(x)) * grad f(x) = 0 efter första iterationen. 2. a) Metod: BL Newton 1 Newton Mod Newton Marq Startpunkt: [-1.5 -1] [-1.5 -1] [-1.5 -1] [-1.5 -1] Funktionsvärde: 0.0015742 2.9716e-25 1.6535e-09 1.6535e-09 Lösningspunkt X1: 0.960329 1 1.00002 1.00002 X2: 0.922164 1 1.00003 1.00003 Antal iterationer: 201 5 12 12 b) Funktionen är lokalt konvex kring punkten [1 1] ty egenvärdena till hessianen i denna punkt är >0. Det optimala värdet till denna funktion är 0 vilket åtminstånde newton1 får även Newton -Mod och -Marq kan vara 0 eftersom de värden vi får där kan bero numeriska felräkningar av matlab. c) Lösningspunkterna hamnar kring [1 1] och med funktionsvärde ~0 för de punkter vi testade. Newtons modifierade gick mot optimum med minskande funktionsvärde hela vägen dit medans newtas med steg 1 ibland ökar och ibland minskar sitt funktionsvärde innan den når optimum. Bl fungerar som newtons modiefierade men tar mycket kortare steg åt gången vilket ger långsam lösning. 3. a) Metod: BL Newton 1 Newton Marq Startpunkt: [0 0] [0 0] [0 0] Funktionsvärde: -58 x -58 Lösningspunkt X1: 2.99978 x 3 X2: 0.99993 x 0.999999 Antal iterationer: 4 x 3 Hessianen är ej positivt definit i punkten [0 0] => newton ej kan räkna ut optimum medan Marquart gör den posdef genom att höja egenvärdena med alfa som gör den posdef vilket garanterar att vi får en descentriktning och kan räkna ut optimum. b) Vi testade punkten [-3 -1] vilket var en stationär punkt ty gradienten=0. 2 stationära punkter en maximipunt och en minimipukt. Del II 1. a) Det optimala värdet vi får När vi startar i punkten X0=[0 0] ligger det optimala värdet -1.5625 i punkten X*=[0.625 1.25]. b) För att vi ska kunna använda KKT villkoren så måste målfuntionen vara på min form så vi multiplicerade målfuktionen med -1. 1) Primal tillåtenhet. x1² - x2 <= 0; 2*x1 - x2 >=0; 2) Komplementaritet. (lambda = l) l1*(x1² - x2) = 0; l2*(2*x1 - x2) = 0; l1,l2 >=0; 3) Dual tillåtenhet Ställ upp Lagrange funktionen och derivera. Vi får nedanstående funktioner. Villkor 1: -1 + 4*x1 - x2 + 2*l1*x1 - 2*l2 = 0; Villkor 2: -2 + 2*x2 - x1 -l1 + l2 = 0; Vi kollar nu att dessa uppfylls. Vi får enligt komplemetariteten l1=0; l2=0.125; l1,l2 >=0 KKT uppfylls och vi får ett globalt max om problemet är konvext. Återstår att kolla konvexitet. Undersöker målfunktionens och de båda bivillkorens respektive Hessianer. Vi får att målfunktionens hessian blir [4 -1;-1 2]. Denna är konstant, samt har egenvärden > 0 => posdef. => strikt konvex. Vi får att bivillkor1s hessian blir [-2 0;0 0]. Denna är konstant, samt har egenvärden >= 0 => negsemidef. => konkav. Vi får att bivillkor2s hessian blir [0 0;0 0]. Denna är konstant, samt har egenvärden >= 0 => negsemidef. => konkav. Alltså har vi ett globalt optima. 2. Punkterna [0 0] => matlab kunde ej hitta ngn giltig lösning. [1 1] => X*=[3.4 1.2] med funktionsvärdet 3.4; [-1 -1] => X*=[-3 -2] med funktionsvärdet -3; [3.7 0] => X*=[3.6056 0] med funktionsvärdet 3.6056; [-1 1] => X*=[-3 -2] med funktionsvärdet -3; [1 -1] => X*=[-3 -2] med funktionsvärdet -3; [9 3] => X*=[3.4 1.2] med funktionsvärdet 3.4; [4 4] => X*=[3.4 1.2] med funktionsvärdet 3.4; Vi observerar att så fort ngn av invariablerna är negativa så går vi mot samma optimala punkt. Den mest optimala punkt vi erhåller är -3; Garanti av globalt minimum: Eftersom målfunktionen är linjär är den konvex. Båda bivillkoren är av grad 2 vilket ger att hessianen kan användas för undersökning av konvexitet det visar sig att hessianen för båda bivillkoren är [2 0;0 2] samt har egenvärden som är strikt negativa vilket ger att båda bivilkoren är konkava. Detta ger att problemet är Konvext vilket garanterar globalt minimum. Del III 1. Exempel2 Yttre straffmetoden => punkterna. [0.68 0.75]; [0.44 3.165]; [3.2222 0.7495]; Innre straffmetoden => punkterna. [3.2222 0.7512]; [0.6826 0.7504]; Exempel3 Yttre straffmetoden => punkterna. [-3.5356 3.5356]; Innre straffmetoden => punkterna. [-3.5196 3.5511]; [3.518 -3.5527]; 2. Vi sätter in erhållna punkter i målfunktionen och undersöker vad det är för punkter. Exempel2 (definithet svår att kolla ty hessianen inehåller funktioner av x) Yttre straffmetoden => punkterna => Funktionsvärdet => optimum. [0.68 0.75] Funktionsvärdet = 0.9388; lokalt optimum [0.44 3.165] Funktionsvärdet = 0.1133; globalt optimum [3.2222 0.7495] Funktionsvärdet = 0.2512; lokalt optimum Inre straffmetoden => punkterna => Funktionsvärdet. [3.2222 0.7512] Funktionsvärdet = 0.2533; lokalt optimum [0.6826 0.7504] Funktionsvärdet = 0.9423; lokalt optimum Exempel3 (indefinit funktion ty hessianes egenvärden antar både -1 och 1) Yttre straffmetoden => punkterna => Funktionsvärdet. [-3.5356 3.5356] Funktionsvärdet = -12.5005; lokalt optimum ty samma optimum på 2 ställen Inre straffmetoden => punkterna => Funktionsvärdet. [-3.5196 3.5511] Funktionsvärdet = -12.4985; lokalt optimum ty samma optimum på 2 ställen [3.518 -3.5527] Funktionsvärdet = -12.4984; lokalt optimum ty samma optimum på 2 ställen 3. Se funktions värdena i uppgigt2.