Tentamen TMA946/MAN280 tillämpad optimeringslära 010821

1. Uppgift: min z = 3x_{1} + x_{2}

Då [ \begin{matrix}2x_{1} + x_{2} ≥ 6 \\ −x_{1} + x_{2} ≥ −2 \\ x_{1}, x_{2} ≥ 0 \end{matrix} ]

Skriv på standardform m.h.aṡlackvariabler min z = 3x_{1} + x_{2}

Då [ \begin{matrix}2x_{1} + x_{2} − s_{1} = 6 \\ x_{1} − x_{2} + s_{2} = 2 \\ x_{1}, x_{2}, s, s_{2} ≥ 0 \end{matrix} ]

Vi ser ingen uppenbar bas ⇒ skapa FAS I problem min w = a

Då [ \begin{matrix}2x_{1} + x_{2} − s_{1} + a = 6 \\ x_{1} − x_{2} + s_{2} = 2 \end{matrix} ]

Välj a, s_{2} som bas ⇒ B = [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ]

Titta på reducerad kostnad:

c_{N}^{T} − C_{B}^{T}B^{−1}N = [0 0 0] − [1 0] [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}2 & 1 & −1 \\ 1 & −1 & 0 \end{matrix} ]

= [−2 − 1 1]

⇒ välj x_{1} som inkommande.

Vi gör min-ratio test för att hitta utgående

Y = B^{−1}A_{ink} = [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}2 \\ 1 \end{matrix} ] = [ \begin{matrix}2 \\ 1 \end{matrix} ]
b̄ = B^{−1}b = [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}6 \\ 2 \end{matrix} ] = [ \begin{matrix}6 \\ 2 \end{matrix} ]

Utgående = [ \begin{matrix}argmin \\ i, Y_{i} > 0 \end{matrix} ] \frac{b̄}{Y_{i}} ⇒ bas variabel 2 utgår. Ny bas blir a, x_{1}

\begin{aligned}⇒ B & = [ \begin{matrix}1 & 2 \\ 0 & 1 \end{matrix} ] B^{−1} = [ \begin{matrix}1 & −2 \\ 0 & 1 \end{matrix} ] B^{−1}b = [ \begin{matrix}2 \\ 2 \end{matrix} ] c_{N}^{T} = [0 0 0] \\ c_{B}^{T} & = [1 0]N = [ \begin{matrix}1 & −1 & 0 \\ −1 & 0 & 1 \end{matrix} ] \end{aligned}

Hitta reducerad kostnad C_{N}^{T} − C_{B}^{T}B^{−1}N =

[0 0 0]−[1 0] [ \begin{matrix}1 & −2 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}1 & −1 & 0 \\ −1 & 0 & 1 \end{matrix} ] = [−1 2] [ \begin{matrix}1 & −1 & 0 \\ −1 & 0 & 0 \end{matrix} ] = [−3 1 2]

icke basvar 1, d.v.s. x_{2} blir inkommande. Gör min ratio.

Y = B^{−1}Aink = [ \begin{matrix}1 & −2 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}1 \\ −1 \end{matrix} ] = [ \begin{matrix}3 \\ −1 \end{matrix} ]

utgående = [ \begin{matrix}argmin \\ i, Y_{i} > 0 \end{matrix} ] \frac{b̄_{i}}{Y_{i}} ⇒ basvar 1 utgår. Ny bas blir x_{2}, x_{1}. Vi har ej länge någon artificiell variabel i basen ⇒ Fas I är klar. Starta fas II. Vi har bas x_{1}, x_{2}

\begin{aligned}⇒ B & = [ \begin{matrix}2 & 1 \\ 1 & = 1 \end{matrix} ] ⇒ B^{−1} = \frac{1}{3} [ \begin{matrix}1 & 1 \\ 1 & −2 \end{matrix} ] B^{1}b = \frac{1}{3} [ \begin{matrix}8 \\ 2 \end{matrix} ] \\ c_{B}^{T} & = [3 1]c_{N}^{T} = [0 0]N = [ \begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix} ] \end{aligned}

Hitta reducerad kostnad. c̄ = c_{N}^{T}−c_{B}^{T}−c_{B}^{T}B^{−1}N = [0 0]−[3 1]\frac{1}{3} [ \begin{matrix}1 & 1 \\ 1 & −2 \end{matrix} ] [ \begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix} ]

