LABORATIONSINFORMATION, LAB 2

TMA946 Tillämpad optimeringslära / MAN280 Optimeringslära

Michael Patriksson

18 februari 2002

Förberedelser

I del 2 finns vissa uppgifter vilka bör förberedas genom att formulera KKT-villkor före labben. Om Ni känner ett lätt obehag i närheten av datorer kan det dessutom vara bra att ha tittat på MATLABs optdemo före det handledda laborationstillfället.

Del I: Obegränsad optimering; MATLAB med grafik

I denna del ska ni lösa några obegränsade ickelinjära problem med hjälp av brantastelutningsmetoden (BL) och Newtons metod. Den senare finns i tre verioner: Newtons metod med steglängd 1 (den klassiska metoden), Newtons modifierade metod som innehåller en linjesökning, och Levenberg–Marquardts modifiering av den senare där egenvärdena hos Hessianen transformeras, vid behov, så att resultatet är en positivit definit matris. Metoderna är implementerade i programsystemet MATLAB. Syftet med laborationen är att grafiskt illustrera metoderna och ge insikter i hur de uppför sig.

Uppstartningsförfarande: Hämta tar-filen från kursens hemsida, och utför instruktionerna som där ges. Flytta till mappen ILP (utför cd ILP), och ge kommandot matlab. (Om detta inte fungerar omedelbart, använd rcopt för att se till att ni har tillgång till matlab.) När MATLAB-fönstret öppnats, skriver ni ilpmeny däri.

Laborationen är menystyrd och i stort sett självinstruerande. Följande val och inställningar kan göras:

Inställning  Defaultvärde
Startpunkt  0 0
Avbrottskriterium  Gradientlängd
Funktion som skall minimeras Funktion 1
Max antal iterationer  200
Utskrift av iterationsdata  På
Metod  Brantaste lutning

Ni kan välja att ta en, 10 eller 100 iterationer i taget och följa hur algoritmen söker i grafen.

Uppgifter

I alla uppgifter ska funktionen minimeras.

1. Studera funktion 1

f(x_{1}, x_{2}) = 2(x_{1} + 1)^{2} + 8(x_{2} + 3)^{2} + 5x_{1} + x_{2}

(a) Lös med BL och Newton (med steglängd 1). Starta i punkterna (10, 10) respektive (−5, −5). Välj även någon egen startpunkt. Mot vilken punkt konvergerar metoderna? Hur många iterationer krävs?

(b) Är erhållen lösningspunkt optimal (lokalt eller globalt minimum)?

(c) Varför konvergerar alltid Newton i en iteration?

2. Studera funktion 2 (Rosenbrocks funktion)

f(x_{1}, x_{2}) = 100(x_{2} − x_{1}^{2})^{2} + (1 − x_{1})^{2}

(a) Lös med BL och Newton (prova med alla versionerna). Starta i punkten (−1.5, −1). Mot vilken punkt konvergerar metoderna? Hur många iterationer krävs?

(b) Är funktionen konvex? Är den erhållna punkten ett globalt optimum?

(c) Välj några egna startpunkter och studera metodernas uppförande.

3. Studera funktion 4

f(x_{1}, x_{2}) = x_{1}^{3} + 2x_{2}^{3} − 27x_{1} − 6x_{2}

(a) Starta i punkten (0,0) och lös med BL och Newton (steglängd 1). Varför fungerar inte Newtons metod? Prova med Levenberg–Marquardts modifiering, och studera metodens uppförande.

(b) Starta i några valfria punkter. Hur många stationära punkter hittar Ni? Vilka typer förekommer?

Den som vill kan prova också de andra funktionerna. Dessa är:

(3) f(x_{1}, x_{2}) = −5e^{− \frac{x^{2}_{1}+x^{2}_{2}}{10}} + 4e^{− \frac{x^{2}_{1}+x^{2}_{2}}{100}} − 5^{− \frac{(x_{1}−5)^{2}+(x_{2}+4)^{2}}{10}} − 5^{− \frac{(x_{1}+4)^{2}+(x_{2}−5)^{2}}{10}} − 4^{− \frac{(x_{1}+4)^{2}+(x_{2}−5)^{2}}{100}}

(5) f(x_{1}, x_{2}) = −4e^{− \frac{(x_{1}+2)^{2}+(x_{2}+1)^{2}}{10}} + 4e^{− \frac{(x_{1}+2)^{2}+(x_{2}+1)^{2}}{100}} + 0.01((x_{1} + 2)^{2} + (x_{2} + 1)^{2}) + 0.01x_{1}

(6) f(x_{1}, x_{2}) = (x_{1}^{3} − x_{2})^{2} + 2(x_{1} − x_{2})^{4}

