grupp: 9
namn1: Lasse Tunturivuori
namn2:
************************************************************
Lasse Tunturivuori
Grupp 9
Laboration 2, Tillämpad optimeringslära
Del 1
=====
Uppgift 1
---------
BL(10,10) kräver 9 iterationer. f(-2.2491,-3.06255)=-11.1562
NewMod(10,10) kräver 1 iteration. f(-2.25,-3.06249)=-11.1562
Marquardt(10,10) dito.
Newton1(10,10) dito.
BL(-5,-5) kräver 9 iterationer. f(-2.25225,-3.06234)=-11.1562
NewMod(-5,-5) kräver 1 iteration. f(-2.24994,-3.06246)=-11.1562
Marquardt(-5,-5) dito.
Newton1(-5,-5) dito. f(-2.25,-3.0625)=-11.1562
BL(6,-3.0625) kräver 1 iteration.
f i kvadratisk form och Hessianen pos.def.=> f globalt konvex => lok
min är glob min.
Taylorutvecklingen för gradienten av en kvadratisk funktion är exakt
med två termer. Newtons ekvation är därför inte approximativ och
Newtons metod hittar därför en stationärpunkt på en iteration. Fknen f
är kvadratisk (och f pos.def)=> stationärpunkt = lok min.
Uppgift 2
---------
BL(-1.5,-1) efter 200 iterationer f(0.929581,0.863728)=0.0049742
Newton1(-1.5,-1) konv efter 5 iterationer f(1,1)=2.9716e-25
NewMod(-1.5,-1) konv efter 13 iterationer
f(1.00002,1.00003)=1.6535e-09
Marquardt dito .
Ej konvex. Det ser man på utseendet eller genom att beräkna Hessianen
i ex. (0,0).
Kan inte säga huruvida optimat är globalt.
Uppgift 3
---------
BL(0,0) 4 iterationer, f(2.99978,0.99993)=-58
Marquardt 3 iterationer, f(3,0.999999)=-58
Vi hittar 4 st. stationära punkter.
En lok min, lok max samt två sadelpkter
Del 2
=====
Optimum i x = [0.625,1.25]^T.
KKT:
(Vi skriver om problemet till ett minimeringsproblem)
Dual tillåtenhet:
-1 + 4x1 - x2 + 2\lambda1 x1 - 2\lambda2 = 0
-2 + 2x2 - x1 - \lambda1 + \lambda2 = 0
\lambda1, \lambda2 >= 0
Komplementaritet:
\lambda1( x2 - x1^2) = 0
\lambda2(2x1 - x2) = 0
Primal tillåtenhet:
x2 - x1^2 >= 0
2x1 - x2 >= 0
Primal tillåtenhet uppfylld, komplementaritet uppfylld med \lambda1 =
0 och \lambda2 fri. Dual tillåtenhet uppfylld med \lambda2 =
0.125. M.a.o är x=[0.625,1.25] ett lokalt minimum till det omskrivna
minimeringsproblemet. Som i uppgiften givet är x ett lokalt maximum.
Om vi tittar på det minimeringsproblem som ovan, har vi en Hessian
[-4 1;
1 -2]
med strikt positiva egenvärden 3+-sqrt(2). Därmed är målfunktionen
konvex. x2 - x1^2 är konkav, varför mängden {x : x2 - x1^2 >= 0} är
konvex. En linjär funktion är alltid konkav, varför {x : 2x1 - x2 >=
0} är konvex. Unionen av konvexa mängder är konvex, varför hela
problemet är konvext. Därför är ett lokalt minimum även ett globalt
minimum. På så sätt är i det ursprungliga problemet optimat ett
globalt maximum.
Uppgift 2
---------
x | f
( 0, 0) | ( 0, 0) Metoden stannar där den är.
( 1, 1) | (3.4,1.2) Hittar rätt. (Antagligen)
( -1, -1) | ( -3, -2) Kommer inte förbi den ena cirkeln och "fastnar i
| ett lokalt min.
(3.7, 0) | (3.6, 0) Fastnar på cirkeln. Vid denna punkt är
tangenten vinkelrät med målfknens gradient.
Man kan väl inte _garantera_ ett globalt minimum om man inte studerar
geometriskt bivillkoren och målfunktionen, men om man exvis ritar upp
randen till det tillåtna området, ser man tydligt att (-3,-2) är ett
globalt minimum.
Del 3
=====
Uppgift 1
---------
Ex 2:
IPA f(3.2219,0.7511)=0.2541
Ex 3:
IPA f(3.5523,-3.5184)=-12.498