grupp: 52
namn1: Viktor Fägerlind
namn2: Bekim Rabushaj, Johannes Reesalu
************************************************************
Redovisning av lab2.

Johannes Reesalu
Viktor Fägerlind
Bekim Rabushaj


--------------------------------------------------
DEL 1
--------------------------------------------------
upp1.
a)
Startp.		= (10, 10)	(-5, -5)	(-7, -8)

#iter.
	BL	= 8		8		7
	Newton	= 1		1		1

Konvergensp.	= (-2.25, -3.06)

b)
Funktionens Hessian är pos. def. =>
ger att funktionen ar konvex, dvs lokalt min = globalt min.

c) 
Newtons metod löser 2-gradens taylorutveckling i 1 iteration eftersom
en 2-gradens funktions 2-grads taylorutveckling är samma som funktionen
själv hittas optimum i 1 steg.

--------------------------------------------------
upp2.
a)
Startp.			= (-1.5, -1)

#iter.
	BL		= 200+
	NewtonMod	= 13
	NewtonMarq.	= 13
	Newton		= 5

Konvergensp. BL		= obestämd
Konvergensp. NewtonMod	= (1.00002, 1.00003)
Konvergensp. NewtonMarq.= (1.00002, 1.00003)
Konvergensp. Newton	= (1, 1)

Allmänt ser man att Newtons(steg1) metod konvergerar snabbast.
BL konvergerar aldrig.


b)
Man ser direkt att funktionen inte är konvex eftersom man kan dra en linje
mellan två punkter på funktionens yta så att linjen skär ytan!

c)
Startp.1	(1, 1)
Startp.2	(2, 3)
Startp.3	(3, 0)
Metoderna uppför sig som i a).

--------------------------------------------------
upp3.
a)
Newtons metod fungerar inte därför att Hessianen till 
funktionen inte är inverterbar i punkt (0,0).
N-Marquardts metod fungerar utmärkt. Konvergerar på 3 iterationer.

b)
4 st.

( 3, -1) Sadelp.
( 3,  1) Minp.
(-3, -1) Maxp.
(-3,  1) Sadelp.

--------------------------------------------------
DEL 2
--------------------------------------------------
upp1.
a)
Lösning x* = (0.6250, 1.2500)

b)
primal feas:
g1(x) = -x1^2 + x2 >= 0 => g1(x*) =  0.8594 > 0 OK!
g2(x) = 2x1   - x2 >= 0 => g2(x*) =  0          OK! (aktivt)

complementary feas:
lam^T * g(x*) = 0 => lam1 = 0
		      
dual feas:
I)  L(x, lam) = f(x) - lam^T*g(x) 
   
    grad(f)     = [-1 + 4*x1 - x2 ; -2 + 2*x2 - x1]
    grad(f(x*)) = [0.25 ; -0.125] 
    grad(g2) = [2 ; -1]
    grad_x(L)  = 0 =>
    [2 ; -1] * lam2 =  [0.25 ; -0.125]  => lam2 = 0.125
   
II) lam = [0 ; 0.125] >= 0	=> KKT UPPFYLLT!!!!

konvexitet:
   hess(f)  = [4 -1 ; -1 2] => eigenV > 0 => strikt positivt definit
   => f strikt konvex

g1 konkav 
ty hess(g1) = [-2 0; 0 0] är negativt semidefinit
g2 (linjärt bivillkor, dvs. är g2 både konkav och konvex) 
Eftersom g1 och g2 är konkava och > villkor kommer mängden att bli
konvex. 
Mängden och funktionen är konvex vilket innebär att problemet i sig är konvext.
Problemet är konvext och punkten uppfyller KKT vilket leder till att 
punkten är ett globalt maximum.

--------------------------------------------------
upp2.
a)
Eftersom vi fick flera olika stationära punkter misstänkte vi 
att det rörde sig om ett ickekonvext problem. Vi testade därför
bivillkoren för att kontrollera huruvida de är konvex eller konkav. 
Att g1 är strikt negativt definit fick vi genom att kontrollera hessianen.
På samma sätt fick vi att g2 var strikt positivt definit. 
Detta innebär att mängden ej är konvex och således är problemet ej heller 
konvext.  
Alltså kan vi ej garantera globalt min enbart med hjälp av KKT.

Om man däremot ritar upp mängden som två cirklar, som ges av g1, g2,  där 
man skall hålla sig utanför den ena (g2)  och innanför den andra (g1) ses 
lätt att punkten (sqrt(13), 0) är globat minimum!
--------------------------------------------------
DEL 3
--------------------------------------------------
upp1.
yttre straffmetoden:
problem 2 -> punkterna (3.2, 0.7)  och (0.3, 3.1)  
problem 3 -> punkterna (3.7, -3.7)

inre straffmetoden>:
problem 2 -> punkterna (0.7, 0.7)
problem 3 -> punkterna (-3.7, 3.7)

Algoritmen skulle kanske kunna konvergera mot fler punkter, men vi fann 
inga fler.

upp2.
Metoderna konvergerar mot lokala minima. 

upp3.
Genom att studera funktionernas bilder fick vi:

Globalt min för ex2: ca (0.3, 3.1)
Globalt min för ex3: ca (3.7, -3.7) och (-3.7, 3.7)