= −[4/3 1/3] [ \begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix} ] = [4/3 − 1/3] icke basvar 2 = s_{2} är inkommen.

Vi gör min ratio test. Y = B^{−1}Aink = \frac{1}{3} [ \begin{matrix}1 & 1 \\ 1 & −2 \end{matrix} ] [ \begin{matrix}0 \\ 1 \end{matrix} ] = [ \begin{matrix}1/3 \\ −2/3 \end{matrix} ]

Utgående = [ \begin{matrix}argmin \\ i, y_{i} > 0 \end{matrix} ] \frac{b̄_{i}}{y_{i}} ⇒ basvar 1 är utgående. Ny bas x_{2}, s_{2}.

Hitta reducerad kostnad:

B = [ \begin{matrix}1 & 0 \\ −1 & 1 \end{matrix} ] B^{−1} = [ \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ] c_{N}^{T} = [3 0]c_{B}^{T} = [1 0]N = [ \begin{matrix}2 & −1 \\ 1 & 0 \end{matrix} ]
c̄ = c_{N}^{T} − C_{B}^{T}B_{N}^{−1} = [3 0] − [1 0] [ \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ] [ \begin{matrix}2 & −1 \\ 1 & 0 \end{matrix} ]
⇒ i = [3 0] − [1 0] [ \begin{matrix}2 & −1 \\ 1 & 0 \end{matrix} ] = 1 1 ≥ 0
⇒ vi har en optimal bas, x_{1}, s_{2}

med värden B^{−1}b = [ \begin{matrix}1 & 0 & 6 \\ 1 & 1 & 2 \end{matrix} ] = [ \begin{matrix}6 \\ 8 \end{matrix} ] ⇒ Z^{∗} = 3x_{1} + x_{2} = 6

Vi har x_{1} = 0, x_{2} = 6, s_{1} = 0, s_{2} = 8.

Kolla! [ \begin{matrix}2x_{1} + x_{2} = 6 ≥ 6 OK \\ −x_{1} + x_{2} = 6 ≥ −2 OK \end{matrix} ]

1b För att avgöra för vilka c mängden påverkar bildar vi problemet. min z = x_{1} + x_{2}

Då [ \begin{matrix}2x_{1} + x_{2} ≥ 6 \\ −x_{1} + x_{2} ≥ −2 \\ x_{1}, x_{2} ≥ 0 \end{matrix} ]

Antag att det optimala värdet på detta problem är z^{∗}. Då påverkas mängden för c > z^{∗}.

2a) Ett exakt straff för “g_{i}(x) ≥ 0” är min{0, g_{i}(x)}. En straffunktionsmetod

baserad på denna är följande:

0. Välj μ_{0} ≥ 0. Sätt t = 0.

1. Lös min_{x∈ℝ^{n}} f(x) − μ^{t} · min{0, g_{i}(x)} → x^{t}.

2. Sätt μ^{t+1} > μ^{t} (så att lim_{t→∞} μ^{t} = +∞), t := t + 1, gå till 1.

b) Låt x := {x = ℝ^{n}|a_{i}^{T} x ≥ b_{i}, i = 1, …, m}. Frank-Wolfe algoritmens itera-

tion är följande:

0. Välj x^{0} = X. Sätt t = 0.

1. Lös min_{y∈X} ∇f(x^{t})^{T} y → y^{t}.

2. Om ∇f(x^{t})^{T} (b^{t} − x^{t}) = 0 ⇒ Stopp! x^{t} är en KKT-punkt.

3. Lös min_{ℓ∈[0,1]} f(x^{t} + ℓ(y^{t} − t^{t})) → ℓ_{t}.

4. Sätt x^{t+1} = x^{t} + ℓ_{t}(y^{t} − x^{t}), t := t + 1, gå till 1.

För att en iteration skall kunna genomföras krävs att stegen 1 och 3 (de två optimeringsproblemen) är genomförbara. Steg 1 är genomförbart om LP-problemet har en lösning, d.v.s. om ∇f(x^{t})^{T} y är nedåt begränsad på X. Steg 2 är genomförbart om f har ett minimum på linjesegmentet [x^{t}, y^{t}]. För detta räcker det med att f är kontinuerligt differentiarbar eftersom den då är kontinuerlig och [x^{t}, y^{t}] är en kompakt mängd (Weierstrass). For steg 1 fordras i allmänhet att x är begränsad.

