Chalmers/GU Matematiska institutionen TENTAMEN

TMA946/MAN280 TILLÄMPAD OPTIMERINGSLÄRA

Datum:  01–05–23
Tid:  förmiddag
Hjälpmedel:  Typgodkänd räknedosa
Antal uppgifter:  7; för godkänd uppgift krävs 2 poäng av 3.

Uppgifterna är inte ordnade efter svårighetsgrad.

För godkänt krävs 10 poäng och tre godkända uppgifter.

Examinator:  Michael Patriksson
Jourhavande lärare:  Michael Patriksson, tel. 0709-263986
Resultat anslås senast: 01–06–11

Kortfattade lösningsförslag anslås vid skrivningstidens slut på anslagstavlan för optimeringslära vid matematiska institutionen.

Tentamensinstruktioner

När Du löser uppgifterna

Redovisa lösningsmetodik och beräkningar. Använd generellt giltiga metoder, t.ex. de som genomgåtts i kursen.

Skriv endast på ena sidan av lösningsbladen. Använd inte rödpenna. Behandla ej fler än en huvuduppgift på varje blad.

Vid skrivningens slut

Sortera Dina lösningsblad i uppgiftsordning. Markera på omslaget de uppgifter Du behandlat. Kontrollräkna antalet inlämnade blad och fyll i antalet på omslaget.

TENTAMEN

Uppgift 1

(Linjärprogrammering)

Betrakta LP-problemet

minimera z = 2x_{1} − x_{2}
då  2x_{1} + x_{2} ≥ 3,
−x_{1} + x_{2} ≤ 2,
x_{1} , x_{2} ≥ 0.

(2p) a) Lös problemet med användande av simplexmetodens båda faser.

(1p) b) Om vi ersätter högerledet för första bivilkoret med α, så blir det optimala värdet en funktion av α, v(α). Beräkna högerderivatan av denna funktion (riktningsderivatan i riktning 1) i punkten α = 3.

Uppgift 2

(Dualitet)

Betrakta LP-problemet

minimera z = 1.5x_{1} + x_{2} + 2x_{3} + x_{4}
då x_{1} + x_{3} + x_{4} ≥ 1,
x_{2} + x_{3} − x_{4} ≥ 0.1,
x_{1} , x_{2} , x_{3} , x_{4} ≥ 0.

(2p) a) Beskriv den polyeder som består av mängden av optimala lösningar genom att lösa det duala problemet grafiskt och använda komplementaritet.

(1p) b) Ange samtliga optimala baser till problemet ovan. Antag att vi ersätter målfunktionskoefficienten för x_{1} med 1.6. Vad blir då den optimala mängden, och vilka baser är optimala?

Uppgift 3

(Heltalsprogrammering)

Ett stort försäljningsföretag vill bygga ett antal distributionscentraler som tillsammans skall förse 30 olika varuhus med varor. Man har tio olika platser att välja mellan. Att bygga på plats i kostar c_{i} pengar och kapaciteten hos central i (mätt i volymenheter per vecka) är k_{i}, i = 1, …, 10. Varuhus j har en efterfrågan på e_{j} volymenheter per vecka som skall tillgodoses, j = 1, …, 30. Avståndet mellan plats i och varuhus j är d_{ij} km, i = 1, …, 10, j = 1, …, 30, och en viss central kan serva ett visst varuhus endast om avståndet mellan dem är högst D km. Man vill minimera kostnaden för investeringen i distributionscentralerna.

(2p) a) Formulera en linjär heltalsmodell som beskriver problemet att bestämma på vilka platser man skall bygga centraler.

(1p) b) Antag att varje varuhus endast får servas av en central. Hur förändras din modell?

Uppgift 4

(Olinjär optimering)

(1p) a) Låt funktionen f vara kontinuerligt differentierbar på ℜ^{n}. Antag att x^{∗} är ett lokalt minimum till f. Ange samtliga de egenskaper x^{∗} har och som kan formuleras utifrån denna information.

(2p) b) Betrakta mängden S := { x ∈ ℜ^{n} | Ax ≥ b }, där A ∈ ℜ^{m×n} and b ∈ ℜ^{n}. För en funktion f med samma egenskaper som anges i a), antag att x^{∗} är ett lokalt minimum till f över S. Ange samtliga de egenskaper x^{∗} har och som kan formuleras utifrån denna information.

