grupp: 30 namn1: Tor Johansson namn2: ************************************************************ Laboration 2, 020228 - 020307 Tor Johansson 641113-7133 Del I: Obegränsad optimering Som avbrottskriterie används defaultvärdet (gradientlängd 0.0001) om inget annat nämns. 1a) BL (Brantaste Lutningen) ger vid startpunkt (10,10) att f(x)= -11.1562 x1= -2.2491 x2= -3.06255 efter 9 iterationer. Vid startpunkt (-5,-5) erhölls istället x1= -2.25225, x2= -3.06234 efter 9 iterationer. Newton (m steg=1) ger vid startpunkt (10,10) f(x)= -11.1562 x1= -2.25 x2= -3.0625 efter 1 (!) iteration. Dessutom gav startpunkt (-5,-5) ett identiskt resultat efter lika många iterationer. b) Ser att funktionen är konvex, ty Hessianen kommer att bli positivt definit (med diagonalelementen 4 & 16). c) Därför att Hessianen blir 4 0 0 16 och vid beräkningen av sökriktningen p i x_k+1 = x+k - p kommer p att bli den skalning av gradienten som ger konvergens direkt. p = inv(H) * grad(f). Det är så Newton jobbar då steg=1! 2a) En snabb jämförelse ger: Metod f(x) x1 x2 iterationer --------------------------------------------------- BL 0.00495 0.92967 0.86403 201 N, steg=1 3.0e-25 1 1 5 N, modifierad 1.7e-09 1.00002 1.00003 13 N, Marquard -"- -"- -"- -"- b) Lite deriverande ger Hessianen: 1200x1^2-400x2-2 -400x1 -400x1 200 där vi kan använda kravet att varje uppåt-till-vänster submatris måste ha en determinant > 0 för att matrisen ska vara positivt definit. Alltså måste elementet a_11 vara > 0, vilket inte är sant för alla x1, x2. Alltså är inte funktionen nödvändigtvis konvex. Å andra sidan ser man ju i bilden att funktionen inte är konvex här.. Ej konvex funktion => vi kan inte veta om vi har ett globalt min. Men ser istället att funktionens paranteser ju är kvadrerade, dvs >= 0. Alltså är funktionens minsta värde noll och vi har ett globalt min. c) Studerar metodernas uppförande. Noterar att N, modifierad använder samma sökriktning som vid steg=1, i första itera- tionen. Modifieringen av steglängden ger en "säkrare" men längre väg till minimat. 3a) Vi har en lasagne-liknande funktionsyta. BL ger vid startpunkt (0,0) f(x)= -58 x1= 2.99978 x2= 0.99993 efter 4 iterationer. Newton (m steg=1) ger ingen nästa iterationspunkt. Detta beror förmodligen på att Hessianen är 6x1 0 0 12x2 och alltså blir 0 i startpunkten (0,0). Quasi-Newton- metoder som konstruerar en positivt definit matris, en "Nästan-Hessian" klarar detta: Newton-Marquard ger f(x)= -58 x1= 3 x2= 0.999999 efter 3 iterationer. b) Sadelpunkt vid (3, -1). Lokalt max vid (-3, -1). Del II: Begränsad optimering 1a) fmincon ger med x0=(0,0): f(x)= -1.5625 x1= 0.6250 x2= 1.2500 efter 3 iterationer. Olika startpunkter gav samma resultat. b) KKT-villkoren (nödvändiga villkor för lokalt optima) tecknas: Skrev om maximera f(x) till minimera -f(x), ställde upp Lagrange- funktionen, och dess gradient. Obs att bivillkoren blir: g_1: -x1^2 + x2 >= 0 g_2: 2x1 - x2 >= 0 DUAL TILLÅTENHET. Finns lambda så att Lagrangefunktionens gradient = 0 ? Punkten x*=(x1, x2) från a) sattes in och gav ekvationssystemet 0.2500 + 1.25 lamb1 + 2 lamb2 = 0 -0.1250 - lamb1 - lamb2 = 0 med lösningen lambda_1 = 0, lambda_2 = -0.125 KOMPLEMENTARITET. Finns lambda så att lambda * g(x*) = 0 ? g_1(x*) = 0.8594 g_2(x*) = 0 ger följande krav på lambda => lambda_1 = 0, lambda_2 = godtyckligt värde PRIMAL TILLÅTENHET. Är g(x*) >= 0 ? Svar ja, enl ovan! Är då problemet konvext? Målfunktionen -f(x):s Hessian är 4 -1 -1 2 och alltså pos definit => -f(x) konvex Ser att g_1 konkav och g_2 konkav(och konvex, ty linjär). Alltså är problemet konvext och optimat globalt! 2) Startpunkt fmincon:s svar ------------------------------------------------------------- (0 ,0) No feasible solution found (1 ,1) x = ( 3.4000, 1.2000 ) (-1 ,-1) x = ( -3.0000, -2.0000 ) (3.7, 0) x = ( 3.6056, 0.0000 ) "No feasible.." tror jag har ett samband med att algoritmen nu inte får någon Hessian att förbättra? x*= (-3, -2) minimerar x1. Punkten ger det nedre hörn där det lutande planet x1 begränsas av båda cirkelprojektionerna g_1 och g_2. f(x) konvex (linjär), men kan inte visa att bivillkoren ger en konvex mängd. Del III: Begränsad optimering, straffunktionsmetoder 1) Algoritmerna konvergerar mot följande punkter (ungefärliga värden anges då huvudsyftet ju är att skilja dem åt) Problem Yttre straff Inre straff ------------------------------------------------------------------ (1) (2,1) (2) (0.5, 3.2) (3.2, 0.7) (0.7, 0.7) (3.2, 0.7) (3) (3.5, -3.5) (-3.5, 3.5) I problem (2) tycktes konvergensen bero på hur man hanterade ändringen av straffets storlek. 2) Båda metoderna konvergerade mot lokala optima 3) Optima till problemen: Problem Har lösningarna i punkten (~=) ------------------------------------------------------------------ (1) Ett, globalt, min (2,1) (2) Glob min (0.5, 3.2) Lok min (0.7, 0.7) Lok min (3.2, 0.7) (3) Lok min (3.5, -3.5) Lok min (-3.5, 3.5) (likvärdiga min)