c) Eftersom f bara är differentierbar en gång har vi inte tillgång till rena Newtonmetoder. Problemet är konvext och inte särdeles stort (n = 500 är att betrakta som ganska litet för ett konvext obegräansat problem). Om ∇f(x) är någorlunda lätt att beräkna rekommenderas Qvari-Neewton/konjugerade gradientmetoder. (se kurslitteraturen för beskrivningar.)

3 a) Modell: Variabler:

x_{ij} = andel av rxxxx j:s efterfrågan som tillgodoses av central i ∀i, ∀j.
y_{i} = \{ \begin{matrix}1, om central i byggs, ∀i. \\ 0, annars. \end{matrix} ]

Ny konstant: a_{ij} = \{ \begin{matrix}1 om d_{ij} ≤ D \\ 0 annars \end{matrix} ] ∀i, ∀j (uppnåelighetsmatris)

Minimera ∑^{10} i = jc_{i}b_{i}

Då

x_{i}j ≤ a_{ij}y_{i}, i = 1, …, 10; j = 1, …, 30 (uppnåelighet)
∑_{j=1}^{30} e_{j}x_{ij} ≤ k_{i}y_{i}, i = 1, …, 10 (tillgång)

∑_{i=1}^{10} k_{ij} = 1, j = 1, …, 30 (efterfrågan)
x_{ij} ≥ 0, i = 1, …, 10, j = 1, …, 30
y_{i} ∈ {0, 1}, i = 1, …, 10.

b) tillägg: x_{ij} ∈ {0, 1}, i = 1, …, 10; j = 1, …, 30.

4 a) x^{∗} är ett lokalt minimum ⇔ f(x^{∗}) ≤ f(x), ∀x ∈ B(x^{∗}), där B(x^{∗}) = {x ∈ ℝ^{n}|∥x − x^{∗}∥ ≤ ϵ} för ett tillräckligt litet ϵ > 0.

x^{∗} är ett lokalt minimum ⇒ ∇f(x^{∗}) = 0^{n}. b) x^{∗} är ett lokalt minimum ⇔ f(x^{∗}) ≤ f(x), ∀x ∈ B(x^{∗})nS.

x^{∗} är ett lokalt minimum ⇒ ∃λ_{∗} ≥ 0^{m} så att

• ∇f(x^{∗}) = A^{T} λ_{∗}.

• λ_{∗}^{T} (Ax^{∗} − b) = 0

• Ax^{∗} ≥ b.

5 a) Sätt ϕ(x) = − ∑_{i=1}^{m} log(−g_{i})(x)), β(x, μ) = f(x) + μϕ(x). Låt μ_{1}, μ_{e}, …

vara en positiv och monotont avtagande följd om tal med gränsvärde 0. Sekvensen x_{1}, x_{2}, …, ges av

x_{k} ∈ arg min_{x∈ℝ^{n}}β(x, μ_{k}).

b) (Iterationsindex k struket här.) Från optimalitetsvillkoret ∇_{x}β(x, μ) = o^{n} fås att

∇f(x) = ∑_{i=1}^{m} \frac{μ}{g_{i}(x)}∇g_{i}(x) = 0^{n}. Eftersom g_{i}(x) > 0, ∀i.

kan vi skriva detta som: (λ_{i} = μ/g_{i}(x), i = 1, …, m)

\begin{aligned}∇f(x) − ∑_{i=1}^{m} λ_{i}∇g_{i}(x) & = o^{n}, \\ λ_{i} · g_{i}(x) & = μ, i = 1, …, m \\ g_{i}(x) & ≥ 0, i = 1, …, m. \end{aligned}

Skillnaden mellan detta och KKT för problemet (1)-(2) är att högerledet 0 i komplementariteten ersatts av μ > 0.

Multiplikator estimat: λ_{i} = μ/g_{i}(x), i = 1, …, m..

