Tentamen i Tillämpad optimeringslära 990827

1. Fas-1 problemet: minimera w = a

då \{ \begin{matrix}−x_{1} + 3x_{2} + s_{1} = 3 \\ x_{1} + x_{2} − s_{2} + a = 5 \\ x_{1}, x_{2}, s_{1}, s_{2}, a ≥ 0 \end{matrix}

Tablå:

bas w x_{1} x_{2} s_{1} s_{2} a h.l.
−w 1 −1 −1 0 1 0 −5 x_{1} inkommande,
s_{1} 0 −1 3 1 0 0 3 a utgående
a 0 1 1 0 −1 1 5
−w 1 0 0 0 0 1 0 Optimum! w^{∗} = 0, dvs
s_{1} 0 0 4 1 −1 1 8 (s_{1}, x_{1}) är en tillåten bas.
x_{1} 0 1 1 0 −1 1 5

Uttryck z i icke-basvariabler och övergå till fas-2:

bas z x_{1} x_{2} s_{1}  s_{2}
−z 1 0 1  0  −2 10 x_{2} inkommande,
s_{1} 0 0 4  1  −1 8 s_{1} utgående
x_{1} 0 1 1  0  −1 5
−z 1 0 0 −1/4 −7/4 8
x_{2} 0 0 1 1/4 −1/4 2 Optimum!
x_{1} 0 1 0 −1/4 −3/4 3

x^{∗} = (3, 2)^{T}; z^{∗} = −8. 2 a) En KKT-punkt är strikt komplementär om varje olikhetsvillkor som är uppfyllt med likhet har en positiv multiplikator. Om problemet är att

minimera f(x)

då \begin{matrix}g_{i}(x) ≤, i = 1, …, m & | & λ_{i} \\ g_{j}(x) = 0, j = 1, …, ℓ & | ∣ & μ_{j} \end{matrix}

och (x^{∗}, λ^{∗}, μ^{∗}) är en KKT-punkt är den alltå strikt komplementär om

λ_{i}^{∗} > 0 för alla i = 1, …, m där g_{i}(x^{∗}) = 0.

b) En extrempunkt i en mängd X är en punkt i X som inte kan skrivas som en konvexkombination av andra punkter i X.

c) En metodik för att (huvudsakligen) beräkna en optimal lösning till ett binärt heltalsproblem. Trädet beskriver en uppdelning av alla möjliga kombinationer av variabelvärden. Uppskattningar och tillägg av bivillkor styr vilka lösningar som genereras och undviker i möjligaste mån att generera onödiga (dåliga) variabelkombinationer.

3. För ett värde på barriär parametern μ > 0 är det obegränsade problemet

minimera_{x∈ℝ^{2}}f(x) − μ · log(x_{1} + 2x_{2} − 10)

entydigt lösbaart, enligt följande:

x_{1} − \frac{μ}{x_{1} + 2x_{2} − 10} = 0; 2x_{2} − −\frac{2μ}{x_{1} + 2x_{2} − 10} = 0

ger att x_{1} = x_{2} måste gälla; den resulterande kvadratiska ekvationen 3x_{1}^{2} − 10x_{1} − μ = 0 har två rötter, varav bara en, x_{1}(μ) = 5/3 + \sqrt{25/9 + μ/3}, är (strikt) tillåten i bivillkoret. Då μ → 0 går x_{1}(μ) = x_{2}(μ) mot 10/3.

Man visar sedan att x^{∗} = (\frac{10}{3}, \frac{10}{3})^{T} är en KKT-punkt. Bivillkoret är bindande, och λ^{∗} = 10/3 ≥ 0, ur det duala systemet. Eftersom problemet är konvext så är x^{∗} optimal.

4 a) Nuvarande optimallösning:

x_{B} = B^{−1}b = [ \begin{matrix}0 & 1/2 & 1/2 \\ 0 & 0 & 1 \\ 1 & −1/2 & 3/2 \end{matrix} ] [ \begin{matrix}2 \\ 7 \\ 3 \end{matrix} ] = [ \begin{matrix}5 \\ 3 \\ 3 \end{matrix} ] . b^{NY} = b + [ \begin{matrix}0 \\ 0 \\ 1 \end{matrix} ]

ger x_{B}^{NY} = B^{−1}b^{NY} = [ \begin{matrix}5 \\ 3 \\ 3 \end{matrix} ] + [ \begin{matrix}1/2 \\ 1 \\ 3/2 \end{matrix} ] = [ \begin{matrix}51/2 \\ 4 \\ 41/2 \end{matrix} ]. Eftersom X_{B}^{NY} ≥ 0

är X_{B}^{NY} optimal. Funktionsvärde:

c^{T} x^{NY} = c_{B}^{T}x_{B}^{NY} = (−2, −1, 0) [ \begin{matrix}51/2 \\ 4 \\ 41/2 \end{matrix} ] = −15.

Förändringen är −15 − (−13) = −2.

Skuggpriset för bivillkor 3 är värdet av dess dualvariabel, dvs y_{3}^{∗} = −2 (hela den duala vektorn är (0, −1, −2)^{T})/ Skuggpriset anger just den marginella förändringen av det optimala målfunktionsvärdet vid en förändring med en enhet i ett högerled, varför de två storheterna är lika.

b) Då c_{1} förändras kommer de reducerade kostnaderna att förändras:

c̄_{N}^{T} = c_{N}^{T} − c_{B}^{T}B^{−1}b = (1, 2); med c_{B}^{NY} = c_{B} + (0, 4, 0)^{T}
fås därför (c_{N}^{NY})^{T} = c_{N}^{T} − (c_{B}^{NY})^{T} B^{−1}b = c̄^{T} N − (0, 4, 0) · B^{−1}b
= (1, 2) − 4 · (0, 1) = (1, −2).

Eftersom x̄_{s_{3}} < 0 är inte x_{B} längre en optimal bas. Om s_{3} införs i basen (obs: ny målfunktionsrad: [1 0 0 0 1 − 21]) fås s_{2} som utgående. Efter en pivotering fås x_{B}^{∗} = (x_{2}, x_{1}, s_{3}) = (4, 1, 2)^{T} och z^{∗} = −5.

c) Beräkna dess reducerade kostnad givet den aktuella optimalbasen:

c̄_{3} = c_{3} − c_{B}^{T}B^{−1} · a^{3} = −2 − (0, −1, −2) ( \begin{matrix}2 \\ 0 \\ 1 \end{matrix} ] = 2 > 0.

Eftersom det är ett minimeringsproblem tjänar vi inte på att öka x_{3} från noll. Den nya aktiviteten påverkar inte optimallösningen.

5. Formulera först Lagrangefunktionen:

L(x, λ) = \frac{1}{2}∥y − x∥^{2} − λ^{T} (Ax).

Lös det obegränsade problemet att minimera denna över x.

Problemet att minimera denna över x:

∇_{x}L(x, λ) = x − y − A^{T} λ = 0^{n} ⇒ x = y + A^{T} λ.

Eftersom L är strikt konvex i x för varje λ är x = x(λ) = y +A^{T} λ den unika lösningen till detta problem. Studera nu den Lagrangeduala målfunktionen:

L(λ) = min_{x} L(x, λ) = L(x(λ), λ) =

= \frac{1}{2}∥y − (y + A^{T} λ)∥^{2} − λ^{T} A(y + A^{T} λ) =

= −\frac{1}{2}∥A^{T} λ∥^{2} − y^{T} A^{T} λ.

Att maximera L(λ) över λ ∈ ℝ^{m} är ett konvext problem, och löses sålunda

∇L(λ) = −AA^{T} λ − Ay = 0^{m}.

Eftersom A har full radrag existerar inversen av AA^{T}. Detta ger att

λ^{∗} = −(AA^{T})^{−1}Ay.

Insätter λ^{∗} i uttrycket

\begin{aligned}x(λ^{∗}) & = y − A^{T} (AA^{T})^{−1}Ay \\ & = [I − A^{T} (AA^{T})^{−1}A]y. \end{aligned}

Att visa att x(λ^{∗}) är den globala optimala lösningen är nu elementärt: vi kan visa från de ovan gjorda beräkningarna att KKT-villkoren är uppfyllda, och konvexiteten hos problemet ger resultatet.

1. 6 a)]

maximera b^{T} y
då \begin{matrix}A^{T} y ≤ c \\ y ≥ 0^{m} \end{matrix} (D)

Optimalitetsvillkor: x^{∗} är optimal i (P) omm:

(i) x^{∗} är tillåten i (P);

(ii) det existerar en komplementär dual lösning, dvs ett y^{∗} så att

(y^{∗})^{T} (Ax^{∗} − b) = 0 och (x^{∗})^{T} (A^{T} y^{∗} − c) = 0;

(iii) y^{∗} är tillåten i (D). b)

maximera = b_{1}^{T} y_{1} + b_{2}^{T} y_{2} + b_{2}^{T} y_{3} + ℓ_{1}^{T} v

då \begin{matrix}A_{11}^{T}y_{1} + A_{21}^{T}y_{2}  + v ≤ c_{1} \\ A_{12}^{T}y_{1} + A_{22}^{T} + A_{32}^{T}y_{3} + ≤ c_{2} \\ y_{1}fri, y_{2} ≤ 0, y_{3} ≥ 0, v ≤ 0 \end{matrix} (D)

7 a) Vi vet att ∇^{2}f(x) är positivt semidefinit om och endast om alla egenvärden är icke-negativa. Dessutom är detta ekvivalent med att p^{T} ∇^{2}f(x)p ≥ 0 för alla p ∈ ℝ^{n}. Alltså har ∇^{2}f(x) minst ett negativt egenvärde om och endast om p^{T} ∇^{2}f(x)p < 0 för något p ∈ ℝ^{n}.

b) Antag att p ∈ ℝ^{n} är sådant att p^{T} ∇^{2}f(x)p < 0. Om ∇f(x)^{T} p ≤ 0, låt p̄ = p; om ∇f(x)^{T} p > 0, låt p̄ = −p. I båda fall gäller:

f(x + ℓp̄) = f(x) = ℓ∇f(x)^{T} p̄ + (ℓ^{2}/2)p̄^{T} ∇^{2}f(x)p̄ + o(ℓ^{3})

< f(x) för alla tillräckligt små ℓ > 0.

c) Det enklaste är att undersöka om det existerar något negativt egenvärde hos ∇^{2}f(x^{t}) då x^{t} närmar sig en stationär punkt. Om vi upptäcker detta, bildar man t.exėn positiv linjärkombination av motsvarande p̄-värde enligt (b) och −∇f(x^{t}), vilket är en descentiriktning. Detta leder till (1).