Lösningar till tintamen i TMA945/MAN280 000823

1 a) tillägg av slackvariabler och en artificiell variabel (bivillkor 1) ger Fas-1-problemet.

minimera w = a

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

Simplextablå:

bas −w x_{1} x_{2} s_{1} s_{2} a b̄
−w 1 −2 −1 1  0 0 −2 inkommande: x_{1}
a  0 2 1 −1 0 1 2 utgående: a
s_{2} 0 −1 1  0  1 0 1
−w 1 0 0  0  0 1 0 red.kostn. ≥ 0 → opt.
x_{1} 0 1 1/2 −1/2 0 1/2 1 w^{∗} = 0 → tillåten lösning
s_{2} 0 0 3/2 −1/2 1 1/2 2 funnen.

z = 3x_{1} + x_{2} = 3(1 − 1/2x_{2} + 4_{2}s_{1}) + x_{2} = 3 − 1/2x_{2} + 3/2s_{1}

bas −z x_{1} x_{2}  s_{1}  s_{2}  b̄
−2 1 0 −1/2 3/2  0  −3 inkommande: x_{2}
x_{1} 0 1 1/2 −1/2 0  1 utgående: s_{2}
s_{2} 0 0 3/2 −1/2 1  2
−z 1 0  0  4/3 1/3 −7/3 Red.kostn. ≥ 0 ⇒ opt.
x_{1} 0 1  0 −1/3 −1/3 1/3 x^{∗} = (1/3, 4/3); z^{∗} = 7/3
x_{2} 0 0  1 −1/3 2/3 4/3

Motivering: Vi kan tolka minimeringen av c^{T} x som valet av det lägsta värdet av z = c^{T} x = c_{B}^{T}x_{B} = c_{B}^{T}B^{−1}b över alla tillåtna baslösningar B. Från den starka dualsatsen vet vi att y^{∗} = (c_{B}^{T}B^{−1})^{T} är \underline{en} dual optimal lösning för ett optimalt val av B. Så om y^{∗} är unik kan vi skriva z^{∗} = min c^{T} x = b^{T} y^{∗}, vilket anger värdet av z^{∗} som funktion av b. Skuggpriset för bivillkor i är y_{i}^{∗}, vilket också fås ur z^{∗}(b) = b^{T} y^{∗} som en partiell derivata, ∂z^{∗}(b)/∂b_{i}, då den existerar. Den reducerade kostnaden för en slackvariabel s_{i}, i ett ≥-villkor är c̄_{s_{i}} = 0 − (c_{B}^{T}B^{−1})(−e_{j}) = y_{i}^{∗}, där e_{j} är den i:te enhetsvektorn, dvs c̄_{s_{i}} är precis skuggpriset för bivillkor i.

2 a) Variabler:

x_{i} = \{ \begin{matrix}1, & om tomt i används \\ 0, & annars. & i = 1, 2, …, 5 \end{matrix}

y_{ij} = \{ \begin{matrix}1, & om vårdcentral på tomt i servar område j \\ 0, & annars i = 1, 2, …, 5; j = 1, 2, …, 18 \end{matrix}

Modell:

Minimera ∑_{i=1}^{5} ∑_{j=1}^{18} a_{j}d_{ij}yÿ

då ∑_{i=1}^{t} c_{i}x_{i} ≤ b  (budget)

∑_{j=1}^{18} a_{j}y_{ij} ≤ k_{i}x_{i}, i = 1, 2, …, t  (kapacitet)

∑_{i=1}^{5} x_{i} = 2  (byggplan)

∑_{i=1}^{5} y_{ij} = 1, j = 1, 2, …, 18  tillordning)
x_{i} ∈ {0, 1}, i = 1, 2, …, 5
y_{ij} ∈ {0, 1}, i = 1, 2, …, 5; j = 1, 2, …, 18

Problem av typen kapaciterad lokalisering. “y_{ij} ∈ {0, 1}” kan bytas mot “y_{ij} ≥ 0” pga heltalsegenskap (unimodularitet) i y_{ij} och tillordningsvillkoren.

b) Byt målfunktionen mot

minimera max_{i,j}{d_{ij}y_{ij}}.

3 a) x^{t+1} karakteriseras av att vara det unika minimat till p(x) = \frac{1}{2}∥y − [x^{t} − γ_{t}∇f(x^{t})]∥^{2} över y ∈ X. Startionaritet: ∇p(x^{t+1})^{T} (y − x^{t+1}) ≥ 0, ∀y ∈ X, dvs

(x^{t+2} − x^{t} + γ_{t}∇f(x^{t}))^{T} (y − x^{t+1}) ≥, ∀y ∈ X.  (∗)

x^{t+1} är unik, typ p(x) är strikt konvex och har begränsade nivåmängder. Antag att x^{t+1} = x^{t}. Då gäller från (∗) att ∇f(x^{t})^{T} (y − x^{t}) ≥ 0, ∀y ∈ X, dvs x^{t} är stationär. Detta är en motsägelse! Alltså gäller att x^{t+1} ≠ x^{t}.

b) Med y = x^{t} i (∗) fås att ∇f(x^{t})^{T} (x^{t+1} − x^{t}) ≤ −(1/γ_{t})∥x^{t+1} − x^{t}∥^{2}, dvs descent fås i riktning x^{t+1} − x^{t}. När det gäller att descent fås med steg 1, dvs att f(x^{t+1}) < f(x^{t})^{2}. Från Lipschitzkontinuiteten hos ∇f fås från tesen att

