Några inledande ord om optimering

Numerisk programvara
Det är väsentliga skillnader mellan programvara och de metoder som presenteras i kurser i matematik. I t.ex. kursen i linjär algebra räcker det att hitta en metod för att lösa linjära ekvationssystem, Ax = b. Om metoden är effektiv, vad gäller minne och tid, spelar inte så stor roll, huvudsaken är att metoden kan lösa problemet. När man som ingenjör löser problem, är tid och minne mycket viktigt. Det spelar stor roll om lösningstiden är en minut eller 100 minuter respektive om minnesbehovet uppgår till Mbyte eller Gbyte. Det gör att man försöker utnyttja problemets egenskaper för att spara tid och minne. Detta framgår tydligt i Lapack-biblioteket, som innehåller standardrutinerna för Ax=b, bland annat. Dessa rutiner används t.ex. i Matlab.

I Lapack finns varianter av LU-faktorisering när A är symmetrisk (halva minnet och tiden), när A är positivt definit (man slipper pivotera). Ytterligare varianter finns för bandmatriser (matriselementen är lika med noll utanför ett band kring diagonalen). Det finns också stöd för matriser vars element är komplexa tal. Det finns då dessutom två symmetriegenskaper. A är komplexsymmetrisk (inte så vanligt) när A(j, k) = A(k, j). Den är hermitsk när A(j, k) = conj(A(k, j)) (där conj markerar komplexkonjugering).

Det finns stöd för fyra datatyper, enkel- och dubbel precision samt enkel- och dubbel komplex. Slutligen finns easy-to-use varianter av rutinerna, där det räcker med ETT anrop för att lösa Ax=b. Om man vill kunna detaljstyra lösningsproceduren, finns rutiner för att först utföra LU-faktoriseringen och sedan rutiner för att använda denna för att lösa LUx=b, t.ex. Detta gör att antalet rutiner uppgår till mer än 100.

Situationen är likartad inom andra problemområden. När det gäller optimering tillkommer dessutom en viktig aspekt. Metoderna, i Lapack, för linjära ekvationssystem är deterministiska. Eftersom de baseras på LU-faktorisering vet man redan innan man anropar rutiner hur många additioner och multiplikationer som kommer att utföras och man ge uppskattningar av hur noga lösningen har beräknats.

Metoder för optimering är iterativa, och man vet inte i förväg om metoden konvergerar och om den gör det, hur många iterationer som kommer att behövas. Normalt har problemen flera lokala minima och det bästa man kan hoppas på, är att hitta ett av dessa. Man har normalt inga garantier för att man hittar det minsta värdet. Optimeringsproblem kan alltså vara besvärliga och för öka chanserna att hitta ett minimum, vill man hjälpa rutinen så mycket som möjligt. Det är en anledning till att vi delar in bivillkoren i så många fall, linjära, ickelinjära, likhet, olikhet etc., i stället för att behandla alla bivillkor som ickelinjära olikhetsbivillkor. Analogt har man olika rutiner beroende på objektfunktionens egenskaper, linjär, ickelinjär, kvadratsumma etc. Dessutom spelar körtiden in. Ickelinjära kvantiteter tar normalt mer tid att hantera än linjära motsvarigheter.

I princip kan man klara sig med en rutin som löser minimeringsproblemet

min f(x) då c(x) <= 0

där f och c är ickelinjära och vektorvärda funktioner av vektorn x. Även likhetsbivillkor kan uttryckas som c(x) <= 0. Likhetsbivillkoret, g(x) = 0, kan ju skrivas som två olikhetsbivillkor, g(x) <= 0 och g(x) >= 0, eller g(x) <= 0 och -g(x) <= 0. Så gör man nu inte i praktiken och en mycket väsentlig del av denna lab är att lära sig att klassificera bivillkor (linjärt-ickelinjärt etc.) och att kunna "förpacka" dessa (använda rätt datastruktur).

För att få godkänt på labben skall Du använda enklast tänkbara förpackning av bivillkoren. Om Du t.ex. behandlar ett linjärt bivillkor som ett ickelinjärt kommer Du att få retur.

Några exempel
Antag att vi vill beräkna x, y och z. Vi säger att variablerna ingår linjärt i ett uttryck om det kan skrivas

a x + by + c z

där a, b och c är konstanter. Övriga uttryck är ickelinjära. Ibland är denna uppdelning för grov och man har varianter av ickelinjära uttryck (t.ex. kvadratiska).

Här några exempel:
2 x - 3 y + 4 z linjärt
2 x - 3 y linjärt
x linjärt

2 x y - 3 sin(y) ickelinjärt
x² ickelinjärt

och här kommer exempel på bivillkor

2 x - 3 y + 4 z = 4 linjärt likhetsbivillkor
2 x y - 3 sin(y) = 3 ickelinjärt likhetsbivillkor

2 x - 3 y + 4 z <= 4 linjärt olikhetsbivillkor
2 x y - 3 sin(y) <= 3 ickelinjärt olikhetsbivillkor

Notera att olikhetsbivillkoren skrivs uttryck <= konstant. Har man uttryck >= konstant får man transformera det till -uttryck <= -konstant. Optimeringsrutiner kräver nämligen att villkoren skrivs på standardform.

Ett specialfall av linjära olikhetsbivillkor är så kallade enkla gränser (konstant <= variabel eller variabel <= konstant), t.ex.

2 <= x <= 7

där vi har en enkel undre och en enkel övre gräns.

Linjära villkor kan förpackas med en konstant vektor och ett tal. Låt v = [x, y, z]^T vara en kolonnvektor som innehåller variablerna. Bivillkoret 2 x - 3 y + 4 z = 4 kan då skrivas som [2, -3, 4] * v = 4 där * markerar vanlig matrismultiplikation.

Olikhetsbivillkoret 2 x - 3 y + 4 z <= 4 kan analogt skrivas [2, -3, 4] * v <= 4.

Om man har flera (o)likhetsbivillkor får vi införa en koefficientmatris. Säg att vi har villkoren: 2 x - 3 y + 4 z <= 4 och 2 x - 3 y <= -7. Vi skriver då

A * v <= b då A = [2, -3, 4], b = [ 4]
                  [2, -3, 0]      [-7]

(A är en matris med två rader och b är en kolonnvektor med två rader).

Man tjänar avlusningstid på att vara försiktig när man formulerar villkoren. Ett felaktigt tecken, till exempel, kan leda till ett olösbart problem. Man vill t.ex. inte skriva 2 <= x OCH x <= -2.

Back