grupp: 51
namn1: Tobias Fries
namn2: Jonas Karlsson
************************************************************
Laboration 2 -Tillämpad optimering (Olinjär optimering)
Labgrupp 51 (top02-51)
Tobias Fries   md9frito@mdstud.chalmers.se
Jonas Karlsson md9karjo@mdstud.chalmers.se

Del1
Uppg.1
a)
  BL:     (10,10) #iter=9 x*=(-2.2491 ,-3.06255)
          ( 5, 5) #iter=8 x*=(-2.24945,-3.06191)
          ( 0, 0) #iter=7 x*=(-2.24945,-3.06253)

  Newton: (10,10) #iter=1 x*=(-2.25,-3.0625)
          ( 5, 5) #iter=1 x*=(-2.25,-3.0625)
          ( 0, 0) #iter=1 x*=(-2.25,-3.0625)

b)
  Enligt grafen är punkten ett globalt min. Vi ser att funktionen är konvex
  (Hessianens egenvärden > 0) och därmed är en lösning ett optimalt min.

c)
  Att Newton konvergerar i ett steg beror på att det är en kvadratisk funktion
  och att Newton är en kvadratisk metod. (Newton bygger ju på den trunkerade
  Taylorserien till grad 2, vilken EXAKT beskriver ovanstående funktion.)

Uppg.2
a)
  BL:              (-1.5,-1) #iter=201 x*=(0.929581,0.863728)
                   ( 1  , 1) är det minimum som metoden strävar mot.

  Newton (steg=1): (-1.5,-1) #iter=5   x*=(1,1)
  Newton (modif.): (-1.5,-1) #iter=13  x*=(1.00002,1.00003)
  Newton (Marqu.): (-1.5,-1) #iter=13  x*=(1.00002,1.00003)

b)
  Nej, ty du kan inte ta dig från (-2,3) till (2,3) med ett steg utan att 
  'bryta' funktionsytan. (Det finns tangentplan som skär ytan.)
  Dock är (1,1) ändå ett unikt globalt optimum (f>=0).

c)
  BL:              Långsam konvergens. Har en tendens att fastna i 'rännan'.
  Newton (steg=1): Konvergerar alltid snabbt pga stora steg.
  Newton (modif.): Tar aningen längre steg än BL => snabbare konv.
  Newton (Marqu.): Tar aningen längre steg än BL => snabbare konv.

Uppg.3
a)
  BL:              #iter=4 x*=(2.99978,0.99993 )
  Newton (steg=1): 'Nästa iterationspunkt kan ej beräknas'.
                   ty Hessianen == 0 (singulär).
  Newton (Marqu.): #iter=3 x*=(3      ,0.999999)

b)
  ( 3, 1) : Lokalt min.
  (-3,-1) : Detta är dock ett lokalt max.
  (3 ,-1) : Sadelpunkt.
  (-3, 1) : Sadelpunkt.

Del2
Uppg.1
a)
  fmincon('upg1f',[10;-25],[],[],[],[],[-Inf;-Inf],[Inf;Inf],'upg1g')
  ger 'optimalvärdet' -1.5625 vid (0.6250,1.2500). Vid denna punkt är 
  ett bivillkor aktivt. Dvs. vårt problem får maxvärdet 1.5625.

b)
  Konvexitet/Optimalitet
  Hessianen=[4,-1;-1,2] => egenvärden > 0 => pos. def. => konvex målfunk.
  Hes(g1)  =[-2,0; 0,0] => egenvärden <=0 => neg. semidef. => konkavt
  Hes(g2) == 0. (konvex OCH konkav)
  Dvs, vårt problem är konvext, och därmed är en optimallsg ett globalt
  maximum.

  KKT
  Våra Lagrangemult. blir 0 resp. 0.125 >= 0 och de uppfyller
  grad(f)+sum(lambda(i)*grad(g(i))). x uppfyller villkoren. Nollmult.
  svarar mot det icke aktiva villkoret och omvänt.
  Härmed är KKT uppfyllt.

Uppg.2

  X(0)=(10,-25) => x*=(-3    ,-2)
  X(0)=(0,0)    => x*=(0     , 0)
  X(0)=(1,1)    => x*=(3.4   , 1.2)
  X(0)=(-1,-1)  => x*=(-3    ,-2)
  X(0)=(3.7,0)  => x*=(3.6056, 0)
  Kan ej garantera optimalitet ty def.mängden ej konvex => ickekonvext 
  problem. Dock verkar (-3,-2) vara ett lok.min.
  Man kan dock teoretiskt se att det är ett globalt min. ty randvillkoren
  är cirklar, och genom att beräkna deras skärningar får man extrempunkterna,
  eftersom målfunktionen är såpass 'lätt'.

Del3
Uppg.1

		 IPA          EPA
  Prob2 x1=    sin(3/4)   1+sqrt(79)/4
        x2=	 3/4	      3/4   

  Prob3 x1=   +-5/sqrt(2)  +-5/sqrt(2)
        x2=   -+5/sqrt(2)  -+5/sqrt(2)
  
Uppg.2

  I prob.1 har vi ett konvext prob. med konkava bivillkor. Därför kan vi
  garantera ett globalt min.

  I prob.2 har vi en indefinit målfunktion, vilket gör att vi inte kan lova
  att det är ett globalt optimum. Man skulle kunna kolla KKTvillkor för
  att se om punkten är ett lokalt min, vilket dock ser ganska jobbigt ut
  så vi nöjer oss med att konstatera att det ser ut att vara ett lok. min
  grafiskt.

  I prob.3 har vi en indefinit målfunktion, egenvärdena är +-1. Detta medför
  att problemet är ickekonvext och vi kan därför inte lova globalt optimum.
  KKT: Alla villkor aktiva. =>
  grad(f)+lambda1*grad(g1)+lambda2*grad(g2)=0 <=>
  [x2;x1]+lambda1*[2x1/5;2x2/5]+lambda2*[-1;-1]=0 <=>
  lambda1=-2.5
  lambda2= 0
  => ej KKT!
  Vi kan inte säga att punkten är ett lokalt optimum.
  (Grafiskt ser det dock ut att vara ett/två globalt min)

Uppg.3

  I prob.1 finns ett globalt min. [2;1]

  I prob.2 finns ett globalt max, (ung. [2;2])
  samt tre lokala min. [1/3;1+sqrt(41)/3], samt de två i uppg.1

  I prob.3 finns ett globalt max, [5/sqrt(2);5/sqrt(2)]
  och två globala min, de från uppg.1.