Chalmers/GU Matematiska institutionen TENTAMEN

TMA945 TILLÄMPAD OPTIMERINGSLÄRA

Datum:  98–05–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.

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

Examinator:  Michael Patriksson
Jourhavande lärare:  Vladislav Panferov, 5338
Resultat anslås senast: 98–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

Motivera och redovisa noga 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

Uppgift 1

Antag att följande problem har lösts med simplex-metoden:

[P]

max f(x) = x_{1} + 2x_{2},
då  −2x_{1} + x_{2} ≤ 2,
−x_{1} + 2x_{2} ≤ 7,
x_{1}  ≤ 3,
x_{1} , x_{2} ≥ 0,

och att följande optimaltablå har erhålits:

\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 & 3 \\ x_{1} & 0 & 1 & 0 & 0 & 0 & 1 & 3 \\ s_{1} & 0 & 0 & 0 & 1 & −1/2 & 3/2 & 3 \end{matrix}

(1p) a) Vad är skuggpriset för det andra bivillkoret? För vilka högerled är det giltigt?

(1p) b) Antag att högerledet i det andra bivillkoret ändras från 7 till 15. Beräkna den resulterande förändringen i det optimala målfunktionsvärdet på lämpligt sätt. (Obs! Lös ej det förändrade problemet från början!)

(1p) c) Utgå åter från det ursprungliga problemet och dess optimala tablå, och antag att en ny variabel, x_{3}, med bivillkorskoefficienter (1, 1, 1)^{T}, tillkommer. Hur stor måste dess målfunktionskoefficient vara för att det optimala målfunktionsvärde skall bli högre än det ursprungliga (13)?

Uppgift 2

(2p) a) Betrakta problemet

[P]

min f(x),
då x ∈ X,
g(x) ≤ 0,

där f : ℜ^{n} ↦ ℜ och g : ℜ^{n} ↦ ℜ är konvexa och kontinuerliga funktioner, och där X ⊆ ℜ^{n} är en icke-tom konvex mängd. Antag att x^{∗} är en global optimallösning till problemet, och att g(x^{∗}) < 0 gäller. Visa att x^{∗} också är en global optimallösning till problemet [P’]

min f(x),
då x ∈ X,
g(x) ≤ b,

för varje val av b > 0. (Speciellt gäller alltså att ett bivillkor som är redundant i optimallösningen till ett konvext optimeringsproblem kan tas bort utan att det påverkar problemets optimallösning.)

(1p) b) Är kravet att [P] är ett konvext problem nödvändigt för att utsagan skall vara sann? Om Ert svar är ’Ja!’, motivera då detta med ett motexempel. Om Ert svar är ’Nej!’, motivera då detta genom att utvidga resultatet i a) till detta mer generella fall. Diskutera också vad svaret kan tänkas betyda för hur man skulle kunna lösa att begränsat optimeringsproblem.

Uppgift 3

Betrakta LP-problemet

[P]

max f(x) = 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}  ≥ b_{2},
A_{32}x_{2} = b_{3},
x_{1} ,  x_{2} ≥ 0,

där x_{j} ∈ ℜ^{n_{j}}, c_{j} ∈ ℜ^{n_{j}}, A_{ij} ∈ ℜ^{m_{i}×n_{j}}, och b_{i} ∈ ℜ^{m_{i}}, i = 1, 2, 3, j = 1, 2.

(2p) a) Formulera LP-dualen till [P].

(1p) b) Antag att [P] har en begränsad optimallösning, och att det optimala målfunktionsvärdet av [P] är f^{∗}.

Antag nu att värdet av något element i vektorn b_{1} ökar från sitt ursprungliga värde, och låt motsvarande LP-problem, [P_{1}], ha ett optimalt målfunktionsvärde f_{1}^{∗}. Utifrån problemet [P] bildar vi på samma sätt också två andra LP-problem, där värdet hos ett element i b_{2} respektive b_{3} ökar från sitt ursprungsvärde. Vi kallar dessa [P_{2}] respektive [P_{3}], och deras respektive optimala målfunktionsvärde f_{2}^{∗} och f_{3}^{∗}.

Uppgift: utan att anta något ytterligare om problemen [P], [P_{1}], [P_{2}] och [P_{3}] än att de alla har ett begränsat målfunktionsvärde, ange samtliga relationer som säkert alltid gäller mellan f^{∗}, f_{1}^{∗}, f_{2}^{∗} och f_{3}^{∗}.

(3p) Uppgift 4

Högsta domstolen har på senare tid fått alltfler ärenden att behandla, och en effektivare planering av verksamheten har blivit nödvändig. Man vänder sig då till Er, som i egenskap av optimeringskonsult har hjälpt andra statliga verksamheter med sina planeringsproblem (oftast med lyckat resultat). Problemet som beskrivs för Er kan (en aning förenklat) beskrivas som följer:

Planeringshorisonten är n veckor. Under dessa n veckor flyter det in ärenden som kan indelas i m olika typer. Det flyter in h_{ij} ärenden av typ i under vecka j, och varje ärende av typ i tar (approximativt) a_{i} timmar att behandla. Under vecka j finns b_{j} timmar till förfogande för domstolsförhandlingar. Er uppgift är att formulera en matematisk optimeringsmodell som kan användas för planeringen. Det har framförts till Er att ett önskemål är att tiden det tar för ett ärende att bli behandlat efter det att det har blivit inlämnat skall vara litet.

Uppgift 5

För ett system av linjära olikheter,

∑_{j=1}^{n} a_{ij}x_{j} ≤ b_{i}, i = 1, …, m,

är ett surrogatvillkor ett villkor som bildas genom att man bildar en icke-negativ linjärkombination av bivillkoren, dvs. ett villkor på formen

∑_{i=1}^{m} β_{i} (∑_{j=1}^{n} a_{ij}x_{j}) ≤ ∑_{i=1}^{m} β_{i}b_{i},

där β_{i} ≥ 0, i = 1, …, m.

Betrakta nu ett LP-problem

[P]

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

där x ∈ ℜ^{n}, c ∈ ℜ^{n}, A ∈ ℜ^{m×n} och b ∈ ℜ^{m}. Låt [P] ha en ändlig optimal lösning och f^{∗} vara dess optimala målfunktionsvärde. För en godtycklig icke-negativ vektor β, bilda nu det relaxerade LP-problemet [P(β)]

max f(x) = c^{T}x,
då β^{T}Ax ≤ β^{T}b,
x ≥ 0^{n},

och låt f^{∗}(β) vara dess optimala målfunktionsvärde (om det är ändligt).

(1p) a) Visa att f^{∗}(β) ≥ f^{∗} för alla β ≥ 0^{m}.

(2p) b) Vi söker den vektor β ≥ 0^{m} som ger det största värdet av f^{∗}(β). Visa att en sådan vektor ges av en optimal lösning till LP-dualen till [P]. Visa också att med detta val av β, f^{∗}(β) = f^{∗} fås.

Uppgift 6

Betrakta problemet

min f(x) := \frac{1}{2}(x_{1} − 2x_{2})^{2} + x_{1}^{4}.

Vi tänker oss att angripa detta obegränsade optimeringsproblem med en Newtonmetod, där vi använder en inexakt linjesökning. Vi använder då Armijos steglängdsregel, dvs. om x är en aktuell iterationspunkt och d är en sökriktning accepteras steget ℓ > 0 om

f(x + ℓd) − f(x) ≤ αℓ∇f(x)^{T}d,  (1)

för en given acceptansparameter α i intervallet (0, 1); om inte så minskas steget på ett väldefinierat sätt. [Vanligen väljs ℓ := 1 som startvärde och om inte olikheten (1) uppfylls för detta värde av ℓ omdefineras det som ℓ := ℓ/2 och olikheten (1) undersöks på nytt.]

(2p) a) Med start i punkten x^{0} := (2, 1)^{T} och med acceptansparameter α := 0.3, applicera denna metod en (1) iteration.

(1p) b) För vilka val av parametern α accepterar Armijos steglängdsregel ett enhetssteg i iterationen ovan?

Uppgift 7

Betrakta problemet

[P]

min f(x),
då g_{j}(x) ≥ 0,  j = 1, …, m,
h_{i}(x) = 0, i = 1, …, r,

där f : ℜ^{n} ↦ ℜ, g_{j} : ℜ^{n} ↦ ℜ och h_{i} : ℜ^{n} ↦ ℜär kontinuerligt differentierbara funktioner. Vi betraktar två specialfall av problemet, [P_{1}] där m = 0 (dvs. ett problem med enbart likhetsvillkor) och [P_{2}] där r = 0 (dvs. ett problem med enbart olikhetsvillkor).

(1p) a) Formulera för [P_{1}] det traditionella straffproblemet, som vi här kallar [P_{1}(μ)], och för [P_{2}] det logaritmiska barriärproblemet, som vi här kallar [P_{2}(ρ)].

(2p) b) Ange optimalitetsvillkoren för de två problemen [P_{1}(μ)] och [P_{2}(ρ)]. Från dessa optimalitetsvillkor, härled de estimat av KKT-multiplikatorer (Lagrange-multi-plikatorer) till [P_{1}] respektive [P_{2}] som man automatiskt kan beräkna. För vart och ett av de två problemen, studera slutligen hur multiplikatorestimaten förändras med respektive straff- och barriärparameter då de växer respektive avtar, och visa att om lösningarna till respektive problem [P_{1}(μ)] och [P_{2}(ρ)] konvergerar mot KKT-punkter till [P_{1}] respektive [P_{2}] så kommer estimaten att konvergera mot KKT-multiplikatorer för dem.