(7) f(x_{1}, x_{2}) = −5 cos(0.2(1 + \frac{x_{2}^{2}−0.5}{x_{1}^{2}+0.5}) + 0.001x_{2}^{4} + 0.003x_{1}^{4} + 2x_{1}

(8) f(x_{1}, x_{2}) = 2(x_{2} − x_{1}^{3})^{2} + 0.1(x_{1} + 2)^{2} + 0.5x_{2}^{2} + x_{1}^{2}x_{2}^{2}

Del II: Begränsad optimering; MATLAB:s Optimization Toolbox

I denna del ska ni använda programpaketet MATLAB:s optimeringsrutiner för att lösa några små ickelinjära problem.

En lämplig förberedelse för laborationen är att ni undersöker rutinernas funktion med hjälp av demonstrationspaketet optdemo, där ni stiftar bekantskap med flera av de tillgängliga funktionerna och de inmatningsrutiner som används. För att få hjälp med vad som finns till hands, skriv help optim.

Observera! Denna del av laborationen bör förberedas genom att KKT-villkoren formuleras. Vi har knackat in problemens målfunktioner och bivilkor i filerna upg1f, upg2f, upg1g samt upg2g. Notera att tecken har ändrats för att passa matlabs konventioner, någor ni behöver tänka på.

Uppgifter

1. Givet problemet

max x_{1} − 2x_{1}^{2} + 2x_{2} − x_{2}^{2} + x_{1}x_{2}
då x_{1}^{2} − x_{2} ≤ 0
2x_{1} − x_{2} ≥ 0

(a) Lös problemet mha fmincon (skriv help fmincon för närmare info)

(b) Teckna optimalitetsvillkoren (KKT-villkoren) samt undersök konvexiteten hos problemet och verifiera att den erållna lösningen är ett globalt maximum.

2. Givet problemet

min x_{1}
då (x_{1} − 1)^{2} + (x_{2} + 2)^{2} ≤ 16
x_{1}^{2}  +  x_{2}^{2}  ≥ 13

Lös problemet mha någon lämplig toolbox minst fem gånger från olika startpunkter. Tips på punkter som ger roliga effekter är (0, 0), (1, 1), (−1, −1), (3.7, 0) Beskriv vad som händer. Vilken punkt finner ni vara den bästa? Kan ni garantera globalt minimum?

Del III: Begränsad optimering; Straffunktionsmetoder

Betrakta problemet

minimera f(x),
då g(x) ≤ 0^{m},

där f och g är kontinuerliga funktioner. Straffunktionsmetoder finns väsentligen av två slag: yttre och inre straffmetoder, beroende på om metoderna i allmänhet ger en otillåten eller en strikt tillåten följd av iterationspunkter. I MATLAB har en algoritm av vardera slag implementerats.

För att köra programmen skall Ni flytta Er från biblioteket ILP till underbiblioteket ILP/EPA respektive ILP/IPA. Båda algoritmerna startas genom att man skriver dispatch i MATLABS kommandofönster.

Notera att problemet är givet med bivillkoren på “≤”-form, medan boken beskriver metoderna utifrån “≥”-formen, detta för ett understryka skillnaden i utseendet på straffunktionerna.

Den yttre straffmetoden (“penalty method” i boken) arbetar med relaxationen

minimera_{x∈ℜ^{n}} f(x) + ρ_{k}ψ(x),

där ρ_{k} > 0 och ρ_{k} → +∞ då k → +∞, och där straffunktionen är den kvadratiska funktionen

ψ(x) := ∑_{i=1}^{m} (max{0, g_{i}(x)})^{2} .

Den inre straffmetoden (“barrier method” i boken) arbetar med relaxationen

minimera_{x∈ℜ^{n}} f(x) + μ_{k}ϕ(x),

där μ_{k} > 0 och μ_{k} → 0 då k → +∞, och där straffunktionen är funktionen

ϕ(x) := − ∑_{i=1}^{m} log(−g_{i}(x)).

För att undvika numeriska problem låter man oftast sekvenserna ρ_{k} respektive μ_{k} konvergera långsamt.

Det finns tre problem inmatade för båda dessa metoder:

(1)

minimera f(x) := ∥x∥^{2},
då g_{1}(x) := −x_{1} + 2 ≤ 0,
g_{2}(x) := −x_{2}/3 + 1/3 ≤ 0.

(2)

minimera f(x) := x_{1} sin(x_{1}) + x_{2} sin(x_{2}),
då g_{1}(x) := x_{1} + 1/3 ≤ 0,
g_{2}(x) := sin(x_{2}) − x_{1} ≤ 0,
g_{3}(x) := −x_{2}/3 + 1/4 ≤ 0,
g_{4}(x) := ∥x − (1, 1)^{T}∥^{2}/5 − 1 ≤ 0.

(3)

minimera f(x) := x_{1}x_{2},
då g_{1}(x) := ∥x∥^{2}/5 − 5 ≤ 0,

g_{2}(x) := −x_{1} − x_{2} ≤ 0.

Uppgifter

1. Använd båda metoderna på problemen 2 och 3. Ange de punkter som de två algoritmerna konvergerar mot för vardera problem.

2. Konvergerar metoderna mot ett globalt optimum, ett lokalt optimum eller något annat?

3. Vilka optima finns till problemen?