Chalmers/GU Matematiska institutionen TENTAMEN

TMA945 TILLÄMPAD OPTIMERINGSLÄRA

Datum:  99–08–27
Tid:  8^{45}–13^{45}
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.

CTH: För godkänt krävs 8 poäng och tre godkända uppgifter. GU: För godkänt krävs 11 poäng och tre godkända uppgifter.

Examinator:  Michael Patriksson
Jourhavande lärare:  Michael Patriksson, tel. 3529
Resultat anslås senast: 99–09–10

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 de standardmetoder som genomgåtts på föreläsningar och lektioner.

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 TMA945 — TILLÄMPAD OPTIMERINGSLÄRA 1

(3p) Uppgift 1

Lös följande LP-problem med simplexmetoden (tvåfasmetoden).

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

Uppgift 2

(1p) a) Definera begreppet strikt komplementaritet. (1p) b) Definera begreppet extrempunkt. (1p) c) Definera begreppet trädsökning.

(3p) Uppgift 3

Betrakta problemet att

minimera f(x) = \frac{1}{2}x_{1}^{2} + x_{2}^{2},
då x_{1} + 2x_{2} ≥ 10.

Angrip detta problem med en logaritmisk barriärmetod. Beskriv explicit den trajektoria som metoden följer, som funktion av barriärparametern.

Uppgift 4

Betrakta LP-problemet att

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

Den optimala lösningen till problemet motsvaras av följande tablå:

\begin{matrix}Basvar & −z & x_{1} & x_{2} & s_{1} & s_{2} & s_{3} & b \\ −z & 1 & 0 & 0 & 0 & 1 & 2 & 13 \\ x_{2} & 0 & 0 & 1 & 0 & 1/2 & 1/2 & 5 \\ x_{1} & 0 & 1 & 0 & 0 & 0 & 1 & 3 \\ s_{1} & 0 & 0 & 0 & 1 & −1/2 & 3/2 & 3 \end{matrix}

TENTAMEN

Föjande deluppgifter skall lösas oberoende av varandra, dvs. de förändringar som anges gäller relativt det ursprungliga problemet.

Vid lösning av uppgifterna skall Ni inte lösa det förändrade problemet från början med simplexmetoden.

(1p) a) Antag att b_{3} = 3 byts mot b_{3}^{NY} = 4. Vad händer med den optimala lösningen x^{∗} och dess funktionsvärde z^{∗}? Vad är skuggpriset för bivillkor 3? Förklara kopplingen mellan dessa frågor.

(1p) b) Antag att c_{1} = −1 ersätts med c_{1}^{NY} = 3. Hur förändras x^{∗}?

(1p) c) Antag att en ny icke-negativ aktivitet, x_{3}, tillkommer, med bidrag c_{3} = −2 till målfunktionen och bivillkorskoefficienter 2, 0, och 1. Påverkar denna nya aktivitet optimallösningen till problemet?

(3p) Uppgift 5

I många sammanhang är det av intresse att beräkna projektionen av en vektor på ett underrum. Speciellt, betrakta problemet att finna den euklidiska projektionen av en godtycklig vektor, y ∈ ℜ^{n}, på nollrummet till en matris, A ∈ ℜ^{m×n}, dvs. att finna ett x ∈ ℜ^{n} som

minimerar \frac{1}{2}∥y − x∥^{2},
då Ax = 0.

Lösningen till detta problem är klassisk: om matrisen A har full radrang ges denna projektion av

x^{∗} = y − A^{T} (AA^{T})^{−1}Ay.

Låter vi P := I^{n} −A^{T} (AA^{T})^{−1}A, där I^{n} ∈ ℜ^{n×n} är enhetsmatrisen, vara den så kallade projektionsmatrisen, kan vi alltså beräkna projektionen med formeln x^{∗} = P y.

Er uppgift är att härleda denna formel, genom att utnyttja Lagrangedualitet! Motivera väl alla steg som utförs, genom att påvisa att nödvändiga förutsättningar är uppfyllda.

Uppgift 6

(2p) a) Betrakta LP-problemet att

(P)

minimera f(x) = c^{T} x,
då Ax ≥ b,
x ≥ 0^{n}.

Ange LP-dualen till (P). Ange också optimalitetsvillkoren för (P) med hjälp av denna LP-dual.

(1p) b) Ange LP-dualen till följande problem:

minimera z = c_{1}^{T} x_{1} + c_{2}^{T} x_{2}
då  A_{11}x_{1} + A_{12}x_{2} = b_{1},
A_{21}x_{1} + A_{22}x_{2} ≤ b_{2},
A_{32}x_{2} ≥ b_{3},
x_{1}  ≤ ℓ_{1},
x_{1},  x_{2} ≥ 0.

Dimensionerna på matriserna A_{ij} och vektorerna c_{j}, b_{i} och ℓ_{1} antas vara korrekta för att kunna ställa upp problemet.

Uppgift 7

Betrakta problemet att

minimera_{x∈ℜ^{n}} f(x),

där f är två gånger kontinuerligt differentierbar.

En vektor p ∈ ℜ^{n} sägs beskriva en riktning med negativ kurvatur för f i x om p^{T} ∇^{2}f(x)p < 0 gäller.

(1p) a) Visa att en sådan riktning existerar om och endast om matrisen ∇^{2}f(x) har minst ett negativt egenvärde.

(1p) b) Visa att om en riktning med negativ kurvatur existerar så existerar också en sådan riktning som samtidigt är en descentriktning till f från x.

(1p) c) Antag att vi löser problemet ovan med någon descentmetod (t.ex. brantaste lutningsmetoden), och att vi är intresserade av att finna en stationär punkt x^{∗} som uppfyller andra ordningens nödvändiga villkor, dvs. en punkt x^{∗} som uppfyller

∇f(x^{∗}) = 0^{n} och p^{T} ∇^{2}f(x^{∗})p ≥ 0, ∀p ∈ ℜ^{n}.  (1)

Beskriv hur metoden som vi använder kan enkelt modifieras för att se till att vi uppfyller (1).