grupp: 27
namn1: Anders Mattson
namn2: Goran Johnsson
************************************************************
Lab 2 - Grupp 27	Anders Mattson, Göran Johnsson


Del 1

1.
   a)	BL-metoden

		Startpunkt: (10,10)		(-5,-5)			(10,-5)
	   konvergenspunkt: (-2.2491, -3.06255)	(-2.25225, -3.06234)	(-2.24885, -3.06266)
	      #Iterationer:    9		   9			  16

	Newton-metoden (steg=1)

		Startpunkt: (10,10)		(-5,-5)			(10,-5)
	   konvergenspunkt: (-2.25, -3.0625)	(-2.25, -3.0625)	(-2.25, -3.0625)
	      #Iterationer:    1		   1			  1
	
   b)	I Newtons metod är det både lokalt och globalt min (se uppg. c) nedan), 
	men inte exakt i BL-metoden (inte samma som i Newtons metod).

   c)	Därför att funktionen är kvadratisk, och alltså kan skrivas på formen

		f(x) = 1/2 * x' * Q * x - c'x + d, x = [x1, x2]

				| 4  0 |
	där Q är matrisen 	|      | och c och d är konstant-vektorer.
				| 0 16 |

	Nu är (v(f) är samma som Grad(f)):

		v(f)  = Q * x - c
	och	v2(f) = Q

	Newtons metod är som följer:

		p1 = p0 - (v2(f(p0))^(-1) * v(f(p0))	= 

		   = p0 - Q^(-1) * (Q * p0 - c) = Q^(-1) * c

	Detta ger v(f) = 0, 	alltså lokal min.-punkt

	Dessutom v2(f) = Q <- pos def. alltså global min.-punkt.

	p1 är alltså en min.-punkt till ekvationen.


2.
   a)			     konvergenspunkt		#Iterationer

	   BL-metoden:	     (0.96,0.92)		Max antal (200)
     Newton(Steg = 1):       (1,1)			5
     Newton(modifier):	     (1,1)			13
    Newton(Marquardt):	     (1,1)			13


   b)  Funktionen ar inte konvex, och i och med detta sa vet vi inte heller
       hur den upptrader globalt.


   c)  BL-metoden beter sig en aning underligt. Till exempel om man startar
       i punkten (-1,1), sa gor iterationspunkterna ett hopp nagonstans mellan
       150:e och 160:e iterationen. Det verkar som om det beror pa ett matfel.


3.
   a)
       BL-metoden konvergerar efter 4 iterationer till punkten (3,1).
       Newtonmetoden anvander sig av Hessianen for att berakna nasta
       iterationspunkt, men i just denna punkt ar Hessianen en nollmatris, 
       vilket gor att Newtonmetoden inte kan fortsatta.
       Med Levenberg-Marquardt-metoden sa "modifieras" matrisen med hjalp av
       en diagonalmatris. Detta gor att matrisen blir nollskild, och metoden
       fungerar.

   b)
       Vi hittar fyra stationara punkter.

       Stationara punkter:	(3,1)		(-3,-1)		(-3,1)		(3,-1)
		      Typ:	lok min		lok max		sadelpunkt	sadelpunkt

Del 2

Uppg 1.

 a.  Losningen som erholls blev f(x) = 1.5625,
     i punkten x1 = 0.625 , x2 = 1.25.

 b.  Alla funktioner ar C2, x* = [0.625 1.250].

  I:
     x* insatt i bivillkor 1 ger: 0.625^2-1.25 <= 0 OK!
     x* insatt i bivillkor 2 ger: 2*0.625-1.25  = 0 OK! (aktivt)

  II:
     (l = lambda)
     
     [l1 l2]*[0.625^2-1.25 0] = 0 ger att l* = [0 l2].

  III:
     (obs, alla berakningar gors pa -f(x), alltsa ekvivalenta min-problemet)
     
     L(x,l*) = f(x) - [0 l2]*[(x2-x1^2) (2*x1-x2)] = f(x) - l2(2*x1-x2)

     gradx(L(x,l*)) = [(-1+4*x1-x2-2*l2) (-2+2*x2-x1+l2)]
     gradx(l(x*,l*)) = 0 => l2 = 0.125   OK!

  IV:
     l* = [0 0.125] >= 0  OK!

  v:
     gradx(gradx(L(x*,l*))) = |4 -1| , denna matris ar pos.definit, ty
                              |-1 2|   egenvardena ar +-sqrt(2)+3>0. OK!
     
  Konvexitet:
  
     f(x) = -x1+2*x1^2-2*x2+x2^2-x1*x2
     
     grad^2(f(x)) = |4 -1| , pos.defint. f(x) ar alltsa konvex.
                    |-1 2|     

     Vidare ar bade x1^2-x2<=0 och 2*x1-x2>=0 konvexa mangder,
     snittet mellan tva konvexa mangder ar konvex mangd.
     Problemet ar saledes konvext.

  Verifiering:

    Alla KKT-villkor uppfyllda & konvext problem => globalt optimum i x*.

Uppg. 2

      Vi loste problemet med "fmincon", och denna gav olika svar varje gang.
      

        Punkt:	(3.7, 0)	(sqrt(13) 0)	(0, sqrt(13)) (0, -sqrt(13))	(0, -3.7)
      Optimum:	3.6056		3.6056		3.4	      -3		-3

      Bivillkoren beskriver en manformad mangd, dar optimum ligger i nagon av spetsarna.
      Borjar vi i nagon tillaten punkt med x2 = 0, sa kommer metoden att terminera direkt,
      ty detta ar en stationar punkt (for ett visst varde pa x1). Startar vi pa endera
      sidan av x1-axeln sa kommer vi att "glida ner" till nagon av "spetsarna".
      Endast en av dessa ar ett globalt optimum. 

      Vi kan inte garantera globalt minimum ty, definitionsmangden ar inte konvex.


Del 3

Uppg 1

		Yttre (EPA)		Inre (IPA)

	Ex 2	(2.6, 2.6)		(3.2, 0.75)
	Ex 3	(0.707, -0.707)		(0.707, -0.707)

Uppg 2

	I fallet med ex. 3 finns 2 identiska lokala optima, som ar antipodala. Bada
	metoderna konvergerar mot samma lokala optimum. Antagligen ligger startpunkten
	nagot narmare detta optimum.

	I ex. 2 konvergerade EPA-metoden mot en lokal sadelpunkt. Troligen beror detta pa
	att startpunkten ar illa vald. Det finns tva lokala min, som finns dar bivillkor
	g4 och g1 resp. g3 ar aktiva.

Uppg 3

	For ex 1 och 2, se uppg 2. I ex 1 ar endast punkten (2, 1) optimal.