\begin{aligned}f(x^{t+1} − f(x^{t}) & ≤ ∇f(x^{t})^{T} (x^{t+1} − x^{t}) + \frac{M}{2} ∥x^{t+1} − x^{t}∥^{2} \\ & ≤ (\frac{M}{2} − \frac{1}{γ_{t}} )∥x^{t+1} − x^{t}∥^{2} \end{aligned}

dvs f(x^{t+1}) < f(x^{t}) om γ_{t} < 2/M.

c)

∥x^{t+1} − x^{∗}∥^{2} = ∥Proj_{x}[x^{t} − γ_{t}∇f(x^{t})] − Proj_{x}(x^{∗})∥^{2}
≤ ∥x^{t} − γ_{t}∇f(x^{t}) − x^{∗}∥^{2} (enligt ledning)
= ∥x^{t} − x^{∗}∥^{2} − 2γ_{t}∇f(x^{t})^{T} (x^{t} − x^{∗}) + γ_{t}^{2}∥∇f(x^{t})∥62
≤ /f konvex ⇒ f(x^{∗}) ≥ f(x^{t}) + ∇f(x^{t})^{T} (x^{∗} − x^{t})/
≤ ∥x^{t} − x^{∗}∥^{2} − 2γ_{t}(f(x^{∗}) − f(x^{t})) + γ_{t}^{2}∥∇f(x^{t})∥^{2}
< ∥x^{t} − x^{∗}∥^{2}

om 0 < γ_{t} < \frac{2(f(x^{t})−f(x^{∗}))}{∥∇f(x^{t})∥^{2}}.

4. Se kursboken!

5. Problem: min f(x) då g(x) ≥ 0, x ∈ X, med f(x) = −2x_{1} + x_{1}^{2} − x_{2} + 2x_{2}^{2}, g(x) = −3x_{1}^{2} − 2x_{2}^{2} + 3 X = [0, 2] × [0, 2].

givet ett iterat (x^{t}, λ^{t}) är subproblemet i SQP:

\begin{matrix}min ∇_{x}L(x^{t}, λ^{t})^{T} p + \frac{1}{2}p^{T} ∇_{x}^{2}L(x^{t}, λ^{t}) (L(x, λ) = f(x) − λ^{T} g(x)) \\ då & \begin{matrix}g(x^{t}) + ∇g(x^{t})p ≥ 0 \\ ′x^{t} + p ∈ X \end{matrix} \end{matrix}

Vi har x^{0} = (0, 0)^{T} och väljer λ^{0} = 0. Då följer att L(x, λ^{0}) = f(x) och vi får som subproblem (med p = x − x^{0}) (ty ∇g(x^{0}) = 0)

min f(x) Sätt ∇f(x) = 0 =: x = (1, 1/4)^{T} ∈ X.
då x ∈ X Så p^{0} = x − x^{0} = (1, 1/4)^{T} .

Med max-steg 1 i riktning p kan inte X överskridas. Vi inkluderar bara g i straffunktionen:

g(x) := min_{ℓ∈[0,1]} f(x^{0} + ℓp^{0}) + 10 ∗ ψ(x^{0} + ℓp^{0}), ψ(x) = min \frac{1}{2}\{g(x), 0\}^{2}

Vi använder Armijos steglängdsregel med acceptansparameter 0.1 och får:

q(x^{0} + ℓp^{0}) − q(x^{0}) ≤ 0.1ℓ∇w(x^{0})^{T} p^{0}

uppfyllt med ℓ = 1 ∵ x^{1} = x^{0} + p^{0} = (1, 1/4)^{T}. (≈ −1.05 ≤ 0.1 · (−9/4)).

6 a) Sant. Bevistekniken (motsägelsetype) visar väsentligen att Q måste vara positivt semidefinit på det tillåtna underrummet för att ett lokalt minimum ska kunna finnas. Så i praktiken har vi därför ett konvext problem, under denna förutsättning.

b) Falskt. Motexempel: f(x) = x^{3}; x = 0; d = −1.

c) Falskt.

7 a) Eulers sats: En Eulertur (en tur som användes varje båge exakt en gång existerar om och endast om varje nod i grafen har jämn valens (antalet bågar som utgår från varje nod är jämnt).

b) Vi konstruerar ett ekvivalent problem genom att resonera som följer. Antag att vi har en brevbärartur i grafen, och att x_{e} är det antal gånger extra (≥ 1) som båge e används. Konstruera en graf där e reproduceras 1 + x_{e} gånger. Denna graf har en Eulertur. Vi kan alltså formulera problemet som det att finna den billigaste uppsättningen x_{e} sådan att den konstruerade grafen uppfyller kraven i uppg. H b).

minimera ∑_{e∈E} c_{e}x_{e}

då \begin{matrix}∑_{e∈A(i)} x_{e} = |A(i)| mod 2, i ∈ N \\ x_{e} ≥ 0, heltal, e ∈ E \end{matrix}

där A(i) är mängden av bågar som ansluter till nod i. c) Noderna A,B,C,D,E och F har udda valens, och AC, BE och DF utnyttjas

två gånger. Ett billigare sätt att addera “x_{e}” är att ersätta AC, DF med AX, XZ, ZF och DC (minskad kostnad: 50). Ny rutt: AY2FDCDEBE2FYXZXACBXA.