LABORATIONSINFORMATION

TMA611 Tillämpad matematik V

Michael Patriksson

24 februari 2000

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 modifierade metod. 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 programmet.) När MATLABfö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  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. 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. 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. Varför fungerar inte Newtons metod?

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

4. Studera funktion 6

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

Lös med BL och Newton och välj själva startpunkter. Vilka punkter konvergerar metoderna mot? Är någon av dessa ett globalt minimum?

Lek gärna lite med några av de andra funktionerna!

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. Räkna också med en stunds förberedelse vid datorn med optdemo för att se hur Ert problem skall matas in. Var uppmärksam på vilket tecken bivillkoren skall ha.

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 någon lämplig toolbox.

(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. Beskriv vad som händer. Vilken punkt finner ni vara den bästa? Kan ni garantera globalt minimum?