grupp: 34
namn1: Jonas Andersson
namn2: Freyr Hermannsson
************************************************************
Tillämpad optimering TM, Lab2
Jonas Andersson, 780816-3310, kf97anjo@chestud.chalmers.se
Freyr Hermannsson, freyzi@hi.is


Del I

Uppgift 1a

Brantaste lutningsmetoden:

Startpunkt: x=[10 10]
Funktionsvärde: -11.1562
x*=[-2.2491 -3.06255]
Antal iterationer: 9

Startpunkt: x=[-5 -5]
Funktionsvärde: -11.1562
x*=[-2.25225 -3.06234]
Antal iterationer: 9

Startpunkt: x=[-2.25 3.0625]
Funktionsvärde: -11.1562
x*=[-2.25 -3.0625]
Antal iterationer: 1

Newtons metond med steglängd 1:

Startpunkt: x=[10 10]
Funktionsvärde: -11.1562
x*=[-2.25 -3.0625]
Antal iterationer: 1

Startpunkt: x=[-5 -5]
Funktionsvärde: -11.1562
x*=[-2.25 -3.0625]
Antal iterationer: 1

Startpunkt: x=[-2.25 3.0625]
Funktionsvärde: -11.1562
x*=[-2.25 -3.0625]
Antal iterationer: 1


Metoderna konvergerara mot punkten x*=[-9/4 -49/16].


Uppgift 1b

Lösningspunkten är ett globalt optimum, ty f(x1,x2) är en konvex funktion.


Uppgift 1c

För en kvadratisk konvex funktion gäller att steglängden är
1. f(x1,x2) är en kvadratisk konvex funktion och således konvergerar
alltid Newtons metod i en iteration.


Uppgift 2a

Startpunkt=[-1.5 -1]
Metoderna konvergerar mot punkten x*=[1 1]. f(x*)=0

Antal iterationer:

BL: > 200, dvs mer än maximalt antal iterationer vi kan välja i programmet. 

Newton (steglängd 1): 5

Newton modifierad: 13

Newton, LM-modifierad: 13


Uppgift 2b

Funktionen är inte konvex.
Den erhållna punkten är ett globalt optimum (minimum), ty f(x)>=0.


Uppgift 3a

Startpunkt x=[0 0] gav med BL lösningen x*=[2.99978 0.99993]. Denna
lösningspunkt är ett lokalt optimum.

Newtons metod (med steglängd 1) fungerar inte i startpunkten x=[0 0],
ty hessianen är ej inverterbar i denna punkt.

LM-modifieringen fungerar och ger lösningspunkten x*=[3
0.999999]. Denna metod fungerar eftersom hessianen transformeras så
att den blir inverterbar.

Uppgift 3b

Startpunkterna x=[-4 -4], x=[-4 4] och x=[4 -4] ger lösningspunkten
minus oändligheten. x=[4 4] ger det lokala optimumet x*=[3 1]. Det
finns en stationär punkt vid x=[-3 -1] som är ett lokalt maximum. Om
vi börjar i denna punkt så stannar vi där, ty gradienten är noll.


Del II

Uppgift 1a

Låt tex startpunkten vara x0=[1 1]. Skriv i matlab
"x=fmincon('upg1f',x0,[],[],[],[],[-inf,-inf],[inf,inf],'upg1g')" så
fås den optimala lösningen x=[0.6250 1.2500].

Uppgift 1b

max f(x) = min -f(x)

Lagrangefunktionen (för motsvarande minproblem): 

L(x,lambda)=-x1+2*x1^2-2x2+x2^2-x1*x2-lambda1*(x2-x1^2)-lambda2*(2*x1-x2)


KKT-villkor:

Primal tillåtenhet:

x1^2-x2 <= 0
2*x1-x2 >= 0

Komplementaritet:

lambda1*(x2-x1^2) = 0
lambda2*(2*x1-x2) = 0

Dual tillåtenhet: 

4*x1-1-x2+2*lambda1*x1-2*lambda2 = 0
2*x2-2-x1-lambda1+lambda2 = 0

lambda1, lambda2 >= 0


Bivillkoren g1(x)=x2-x1^2>=0 och g2(x)=2*x1-x2>=0 är konkava och -f(x)
är en konvex funktion, ty -f(x) är positivt definit. Den erhållna
lösningen i uppgift 1a är en KKT-punkt. Således är den erhållna
lösningen i uppgift 1a ett globalt minimum till problemet att minimera
-f(x) under de två bivillkoren. Och härav följer att lösningen i
uppgift 1a är ett globalt maximum till problemet att maximera f(x)
under de två bivillkoren.

Uppgift 2

Ange x0 och skriv i matlab
"x=fmincon('upg2f',x0,[],[],[],[],[-inf,-inf],[inf,inf],'upg2g')".

Följande resultat fås

x0=[0 0] => x=[0 0]. Ej tillåten lösning. Bivillkoren ej uppfyllda.
x0=[1 1] => x=[3.4 1.2]. Bivillkor 1 och 2 är aktiva. Lokalt minimum.
x0=[-1 -1] => x=[-3 -2]. Bivillkor 1 och 2 är aktiva. Globalt minimum.
x0=[3.7 0] => x=[3.6056 0]. Bivillkor 2 aktivt. Lokalt minimum.
x0=[4 0] => x=[-3 -2]. Bivillkor 1 och 2 är aktiva. Globalt minimum.

Den bästa punkten är x=[-3 -2].  Vi kan inte garantera globalt
minimum, ty problemet är ej konvext. Bivillkor 2,
g2(x)=x1^2+x2^2-13>=0, är ej konkav.


Del III

Uppgift 1

Yttre straffmetoden (EPA):

Problem 2 konvergerar mot punkten x=[0.44 3.16] eller x=[0.68 0.75]
eller x=[3.22 0.75] beroende på vilket värde på p man börjar på och
hur mycket man succesivt ökar detta värde.

Problem 3 konvergerar mot punkten x=[3.53 -3.53].

Inre straffmetoden (IPA): 

Problem 1 konvergerar mot punkten x=[2 1].
Problem 2 konvergerar mot punkten x=[3.22 0.75].
Problem 3 konvergerar mot punkten x=[3.53 -3.53].

Uppgift 2

Problem 1 konvergerar i båda metoderna mot punkten x=[2 1], som är ett
globalt minimum.

Problem 2 konvergerar mot ett lokalt minimum.
Problem 3 konvergerar mot ett lokalt minimum.

Uppgift 3

Problem 1 har ett globalt minimum i x=[2 1], ty x=[2 1] är en
KKT-punkt och vi har ett konvext problem. Problem 2 och 3 saknar
globala minimum.