grupp: 28
namn1: Elin Göransson
namn2: Agneta Johansson
************************************************************
Del I: Obegränsad optimering; MATLAB med grafik

Uppgift 1:

a)

Brantastelutningsmetoden med startpunkt (10,10) konvergerar mot 
(-2.2491,-3.06255) efter 9 iterationer. 

Newton med steglängd 1 med startpunkt (10,10) konvergerar mot (-2.25,-3.0625)
efter endast 1 iteration. 

Om vi istället startar i (5,5) får vi konvergens mot samma punkter. Newton gör det 
fortfarande på 1 iteration, men BL har minskat till 8 iterationer.

Vi väljer en egen startpunkt (-3,-4). Detta ger konvergens mot samma punkter. 
Newton klarar det fortfarande på 1 iteration, men BL har nu minskat till 6 då vi kommit 
närmare optimalvärdet.

b) Erhållen lösningspunkt är ett optimalt globalt minimum.

c) Newton konvergerar alltid i en iteration i detta fall för att funktionen 
är konvex och kvadratisk. På grund av detta är hessianen konstant.

Uppgift 2:

a) BL konvergerade ej efter 200 iterationer. Den fastnade nära startpunkten (1.5,-1) i 
(1.01393,1.02814)

Newton med steglängd 1 konvergerade efter 3 iterationer  mot (1.00039,1.00077)

Newtons modifierade metod konvergerade efter 6 iterationer mot punten (0.999986,0.999973), 
Levenberg- Marquardts modifiering konvergerar mot samma punkt efter samma antal iterationer.

b) Funktionen är konvex. Den ergållna punkten är inget globalt minimum.

c) BL: (0,3); (på puckeln) tar ett stort steg och går mot samma punkt som i a). 
(-1,-0.5); går mot punkten (0.999667, 0.999345)
(1,-0,5); går först åt "fel håll", men går sedan till den i a) erhållna punkten.  

Newton med steglängd 1: (0,3); går ingenstans, står på en stationär punkt. 
(-1,0.5); går mot (1,1) efter 5 iterationer. Letar inte efter min, utan stationära punkter.

Newtons modifierade metod: (0,3); gå ingenstans, står ju i en stationär punkt.
(-1,-0.5); går i riktningen med störst gradient, följer sedan nivåkurvorna till (1,1), tog 
12 iterationer.

LM: (0,3); klarar av att ta sig härifrån, går i brantaste riktningen och följer sedan 
nivåkurvorna till (1,1).
(-1,-0.5) följer även i detta fall nivåkurvorna till (1,1). 

Uppgift 3:

a) Startar i (0,0)

BL hittar ett lokalt min i (2.99978, 0.99993) efter 4 iterationer. 

Newton med steglängd 1 fungerar inte. Vi står i en sadelpunkt som ju är en stationär punkt. 

LM konvergerar mot punkten (3,0.999...) efter 3 iterationer.

b) Vi hittade 5 stationära punkter. En lokal max-punkt, 3 sadelpunkter och en min-punkt.


Del II: Begränsad optimering; MATLAB:s Optimization Toolbox

Uppgift 1:

a)

x = (0.6250,1.2500)
f = 1.5625

b)

Primal tillåtenhet:

g1(x) = x1^2 - x2 = -0.8594 < 0 ok
g2(x) = 2x1 - x2 = 0 ok

Komplementaritet:

lambda1 = 0 ty g1 < 0

Dual tillåtenhet:

L(x,lambda) = 0
grad f(x) = (-1 + 4x1 - x2 , -2 + 2x2 - x1) = (0.25 , -0.125)
grad g2(x) = (2,-1)
Finn lambda2 så att
grad f - lambda2 * grad g2 = 0
=>lambda2 = 0.125
lambda = (0 , 0.125) >= 0 KKT-villkor uppfyllda!

Konvexitet hos problemet:

Undersök hessianerna till f och g
grad^2 f  = konstant, positivt definit => f konvex
grad^2 g2 = 0 = konstant negativt semidefinit => g2 konkav
grad^2  g1 = konstant positivt definit => g1 konvex
X = {x | g1(x) =< 0 , g1(x) >= 0} konvex mängd ty g2 konkav och g1 konvex
f är konvex och ska minimeras => konvext problem

KKT tillräckligt för att garantera globalt minimum!

Uppgift 2:

Vi löste problemet mha fmincon 6 gånger från olika startpunkter.

(0,0):	x = (-3 , -2),  f(x) = -3, biv 1 aktivt
(1,1): 	x = (3.4 , 1.2), f(x) = 3.4, biv 1 och 2 aktiva
(-1,-1):   x = (-3 , -2), f(x) = -3, biv 1 och 2 aktiva
(3.7,0):   x = (3.6056 , 0) och f(x) = 3.6056, biv 2 aktivt
(10,10):   x = (3.4 , 1.2) och f(x) = 3.4, biv 1 och 2 aktiva
(-10,-10): x = (-3 , -2) och f(x) = -3, biv 1 och 2 aktiva

Vi finner att punkten x = (-3 , -2) är den bästa. Vi kan dock inte garantera globalt minimum eftersom 
problemet inte är konvext.
grad^2 g1 = konstant, positivt definit => g1 konvex. (om mängden ska vara konvex måste g1 vara konkav och g2 konvex)
Man kan undersöka alla KKT-punkte och se om det finns någon bättre, om man vill vara säker på globalitet.


Del III: Begränsad optimering; Straffunktionsmetoder

Uppgift 1:

Vi använde båda metoderna på problem 2 och 3.
Problem 2
EPA konvergerade mot x = (0.75 , 0.75)
IPA konvergerar inte mot något x. Finns inget tillåtet.
Problem 3
EPA och IPA konvergerar mot samma punkt, x = (3.5 , -3.5)

Uppgift 2 och 3:

För problem 2 konvergerar EPA mot en icke tillåten punkt. Det tillåtna området är en tom mängd. 
Alltså existerar inga optima. IPA fastnar i startpunkten.
För problem 3 konvergerar båda metoderna mot ett av två globala min, x = (3.5 , -3.5). 
Den andra min-punkten är x = (-3.5 , 3.5) Båda punkterna ger samma funktionsvärde och det 
existerar inga punkter med lägre funktionsvärde. Alltså är de globala min.