c) Låt I(x^{∗}) = {i|g_{i}(x^{∗}) = 0}. x^{∗} är reguljär betyder att ∇g_{i}(x^{∗}), i ∈ I(x^{∗}) är linjärt oberoende. Pga att f och g_{i} är kontinuerligt differentierbara så följer att {x_{k}} → x^{∗} ⇒ {∇f(x_{k})} → ∇f(x^{∗}); {∇g_{i}(x_{k})} → ∇g_{i}(x^{∗}), ∀i. Multiplikator estimatet ger att för i ∉ I(x^{∗}) : {λ_{ik}} = {μ_{k}/g_{i}(x_{k})} → 0/g_{i}(x^{∗}) = 0. För i ∈ I(x^{∗}), notera att systemet ∇f(x^{∗}) − ∑_{i∈I(x^{∗})} λ_{i}∇g_{i}(x^{∗}) = 0^{n} har en unik lösning λ_{i}^{∗}, i ∈ I(x^{∗}), vilken måste vara gränsvärdet för {λ_{ik}}, i ∈ I(x^{∗}). Ty antag att {λ_{ik}}, i ∈ (x^{∗}), konvergerar mot λ̄, där λ̄_{i} ≠ λ_{i}^{∗} för något i ∈ I(x^{∗}). Då följer att

0 = ∇f(x_{k}) = ∑_{i∉j(x^{∗})} λ_{ik}∇g_{i}(x_{k}) − ∑_{i∈I(x^{∗})} λ_{i}^{∗}∇g_{i}(x_{k}) − ∑_{i∈I(x_{∗})}[λ_{ik} − λ_{i}^{∗}]∇g_{i}(x_{m}) →

→ ∇f(x^{∗}) − 0 − ∑_{i∈j(x^{∗})} λ_{i}^{∗}∇g_{i}(x^{∗}) − ∑_{i∈j(x^{∗})}[λ̄_{i} − λ_{i}^{∗}]∇g_{i}(x^{∗}) =

= − ∑_{i∈I(x^{∗})}[λ̄_{i} − λ_{i}^{∗}]∇g_{i}(x^{∗}).

Denna summa är 0 endast om λ̄_{i} = λ_{i}^{∗} ∀i ∈ I(x^{∗}), ty ∇g_{i}(x^{∗}) är linjärt oberoende. Alltså är {λ_{k}} konvergent, och vi kan sammanfatta läget så här: eftersom g_{i}(x_{k}) > 0 för alla i och k kommer g_{i}(x^{∗}) ≥ 0 att gälla. Dessutom för (x^{∗}, λ^{∗}) gäller att

\begin{aligned}∇f(x^{∗}) − ∑_{i=1}^{m} λ_{i}^{∗}∇g_{i}(x^{∗}) & = 0^{n} \\ λ_{i}^{∗}g_{i}(x^{∗}) & = 0, i = 1, …, m \\ λ_{i}^{∗} & ≥ 0, i = 1, …, m \end{aligned}

∵ I limes fås vektorer (x^{∗}, λ^{∗}) som tillsammans uppfyller KKT-villkoren för ursprungs problemet!

6 a) KKT: L(x, λ, μ) = \frac{1}{2}x^{T} Qx − q^{T} x + λ^{T} (Ax − b) − μ^{T} x ger

• [ \begin{matrix}Qx + λ^{T} λ − Iμ = q \\ λ, μ ≥ 0 \end{matrix} ] (dual till.)

• [ \begin{matrix}λ^{T} (Ax − b) = 0 \\ μ^{T} x = 0 \end{matrix} ] (kompl.)

• [ \begin{matrix}Ax ≤ b \\ x ≥ 0 \end{matrix} ] (primal till.)

KKT beskrives mängden av globalt optimala lösningar om Q är positivt semidefinit.

b) Inför en slackvariabel i Ax ≤ b. Då fås ur KKT:

\{ \begin{matrix}Qx + A^{T} λ − I_{n}  = q \\ Ax  + Is = b \\ x, A, μ, s ≥ 0 \end{matrix} ] samt \{ \begin{matrix}λ^{T} s = 0 \\ μ^{T} x = 0 \end{matrix} ]

Vi indentifierar v = [ \begin{matrix}x \\ s \end{matrix} ]; w = [ \begin{matrix}μ \\ λ \end{matrix} ]; T = [ \begin{matrix}Q & 0 \\ A & I \end{matrix} ]; U = [ \begin{matrix}A^{T} & −I \\ 0 & 0 \end{matrix} ]; p =

[ \begin{matrix}q \\ b \end{matrix} ].

Fas-1-metodP: Inför artificiella variabler z^{1} ∈ ℝ^{n} och z^{2} i ℝ^{m} och betrakta problemet (multipliera först rader så att q, b ≥ 0!)

minimera ∑_{j=1}^{n} z_{j}^{1} + ∑_{i=1}^{m} z_{i}^{2}

