Tentamen TMA945/MAN280 Optimeringslära 000306

1 a) Efter tilläggs av en slackvariabel fås:

\begin{matrix}min z = −4x_{1} − 2x_{2} − 4x_{3} \\ då & \begin{matrix}2x_{1} − x_{2} + x_{3} + s_{1} = 20 \\ x_{1} + x_{2} + 2x_{3} = 20 \\ x_{1}, x_{2}, x_{3}, s_{1} ≥ 0 \end{matrix} \end{matrix}

Fas-1-problemet:

\begin{matrix}min w = a_{1} \\ då & \begin{matrix}2x_{1} − x_{2} + x_{3} + s_{1} = 20 \\ x_{1} + x_{2} + 2x_{3} + a_{1} = 20 \\ x_{1}, x_{2}, x_{3} s_{2}, a_{1} ≥ 0 \end{matrix} \end{matrix}

Startbas: (s_{1}, a_{1}); w = a_{1} = 40 − x_{1} − 2x_{2} − 4x_{3}

bas −w x_{1} x_{2} x_{3} s_{1} a_{1} b̄
−w 1 −1 −1 −2 0 0 −20 x_{3} ink.
s_{1} 0 2 −1 1 1 0 20 a_{2} utg.
a_{1} 0 1 1 2  0 1 20
−w 1 0 0 0 0 1 0
s_{1} 0 3/2 −3/2 0 1 −1/2 10 c̄_{w} ≥ 0 → Fas-1 optimum!
x_{3} 0 1/2 1/2 1 0 1/2  10 w^{∗} = 0 → tillåten lösning funnen!

Återta

\begin{aligned}z & = −4x_{1} − 2x_{2} − 4x_{3} = −4x_{1} − 2x_{2} − 4(10 − 1/2x_{1} − 1/2x_{2}) \\ & = −40 − 2x_{1} \end{aligned}

bas −z x_{1}  x_{2} x_{3} s_{1}  b̄
−z 1 −2  0  0  0  40 x_{1} ink.
s_{1}  0 3/2 −3/2 0  1  10 s_{1} utg.
x_{3}  0 1/2 1/2 1  0  10
−z 1  0  −2 0 4/3 160/3 x_{2} ink.
x_{1}  0  1  −1 0 2/3 20/3 x_{3} utg.
x_{3}  0  0  1  1 −1/3 20/3
z − 1 1  0  0  2 2/3 200/3
x_{1}  0  1  0  1 1/3 40/3 c̄_{z} ≥ 0 → fas-2 optimum!
x_{2}  0  0  1  1 −1/3 20/3

Optimum: (x_{1}^{∗}, x_{2}^{∗}, x_{3}^{∗}) = (40/3, 20/3, 0); z^{∗} = 200/3.

b) x_{B} = (s_{1}, x_{3})^{T} → B = [ \begin{matrix}1 & 1 \\ 0 & 2 \end{matrix} ] ⇒ Bx_{B} = b ⇔ x_{B} = [ \begin{matrix}10 \\ 10 \end{matrix} ]

B^{T} y = c_{B} ⇔ y = [ \begin{matrix}0 \\ −2 \end{matrix} ];

c̄_{N}^{T} = c_{N}^{T} − y^{T} N = (−4, −2) − (0, −2) [ \begin{matrix}2 & −1 \\ 1 & 1 \end{matrix} ] = (−4, −2) − (−2, −2) =

(−2, 0) ⇒ x_{1} inkommande.

Bā_{1} = a_{1} ⇔ ā_{1} = [ \begin{matrix}3/2 \\ 1/2 \end{matrix} ] ⇒ min\{\frac{10}{3/2}, \frac{10}{1/2}\} = \frac{20}{3} ⇒ s_{1} utgående.

x_{B} = (x_{1}, x_{3})^{T} ⇒ B = [ \begin{matrix}2 & 1 \\ 1 & 2 \end{matrix} ] ⇒ Bx_{B} = b ⇔ x_{B} = [ \begin{matrix}20/3 \\ 20/3 \end{matrix} ]