Uppgift 5

(Inre punktsmetoder)

Betrakta det olinjära optimeringsproblemet att

minimera f(x),  (1)
då g_{i}(x) ≥ 0,  i = 1, …, m,  (2)

där f : ℜ^{n} ↦ ℜ och g_{i} : ℜ^{n} ↦ ℜ, i = 1, …, m, samtliga är kontinuerligt differentierbara funktioner på ℜ^{n}.

(1p) a) För den logaritmiska barriärfunktionen, beskriv inre punktsalgoritmen för att lösa detta problem.

(1p) b) Beskriv första ordningens optimalitetsvillkor för barriärsubproblemet för ett godtyckligt positivt värde på barriärparametern. Beskriv skillnaden mot KKT-vill-koren till det ursprungliga problemet. Med ledning av denna, ge formeln för det naturliga estimatet av Lagrangemultiplikatorerna för bivillkoren (2) till ursprungsproblemet.

(1p) c) Antag att sekvensen av KKT-punkter till barriärsubproblemet är konvergent, med gränsvärde x^{∗}. Visa att om x^{∗} är en reguljär punkt (dvs. att bivillkorsnormalerna till de bindande bivillkoren i x^{∗} är linjärt oberoende), så kommer också sekvensen av multiplikatorestimat att konvergera, och detta mot en vektor av KKT-multiplikatorer som tillsammans med x^{∗} uppfyller KKT-villkoren för ursprungsproblemet.

Uppgift 6

(Kvadratisk programmering)

Betrakta följande kvadratiska optimeringsproblem: finn x^{∗} som

minimerar f(x) := \frac{1}{2}x^{T}Qx − q^{T}x,
då Ax ≤ b,
x ≥ 0^{n},

där Q ∈ ℜ^{n×n}, q ∈ ℜ^{n}, A ∈ ℜ^{m×n} och b ∈ ℜ^{m}.

(1p) a) Formulera de nödvändiga villkoren (KKT-villkoren) för att x^{∗} skall vara lokalt minimum för detta problem. Ange tillräckliga villkor på data för problemet, dvs. på (Q, q, A, b), för att de skall beskriva mängden av globalt optimala lösningar för problemet.

(2p) b) Visa att KKT-villkoren kan omformuleras på ett ekvivalent sätt på formen

T v + Uw = p,
v ≥ 0^{n+m}, w ≥ 0^{n+m},
v^{T}w = 0

(p är en vektor medan T och U är matriser, samtliga av lämplig storlek). Ledning: Detta kräver tillägg av nya variabler till KKT-systemet i a). Att finna en tillåten lösning till KKT-villkoren, beskrivna på detta sätt, kan göras nästan lika enkelt som att använda Fas-1 i simplexmetoden för att hitta en tillåten lösning till ett system av linjära ekvationer i ickenegativa variabler. Vad i systemet gör att det inte är riktigt lika enkelt? Formulera en Fas-1-liknande algoritm för att finna en lösning till det system som Ni beskrivit tidigare i denna uppgift. Om ni inte har lyckats finna denna ekvivalenta formulering till den i uppgift a), får ni använda den som ges ovan i variablerna (v, w), och kan då få maximalt en poäng på uppgiften.

Uppgift 7

(Newtons metod för ickekonvexa problem)

Betrakta problemet att

minimera_{x∈ℜ^{2}} f(x) := 2x_{1}^{3} + 2x_{2}^{3} + 12x_{1}x_{2} − 24x_{1} − 20x_{2}.

(1p) a) Undersök konvexiteten hos problemet. Var är funktionen konvex, konkav, ingetdera?

(2p) b) Beräkna, om möjligt, sökriktningen i Newtons modifierade metod (Newtons metod med linjesökning) i punkten (x_{1}, x_{2}) = (1, 1)^{T}. Beräkna den iterationspunkt som nås efter en iteration. Om det inte var möjligt att beräkna en sökriktning enligt proceduren i Newtons metod, modifiera då, på lämpligt sätt, proceduren så att sökriktningen ger descent med avseende på f i punkten (1, 1)^{T}, och så att modifieringen av det riktningsbestämmande problemet är så liten som möjligt. Även i detta fall önskas nästa iterationspunkt.

Lycka till!