då \{ \begin{matrix}Qx + A^{T} λ − I_{m}u + z^{1} = q \\ Ax  + Is + z^{2} = b \\ , λ, m, s, z^{1}, z^{2} ≥ 0 \\ λ^{T} s = 0, μ^{T} x = 0 \end{matrix} ]

Enda skillnaden mot ett Fas-1-problem i LP är kraven att λ^{T} s = 0 och μ^{T} x = 0. Det betyder i själva verket att λ_{i} · s_{i} = 0 ∀i och μ_{j} · x_{j} = 0 ∀j. Att säkerställa att detta är uppfyllt är inte svårt: vi inför ett tillägg till inkommande kriteriet:

• Om λ_{i}(s_{i}) redan finns i basen, får inte s_{i}(λ_{i}) vara inkommande, såvida det inte inträffar att s_{i}(λ_{i}) blir den utgående variabeln.

• Motsvarande för paret (μ_{j}, x_{j}).

7 a) f(x) = 2x_{1}^{3} + 2x_{2}^{2} + 12x_{1}x_{2} − 24x_{1} − 20x_{2} ⇒

∇f(x) = (6x_{1}^{2} + 12x_{2} − 24; 6x_{2}^{2} + 12x_{1} − 20)^{T}

∇^{2}f(x) = [ \begin{matrix}12x_{1} & 12 \\ 12 & 12x_{2} \end{matrix} ] = 12 [ \begin{matrix}x_{1} & 1 \\ 1 & x_{2} \end{matrix} ]

Egenvärden hos [ \begin{matrix}x_{1} & 1 \\ 1 & x_{2} \end{matrix} ] : det [ \begin{matrix}x_{1} − λ & 1 \\ 1 & x_{2} − λ \end{matrix} ] = 0 ⇒ … ⇒

Egenvärden: [ \begin{matrix}λ_{1} = (x_{1} + x_{2})/2 + \sqrt{(\frac{1}{2}x_{1} − \frac{1}{2}x_{2})^{2} + 1} \\ λ_{2} = (x_{1} + x_{2})/2 − \sqrt{(\frac{1}{2}x_{1} − \frac{1}{2}x_{2})^{2} + 1} \end{matrix} ] λ_{1} ≥ λ_{1}!

λ_{2} ≥ 0 om och endast om x_{1}, x_{2} ≥ 0 och x_{1}x_{2} ≥ 1. ∵ f är konvex då x_{1}, x_{2} ≥ 0, x_{1}x_{2} ≥ 1

λ_{1} ≤ 0 om och endast om x_{1}, x_{2} ≤ 0 och x_{1}x_{2} ≥ 1. ∵ f är konkav då x_{1}, x_{2} ≥ 0, x_{1}x_{2} ≥ 1

∵ f är följaktligen varken konvex eller konkav då x_{1}x_{2} < 1.

b) x̄ = (1, 1)^{T}. Newtons metod utnyttjar sökriktningen p från ∇^{2}f(x̄)p =

−∇f(x̄). Ix̄ = (1, 1)^{T} är ∇f(x̄) = (−6, −2); ∇^{2}f(x̄) = [ \begin{matrix}12 & 12 \\ 12 & 12 \end{matrix} ]. Det

existerar inte något p som uppfyller ∇^{2}f(x̄)p = −∇f(x̄)! Modifiering à lá Levenberg-Marquardt: addera en lämpligt skalad enhetsmatris till ∇^{2}f(x̄). Lös t.ex.

\begin{matrix}[∇^{2}f(x̄) + σI]p = −∇f(x̄) för σ = 10. \\ [ \begin{matrix}22 & 12 \\ 12 & 22 \end{matrix} ] p = [ \begin{matrix}6 \\ 2 \end{matrix} ] ⇔ p ≈ (0.32, −0.08) \end{matrix}

Vi använder Armijos steglägdsregel:

f(x̄ + ℓp) ≤ f(x̄) + αℓ∇f(x̄)^{T} p, α ∈ (0, 1).

Med α = 0.1 och ℓ = 1 som startsteglägd fås:

∇f(x̄)^{T} p ≈ −1.74 < 0 f(x̄) = −28; x̄ + ℓp ≈ (1.32, 0.92); f(x̄ + ℓp) ≈ −29.35 f(x̄) + αℓ∇f(x̄)^{T} p ≈ −28.17 ≥ −29.35, d.v.s. steglägd 1 accepteras av Armijos steglägdsregel.

Nästa iterationspunkt är x = (1.32, 0.92).