B^{T} y = c_{B} ⇔ y = [ \begin{matrix}−4/3 \\ −4/3 \end{matrix} ]; c̄_{N}^{T} = c_{N}^{T}−y^{t}N = (−2, 0)−(−4/3, −4/3) [ \begin{matrix}−1 & 1 \\ 1 & 0 \end{matrix} ] =

(−2, 4/3) Dualen är: max v = 20y_{1} + 20y_{2}

då \{ \begin{matrix}2y_{1} + y_{2} ≤ −4 & uppfylls \\ −y_{1} + y_{2} ≤ −2 & uppfylls ej ← \\ y_{1} + 2y_{2} ≤ −4 & uppfylls \\ y_{1} ≤ 0 & uppfylls \end{matrix}

2 a) Primal tillåtenhet: \begin{matrix}g_{1}(x) = −2x_{1} + 2x_{2} − 1 \\ g_{2}(x) = −2x_{1} + x_{2} \\ g_{3}(x) = − x_{1} \\ g_{4}(x) = x_{2} \end{matrix}

Med x̄(0, \frac{1}{2}) : g_{1}(x̄) = 0, g_{2}(x̄) > 0, g_{3}(x̄) = 0, g_{4}(x̄) > 0 Komplementaritet: från ovan fås att λ_{2} = λ_{4} = 0

Dual tillåtenhet: \begin{matrix}∇f(x) = (8x_{1} − 6x_{2} + 1, 4x_{2} − 6x_{1})^{T} \\ ∇g_{1}(x) = (−2, 2)^{T} \\ ∇g_{3}(x) + (−1, 0)^{T} \end{matrix}

Med x̄ = (0, \frac{1}{2}) : ∇f(x̄) − λ_{1}∇g_{1}(x̄) − λ_{3}∇g_{3}(x̄) = (0, 0)^{T},

d.v.s. [ \begin{matrix}−2 \\ 2 \end{matrix} ] − λ_{1} [ \begin{matrix}−2 \\ 2 \end{matrix} ] − λ_{3} [ \begin{matrix}−1 \\ 0 \end{matrix} ] = [ \begin{matrix}0 \\ 0 \end{matrix} ] . λ_{1} = 1, λ_{3} = 0

λ = (1, 0, 0, 0)^{T} ≥ 0. KKT-villkoren är uppfyllda!

b) Svaret är att x̄ är ett globalt minimum. Att verifiera det är inte lätt, beroende på att f inte är en konvex funktion, så att problemet faktiskt inte är konvext. (Vi kan verifiera att x̄ uppfyller andra ordningens nödvändiga krav för lokalt minimum, men inte andra ordningens tillräckliga krav för lokalt minimum.) Det enda sättet att verifiera att x̄ är ett globalt minimum är att resonera som följer. Uppenbarligen är f en funktion som växer mot +∞ i alla tillåtna riktningar. Eftersom den tillåtna mängden är sluten och icke-tom och f är kontinuerlig, kan vi dra slutsatsen att f måste anta sitt minsta värde på den tillåtna mängden, alltså att det existerar(Weierstrass Sats!) en optimallösning till problemet. Eftersom den tillåtna mängden är konvex och har en inre punkt kan vi också konstatera att varje lokalt (och globalt förstås!) minimum måste vara en KKT-punkt. Strategin här blir alltså att finna samtliga KKT-punkter och visa att x̄ (om det finns fler KKT-punkter än den) är den bästa. (Detta är egentligen ingen metod för att finna en optimallösning, men här finns knappast något bättre alternativ.) Innan vi börjar kan vi först konstatera att bivillkor (2) är redundant, eftersom det följer av teckenkraven på x. Det underlättar analysen att ta bort det. Vi kommer i tur och ordning att gissa vilka bivillkor som är aktiva.

1. Inga bivillkor är aktiva. Då fås som KKT:

∇f(x) = 0, dvs (8x_{1} − 6x_{2} + 1, −6x_{1} + 4x_{2}) = (0, 0), d.v.s.

x = (1, 3/2)^{T}. Detta är en otillåten punkt.

2. Alla bivillkor är aktiva. Uppenbarligen omöjligt, ty x = (0, 0)^{T} är otillåtet.

3. Bivillkor (1) är aktivt. Då fås som KKT:

[ \begin{matrix}8x_{1} − tx_{2} + 1 \\ −6x_{1} + 7x_{2} \end{matrix} ] − λ_{1} [ \begin{matrix}−2 \\ 2 \end{matrix} ] = [ \begin{matrix}0 \\ 0 \end{matrix} ]

En parametrisk lösning är:

(x_{1}, x_{2}) = (1, 3/2) − λ_{1}(1, 1), λ_{1} ≥ 0. Med kraven (2) och (3) fås att λ_{1} = [1, 3/2]. Insättning i f ger också att f(x) = 1 för alla x på denna form. Så x = 1, 3/2) − λ_{1}(1, 1), λ − [1, 3/2] är samtliga KKT-punkter, med samma målfunktionsvärde. Notera att med λ_{1} = 1 fås x = x̄!

4. Bivillkor (2) är aktivt. Med x_{1} = 0 fås ur KKT att också x_{2} = 0, vilket ger en otillåten punkt.

5. Bivillkor (3) är aktivt. Ger också x = (0, 0)^{T}.

6. Bivillkor (1) och (2) är aktivt. Ger x = (0, 1/2)^{T}, d.v.s. x̄.

7. Bivillkor (1) och (3) är aktivt. Ger x = (1/2, 0) som är otillåtet.

detta är samtliga kombinationer. Ur detta fås att mängden av KKTpunkter är

x = (1, 3/2)^{T} − λ_{1}(1, 1)^{T} , 1 ≤ λ_{1} ≤ 3/2.

Samtliga dessa har målfunktionsvärde 1, och är alltså globalt optimala. Ibland dessa återfinns x̄.

3 a) Låt (Â, b̂) vara de rader i (A, b) som motsvarar de bivillkor som är aktiva i x_{∗}, d.v.s. där a_{i}^{T} x_{∗} = b_{i}. Att det inte existerar en tillåten riktning i x_{∗} som samtidigt är en descentriktning kan beskrivas som att det \underline{inte} finns ett p ∈ ℝ^{n} med ∇f(x_{∗})^{T} p < 0 och Âp ≥ 0.

Optimalitetsvillkor. Om x_{∗} är ett lokalt min existerar λ̂_{∗} ≥ 0 så att ∇f(x_{∗}) = Â^{T} λ̂_{∗}.

b) tolka: x = p; B = Â; c = ∇f(x_{∗}). Då är utsagan att det \underline{inte} existerar en tillåten descentriktning i x_{∗} ekvivalent med att systemet I \underline{inte} har en lösning. Farkas Lemma leder då till att systemet II har en lösning. Tolkas II i detta problem fås, med y = λ̂_{∗}, att det existerar λ̂_{∗} ≥ 0 så att Â^{T} λ̂_{∗} = ∇f(x_{∗}), d.v.s. första ordningens nödvändiga krav!

4 a) Dualen till (P) är

\begin{matrix}max w = 240y_{1} + 60y_{2} \\ då & \{ \begin{matrix}2y_{1} + 2y_{2} ≤ 100 \\ 6y_{1} + y_{2} ≤ 100 \\ 10y_{1} ≤ 100 \\ y_{1}, y_{2} ≥ 0 \end{matrix} \end{matrix} ; (D)

Geometrisk lösning av (D) ger: y_{∗} = (10, 40). (Men detta behövs inte. Vi härleder den lösningen nedan.)

För att verifiera att x_{∗} = (12, 36, 0)^{T} utnyttjas de tre optimalitesvillkoren i LP.

Primal tillåtenhet: \begin{matrix}2x_{1} + 6x_{2} + 10x_{3} = 240 OK \\ 2x_{1} + x_{2} = 60 \\ x_{1} > 0, x_{2} > 0, x_{3} = 0 \end{matrix}

Komplementaritet: \begin{matrix}y_{1} · (2x_{1} + 6x_{2} + 10x_{3} − 240) = 0 & o \\ y_{2} · (2x_{1} + x_{2} − 60) = 0 & ii \\ x_{1} · (2y_{1} + 2y_{2} − 100) = 0 & iii \\ x_{2} · (6y_{1} + y_{2} − 100) = 0 & iv \\ x_{3} · (10y_{1} − 100) = 0 & v \end{matrix}

ger ur iii och iv att \begin{matrix}2y_{1} + 2y_{2} = 100 \\ 6y_{1} + y_{2} = 100 \end{matrix} , d.v.s. y_{1} = 10, y_{2} = 40.

Du tillåtenhet: återstår att kontrollera: \begin{matrix}10y_{1} ≤ 100 & ok \\ y_{1}, y_{2} ≥ 0 & OK \end{matrix}

Alla optimalitetsvillkoren uppfylls tillsammans med den (unika) duala optimalllösningen y_{∗} = (10, 40)^{T}. b) Med utgångspunkt från den optimala duala optimallösningen utnyttjas op-

timalitetsvillkoren för att finna samtliga x_{∗} som satisfierar dem.

y_{∗} = (10, 40)^{T} uppfyller de tre linjära bivillkoren i (D) med likhet, så iii - v ger inget. Ur i - ii fås (y_{∗} > 0!):

\begin{matrix}2x_{1} + 6x_{2} + 10x_{3} = 240 \\ 2x_{1} + x_{2} = 60 \end{matrix} \} ⇔ \begin{matrix}x_{1} = 12 + x_{3} \\ x_{2} = 36 − 2x_{3} \end{matrix}

Primal tillåtenhet som återstår att lägga till är x ≥ 0, vilket ger att x_{3} = 18 måste gälla.

Samtliga optimallösningar ges alltså av:

x_{∗} = [ \begin{matrix}12 \\ 36 \\ 0 \end{matrix} ] + t · [ \begin{matrix}1 \\ −2 \\ 1 \end{matrix} ] , 0 ≤ t ≤ 18.

5 a) Att steglängden blir noll beror på att sökriktningen inte är en descentriktning. Anledningen till detta är att Hessianen ∇^{2}f(x_{k}) i den aktuella punkten x_{k} är indefinit eller negativ (semi)definit.

b) Att sökriktning saknas beror på att det linjära systemet ∇^{2}f(x_{k})p = −∇f(x_{k}) inte kan vara inverterbar (notera dock att systemet \underline{kan} vara lösbart för vissa

högerled även om ∇^{2}f(x_{k}) inte är inverterbar, som t.ex. [ \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ] p = [ \begin{matrix}2 \\ 2 \end{matrix} ]

som har lösningen p = [ \begin{matrix}1 \\ 1 \end{matrix} ]), vilket gäller speciellet om determinanten för

∇^{2}f(x_{k}) är noll (ett egenvärde till ∇^{2}f(x_{k}) är noll).

c) I Levenberg-Marquardts modifiering av Newtons metod undersöks egenvärdena till ∇^{2}f(x_{k}) under tiden som systemet ∇^{2}(x_{k})p = − = ∇f(x_{k}) löses. Om ett negativt egenvärde påträffas (genom att t.ex. ett pivotelement i Gauss-eliminationen är negativt) adderas en positiv term till diagonalen av ∇^{2}f(x_{k})p = −∇f(x_{k}) ersätts av ett system på formen [∇^{2}f(x_{k}) + γI]p = −∇f(x_{k}), där γ > 0 har valts så att ∇^{2}f(x_{k})+γI är positivt definit. Eftersom detta gäller, existerar p (så problemet i b) försvinner), och ∇f(x_{k})^{T} p = −p^{T} [∇^{2}f(x_{k}) + γI]p < 0 av samma skäl, så p är en descentriktning (problemet i a) försvinner också). Alternativ: gör en iteration av brantaste lutningsmetoden.

6. Låt X = {x ∈ ℝ^{2}|0 ≤ x_{j} = 1, j = 1, 2}.

L(x, λ) := f(x) − λ · (3x_{1} + 2x_{2} − 4), λ ≥ 0. Lagrangeduala problemet är då att

(LD)  max_{λ≥0} L(λ),

där L(λ) = min_{x∈X} L(x, λ). Utvecklas L(x, λ) fås:

\begin{aligned}L(λ) & = 4λ + min_{0≤x,≤1}\{(1 − 3λ)x_{1}\} + min_{0≤x_{2}≤1}\{(1 − 2λ)x_{2}\} \\ & = \{ \begin{matrix}4λ, & 0 ≤ λ ≤ 1/3 \\ 1 + λ, & 1/3 ≤ λ ≤ 1/2 \\ 2 − λ, & 1/2 ≤ λ \end{matrix} \end{aligned}

λ_{∗} = 1/2; L(λ_{∗}) = 3/2. Problemet är konvext och det existerar en inre punkt i det tillåtna området. Stark dualitet gäller alltså, och en primal optimallösning kan lösas ut ur optimalitetsvillkoren: Motsvarigheten till “∇_{t}L(x_{∗}, λ_{∗}) = 0” i KKT i det konvexa fallet är att

x_{∗} löser min_{x∈X} L(x, λ_{∗}), d.v.s. x_{∗} löser min_{0≤x,≤1}\{−\frac{1}{2}x_{1}\} och min_{0≤x_{2}≤1}\{0, x_{2}\}, med

optimallösning x_{1} = 1 och x_{2} ∋ [0, 1]. Komplementaritet ger (λ_{∗} > 0!) att 3x_{1} + 2x_{2} = 4. Med x_{1} = 1 ger det att x_{2} = 1/2. Primal tillåtenhet gäller eftersom x ∈ X och det linjära bivillkoret (1) är uppfyllt med likhet.

Så x_{∗} = [ \begin{matrix}1 \\ 1/2 \end{matrix} ] är den unika optimallösningen.

(Notera att f(x_{∗}) = 3/2 = L(λ_{∗}).)

7. Variabeldeklaration:

y_{t} = 1 om vi rekryterar i månad t, 0 annars (t = 1, …, 10).
x_{st} = antalet nyrekryterande den förste i månad s som avskedas den siste i månad t (s = 1, …, 10 : t = 1, …, 10).
ö_{t} = överbemaning under månad t (t = 1, …, 10).

Modell: min f(y, ö) = ∑^{10} t = 1s_{t}y_{t} + ∑_{t=1}^{10} c_{t}ö_{t}

då

(1)  ∑_{i=1}^{t} ∑_{k=t}^{10} x_{ik} = r_{t} + ö_{t} (t = 1, …, 10)

x_{st} = 0(t = 1, …, 9, s ≥ t − 2) (2)

∑_{t=s}^{10} x_{st} ≤ M · y_{t}(t = 1, …, 10) (M ≫ 0) (3)

y_{t} ∈ {0, 1} (t = 1, …, 10) x_{st} ≥ 0, heltal (s = 1, …, 10 : t = 1, …, 10) ö_{t} ≥ 0, heltal (t = 1, …, 10)

(1): antalet arbetande under månad t = kravet + överbemanning; (2): förbjudet att avsheda någon före tre månader om start före månad 9_{j} (3): ej anställning (x > 0) om inte rekrytering skett (y > 0)